Formato de presentacion de seminario

IV Congreso Mexicano de Computación Evolutiva

Síntesis de Funciones Lógicas Mediante un EDA Poliárbol
Por: Cyntia Araiza Delgado Dr. Arturo Hernández Aguirre
Centro de Investigación en Matemáticas A.C.

Contenido
• Hardware Evolutivo – Antecedentes – Compuertas Lógicas • Algoritmos de Estimación de Distribución – ¿Qué es un EDA? – Ejemplos de EDAs • Algoritmo de Aprendizaje del Poliárbol– Poliárbol – Aplicación del Poliárbol en Hardware Evolutivo • Experimentos y Resultados • Conclusiones

Hardware Evolutivo
Antecedentes

•Se llama Hardware Evolutivo al uso de las técnicas basadas en la evolución para el diseño de circuitos lógicos combinatorios.

Hardware Evolutivo
Antecedentes

•El objetivo principal en el diseño de circuitos lógicos combinatorios es encontrar laexpresión que proporcione el comportamiento deseado con el menor número de compuertas .

Hardware Evolutivo
Compuertas Utilizadas
• AND • OR • NOT • XOR

Algoritmos de Estimación de Distribución
¿Qué es un EDA?
• Es un algoritmo que, al igual que el algoritmo genético, está basado en poblaciones que evolucionan. Sin embargo, a diferencia de los AG en los EDAs no existen los operadores decruza y mutación. En lugar de ello la nueva población se muestrea de una distribución de probabilidad, la cual es estimada de una muestra que contiene individuos seleccionados previamente de la población de la generación anterior.

Algoritmos de Estimación de Distribución
¿Qué es un EDA?

Algoritmos de Estimación de Distribución
MIMIC BMDA Árbol de Dependencias Poliárbol

Algoritmo deAprendizaje del Poliárbol
Poliárbol
•El poliárbol es un grafo simplemente

conectado, es decir, que un nodo puede tener varios padres, pero sólo debe existir una trayectoria entre dos nodos.

Algoritmo de Aprendizaje del Poliárbol
Poliárbol
•Para la inserción de las aristas nos basamos

en dos medidas
– La Información Mutua Marginal

– La información Mutua Condicional

Algoritmo deAprendizaje del Poliárbol
Poliárbol
•Esto lo podemos visualizar con un ejemplo de la vida cotidiana.

Algoritmo de Aprendizaje del Poliárbol
Poliárbol
•Esto lo podemos visualizar con un ejemplo de la vida cotidiana.

Algoritmo de Aprendizaje del Poliárbol
Poliárbol
• En los poliárboles es posible encontrar tres tipos

de tripletas adyacentes: 1. Secuencial: X i → X k → 2.Divergente: X i ← X k → 3. Convergente: X i → X k ←
• La tripleta X i
→ Xk ← X
j

X X X

j j j

se llama patrón cabezacabeza o conexión cabeza-cabeza y el nodo hacia el cual convergen los arcos se conoce como nodo

cabeza-cabeza.

Algoritmo de Aprendizaje del Poliárbol
Poliárbol

Algoritmo de Aprendizaje del Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
DEFINICIÓN DEL PROBLEMAEl problema consiste en diseñar un circuito que desempeñe una función lógica deseada (especificada por una tabla de verdad) usando el menor número de compuertas.

Algoritmo de Aprendizaje del Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
REPRESENTACIÓN Cada elemento de la matriz es una tripleta, que indica el Tipo de Compuerta, Entrada 1 y Entrada 2.

Algoritmo de Aprendizajedel Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
REPRESENTACIÓN Donde cada elemento de la tripleta tiene una representación binaria.

Entonces la matriz puede ser vista como a continuación se muestra:

Algoritmo de Aprendizaje del Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
REPRESENTACIÓN Partiendo de la matriz anterior formamos una cadena binaria:

Algoritmo deAprendizaje del Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
REPRESENTACIÓN
Celda 1 Celda 4 Celda 7 Celda 2 Celda 5 Celda 8 Celda 3 Celda 6 Celda 9

X1

X2

X1

X2

X3

X4

X3

X4

X5

X5

Individuo

001001110

111001010

101001100

Algoritmo de Aprendizaje del Poliárbol
Aplicación del Poliárbol en Hardware Evolutivo
CASO DE ESTUDIO
Se trabajo...