Post on 18-Oct-2020
SEP SElT I < -. DGlT
CENTRO NACIONAL DE INVESTIGACIÓN Y DESARROLLO TECNOL~GICO
Cenidet
ENRUTADOR DE ARREGLOS EMBRIÓMICBS UTILIZANDO ALGORITMOS GENÉTICOS
T E S I S
PARA OBTENER EL GRADO DE : MAESTRO EN C!ENCIAS EN INGENlERíA ELECTRÓNICA
P R E S E N T A : JORGE MORALES CRUZ
DIRECTORES DE TESIS
DR. CÉSAR ORTEGA SÁNCHEZ DR. JOSÉ TORRES JIMÉMEZ
CUERNAVACA, MORELOS SEPTIEMBRE DEL 2002.
0 2 - 0 7 0 6
Cuernavaca, Morelos
Ing. Jorge Morales Cruz Candidato al grado de Maestro en Ciencias en Ingeniería Electrónica Presente
Despuhs de haber sometido a revisión su trabajo final de tesis titulado: “Enrutador de Arreglos Embriónicos util izando Algoritmos Genéticos”, y habiendo cumplido con todas las indicaciones que el jurado revisor de tesis le hizo, le comunico que se le concede autorización para que proceda a la impresión de la misma, como requisito para la obtención del grado.
Reciba un cordial saludo.
A T E N T A M E N T E
/&Fi /,
Dr. Enrique Quintero-Mármol Márquez Jefe del Depto. de Electrónica
C.C.P. expediente.
INTERIOR INTERNADO PALMIRA SIN. COL. PALMlRA , A.P. 5-164. CP. 62490, CUERNAVACA. MOR. -MEXICO TELS. (777) 312 23 14.318 77 41. FAX (777) 312 24 34 EMAIL eqrn@cenidet.edu.mx
Cuernavaca, Morelos
Ing. Jorge Morales Cruz Candidato al grado de Maestro en Ciencias en Ingeniería Electrónica Presente
Después de haber sometido a revisión su trabajo final de tesis titulado: "Enrutador de Arreglos Embriónicos util izando Algoritmos Genéticos", y habiendo cumplido con todas las indicaciones que el jurado revisor de tesis le hizo, le comunico que se le concede autorización para que proceda a la impresión de la misma, como requisito para la obtención del grado.
Reciba un cordial saludo
A T E N T A M E N T E
v,/ Dr. Enriaue Quintero-Mármol Márauez .~ ~ - Jefe del Depto. de Electrónica
C.C.P. expediente.
INTERIOR INTERNADO PALMIRA S/N, COL, PALMIRA , A.P. 5-1 64, CP. 62490. CUERNAVACA, MOR. - MÉXICO TELS.(777)312 2314.318 7741,FAX(777) 312 2434 EMAlL eqrn@cenidei.edu.mx
Dios, por darme la oportuniáaúdé e2istiK
mis padres, por su enorme apoyo y gran cariño incondicionacez
todo momento.
mis hermanos, por con$ar siempre en mi
mis amigos, por regalarme un poco dé su tiempo.
mis maestros, por contri6uir a Iá realización dé este suego.
2
Al OK César Ortega Sánchez y a l CDK José Torres Jiménez, por su
atinada dirección en Ia reahzación de ésta tesis.
A Cos maestros en ciencias: José de Jesús Noreno, José Ai. Hoyo, Pedro
Si6aja, W a r c o g . Paz, por su valiosa contri6ución a este tra6ajo.
,UCentro Facionaldé Investigación y Desarrollo Tecnologico (íendet),
por 6rináame 1a oportundaddé estudar Ia maestría
A l Conacyt y Ia s e p por e l apoyo económico proporcionado durante e l
desarrollo dé este tra6ajo.
3
INTRODUCCI~N ................................................................................................................... 12
1. ARREGLOS EMBRI~NICOS .......................................................................................... 18
1.1 INTRODUCCION .._.. ..................................... 1s 1.1.1 Antecedentes ......................................................................................... 18
1.1.2 Definición. 1.1.3 Conceptos ............................... 20
1.2 ESTRUCTURA ,_. ............................................................................................................. 20
1.2.1 Memoria ................................................................................................................................. 21 1.2.2 Generador de coordenadas ............... .......... 22
1.2.3 Enrutador de entrada /salida ................................................................................................ 23
1.2.4 Elemento de procesamiento 1.2.5 Registro de configuración ..
1.3 MECANISMOS DE RECONFIGURA
1.3.1 Estrategia de eliminación de Unafila o una coluiiina ........................................................... 27
.............................. 28
.................... 2s
1.3.2 Esirategia de elimiiiacióii de una célula ..................
1.4. I Planteamiento del problema. .................................................................................. .. 26
1.4.3 Obtención del diagrama biiiario de decisión ................................
1.4.5 Implementación del OBDD como árbol de multiplexores .....
1.4.6 Enrutado del árbol de multiplexores en el Arreglo Embriónico ...
1.4 METODOLOGiA PARA IMPLEMENTAR APLICACIONES ...............
1.4.2 Obtención de la tabla de verdad ....................... ............................................................. 29
...... : ............. 29
1.4.4 Simplificación de los BDD .........
.................... 32 1.5 EJEMPLO: CIRCUITO VOTADOR ..........................................
1.6RESUMEN ....... .......................................... ......................................... ..
2. ALGORITMOS GENETICOS YENRUTADORES ....................................................... 35
2.1 INTRODUCCI~N ... .........................................
2.1.1 Antecedenies ................................
2. I . 2 Aplicaciones ..........................................
2.2.1 Representación delproblema ............... .........................................
.......................................... 2.2 FUNCIONAMIENTO DE LOS ALGORITMOS GENETICOS ....................................
4
....................................... ................................ 38 2.2.2 Evaluación ................... 2.2.3 Selección ................................ 2.2.4 Funcióii de aptitud ....
............................
2.3 ENRUTADORES ................. ...............................................................
2.3.1 Defiiiicióii de enruta
2.3.2 Elproblenia de eiirutar .......................
2.3.3 Enrutaniiento usando algoritmos genéticos ......................................................................... 42
2.4 RESUMEN .............
3. ENRUTADOR PROPUESTO ........................................................................................... 44
3 .1 REPRESENTACI~N DE LA CONECTlVlDAD ENTRE CÉLULAS DEL ARREGLO E M B R I ~ N I C O ............ 44 3.2 LLENADO DE LA MATRIZ DE CONECTlVlDAD .... ...... 48
3.2.1 Decodificación de los bits correspondientes al enruiador de EíS ......................................... 48
3.2.2 Cargar variables de eiitrado de la aplicación. ................................................................ 49
3.2.3 Propagncroii de las val-iables ................................................................................................ SO
3.2.4 Llenado de las entradas del eleinento deprocesainiento
3.2.5 Verijicacióri de las entradas de cada célula .......................................................................... 56
3.3 ELEMENTOS DEL ALGORITMO GENÉTICO PROGRAMADO (AGP) ................................................ 57
3.3. I Representación de los cronio.Tonzas del AGP ..,. . ................................................. 58
3.3.2 Función de aptitud (FA) .................................................................... ...... 58 3.3.3 Selección por torneo .................................... ....................................... 60 3.3.4 Cruza ................ ............................................................... 61
. I
.....................................................
3.4 IMPLEMENTACION DEL AGP ............................. 3.4. I Ajuste de los paráineiros del AGP.. .............
............................................... 62 ................................................... 66
........................... 67
4. RESULTADOS .................................................................................................................... 68
....................................................
4.1 AMBIENTE DE DES
4.2 RELOJ DE 12 HORAS ... .......................................... 4.2.1 Contador 0-9. 4.2.2 Contador 0-5.
4.2.3 Coniador 0-11.
5
4.3 OTRAS APLICACIONES ................................................ ......__._.__..,_..._.... 80 4.3.1 CONTADOR ASCENDENTE/DESCENDENTE DE 2 BITS .................................................................. 80
4 . 3 . 2 Circuito votador de 3 bits .... . . .. . .._. . .. . . . . .. .. . . .. ........... .. .. .. 4.3.3 Sumadorparalelo de 2 bits ...._......._.. . . . . . . . . . . . . . . . . . . . , . .
4 .3 .4 Generador de Redundancia Ciclica de 4 bi/s (CRC-4)
4.3.5 Generador deparidadpar de 4 bits ....................................................................................... 87
..... 88
4.4 RESUMEN .. ................................. 91
CONCLUSIONES ................................................................................................................... 92
AFJÉNDICE .............................................................................................................................. 97
BIBLIOGRAFIA Y REFERENCIAS .................................................................................. 105
6
Figura 0.1.- Estructura de la tesis
Figura 1.1 .- Componentes básicos de un arreglo embriónico.
Figura 1.2.- Estructura de la memoria de un arreglo embriónico
Figura I .3.- Generación de coordenadas p
...................... 16
Figura 1.4.- Estructura del enrutador [OrtOOb]. ..................................... Figura 1.5.- Arquitectura del elemento de
Figura 1.6.- Registro de configuración. .... Figura 1.7.- Sistema celular con células d
................................... 26
Figura 1 .S.- Proceso de eliminación de u .................... 21 Figura 1.9.- Tolerancia a fallas mediante la eliminación de una célula [OrtOOb] ................................... 28
Figura 1.10.- Árbol binario de decisión de la tabla de verdad de la tabla 1 . I
Figura 1 . I 1.- Reducción de un árbol de decisión en OBDD. .................. Figura 1.12.- Árbol de multiplexores del OBDD de la figura 1.1 IC. ..................................................... 31
Figura 1.13.- Función implementada en un arreglo embri
Figura 1.14.- BDD del circuito votador ............................ Figura 1.15.- Implementación en un árbol de multiplexores del circuito votador .................................. 33
Figura 1.16.- Circuito votador implement
Figura 2.1 .- Funcionamiento básico de u
Figura 2.2.- Representación gráfica de la solución del problema del agente viajero. .
Figura 3.1 .-Árbol de multiplexores del
Figura 3.2.- Conectividad de un Arregl
Figura 3.3.- Enrutador de WS de una célula. .................... Figura 3.4 .- Registro de configuración
Figura 3.5.- Elemento de procesamient
Figura 3.7.- Árbol de multiplexoTes y acomodo en un AE del circuito votador ...........
Figura 3.9.- Aplicación de la mutación a un cromosoma de la población .....
Figura 3.10.-Diagrama de flujo del AGP.
Figura 4.2.- Estructura del reloj de O a 12 horas ..............................
......................... .46
.......................... 48
.......................... 54
Figura 3.6.- Representación de un cromosoma.
Figura 3.8- Generación de nuevos cromosomas mediante la cmza ............................................
........................................... Figura 4.1 _- Cuenta máxima del reloj de O a 12 horas
.......................... IO
7
............ ........................ 71 Figura 4.3.- OBDD para el contador 0-9.
....... .......................... 74 Figura 4.5.- Enrutamiento del contador 0-9
Figura 4.7.- Simulación del contador 0-9 con una fila dañada. .....
Figura 4.9.- Enrutamiento del contador 0-5 ................... Figura 4.10.- Simulación del contador 0-5. ...... Figura 4.1 1.- Árboles de multiplexores del contador 0-1 1. ........................ Figura 4.12.- Enrutamiento parcial del contador 0-1 1, primera parte
Figura 4.13.- Enrutamiento parcial del contador 0-1 1, segunda parte ................................ Figura 4.14.- Simulación del contador 0-1 1. ...............
Figura 4.15.- Árboles de multiplexores del contador ascendentddescendente de 2 bits. ..
Figura 4.17.- Simulación del contador ascendente/descendente de 2 bits. ............................................. 81
Figura 4.19.- Enrutamiento del circuito votador de 3 bits. ...................................................
Figura 4.20.- Simulación del circuito votador de 3 bits
........................
Figura 4.4.: Árboles de multiplexores del contador 0-9. ......... ............................ ..71
....................... ................ Figura 4.6.- Simulación del contador 0-9 con todas las células en buen estado
Figura 4.8.- Árboles de multiplexores dekont ..................................
.....................................
................................ 19
................................... 80
Figura 4.16.- Enrutamiento del contador ascendente/descendente de 2 bits
Figura 4.18.- &bol de multiplexores del circuito votador de 3 bits ....................................................... 82
82
............................................................. 83
Figura 4.21 .- Arboles de multiplexores del sumador paralelo de 2 bits. ..........................................
Figura 4.22.- Enrutamiento del sumador paralelo de 2 bits .................................................................... 84
Figura 4.23.- Simulación del sumador paralelo de 2 bits. ...................................................................... 84
Figura 4.24.- Árboles de multiplexo
Figura 4.25.- Enrutamiento del CRC-4. ... Figura 4.26.- Simulación del CRC-4 .................................................................................... 86 Figura 4.27.- Árbol de multiplexores del generador de paridad par de 4 bits. ....................................... 87
Figura 4.28.- Enrutamiento del generador de paridad par de 4 bits.. Figura 4.29.- Simulación del generador de paridad par de 4 bits. ................................
Figura 4.30.- Árbol de multiplexores del generador de paridad par de 5 bits
Figura 4.31.- Enrutamiento del generador de paridad de 5 bits ... Figura 4. 32.- Simulación del generador de paridad par de 5 bits. ......................................................... 90
Figura A. 1 .- Módulo de memoria ............................................... ................................... 98 Figura A.2.- Generador de coordenadas ................................................................................................. 99
Figura A.3.- Emtador de Entrada / Salida. ......................................................................................... 100
101 Figura A.4.- Elemento de procesamiento
a
Figura AS.- Arquitectura de una célula embriónica ............................................................................ 102
Figura A.6.- Símbolo creado a partir del esquemático de la figura A S ............................................... 103
Figura A.7.- Arreglo embriónico de 5x8 para simular el contador 0-9 y su detector de rebose (DR) .. 104
9
Tabla 0.1 .- Diferencias entre inteligencia artificial y vida artificial [OrtOOa]. ...................
Tabla 1.1 .- Ejemplo de una tabla de verdad
Tabla 1.2.- Tabla de verdad del circuito votador .................................................................................... 32
Tabla 3.1.- Tabla de verdad del circuito votador .... ..... .... ... 44
Tabla 3.2.- Entradas fuentes del circuito votador. .. .............................................................. 44
Tabla 3.3.- Matriz que representa la conectividad del AE de la figura 3.2
Tabla 3.4.- Decodificación de los bits correspondientes al enrutador de E/S
Tabla 3.5.- Carga de variables de entrada al AE. ................................................... : ............................... 49
Tabla 3.6.- Propagación parcial de las variables del AE . . j l
Tabla 3.7.- Propagación de las variables, primera pasada. ..................................................................... 52
Tabla 3.8.- Propagación de las variables, segunda pasada. .................................................................... 53
Tabla 3.9.- Propagación completa de las variables
Tabla 3.10.- Significado de las entradas del regis
Tabla 3.1 1.- Llenado de las entradas del element
Tabla 3.12.- Entradas fuentes del árbol de multiplexores del circuito votador.
Tabla 3.13.- Actt~alización de las salidas de las células
Tabla 3.14.- Matnz de conectividad parcial de un cromosoma que no resuelve el enrutado. ................ 6U
.............. i o Tabla 4.1 .-Tabla de verdad para el contador 0-9.
Tabla 4.3.- Tabla de verdad para el contador 0-5. ........
Tabla 4.4.- Tabla de verdad para el contador 0-1 I .
Tabla 4.5.- Tabla de verdad para el contador ascendenteidescendente de 2 bits ......................
Tabla 4.6.- Tabla de verdad para el circuito votador de 3 bits. .............
Tabla 4.7.- Tabla de verdad para el sumador paralelo de 2 bits. ...................... Tabla 4.8.- Tabla de verdad del CRC4. .................................... ..................................... 85
......................... 81 Tabla 4.9.- Tabla de verdad del generador de paridad par de 4 bits. ..... .. 89
Tabla 3.15.- Población ordenada de acuerdo con la mejor aptitud ................................................. 65
....................................
Tabla 4.2.- Resultados de las corridas del programa del algoritmo genético. ........................................ 72 .................................. .. 15
......................... 77
..so ......................... 82
......................... 83
Tabla 4.10.- Tabla de verdad del generador de paridad par de 5 bits. ...........................
10
Listado 3.1 .- Archivo de entrada del AGP. .......................
Listado 3.2.- Archivo de salida del AGP
Listado 4.1 .- Archivo de entrada para en
Listado 4.2.- Archivo VHDL que describe la memoria del reloj de 12 horas. ........
Listado 4.4.- Archivos de entrada para enrutar el contador 0-1 1. ..........................................
Listado 4.5.- Archivo de entrada para enrutar el contador ascendente/descendente de 2 bits .....
.............
..................................................................... 66
...................... 72
Listado 4.3.- Archivo de entrada para enrutar el contador 0-5. .............................................................. 76 ~
Listado 4.6.- Archivo de entrada para enrutar el circuito votador de 3 bits. .......................................... 82
Listado 4.7.- Archivo de entrada para enrutar el sumador paralelo de 2 bits. .......................... 84
..... .......................... 85
Listado 4.9.- Archivo de entrada para enrutar el generador de paridad par de 4 bits.. .87 Listado 4.10.- Archivo de entrada para enrutar el generador de paridad par de 5 bits. .......................... 89
Listado 4.8.- Archivo de entrada para enrutar el CRC-4
11
Sistemas Bioinspirados
Desde hace algunos años hemos sido testigos de una fusión de ideas innovadoras con
tecnologías avanzadas, dando origen al viejo sueño de construir máquinas capaces de imitar
algunos de los mecanismos que encontramos en los seres vivientes. Esta temática, en su
forma moderna, fue tomada por primera vez hace casi 50 años por el padre de la cibernética,
John Von Neumann. La idea central de su trabajo eran los conceptos de autoreproducción y
autoreparación. Desafortunadamente. la tecnología disponible en su época no era suficiente
para realizar sus ideas.
En los años siguientes, hemos visto el surgimiento de sistemas bioinspirados tales como
las redes neuronales, acompariado por la aparición de una nueva rama de estudio llamada
vida artificial. La idea central del estudio de la vida artificial es la aplicación de mecanismos
que presenta la evolución natural a sistemas artificiales. John Holland fue otro pionero de
estas investigaciones y propuso las bases de lo que hoy se conocen como algoritmos
genéticos. Aunque los conceptos de la vida artificial han avanzando muy lentamente, han
encontrando un lugar dentro de muchas disciplinas tradicionales de la ingenieria [OrtOOa].
El incremento considerable en el poder computacional y más recientemente, la aparición
de una nueva generación de dispositivos lógicos programables, han hecho posible la
realización de modelos de codificación genética y evolución artificial. Esto ha permitido la
simulación y finalmente la realización en hardware de un nuevo tipo de máquinas. Hemos
cruzado una barrera tecnológica que nos impedía en lugar de disetiar, evolucionar máquinas
para obtener el comportamiento deseado. Este nuevo enfoque ha sido llamado ingeniería evolutiva: “El arte de usar algoritmos evolutivos para construir sistemas complejos”. Aunque sólo se han dado los primeros pasos, promete revolucionar la forma de diseñar nuestras
máquinas futuras. Estamos siendo testigos del nacimiento de una nueva era, en la cual los
términos ‘adaptación’ y diseño no serán conceptos opuestos [OrtOOa].
introducción
La evolución natural implica poblaciones de individuos, cada uno conteniendo una
descripción de sus características físicas, el genotipo. Una nueva generación de individuos es creada a través del proceso de reproducción, en el cual los genotipos son transmitidos a sus descendientes con modificaciones debido a la cruza y la mutación. Estas operaciones
genéticas se realizan de manera autónoma dentro de cada entidad, esto es, dentro del genotipo. A la manifestación física del genotipo se le conoce como el fenotipo, esto es, el
individuo que resulta de interpretar el genotipo. Durante su vida, el individuo es sometido al
medio ambiente el cual, a través de un proceso de selección natural, mantiene a los individuos mejor adaptados. El proceso evolutivo no tiene un controlador central; la .aptitud
de un individuo está implícitamente determinada por su capacidad para sobrevivir y reproducirse en el medio ambiente [OrtOOa].
La vida natural sobre la tierra está organizada en por lo menos cuatro niveles
fundamentales de estructura:
9 Nivel de población-ecosistema.
9 Nivel de organismo ,:
9 Nivel celular
9 Nivel molecular.
El estudio de la vida en cualquier contexto requiere del entendimiento de los cuatio
niveles, por ello las ciencias biológicas están usando sistemas de vida artificial para entender
la vida natural. Los sistemas de hardware son usados para estudiar ei nivel de organismos.
Los niveles de población y celular son estudiados a traves del uso de sistemas de software.
El nivel molecular es estudiad0.a través de experimentos con moléculas RNA (Ácido
Ribonucleico) [OrtOOa].
El trabajo en vida artificial puede ser dividido en dos ramas generales: el diseño de sistemas con "propiedades biológicas" para realizar una tarea particular. por ejemplo las redes neuronales artificiales; y el uso de técnicas de la ingeniería.para precisar un modelo
biológico con el propósito de probar una hipótesis en la biología por ejemplo, la ingeniería genética. La investigación sobre inteligencia artificial se ha llevado a cabo en los laboratorios
de ciencias de la computación por más de cuarenta años. En contraste, el estudio de la vida 'artificial es más moderno y aún está en sus inicios. Es importante hacer una clara distinción
entre inteligencia artificial y este nuevo paradigma llamado vida artificial. La tabla 0.1 muestra
algunas diferencias importantes entre las dos disciplinas [OrtOOa].
13
INTELIGENCIA ARTIFICIAL (Al) VIDA ARTIFICIAL (ALIFE) I Enfocado a individuos Conocimiento sobre operaciones de lógica Inicia con el conocimiento del nivel humano Jerarquía principal: sistemas complejos de ingeniería Especificación directa de conocimiento de arquitecturas
I individuos -
Enfocado a un grupo o población Conocimiento sobre operaciones de sistemas nerviosos Conocimiento situado con experiencias sensorahotríz Jerarquía principal: cuenta con la evolución. desarrollo y aprendizaje Especificación indirecta de conocimiento de arquitecturas por medio de mapeo de
Tabla 0.1 .- Diferencias entre inteligencia artificial y vida artificial (OrtOOa].
El Modelo POE
Para clasificar los sistemas bioinspirados, Sánchez et al. prcponen el modelo POE
(Phylogenia, Ontogenia y Epigénesis) [San97]. En este modelo, los sistemas bioinspirados
Se clasifican de acuerdo al nivel donde se lleva á cabo la adaptación al ambiente. En la
Phylogenia se encuentran los sistemas que se adaptan al medio ambiente a través de la
transmisión de material genético de una generación a otra. La adaptación se iogra a nivel de
especies. En este eje encontramos a todas las estrategias evolutivas (algoritmos genéticos,
programación evolutiva, etc.). La Ontogenia agrupa a los sistemas multicelulares que logran
su adaptación al medio ambiente a través de mecanismos de regeneración a n'ivel local
(sanar, cicatrización); en este eje se encuentran los arreglos celulares y Embriónicos.
Finalmente, la epigénesis agrupa a los sistemas que logran su adaptación al medio ambiente
mediante el aprendizaje. Aquí encontramos a las redes neuronales, los sistemas
inmunológicos artificiales y los sistemas inteligentes [OrtOOa].
El trabajo en esta tesis combinará dos ejes del modelo: la phylogenia (algoritmos genéticos) y la ontogenia (arreglos Embriónicos).
Los arreglos Embriónicos forman parte del estudio de la vida artificial. En embriónica se
pretende tomar conceptos de la biología y realizar un sistema celular que pueda desarrollar
una función deseada, aún cuando existan fallas en algunas de sus unidades básicas
(propiedades de tolerancia a fallas). En otras palabras, un sistema embnónico trata de
Tareas mentales a nivel humano Tiempo de trabajo en horas
14
genotipo y fenotipo Sobrevivencia en ambientes complejos Evolución, generación y vida de los
Introducción
La hipótesis a comprobar en esta tesis es que es posible resolver el enrutado de un arreglo embriónico utilizando un
algoritmo genético. <<
emular las propiedades de la naturaleza como lo son reproducción, sobrevivencia,
adaptabilidad, para seguir operando cuando se presente algún daño al arreglo embriónico.
Hipótesis
La idea primordial en embriónica es tomar los conceptos de la Biología para realizar un
arreglo de células electrónicas que sea capaz de reconfigurarse y proporcionar un sistema
tolerante a fallas. Las células embriónicas tienen una conectividad limitada, por lo que el
problema de enrutar una aplicación se vuelve más dificil a medida que la aplicación crece en
complejidad.
Objetivo general
Diseñar, desarrollar y probar un enrutador automático basado en algoritmos genéticos
para resolver el problema de enrutado en los arreglos embriónicos.
Objetivos particulares
9
9
9
b
9
9
Representar en forma abstracta de la conectividad del arreglo embriónico (enrutado
deseado).
Generar los cromosomas del problema de enrutado. Desarrollar un algoritmo genético que resuelva el enrutado del arreglo embriónico.
Convertir la salida del algoritmo genético en registros de configuración. Sintetizar el arreglo ernbriónico para un FPGA.
Comprobar los resultados por simulación.
Alcances
AI desarrollar el presente tema de tesis se propone obtener los siguientes alcances:
9 Representación abstracta de la topología del arreglo de multiplexores y de la
conectividad del arreglo embriónico que sea adecuada para usarse en un algoritmo
genético.
15
.iijlj ,, . t , .., *.e).,' ,
Introducción
9 Algoritmo genético que resuelva el enrutado del arreglo de multiplexores en el arreglo
P Programa que genere automáticamente el contenido de los registros de configuración
del arreglo embriónico diseñado. P Selección de una aplicación típica para probar el sistema diseñado.
embriónko.
Aportación o contribución del trabajo
Con el presente trabajo de tesis se pretende obtener:
> Inicio del estudio de los arreglos embriónicos en México. 9 Uso de los algoritmos genéticos para solucionar un problema de enrutado. 9 Diseno y desarrollo de un enrutador automático de arreglos embriónicos el cual
puede contribuir al estado del arte en esta área.
Estructura de la tesis
En la figura 0.1 se muestra la estructura de la tesis:
Figura 0.1.- Estructura de la tesis.
16
introducción
EI capítulo I presenta los conceptos básicos tomados de la biología Por la embriónica.
Se describen los antecedentes, estructura y funcionamiento de los arreglos embriónicos. Se
presenta una aplicación realizada mediante una metodologia rústica y poco manejable. De
aquí surge la problemática del enrutamiento de los arreglos embriónicos, motivo por el cual
se propone una forma más rápida y automática de enrutamiento mediante los algoritmos
genéticos.
El capítulo II trata todo lo referente a los algoritmos genéticos como son sus
características, estructura y funcionamiento. Se describen los elementos que constituyen a
un algoritmo genético en forma general. Se presenta una definición y clasificación de lo que
es un enrutador. Se muestra el enrutamiento basado en los algoritmos genéticos como una
herramienta de optimización de problemas.
El capítulo 111 describe la forma de implementar a los elementos que constituyen al
algoritmo genético programado que resuelve el enrutamiento de los arreglos embriónicos. El
algoritmo genético se implementó en el lenguaje de programación C.
En el capítulo IV. se presentan los resultados de la simulación en Foundation de Xilinx
de varios circui:os combinacionales y secuenciales. para probar el enrutador de arreglos
embriónicos basado en los algoritmos genéticos propuesto en este trabajo de investigación.
Como parte final se plasmarán las conclusiones obtenidas a través del desarrollo de
este trabajo. En el se mostrarán 10s detalles, aspectos relevantes y sucesos importantes que
Se vivieron durante la realización de los objetivos. Así también se mostrarán las apoflaciones
Y trabajos futuros relacionados con el desarrollo del presente trabajo,
17
.. -
CcaPÍW.0 I
1. ARREGLOS EMBRIÓNICOS
Este capitulo presenta en la sección 1.1 los antecedentes y conceptos tomados de la biología que definen a los arreglos embriónicos. La estructura de los arreglos embriónicos se presenta en la sección 1.2. En la sección 1.3 se muestran dos estrategias para realizar la reconfiguración de un arreglo embriónico en caso de falla. La sección 1.4 presenta el procedimiento para irnplementar aplicaciones en un arreglo embriónico. En la sección 1.5 se presenta una aplicación siguiendo el procedimiento planteado en la sección 1.4.
1.1 Introducción
1.1.1 Antecedentes
Una de las instituciones dedicadas al estudio de la electrónica inspirada en la biología es la
Universidad de York, en York, Inglaterra, denominando su campo de trabajo como
"lngenieria bioinspirada", la cual comprende diversas ramas de estudio como son:
D Embriónica: La embriónica propone una nueva familia de arreglos de procesadores
tolerantes a fallas inspirados en el desarrollo ontogénico de organismos multicelulares [OrtOOb].
9 Embriónica Asíncrona: La embriónica asíncrona intenta aplicar la metodologia para
implementar circuitos asíncronos al diseño de circuitos embriónicos [JacOl]. 9 Hardware Evolutivo: Es la aplicación de Algoritmos Evolutivos (corno Algoritmos
Genéticos o Programación Genética) para el diseño de circuitos electrónicos. Este
pnegcOs em btiónicos ~ P Í r n L O I
proyecto incluye la investigación de tolerancia a fallas Como Una Propiedad implícita
de circuitos electrónicos evolucionados [Tyrol]. p /nmunotrónjca: Diseño de sistemas electrónicos tolerantes' a fallas inspirados en el
sistema inmune humano. Los sistemas electrónicos aprenden a diferenciar entre la
operación correcta y la operación no correcta del sistema [BraOZI. 9 Programación Genética de Enzimas: Se utiliza como una herramienta Para generar
automáticamente programas. Usa una representación derivada del Sistema natural
genético para incrementar la capacidad para evolucionar de Programas en desarrollo,
[LonOl].
F,~
Otra institución dedicada a la búsqueda de nuevas aplicaciones electrónicas inspiradas en la biología es el Politécnico de Lausana, en Lausana, Suiza. En esta institución se
realizan estudios acerca del modelo POE utilizado para clasificar a los sistemas de hardware
bioinspirados (ver sección '1.1.2) [OrtOOa]. Su proyecto $e embriónica está inspirado en los procesos básicos de la biología molecular y el desarrollo embrionario de los seres vivientes.
Adoptando ciertas características de organización celular, . y adaptándolas al mundo
bidimensional de los circuitos integrados de silicio, se logran propiedades del mundo viviente,
tales como auto replicación y auto reparación.
- .,i . '
El objetivo principal del grupo de investigación 'en el Politécnico de Lausana es ,el
desarrollo de circuitos de .muy grande escala de integración (VLSI) capaces de auto
repararse y auto replicarse. La auto reparación permite la reconstrucción parcial en caso de una falla menor, mientras la auto replicacijn permite la reconstrucción completa del
dispositivo original en caso de una falla mayor. Estas dos propiedades son paicularmente
deseables para sistemas artificiales complejos tales como:
P Aplicaciones que requieren muy alto nivel de confiabilidad, como la electrónica aeronáutica o médica.
k Aplicaciones diseñadas para ambientes hostiles, como el espacio, donde el
incremento de los niveles de radiación reducen la eficiencia de los componentes.
b Aplicaciones avanzadas que manejan niveles bajos de consumo de potencia, y alta
velocidad de operación.
Estas áreas de aplicación requieren del desarrollo de un nuevo paradigma de diseño que Sea capaz de soportar pruebas confiables en tiempo real de circuitos VLSl y sobre todo
soluciones que permitan la auto reparación,
19 Enrutador dé aneghos em6nóntcos utiíiiando abontmosgenéttcos
1.1.2 Definición
Embriónica es un término adoptado para describir un hardware reconfigurable capaz de
repararse y de reproducirse dinámicamente. Toma su nombre de la fusión de la embriología
con los sistemas electrónicos. La embriónica fue propuesta originalmente por Mange y
Marchal [2. 31. La embriónica también ha sido estudiada como una técnica que proporciona
propiedades de tolerancias a fallas en una arquitectura celular. El proyecto Embriónica se
ubica en el marco del Hardware Evolutivo (EHW), el cual comprende el diseño y la
realización de sistemas electrónicos bioinspirados capaces de adaptarse a cambios del
medio ambiente de manera autónoma.
1.1.3 Conceptos tomados de la biología
Las Células son las unidades básicas de los seres vivos. Los animales están formados
por células especializadas que forman la sangre, los huesos, los cartílagos, los músculos y
las células nerviosas. Los humanos tienen cerca de 350 tipos de células diferentes. Todas
las células que constituyen a un ser vivo, que se reproduce sexualmente, tienen su origen en
la división repetida de un óvulo fecundado.
Las células se diferencian dentro de un embrión de acuerdo a la posición que guardan
con respecto a las otras células. La información de la posición la adquieren por medio de
gradientes químicos. Cada célula tiene un conjunto de instrucciones (información genética), que define su función para cada posición [OrtOOb]. Se puede decir que cada célula en un
organismo tiene una biblioteca donde está almacenado el código para controlar SUS
acciones: el ácido desoxirribonucleico o ADN. Una célula tiene una planta química y una
respuesta química que actúan como sus dispositivos de entrada y salida. Diferentes dosis de
quimicos y en combinaciones diferentes causan que una célula actúe de formas diferentes.
1.2 Estructura
Las arquitecturas embriónicas permiten emular algunos de los mecanismos observados durante la ontogénesis de los organismos que se reproducen sexualmente. Un sistema
embriánico es un arreglo bidimensional de células, donde cada una es un elemento de
procesamiento. Todas las células realizan la misma operación básica y su función específica está determinada por su posición dentro del sistema celular. En la figura A.7 del apéndice se
20 Enrutador di arreglos embnónuos utiluando afgantmos genétrcos
i i' 1.
ArregcOs em6nónicos MPÍTVLO I
muestra un arreglo embriónico de 5x8 células implementado para simular disetios digitales utilizando el ambiente de desarrollo Foundation de Xilinx.
La función lógica de cada célula es determinada por uno de los registros de
configuración localizados en su memoria. Los registros de configuración son seleccionados
por las coordenadas de la célula en relación a sus vecinos. La figura 1.1 muestra la
arquitectiira básica de un sistema embriónico genérico.
Figura 1.1.- Componentes básicos de un arreglo embriónico.
La arquitectura mostrada en la figura 1.1 presenta las siguientes ventajas:
> Es altamente regular, lo cual facilita su implementación en silicio. El elemento de
procesamiento (multiplexor en este caso) puede ser diseñado para realizar otras
funciones lógicas.
P La arquitectura del elemento de procesamiento es simple, pÓr lo que es posible llevar a cabo autodiagnóstico sin incrementar excesivamente el área de silicio.
En un arreglo embriónico convencional se requiere tener en cada célula, memoria suficiente para almacenar los registros de configuración de todas las células del arreglo
(cromosoma de la célula). Esta arquitectura requiere de una cantidad de memoria por célula
muy grande y difícil de implementar.
1.2.1 Memoria
Cada célula embriónica contiene una copia de los registros de configuración de todas las células del arreglo embriónico. La configuración transparente configura a la célula de tal
. . manera que la entrada de un punto cardinal del enrutador de EIS se propague a la salida del
punto cardinal contrario correspondiente. por ejemplo, la entrada del bus del Sur se
propague a la salida del bus del Norte. La configuración transparente se selecciona cuando
se detecta una falla en la célula.
El elemento de procesamiento de la célula requiere de 17 bits para su configuración. La cantidad total de memoria requerida en cada célula embriónica es: (n registros del arreglo
embriónico)*(17 bits por registro) = 17n bits. La figura 1.2 muestra la estructura de la memoria utilizada en un arreglo embriónico.
La figura A . l del apéndice muestra el esquemático de la memoria implementada para
simular diseños digitales sobre Foundation de Xilinx. Este esquemático ha sido generado a
partir de un archivo VHDL que proporciona el algoritmo genético programado en el capitulo
3. El archivo VHDL contiene los registros de configuración de todas las células del arreglo
embriónico. La memoria es la misma para todas las células. De acuerdo a las coordenadas
(m, n) de cada célula, se decodifica su registro de configuración correspondiente.
I I
Figura 1.2.- Estructura de la memoria de un arreglo embriónico.
1.2.2 Generador de coordenadas
Cada célula genera una coordenada (rn, n) para sus vecinos del norte y del este. El
valor de la coordenada rn depende del estado de la célula que lo genera. Solo si la CélUla
está en buenas condiciones de operación, la coordenada rn se incrementa en 1 y el valor resultante se propaga hacia la célula del norte. La coordenada n siempre se incrementa en 1 y el valor resultante se propaga hacia la célula del este.
22 Znrutaáor de arreglos emGnónicos utilizando a!&ntmosgenéticos
Aneglós em6riónicos ~ C P Í W L O I
Si la célula está en malas condiciones de operación entonces se vuelve transparente, es
decir, todas las entradas del sur se propagan hacia las salidas del norte y la coordenada m se propaga hacia el norte sin incrementar. La figura 1.3 ilustra el proceso de la generación de
coordenadas. La figura A.2 del apéndice muestra el circuito generador de coordenadas de
la célula implementado para simular diseños digitales sobre Foundation de Xilinx.
I Coordenada m
4 Hacia el
Coor- vecino
n
z t AI bloque de
memoria Coordenada del sur
I a) Generador de coordenadas b) Coordenadas generadas
Figura 1.3.- Generación de coordenadas para cada célula. ..1 . .
El circuito que genera ,las coordenadas es combinacional, por lo tanto, el tiempo
requerido para reconfigurar un arreglo completo es muy coito ya que depende solamente del
número de células en el arreglo y el retardo de propagación de las compuertas involucradas.
La reconfiguración de un arreglo embriónico incluye dos fases: la fase de inicialización,
donde las ‘coordenadas son calculadas y el cromosoma (registros de configuración) es
descargado^ y la fase operacional, donde el arreglo realiza la función deseada. Durante la
fase de inicialización las coordenadas son ignoradas y las salidas del arreglo son
consideradas inválidas. Cada célula dentro del arreglo selecciona un registro de configuración y las salidas se vuelven válidas.
1.2.3 Enrutador de entrada I salida
En un arreglo celular convencional la comunicación entre células está restringida a los vecinos más próximos. Para sobrellevar esta limitación el enrutador proporciona trayectorias
adicionales para que la información pueda ser propagada hacia células no vecinas.
La figura 1.4 muestra la estructura interna del enrutador. El enrutador está formado por cuatro selectores 4-1, uno para cada salida. Las etiquetas en negrillas representan los bits
23 “Enmiador lie aneglós em6riónicos utiíkando ahonitnosgenétuos
.. . , " . i + ; " L : I * - - I ' . , .. ~
,. .r* . 4' , CaPÍTULO 8 . I b 8 ' AnegCOs em6n5nicos
de selección de cada selector y se encuentran presentes en el registro de configuracióri. Los
bits de configuración N1:0, Sl:O, E1:O y W1:O ajustan la salida del selector correspondiente.
La figura A.3 del apéndice muestra el circuito del enrutador de la célula .implementado para
simular diseños digitales sobre Foundation de Xilinx.
I
EOBUS +
EIBUS -
I I
Figura 1.4.- Estructura del enrutador [OrtOOb].
1.2.4 Elemento de procesamiento
El elemento de procesamiento de la célula la realiza un multiplexor 2-1, donde cada
entrada puede ser seleccionada de 8 posibles fuentes. La salida puede ser almacenada y
del elemento de procesamiento. La figura A.4 del apéndice muestra el circuito del elemento
de procesamiento de la célula implementado para simular disetios digitales sobre Foundation
de Xilinx.
realimentada para realizar circuitos Secuencialec'La 'figura.l-.5.1!1uest~ lasfru-ctura interna I - - --.-
Los selectores mostrados en la figura 1.5 permiten varias combinaciones de entrada-
salida, una de las cuales es seleccionada por los registros de configuración (escritos en
negrillas en la figura 1.5). Esta capacidad de selección, junto con el enrutador de entradalsalida (Enrutador), permite la implementación de diagramas binarios de decisión ordenados (OBDD).
24 Ennitador di aneglüs embnónicos utifizanáo akoritmosgenéticos
gznegúx em6nónicos C,mPfTL!LO I
I I
Figura 1.5.- Arquitectura del elemento de procesamiento de la célula [OrtOOb].
Existen dos tipos de datos de entrada para este módulo: aquellos que son propagados
naturalmente y no requieren de configvración alyuna (EIN, WIN, SIN, NOUT, WOUT y E O o T ) m ¿ u y a - - f T e G e y destino son: seleccionados mediante el registro de
configuración y el módulo enrutador (EOBUS, EIBUS, SIBUS y SOBUS). El enrutador
permite el intercambio de información entre células no vecinas. Los prefijos N, E. W, y S
indican el vecino que está recibiendo o transmitiendo la serial correspondiente. Por ejemplo, NOUT es la salida que va al vecino del norte, mientras que EIBUS es la entrada controlada que viene del vecino del este.
- 2- -.. . ~ - ~-
L2:O y R2:O seleccionan una salida en sus multiplexores respectivos. Es posible
propagar las constante cero o uno para facilitar la implementación de los nodos finales en los
OBDD. La salida Q es realimentada a la entrada 5 de cada multiplexor 8-1, esto permite la implementación de circuitos secuenciales. El bit REG del registro de configuración determina
si la salida del elemento de procesamiento es combinacional o secuencial. La entrada de
selección para el multiplexor principal (marcado con un asterisco en la figura 1.5) puede ser
una de cuatro señales. El valor de los bits de €BUS [I ... O] del registro de configuración
25 Enrutador de anegbs em6riónuos utihando ahontmosgenéticos
c,mm.m I ilwegbs em6nóntros
determinan si EOBUS. EIBUS, EIN o WIN seleccionará la salida del bloque. La entrada SIN
es automáticamente propagada a través de las salidas EOUT y WOUT.
1.2.5 Registro de configuración
La figura 1.6 muestra el contenido del registro de configuración.
I 1 161514131211109 8 7 6 5 4 3 2 1 O
u u - l I u _ I u u u u
R2:O REG
EEUS1:O
Figura 1.6.- Registro de configuración
EBUS1:O.- Determina si la entrada de selección para el multiplexor principal será
EOBUS (EBUS = O), EIBUS (EBUS = I), EIN (EBUS = 2) o WIN (EBUS = 3).
REG.- Si el bit REG está a 1, la salida del bloque lógico es combinacional, en caso
contrario es secuencial.
N1:0, E1:0, W1:0, C1:O.- Estos pares de bits seleccionan la entrada que será propagada
L2:0, R2:O.- Las entradas izquierda (L, left) y derecha (R. right) del multiplexor prin.cipal
son seleccionadas de acuerdo con los valores de estos bits. Existen ocho posibles setiales
que pueden ser seleccionadas por la combinación de estos bits.
hacia las salidas NOBUS, EOBUS, WOBUS y SOBUS de los selectores del enrutador.
Una vez cargado el valor del registro de configuración, éste permanece sin cambios. AI final del proceso de configuración, el contenido de la memoria de todas las células del
arreglo es el mismo. La posición de la célula dentro del arreglo es la que determina el registro de configuración que será decodificado.
1.3 Mecanismos de reconfiguración
El problema de la tolerancia a fallas en un arreglo de procesadores de tamaño rn x n implica garantizar que siempre se tendrá un subarreglo de menor tamaño (r x k) trabajando correctamente. La figura 1.7 ilustra estas aseveraciones.
26 %?rutador de anegbs embnónicos utiíizando a@oritmosgene’ticos
O
C6iula Activa
Celula de repuesto
Figura 1.7.- Sistema celular con células de repuesto !OrtOOb].
En la figura 1.7, las células activas son el número mínimo de células necesarias para
realizar la función deseada. Las células de repuesto están presentes, pero no contribuyen a
la operación normal del arreglo, sólo se vuelven activas cuando sustituyen a células en falla.
1.3.1 Estrategia de eliminación de una fila o una columna
En esta estrategia la falla de una célula provoca la eliminación de la fila (o columna)
correspondiente [OrtOOb]. Esta es la estrategia que se adoptó para el desarrollo este trabajo.
Las células son lógicamente movidas hacia arriba haciendo uso de una fila de repuesto. La
figura 1.8 muestra un ejemplo de eliminación de una fila en un arreglo
repuesto.
Propagaci6n de la setial que indica una falla
con una fila de
a) Arreglo completo I
c) Error corregido I
bl Error en una celula
Célula activa
Célula de repuesto
0 Ceiuia transparente
Figura 1.8.- Proceso de eliminación de una fila en un arreglo embriónico
27 Enrutador dé anegbs em6nónuos utikando ahontmosgenéticos
Cuando una fila es eliminada, las coordenadas de las células son recalculadas y nuevos
registros de configuración son seleccionados en cada célula. La reconfiguración se considera
concluida cuando cada célula ha seleccionado el registro de configuración que corresponde
a sus nuevas coordenadas y los flip flops han actualizado sus salidas.
Esta estrategia está muy lejos de ser óptima con respecto al uso de células de repuesto, pero el corto tiempo de recuperación cuando ocurre una falla lo hace atractivo para
implementarlo en sistemas tolerantes a fallas de tiempo real.
1.3.2 Estrategia de eliminación de una célula
En esta estrategia, las células en falla se reemplazan en dos etapas. Primero, se
localizan repuestos en la misma fila para reemplazar a las células en falla. Cuando el número
de células que han fallado en una fila sobrepasa el número de células de repuesto en esa
fila, se elimina la fila. La figura 1.9 muestra un ejemplo con una columna y una fila de
repuesto.
amm mmEl Llmm Elam 0 Célula activa Céluia de repuesto I I_ - - 1 l Célula inactiva (muerta)
Figura 1.9.- Tolerancia a fallas mediante la eliminación de una célula [OrtOOb].
1.4 Metodología para implementar aplicaciones
1.4.1 Planteamiento del problema.
Para realizar un circuito lógico utilizando un arreglo embriónico. la descripción del circuito debe estar dada como un conjunto de ecuaciones booleanas. Ejemplos de circuitos que se pueden implementar son: contadores, sumadores, restadores, temporizadores.
relojes, decodificadores, circuitos de detección de error, divisores de frecuencia, etc.
28 Enrutador dé arreglos em6riónicos utiíiaiuio aboritmosgedtuos
Arreglos em6nónicos C a P í W L O I
1.4.2 Obtención de la tabla de verdad
Una vez que se tiene el problema en forma de ecuaciones booleanas, se reallza la tabla de verdad respectiva. La tabla 1.1 muestra un ejemplo de una tabla de verdad de una función y = f(A,B.C).
Tabla 1 .I .- Ejemplo de una tabla de verdad.
1.4.3 Obtención del diagrama binario de decisión
Un árbol o diagrama binario de decisión (RDD: Binary Decision Tree or Diagram) es la representación gráfica de una función booleana. Los BDD encuentran diversas aplicaciones
en campos como: bases de datos [Han77]. reconocimiento de patrones [Be178], identificación
y taxonomía, diagnóstico de máquinas (Cha7Ol y aplicaciones de algoritmos DR/ei77]. La
amplia variedad de aplicaciones, hacen que los BDD sean utilizados en campos como la
biología, ciencia computacional, teoría de la información y teoría de la conmutación.
Cada nodo no terminal (dibujado como un círculo en la figura 1.10) tiene dos líneas de decisión. La linea dibujada en negrilla indica cuando el valor de la variable del nodo vale 1 y
la otra línea indica cuando vale cero. Cada nodo terminal (dibujado como un rectángulo en la figura 1.10) contiene el valor de una constante (cero Ó uno). Para una asignación dada de
variables, el valor proporcionado por la función es determinado trazando una trayectoria
desde el nodo superior hacia el nodo terminal, siguiendo los saltos indicados por los valores
a las variables. El valor de la función es entonces dado por el valor del nodo terminal.
29 $%rutador& arreglos em6nónuos utilizando ahontmosgenéttcos
Arreghs cmbnónicos
I I
Figura 1.10.- Árbol binario de decisión de la tabla de verdad de la tabla 1.1
1.4.4 Simplificación de los BDD
Para facilitar la transformación de los árboles binarios de decisión en árboles de
multiplexores, es necesari@ realizar la simplificación de los mismos obteniendo árboles
binarios de decisión ordenados (OBDD). Para llevar a cabo la simplificación, se deben
aplicar las siguientes reglas [OrtOOa]:
9 Remover los nodos terminales duplicados.- Eliminar todos los nodos terminales
repetidos, menos uno a donde se deberán redirigir los demás nodos terminales
eliminados. Ver figura 1 .I la . > Remover los nodos no terminales duplicados.- Si dos nodos no terminales u y v con
var(u)=var(v), tienen lo(u)=lo(v), y hi(u)=hi(v), entonces eliminar uno de los dos nodos
no terminales y redirigir todas las líneas al vértice no eliminado. Ver figura 1.1 1 b. > Remover nodos redundantes.- Si un nodo no terminal v tiene /o(v)=hi(v), entonces
eliminar v. Ver figura 1 .I IC.
El término OBDD se refiere a la máxima reducción del BDD siguiendo las reglas
anteriores.
30 Enrutador de arreghs embriónicos utihando abontmosgenéticos
amealos embnónicos , Y
C,WPÍT#LO I
Y " Y
Figura 1.1 1.- Reducción de un árbol de decisión en OBDD.
1.4.5 Implernentación del OBDD como árbol de multiplexores
Los OBDD pueden ser implementados en hardware como árboles y redes de
multiplexores [Cer79]. En un árbol de multiplexores cada nodo no terminal interno del OBDD
se representa como un multiplexor 2-1 controlado por la variable del nodo y cada nodo
terminal se implementa como una constante (cero ó uno). Ver figura 1.12.
Y I
Figura 1.12.- Arbol de multiplexores del OBDD de la figura 1 .I IC.
La evaluación de una función entonces inicia desde los nodos terminales (constantes) hacia el multiplexor final. Las variables de la función se usan como variables de control, las
cuales seleccionan una trayectoria Única desde la parte superior hasta los nodos terminales
y el valor asignado a los nodos terminales se propaga a lo largo de la trayectoria a la salida del multiplexor final. Ver figura 1.12. Es importante notar que el número de multiplexores
usados en una red es precisamente el número de nodos no terminales.
31 Enrutador& areghs em6riónuos ut ikando a@vitmosgenétuos
MPÍTVLO I JwegIÓs emótiónicos
1.4.6 Enrutado del árbol de multiplexores en el Arreglo Embriónico.
Una vez obtenido el árbol de multiplexores que representa la función, se necesita
trasladar la red de multiplexores a las células del arreglo embriónico, asignando un
multiplexor del árbol a cada célula. La experiencia adquirida en este trabajo ha demostrado
que este es el paso más complicado debido a la conectividad limitada de las células. La
figura 1.13 muestra el enrutado del arreglo de multiplexores de la figura 1.12 sobre un
arreglo embriónico 3x2. Solo se muestra la parte final del enrutado. En la sección 1.5 se
detalla este procedimiento mediante un ejemplo
Y
Fila de repuesto +
A C B
Figura 1.13.- Función implementada en un arreglo embriónico
1.5 Ejemplo: Circuito votador
Este ejemplo es un circuito combinacional que realiza la función de votador. Los
votadores son utilizados en sistemas redundantes tolerantes a fallas para comparar la salida
de los elementos replicados y de esa manera detectar y enmascarar los errores. En general
un votador recibe n entradas y genera una salida. El valor de la salida es verdadera cuando
recibe por los menos L.14 + 1 entradas verdaderas. En un votador de 3 entradas, la salida
es alta o baja si por lo menos dos de las entradas son altas o bajas respectivamente. La tabla 1.2 muestra la tabla de verdad para esta función.
Tabla 1 2 -Tabla de verdad del circuito votador
32 Enrutudorde arregbs em6nónuos utiíazando a!&mtmosgem’tuos
La función lógica reducida es F(A,B,C) = AB + AC + BC. La figura 1.14 muestra el árbol
binario de decisión para este ejemplo, con su respectiva reducción (1.14~).
Y
a) BDD completo a) BDD semireducido a) OBDD final I Figura 1.14.- BDD del circuito votador.
Una vez obtenido el OBDD del circuito votador, es necesario reemplazar cada nodo del
OBDD por un multiplexor 2-1. La figura 1.15 muestra este proceso.
-i;i O B A A B
Figura 1.15.- Implementación en un árbol de multiplexores del circuito votador
La figura 1.16 muestra la asignación de los tres multiplexores que representan el circuito votador dentro de un arreglo embriónico.
I Y I Fila de
repuesto - I A C €3
Figura 1.16.- Circuito votador implementado en un arreglo ernbriónico
33 (Enrutador dé aneghs cmbtióriicos utií&mdo abotitmos genéticos
Cr7PíTLLO I
1.6 Resumen
En este capitulo se desarrolló el tema de los arreglos embriónicos, presentando sus
antecedentes y conceptos básicos que toman de la biología para surgir como línea de
investigación. También se describió la arquitectura utilizada para llevar a cabo la presente
tesis. Se describieron dos tipos de reconfiguración de células de un arreglo ernbriónico en
caso de ocurrir una falla. Se incluyó una sección donde se dió a conocer el procedimiento
necesario para realizar aplicaciones en un arreglo embriónico. Se describió la forma de
utilizar un arreglo embriónico mediante el ejemplo sencillo de un circuito votador.
34 Enrutador de anegfos emórióniros u t i ~ u a d o n ~ o n t m o s genéticos
U P Í r n L O AI
2. ALGORITMOS GENETICOS Y ENRUTADORES
Este capitulo presenta en la sección 2.1 los antecedentes y aplicaciones de los algoritmos genéticos. La secciór? 2.2 describe el funcionamiento general de los algoritmos genéticos así como las partes que constituyen a un algoritmo genético común. La sección 2.3 trata sobre enrutadores, dando a conocer su definición, una clasificación y sus aplicaciones. También muestra un panorama del problema de enrutar dos o más elementos de un sistema que opera en forma conjunta y presenta la propuesta de enrutar a los arreglos embriónicos mediante los algoritmos genéticos.
IF' '11 . 2.1 Introducción
2.1.1 Antecedentes
Durante los Últimos 30 años ha habido un crecimiento en el interés por resolver
problemas utilizando sistemas basados en los principios de la evolución y la herencia. Tales
sistemas mantienen una población de soluciones potenciales a las cuales se les aplica un
proceso de selección basado en la aptitud de los individuos, además de algunos operadores genéticos. Un tipo de estos sistemas lo constituyen las estrategias evolutivas, que son algoritmos que imitan los principios de la evolución natural para solucionar problemas de
optimización [Rec73][Sch81]. La programación evolutiva de Fogel [Fog661 es una técnica de
búsqueda en un espacio de pequeñas máquinas de estado finito. Otro tipo de sistemas
basados en la evolución son los algoritmos genéticos de Holland [Ho192].
En la naturaleza, las estructuras biológicas que son más exitosas en adaptarse al
ambiente, sobreviven y se reproducen en una proporción más alta. Los biólogos interpretan las estructuras que ellos observan como una consecuencia natural de la selección dawiniana operando en un medio ambiente durante Un periodo de tiempo. En la naturaleza,
la creación de una estructura está determinada por meCaniSmOS tales 0~mO la selección
natural y 10s efectos creativos de la recombinación Sexual (Cruza genética) Y mutación. John
Holland, un investigador de la Universidad de Michigan, impresionado Por 10s
descubrimientos de los genetistas desarrolló a finales de los años sesenta una técnica que permitió adaptarlos a una computadora, su sueño era lograr que las computadoras
aprendieran por si mismas.los algoritmos genéticos de Holland son una herramienta muy poderosa de optimización que realiza una búsqueda paralela de soluciones satisfactorias a
un problema dado. Es muy utilizada para resolver problemas cuyo espacio de búsqueda es
muy grande. Son algoritmos muy rápidos y poderosos debido a su capacidad de
procesamiento. La búsqueda paralela que realizan les permite no caer en un rniiximo o
minim0 local, si se está maximizando o minimizando, respectivamente. Es importante mencionar que los algoritmos genéticos son poderosos pero existe una pequeña
probabilidad de no encontiar el máximo o mínimo total buscado [Zbi96].
Los algoritmos genéticos tratan de emular el proceso de selección natural al generar
una población de individuos virtuales representados por bits y someterlos a un medio
ambiente (función de aptitud) durante un periodo de tiempo (ciclos computacionales). La
función de aptitud es básicamente una función matemática que discrimina a aquellos
individuos lejanos a una solución deseada y favorece el crecimiento de aquellos que se encuentran cerca de ella. Los algoritmos genéticos requieren de un enorme poder de
procesamiento, pero pueden suministrar soluciones a problemas que no sabemos como
resolver o no sabemos resolver rápidamente. Los algoritmos genéticos también nos permiten obtener soluciones a problemas que no pueden ser resueltos de manera directa, analítica o
algoritmicamente.
2.1.2 Aplicaciones
Debido a las caracteristicas atractivas que poseen y por su funcionamiento en paralelo, los atgoritmos geneticos están siendo ampliamente utilizados en la solución de problemas de
optimización y búsqueda. Existen diversas aplicaciones prácticas como por ejemplo,
enrutamiento de canales de comunicación o redes [Ahn95, Lie96, Goc96, YouOl],
enrutamiento de componentes electrónicos para el diseño de circuitos impresos [WolSG,
36 Enrutodor ái arrcgbs emónónicos u t i fmndo oí@ntmos genéticos
,Zlgontmosgenéticosy enmtndores
Mil99. Sch9.5, Man97, SinOl], determinación de la ruta más corta [InaOl], solución .de
problemas matemáticos [Zbi96]. solución del problema del agente viajero [Zbi96]. etc.
2.2 Funcionamiento de los Algoritmos Genéticos
La forma de operar de los algoritmos genéticos es mediante la generación aleatoria de
posibles soluciones a un problema determinado (población de individuos virtuales), donde
estas Soluciones son codificadas mediante cadenas de caracteres binarios o decimales,
denominados cromosomas (a este proceso se le conoce como representación del problema).
En la población generada se realiza la evaluación de cada individuo para determinar su
aptitud (capacidad para resolver el problema dado), para posteriormente realizar con esta
evaluación una discriminación a favor de los individuos más aptos. El proceso de selección
se puede realizar de diversas formas, de esta manera se permite la utilización de los
individuos creados, Después de la selección se realiza la reproducción entre los individuos
seleccionados mediante la cruza (apareamiento de dos individuos) y la mutación (cambio de
un caracter aleatorio dentro de un individuo) para producir a la siguiente generación de
individuos virtuales.
Este proceso se lleva a cabo de manera ciclica hasta satisfacer la función de aptitud
requerida, que se encarga de medir el proceso de aproximación a la solución final. La figura
2.1 muestra el funcionamiento básico de un algoritmo genético.
Figura 2.1 .- Funcionamiento básico de un algoritmo genético.
37 Enrutador dé a n e g h embtiónicos utilizando akontmos genéticos
I I Abontmos genéticos y enrutadores
C~PÍTOLO I I
2.2.1 Representación del problema
~~l vez la parte más dificil de todo problema sea su representación en términos de 10s
parametros necesarios para poder solucionarlos mediante 10s algoritmos genéticos. Resulta
indispensable dedicar la suficiente atención para plantear la representación del problema en forma de cromosomas (cadenas de caracteres) de tal forma que dichos cromosomas representen en realidad la solución del problema.
Es neceszrio que los cromosomas definidos representen posibles soluciones ai
problema para poder ser manipulados correctamente por el algoritmo genético. A continuación se presentan tres ejemplos de la representación de cromosomas (individuos virtuales) en forma de cadenas de caracteres:
P En forma binaria: 11001010100111101.
2, En forma decimal: 1233534556958874.
P Combinación de letras y números decimales: 3CD4M5DF6KJ3JKE.
La representación dependerá del tipo de problema a solucionar. Para algunos
problemas será más oportuno y práctico utilizar la primera representación, en otros no tanto.
2.2.2 Evaluación
Consiste en determinar el valor potencial (aptitud) de cada cromosoma generado
aleatoriamente. mediante la función que lo relaciona con el problema a solucionar. Por
ejemplo si se requiere solucionar la ecuación: f(x) = x2 + 2x + 3 = O, entonces cada valor
codificado de x se sustituirá en la función para determinar su valor. En la evaluación se
determina el valor de aptitud de cada cromosoma.
,
2.2.3 Selección
La selección determina a los cromosomas padres que generarán a la siguiente generación de cromosomas. Es de vital importancia determinar el mejor método de selección
de acuerdo con el problema dado. Existen diversas técnicas para realizar la selección de individuos, a continuación se listan las más comunes:
2. Selección por rueda de la ruleta [Go189].- Se calcula la probabilidad de selección
(Ps) de cada cromosoma con respecto al total de cromosomas de la población. Se
obtiene una probabilidad acumulativa (Pa) para cada cromosoma de la siguiente
manera: para el primer cromosoma su Pa es igual a su Ps porque es el primer
3a Enrutador de arreglos em briónicos ufiíizando aboritmosgeiiéticos
cromo~oma Y Para el último cromocoma su Pa es igual a la suma de todas las ps de 10s cromosomas calculados anteriormente. Se genera un número r entre 0 y 1 en forma aleatoria. Se busca un cromosoma i con una Pa tal que r c Pai entonces ese
cromosoma es seleccionado como padre. 3 Selección por torneo [Bli95].- En este tipo de selección se toman a dos cromosomas
de la población en forma aleatoria. Se comparan las aptitudes de los dos
crosomomas y el que resulte tener la mejor aptitud será el cromosoma seleccionado
como padre.
9 Selección por rango [Bak85].- Los cromosomas son tomados proporcionalmente de
acuerdo a su taza de rango proporcionada por la evaluación actual. Este método se
basa en la creencia de que una causa común de la convergencia rápida (prematura)
es la presencia de superindividuos que son mucho mejores que la aptitud promedio
de la problación. Tales superindividuos generan un gran número de descendientes
(hijos) y evitan que otros individuos contribuyan a la formación de descendientes - :. ~ " ~ - para - - . - -_e--. las siguientes generaciones. En pocas generaciones un superindividuo puede no
considerar material cromosómico deseable y aún así causar una convergencia rápida
ai óptimo (pcsiblemente local).
. . . ._ . ,- - -
2.2.4 Función de aptitud
La función de aptitud sirve para medir la aproximación de un cromosoma hacia la
solución del problema planteado. De esta manera la función de aptitud proporciona un indice
de desempeño de la cadena de caracteres. Es importante plantear correctamente la función
de aptitud porque de ella dependerá la convergencia del problema hacia una mejor solución en cada generación.
Satisfacer la función de aptitud puede ser uno de los criterios de paro en el ciclo de
búsqueda de los algoritmos genéticos; al obtener la aptitud requerida por el problema el ciclo
se rompe. Otro criterio de paro puede ser al concluir un número determinado de ciclos en el programa del algoritmo genético. Este trabajo combina los dos criterios de paro antes mencionados.
2.2.5 Cruza
Este operador genético consiste en aparear dos cromosomas seleccionados
(cromosomas padres) a través del intercambio de algunos de sus elementos para generar
dos nuevos cromosomas (cromosomas hijos) de la siguiente generación. A continuación se
~ 39 (Enrutador de arregló5 em6riónuos utilizando al&ontmosgenéLicos
~ ~ o n t m o s g e n é t i c u s y enrutadores iyPíWL0 I I
muestra un ejemplo donde se obtienen dos nuevos cromosomas (A y B') a partir de dos cromosomas padres (A y B):
Padres: A=110010010110 y B=001101011010 Partición: A = 110010010110 y B = 001101 011010 Hijos: A = 110010011010 y B'=001101010110
2.2.6 Mutación
La mutación es otro operador genético, para representaciones binarias consiste en
tomar aleatoriamente un bit de un cromosoma seleccionado y negarlo, es decir, si es 1 convertirlo en O y viceversa. La probabilidad con que se realiza la mutación varía
dependiendo de la aplicación, pero de manera comiin se propone de 0.001 [Paz99]. A continuación se muestra el proceso de mutación:
~~ ~ Antes de la mutación: 11001001001 I.
Después dela-mutación: 11001101001 1. .. i_ ~ ~ .
La mutación es importante ya que permite explorar otras regiones del espacio de búsqueda.
2.3 Enrutadores
2.3.1 Definición de enrutador
Un enrutador es una herramienta que permite conectar diversos puntos (nodos o terminales) entre si, de tal manera que puedan interactuar para poder realizar una actividad,
cumpliendo con los requerimientos de enlace y comunicación planteados [Ron98, Tan97,
Ahn951.
I
Los enrutadores se clasifican principalmente en dos grandes grupos. El primer grupo engloba a los enrutadores comúnmente usados en la Internet, lo forman computadoras
especializadas que mandan mensajes a través de paquetes de datos llamados datagramas a
diferentes puntos del mundo a través de diversas trayectorias de enrutamiento. Este tipo de
enrutador es muy conocido por los expertos en la transmisión de datos a través de redes de computadoras Fan971.
El segundo grupo comprende la aplicación de diversas herramientas de programación
utilizadas para enrutar, entre las cuales podemos mencionar a los algoritmos genéticos.
programación entera, programación evolutiva, recocidos simulados, algoritmos
40 Enrutador de aneglos em6riónuos u t i í u a d o abon'ttnusgenéticos
Abontmosgenétlcos y enrutadores CaPÍWLO Ir
evolucionarios, entre otros. Estas herramientas se utilizan genéricamente en la búsqueda y
optimización de soluciones a problemas tales como: localización de células [Ars96],
enrutamiento de canales íAhn95, Lie96, GOc96, YouOl], procesamiento de señales basados
en circuitos VLSl [Sch95, SinOl], optimización de problemas matemáticos [Zbig6], etc.
2.3.2 El problema de enrutar
La solución al problema de conectar dos nodos tal vez resulte muy trivial, pero a medida
que el número de nodos crece, al igual que la complejidad de su ubicación, el problema se
vuelve mucho más complicado. Por tal motivo se hace necesaria la utilización de
herramientas que faciliten alcanzar el objetivo fijado.
Los problemas de enrutamiento requieren encontrar una trayectoria que satisfaga las
condiciones del problema bajo prueba. Encontrar trayectorias libres de problemas de
enrutamiento en dos dimensiones implica la determinación de una trayectoria en el plano que
optimice un conjunto de criterios.
El problema de conectar un número de puntos es muy común encontrarlo en el diseño
de circuitos VLSI, en problemas de optimización como el del agente viajero [Zbi96] (ver figura
2.2). en la conectividad de células procesadoras, diseño de redes y sistemas de
computadoras, entre otras aplicaciones.
Figura 2.2.- Representación gráfica de la solución del problema del agente viajero.
Diseñar un programa 0 mecanismo que permita resolver el enrutado deseado, necesita
del delicado planteamiento de las condiciones y requerimientos especiales del enrutado
mismo para poder lograr la conectividad.
Una representación correcta del problema es importante Para determinar Y Seleccionar
la herramienta que lo resuelva, porque dependiendo del problema se deberá seleccionar el método más adecuado.
41 Ennitador <ie arregh em6riónuos utilizando al&ontmosgedt¡cos
g&itrnosgenét icosy ennitadores ~ P Í T V L O I I . . .
Una vez que se ha descrito-perfectamente el problema de enrutamiento y se ha
seleccionado el método de solución, se debe realizar la programación de la herramienta. El programa propuesto deberá resolver el problema de enrutamiento de manera efectiva ai
satisfaciendo los requerimientos especiales establecidos.
2.3.3 Enrutamiento usando algoritmos genéticos
En problemas de enrutamiento utilizando algoritmos genéticos cada C~OmO~oma de la
población representa una posible solución al problema. La representación de los
cromosomas como cadena de caracteres debe incluir la información necesaria que permita
manejar adecuadamente los parámetros y condiciones del enrutamiento deseado. La función de aptitud debe estar encaminada hacia la obtención del mejor enrutamiento (ruta más Corta o conexión de todos los elementos) mediante la evaluación de cada cromosoma. La
aplicación del proceso de selección y de los operadores genéticoc (cruza y mutación) a los posibles enrutados hace que la búsqueda de la solución sea más eficiente porque explora en
paralelo diferentes regiones del espacio de búsqueda.
Durante los últimos años los algoritmos genéticos han sido muy utilizados para realizar
búsquedas, optimización y creación de máquinas que puedan aprender. En muchas áreas
resultan muy superiores a las técnicas clásicas de optimización [Goc96].
Los algoritmos genéticos han sido satisfactoriamente aplicados a problemas duros y
recientemente se han usado como herramienta de optimización en el Diseño Asisiido por
Computadora (CAD: Computer Aided Design), en aplicaciones tales como. localización,
generación de patrones de prueba y sintesis lógica. Frecuentemente los algoritmos genéticos se usan en combinación con otras técnicas que explotan el conocimiento de
problemas específicos. Los algoritmos genéticos resultantes son llamados algoritmos genéticos Hibridos (HGA) y sus operadores genéticos (cruza y mutación) son establecidos de acuerdo con las características del problema específico [Goc96].
Los registros de configuración de las células embriónicas presentados en el capítulo 1 forman la memoria del arreglo embriónico. Esta memoria determina el enrutamiento interno y
funcionamiento de cada célula dentro del arreglo. La facilidad de trasladar estos registros de
configuración en cromosomas que representen una solución al problema de enrutamiento de los arreglos embriónicos hace atractivo el uso de los algoritmos genéticos [OrtOOb]. Agregando a lo anterior las eficientes propiedades que poseen los algoritmos genéticos
42 Enrutador de aweglós emónónuos utiEzando ahontmosgenéticos
- _. *...pw
C,wÍWLO Ir Abontmosgenéizcosy enrutadores
descritos en este capitulo se han.elegido para realizar el enrutamiento de los arreglos
embriónicos
2.4 Resumen
Este capitulo fue dedicado a la descripción detallada de los algoritmos genéticos dando
a conocer sus antecedentes, propiedades y aplicaciones. Se describió el funcionamiento
básico de cada elemento de los algoritmos genéticos como son: representación del
problema, evaluación, selección, función de aptitud y los operadores genéticos (cruza y
mutación). Se describió el concepto de enrutador y se planteó la dificultad de enrutar
diversos elementos. Por último se propuso resolver el problema de enrutamiento mediante el
uso de los algoritmos genéticos.
43 Enrutador di arreglos embtiónuos utiíiando al&otitmosgenéticos
- -
cm!ÍmLo III
3. ENRUTADOR PROPUESTO
Este capitulo presenta el desarrollo del algoritmo genético que resuelve el enrutado de los arreglos embriónicos. En la sección 3.2 se describe la representación de la conectividad entre células del arreglo embriónico. En la sección 3.3 se muestra la manera de implementar cada elernentc del algoritmo genético. En el apartado 3.4 se presenta la implementación del algoritmo genético utilizando el lenguaje de programación C.
3.1 Representación de la conectividad entre células del Arreglo Embriónico
Para explicar la representación de la conectividad entre células del arreglo ernbriónico
(AE), se utilizará como ejemplo el circuito votador presentado en el capitulo 2. Su tabla de
verdad se encuentra en la tabla 3.1 y su árbol de multiplexores en la figura 3.1.
Tabla 3.1.- Tabla de
Y I
hc+J o s 1 o s 1
O B A A B 1
Figura 3.1 _- Árbol de
I MUXO I MUXI I MUXZ I
A Y2 O A I Y’
Tabla 3.2.- Entradas fuentes del circuito votador.
verdad del circuito votador.
mult@lexores del votador,
circuito votadar se ha enrutado en un AE de taman0 2x3 (2 filas Y 3 columnas). La
figura 3.2 muestra el enrutado obtenido, del cual se describen los siguientes aspectos:
> Existen dos tipos de conexiones: las que se programan en el registro de configuración, denominadas buses (conexiones con lineas punteadas) y las que no se programan,
llamadas naturales por conectarse sin necesidad de’ser programadas (conexiones con líneas sólidas). Ambos tipos de conexiones no pueden mezclarse, con excepción de la
salida Nout (Salida del elemento de procesamiento).
> Las etiquetas con terminación “OBUS (Output Bus = Bus de salida) indican una salida del enrutador de la célula. La señal que se propaga en cada salida del bus puede
provenir de cuatro fuentes diferentes (las tres entradas que tienen diferente dirección que
la salida y Nout). ver figura 3.3. Estas salidas ”OBUS propagan sus variables hacia sus Células vecinas correspondientes.
Figura 3.2.- Conectividad de un Arreglo Embriónico de tamaño 2x3.
P Las etiquetas con terminación “IBUS (Input Bus = Bus de entrada) indican una entrada
hacia el enrutador de la célula. Estas entradas provienen de las terminales OBUS de las
células vecinas correspondientes.
P La salida Nout puede ser propagada hacia cualquier punto cardinal del enrutador. También se conecta con la entrada natural del sur Sin de la célula vecina del norte.
45 Znmtador dé ancghs em6riónuos utziizando oboritmosgenéticos
Sin se propaga de manera directa hacia las salidas naturales este (Eo) y oeste (WO) de la misma célula. Estas son las conexiones en líneas sólidas de la figura 3.2.
?P Las entradas naturales del este (Ein) y oeste (Win) de una célula provienen de las células vecinas, de las salidas Wo y Eo respectivamente.
D Las variables de entrada para el árbol de multiplexores sólo pueden introducirse en el lado sur del arreglo, a través de las entradas SIB y Sin de cada célula colocada en la fila
inferior del AE.
h Cada célula puede tener diferente enrutado. Existen 256 maneras de enrutado que se
pueden realizar con el enrutador de EIS ya que es programado por los 8 bits menos
significativo del registro de configuración. Cada posibilidad puede habilitar solo cuatro
conexiones para cada enrutado. Existen dos conexiones naturales que no Se Programan:
la entrada de Sin propagada hacia Wo y Eo pero formana parte de la conectividad de la
célula.
Figura 3.3.- Enrutador de €IS de una célula.
La necesidad de representar la conectividad entre células surge del problema de realizar la propagación de las variables de entrada del árbol de multiplexores a través de las
conexiones (enrutado) del AE. De esta manera se podrá efectuar la evaluación de los
enrutados propuestos durante la ejecución del algoritmo genético.
.
La tabla 3.3 contiene la información que describe todas las conexiones posibles dentro
de cada célula. Esta tabla sirve para llevar el control de la propagación de las variables de entrada del árbol de multiplexores del circuito votador de la figura 3.1 (o cualquier otra aplicación) a través de las conexiones válidas de cada célula.
46 Enrutador de anegtós emfiriónicos utilizando n@itmosgenéticos
Tabla 3.3.- Matriz que representa la conectividad del AE de 13 figura 3.2.
La descripción de los elementos de la tabla 3.3 se encuentra a continuación. El AE de la
figura 3.2 se tomará como ejemplo para llenar la matriz:
9 Cada par de columnas contienen la información de la célula referenciada en la parte superior de la matriz.
9 Las etiquetas en negrillas representan las 16 posibles conexiones de entrada-salida del enrutador interno de cada célula. Donde N = norte, S = sur, E = este, W = oeste y No = Nout. Solamente cuatro combinaciones de E/S pueden ser válidas. Si la etiqueta esta
antes del guión es fuente (entrada), si está después es destino (salida).
9 Las siguientes cuatro etiquetas (Sin = Wo = Eo, Ein, Win, Nout) representan las
entradas y salidas naturales de la célula y éstas no se programan.
9 Las Últimas tres etiquetas (Sel, R(l ) y L(0)) hacen referencia a las entradas del
multiplexor principal que se encuentra dentro de cada célula del arreglo.
47 (Enrutodor dé arreglos em6tiónuos utitznndo nhontmos genéticos
- - ~~ . . .1" -
CmíTVLO III Enmtaáorpropuesto
3.2 Llenado de la.matriz de conectividad
3.2.1 Decodificación de los bits correspondientes al enrutador de EIS
Se decodifican los 8 bits menos significativos del registro de configuración (figura 3.4)
que corresponde a los 4 pares de bits que definen la salida de cada multiplexor 4-1 del
enrutador (figura 3.3). La tabla 3.4 muestra las 16 conexiones posibles (etiquetadas en
negrillas) divididas en grupos de cuatro, Se colocará una bandera de "1" para señalar la
conexión que es válida de acuerdo con la decodificación de los bits del enrutador de EIS. I
161514131211109 8 7 6 5 4 3 2 1 O
7 I y y KZ]Ey;F I 1 m i / ' )""'"'"lasentradas del MUX de
EB"Sl:O pmce*amiento
Figura 3.4.- Registro de configuración de una célula embriónica
Tabla 3.4.- Decodificación de los bits correspondientes al enrutador de EIS.
48 Enmtndor de anegCo5 em6nónicos utihando aboritmos genéticos
Enrutndor propuesto CpPíWLO I l l .
En la célula 00, la entrada SIBUS está conectada con la salida NOBUS (S-N = I), la
entrada ElBUS está conectada con la salida SOBUS (E-S = I ) , la entrada WIBUS está conectada con la salida EOBUS (W-E = 1) y la entrada NIBUS está conectada con la salida WOBUS (N-W = 1). Ver las celdas sornbreadas de la tabla 3.4
En la célula 11, la entrada Nout está conectada con la salida NOBUS (No-N = l), la
entrada WIBUS está conectada con la salida SOBUS (W-S = I) , la entrada SIBUS está
conectada con la salida EOBUS (S-E = 1) y la entrada EIBUS está conectada con la salida WOBUS (E-W = 1).
3.2.2 Cargar variables de entrada de la aplicación
Las entradas ai AE sólo se pueden recibir en la fila O a través de las entradas SIB y Sin de cada célula. En la figura 3.2 se observa la colocación de las tres variables de entrada (A, B y C). Se llena la columna de variables en la tabla 3.5 de la siguiente manera: la variable " A se introduce por el SIB de la célula 01, entonces se coloca dicha letra en cada una de las
salidas a donde puede ser direccionada la entrada SIB por el enrutador de E/S (S-N, S-E y s-W)
Tabla 3.5.- Carga de variables de entrada al A€.
49 Enrutador de arregbs einbtióntios utiíuando a~ot i tmos genéticor
Enrutador propuesto MPÍTVLO III
Las.letras cargadas en S-E y S-W de la célula O 1 (casillas sombreadas) pueden ser propagada porque la conexión de esas combinaciones han sido seleccionadas (indicada por el 1 en la casilla de la izquierda). La variable " B se introduce por Sin de la célula 01, y se
propaga automáticamente al Wo y Eo de la misma célula. La variable " C se introduce por la
entrada SIB de la célula 02. A las salidas de los elementos de procesamiento (Nout) se les
carga una etiqueta de identificación xi,j. porque aun no se sabe si proporcionan una salida
útil.
3.2.3 Propagación de las variables
La Propagación de las variables a través de las células del AE se realiza de izquierda a
derecha y de abajo hacia arriba. En el ejemplo de la figura 3.2 la propagación lleva la
siguiente secuencia de células: 00, 01, 02, 10, 11 y 12. La propagación de las señales
consiste en colocar la variable correspondiente en cada casilla habilitada, tomando la
variable de la salida de la célula vecina. Las variables podrán ser propagadas a través de las
conexiones habilitadas con la bandera de "1".
a) Primera propagación:
En la célula 00, la conexión C-N toma su valor de SIB de esta misma célula por
portenecer a la fila O, en este caso debe cont-ner un cero (O) ya que la entrada SIB sirve
para introducir las variables de entrada y por esa entrada no se introduce ninguna variable
(ver figura 3.2). La conexión E-S toma su valor de la salida oeste (WOB) de la célula O1
(casilla sombreada), en este caso le corresponde la letra A. La conexión W-E no está
conectada con ninguna célula por la entrada oeste (WIB), por ese lado solo se introducen
ceros, por lo tanto esa casilla contiene un cero. La conexión N-W toma su valor de la salida
sur (SOB) de la célula 10, como la célula 10 aún no ha sido propagada sus variables
(casillas sombreadas vacias), esta casilla (N-W) queda vacia en esta primera propagación.
Para las entradas naturales: la entrada Sin depende del valor cargado en esa entrada, en
este caso no existe variable de entrada por lo que se coloca un cero. Ein toma su valor de la
salida natural del oeste (Sin=Wo=Eo) de la célula 01, en este caso su valor es la letra B.
Win no tiene conexión con ninguna célula, por lo cual su valor es cero. Ver figura 3.6a. L
En la célula O f . la conexión E-N toma su valor de la salida oeste (WOB) de la célUla 02,
por lo tanto le corresponde la letra C a esta casilla. La conexión N-S toma su valor de la
salida sur (SOB) de la célula 11, como la célula 11 aún no ha sido propagada, esta casilla
permanece vacía. La conexión S-E toma su valor SIB de esta misma célula, en este caso
50 Enrutador de aneglos emónónicos utibando abontmosgeniticos
(Enrutador propuesto ~rPicrriL0 I I I
debe contener la letra A ya que por SIB se introduce la variable A. La conexión S-W toma su
valor de SIB de esta misma célula, en este caso debe contener la-letra A ya que por SIB se introduce la variable A. Para las entradas naturales: la entrada Sin depende del valor cargado en esa entrada, en este caso la variable de entrada es la letra B. Ein toma su valor
de la salida natural del oeste (Sin=Wo=Eo) de la célula 02, por lo tanto SU valor es cero
porque no se introdujo ninguna variable de entrada por ahí. Win toma su valor de la salida
natural del este (Siii=Wo=Eo) de la célula 00, por lo tanto su valor es cero porque no se
introdujo ninguna variable de entrada por Sin. Ver figura 3.6b.
Tabla 3.6.- Propagación parcial de las variables del AE
La propagación de las células restantes se realiza de manera similar a las células O0 y
01. Se puede notar que en una propagación no se puede reafizar el llenado completo de la
tabla con las conexiones de los buses (ver casillas en color gris en la tabla 3.7), porque al
momento de actualizar una célula existen células posteriores que aun no han sido
51 Enrutador de aneglos em6tiónlos u t ibando ahoritmosgenéticos
CaPÍWLO III Enrutadorpropusto
propagadas (Por ejemplo el caso de la célula 00). La tabla 3.7 muestra la propagación de todas las células del AE en una primera pasada,
Tabla 3.7.- Propagación de las variables, primera pasada.
b) Segunda propagación:
En esta segunda propagación solo se buscan las casillas que aún se encuentran vacías.
En la tabla 3.7 se observa que la conexión N-W de la célula O0 está vacia, toma su valor de
la salida sur (SOB) de la célula 10, ahora ya está actualizado esa casilla (cuadro sombreado
de la tabla 3.8), y su valor equivalente es cero. La conexión E-W de la célula 10 también se
encuentra vacía, toma su valor de la salida oeste (WOB) de la célula 11, pero esta casilla de
esta célula se encuentra vacía, entonces no se puede llenar aun esta conexión. La conexión
E-W de la célula 11 se encuentra vacía, toma su valor de la salida oeste V O S ) de la célula 12, en este caso su valor será de cero.
Se puede observar en la tabla 3.8 que en la segunda propagación de las variables de
entrada, solo falta llenar una conexión, por lo cual requerirá una tercera propagación para completar la tabla. El proceso de llenado puede necesitar varias propagaciones para
completar todas las casillas habilitadas. La tabla 3.9 muestra el proceso terminado.
52 Enrutador dé avegbs ern6riónicos utitiando ahontrnosgenéticos
Enrutador propuesto
Tabla 3.8.- Propagación de las variables, segunda pasada.
Tabla 3.9.- Propagación completa de las variables.
53 Enrutador de arreghs em6rióiiicos uti[uanáo aboritmos genéticos
- - ~ . . ~ . .~ ~ . ~ . . . . .~ ~ ~
, #lWY*’
CaPfrnLO III Enrutadorpropuesto
3.2.4 Llenado de las entradas del elemento de procesamiento
Se realiza decodificando ocho de los nueves bits mas significativos del registro de
configuración (figura 3.4). El elemento de procesamiento principal es un multiplexor 2-1,
donde cada una de sus entradas (A0 y AI) es seleccionada de 8 diferentes fuentes y a su
vez la entrada de selección (SO) puede ser seleccionada de cuatro diferentes fuentes (figura
3.5). Se sigue el mismo ejemplo del capitulo para el llenado de la tabla 3.10.
N
WlBUS-
N 0 8 U S C
Ein -
wout . s
US NIBUS CLK I N w t I t I I
I
D E E l S T I I + EOBUS
ENRUTADOR .
f SOBUS I ^.
. Si” I
Figura 3.5.- Elemento de procesamiento.
L2:0/R2:0
Win
(a)
(b)
Tabla 3.10.- Significado de las entradas del registro de configuración
54 Enrutador de arreghs embriónicos utilizando a@oritmosgenéticos
Errrutador propuesto c / z P í m L o I I I
a) Para la célula OO. su registro de configuración es: EBUS R2:O REG L2:O N S E W
( 1 ( 0 ( 1 ( 1 ~ I ~ o ~ 0 / 0 / 0 ~ 0 ~ 0 ( 0 ) 1 / 0 ~ 0 1 0 ( 1 /
Los bits de €BUS indican la seiial que se tomará como entrada de selección (Sei), en este caso tiene el valor binario de " I O y de acuerdo con la tabla 3.10a le corresponde la variable presente en la entrada Ein, entonces de la tabla 3.1 1 se toma el valor de €in ("E) y se carga al campo "Sel" de la célula O0 de la misma tabla. La entrada uno (Right) vale "1 11"
y corresponde al valor de la salida SOB según la tabla 3.10b, por lo tanto el valor de la
entrada uno es "A. La entrada cero (Left) vale "O00 y corresponde al valor la constante cero
(O) según la tabla 3.10b, por lo tanto el valor de la entrada cero es " O . Ver celdas sombreadas de la tabla 3.1 1.
Tabla 3.1 1 .- Llenado de las entradas del elemento de procesamiento.
b) Para la célula O í , su registro de configuración es:
EBUS R2:O REG L2:O N S E W 1 0 1 1 1 0 1 0 1 1 1 o ~ 0 1 0 / 1 ( 0 ~ 1 ~ 0 ( 0 ~ 1 ( 0 ~ 1 ~ 0 ~
La selección (EBUS) vale "01" y le corresponde la variable presente en la entrada EIB, entonces el valor del campo Se1 es la "C". La entrada uno (R) vale "001" y corresponde al
55 Enrutador de arreglós einónónicos utiíizando algon'tmor genéticos
CaPÍlrlLO III Enrutadorproplusto
valor constante uno, por lo tanto el valor de la entrada uno es "1". La entrada cero (L) vale
"001" y corresponde al valor constante uno, por lo tanto el valor de la entrada cero es " O . Ver
celdas sombreadas de la tabla 3.11,
c) Para la célula 02, su registro de configuración es:
EBUS R2:O REG L2:O N S E W I 1 I 1 1 0 1 0 1 1 1 o ~ 1 ~ 1 ~ 1 / 0 / 1 ~ 1 / 0 / 0 ~ 1 ~ 1 ~ 0 ~
La selección (EBUS) vale "1 1" y le corresponde la variable presente en la entrada Win, entonces el valor del campo Se1 es la "B . La entrada uno (R) vale "001" y corresponde al
valor constante uno, por lo tanto el valor de la entrada uno es "1". La entrada cero (L) vale
" 111" y le corresponde la variable presente en la salida SOB, por lo tanto el valor de la
entrada cero es "A. Ver celdas sombreadas de la tabla 3.1 1.
El llenado de la tabla continúa de igual forma para las siguientes células. La tabla 3.1 1
muestra el proceso terminado.
3.2.5 Verificación de las entradas de cada célula
Una vez que se han llenado las entradas del elemento de procesamiento principal de
cada célula, se procede a verificar que las entradas fuentes (las del circuito votador
mostradas en la tabla 3.12) coincidan con las entradas de alguna célula de la tabla 3.1 I.
MUXO M U X I MUX2 mi R 1 Y2 L O A Y1
Tabla 3.12.- Entradas fuentes del árbol de multiplexores del circuito votador.
En la tabla 3.1 1 se observa que las entradas (Sei, R, L) de la célula O0 coinciden con las
entradas (Sei, R, L) del multiplexor O de la tabla 3.12, entonces la salida Nout de la célula O0 se actualiza colocando la etiqueta "yl" (casilla de color gris) en la tabla 3.13. Se actualizan los lugares donde se encontraba la etiqueta anterior de la salida Nout de la célula O0 (casillas sombreadas).
Las entradas (Sei, R, L) de la célula 02 coinciden con las entradas (Sei, R, L) del
multiplexor 1, entonces la salida Nout de la célula 02 se actualiza colocando la etiqueta " y 2
(casilla de color gris) en la tabla 3.13. Se actualizan los lugares donde se encontraba la
etiqueta anterior de la salida Nout de la célula 02.
56 Enrutador de arreghs emóriónuos utiíkando al&ntmorgenéticos
Enrutadorpropuesto Cp?ÍWLO III
Las entradas (Sei. R, L) de la célula 11 coinciden con las entradas (Sei, R, L) del
multiplexor 2, entonces la salida Nout de la célula 11 se actualiza colocando la etiqueta "y"
(casilla de color gris) en la tabla 3.13. Se actualizan los lugares donde se encontraba la
etiqueta anterior de la salida Nout de la célula 11
Con el llenado de la tabla 3.13 se comprueba la efectividad de la matriz de conectividad para controlar la propagación de las variables de entrada a través del A€
Tabla 3.13.- Actualización de las salidas de las células.
3.3 Elementos del Algoritmo Genético Programado (AGP)
En el capitulo 2 se habló acerca de los elementos que componen a un algoritmo genético en general. La manera de implementar cada uno de estos elementos dependerá del problema a resolver, resultando un algoritmo genético particular para cada aplicación. En los
siguientes apartados se presenta la forma en que se desarrollaron los elementos que
conforman el AG que resuelve el problema de enrutado de arreglos embriónicos.
57 Enrutador de a7re5hs em6riónicos utifiando a~on t?nos~ené t i cos
.. .- ~ -.
~~, .-.FdT*;--~' ~
Enrutaáorpropuesto C m Í W L O III
3.3.1 Representación de los cromosomas del AGP
La función y conectividad de cada célula del AE las determina su registro de configuración (figura 3.4). Los 8 bits menos significativos del registro de configuración
corresponden a los bits de selección del enrutador. que determinan las conexiones de los
buses de la célula (ver enrutado de la figura 3.2). En el algoritmo genético desarrollado,
únicamente se toman en cuenta los bits de los registros de configuración relacionados con el
enrutado, es decir, los ocho bits menos significativos del registro de configuración (fig. 3.4).
Estos bits forman lo que en adelante se denominará un semiregistro.
Un cromosorna o individuo de la población del AGP está formado por la
concatenación de los semiregistros de todas las células del arreglo. El número de
semiregistros depende del tamaño del AE, que equivale al número de filas multiplicados por
el número de columnas del AE. Así por ejemplo, para un arreglo de 2x3 células, cada
individuo o cromosoma tendrá 6 semiregistros Ó 48 bits. Para generar una población inicial,
los semiregistros sGn generados aleatoriamente. La figura 3.6 muestra uno de los múltiples
cromosoma posibles para el AE de la figura 3.2
I C: I SMOO I SM07 I SM02 I SM7O I SM77 I SM72 1
I sM02 = I ( SMlO = ~ 0 1 0 ~ 0 ~ 0 / 0 1 0 1 0 / 0 SMll = ~ l ~ l ~ l ~ o ~ l l o ~ o l o SM12 = I o 1 o I o 1 0 . 1 o I o I o I o
Donde: C = cromosoma SM = semiregistro NI, NO = bits de selección para la salida norte SI, SO = bits de selección para la salida sur E l , EO = bits de selección para la salida este
W1. WO = bits de selección Dara la salida oeste
Figura 3.6.- Representación de un cromosoma
3.3.2 Función de aptitud (FA)
La idea principal del enrutamiento es lograr trasladar el árbol de multiplexores (fig. 3.7a)
que describe a la aplicación en un conjunto bidimensional de células embriónicas (fig. 3.7b).
58 Enrutador de arreglos em6rióiiuos utifiznndo a@ontinosgenéticos
Enrutador propuesto CaPiTvLO III
Figura 3.7.- Arbol de multiplexores y acomodo en un A€ del circuito votador.
Cada multiplexor del árbol de multiplexores será acomodado en alguna célula del AE. El objetivo del AGP es lograr acomodar un árbol de multiplexores con todas sus conexiones y valor de sus entradas correspondientes en un espacio determinado de células embriónicas.
Se define la función de aptitud Fa(n) como la sumatoria del número de entradas encontradas de cada multiplexor del árbol:
Donde n = número de multiplexores del árbol objetivo. ei = número entradas encontradas para cada multiplexor
La aptitud objetivo es la que indica cuando un cromosoma resuelve el enrutado, es decir, cuando se han encontrado todas las entradas de !os multiplexores del árbol objetivo en
el arreglo embriónico:
a,, = e,x no
Donde no = número de multiplexores del árbol e, = entradas de cada multiplexor = 3.
La aptitud maxima para el circuito de la figura 3.7 es 9,
Para calcular la aptitud de un individuo de la población se necesita llenar la matriz de
conectividad mediante un cromosoma generado aieatoriamente como se mostró en la sección anterior. Se debe ubicar cada multiplexor del árbol objetivo dentro del arreglo
embriónico, esto no quiere decir que los multiplexores del árbol objetivo deban contener
todas sus entradas correctas en un principio. La función de aptitud entonces se encarga de
calcular el número de entradas encontradas para cada multiplexor ubicado en el arreglo.
59 Enrutadar de aneghs etn6nónicos uttiuandn a!@niniosgenéticns
Enrutador propuesto CAPÍ'LO III
En la tabla 4.14.se muestra una matriz de conectividad parcial donde se ha decodificado
un cromosoma que no resuelve el enrutado. Se observa en la tabla 4.14 que el multiplexor
de la célula O0 contiene dos entradas iguales al multiplexor O de la tabla 3.12 (Sei = B y L = O), pero el multiplexor O se le asigna esa posición por ser el lugar donde tiene un mayor
número de entradas en el arreglo. El multiplexor de la célula 02 contiene dos entradas iguales al multiplexor 1 (Sei = B y L = A). El multiplexor de la célula 11 contiene las tres entradas iguales al multiplexor 2. Sumando las entradas encontradas de cada multiplexor se
obtiene la aptitud de este cromosoma el cual es de 7.
En una primera evaluación de los individuos de la problación (primera generacion) es
dificil encontrar un cromosoma con la aptitud objetivo, por lo que se deberá aplicar los
operadores genéticos (cruza y mutación) para producir nuevos individuos para mejorar la
aptitud real e igualarla a la ideal. La !abla 3.13 muestra la decodificación de un cromosoma
con aptitud 9 que presentado un enrutado para el árbol objetivo,
Tabla 3.14.- Matriz de conectividad parcial de un cromosoma que no resuelve el enrutado
3.3.3 Selección por torneo
La selección es el proceso de determinar a los cromosomas que serán los progenitoies
de los individuos que formarán a la siguiente generación. Se escogió la selección por torneo
porque toma en cuenta a todos los individuos de la población, la cual consiste en escoger
por lo menos dos cromosomas al azar y hacerlos competir de acuerdo a su aptitud, ganando
el cromosoma que tenga la mayor. A continuación se muestra la selección por torneo entre
dos cromocomas.
Si ACl > AC2, entonces: Cs = CI Si ACi > ACl, entonces: Cs = C2 Si ACl = AC2. entonces: Cs = Cl
Donde, AC, = Aptitud del cromosoma 1 AC2 = Aptitud del cromosoma 2 Cl = Cromosoma 1 Cz = Cromosoma 2 Cs = Cromosoma seleccionado (ganador)
60 Enrutador aG arreglós em6riónicos utilizando a@oritmosgenéticos
CaPíWLO 111 Ennitador propuesto
El número de cromosomas tomados al azar que competirán en el torneo (tamaño del torneo) puede ser mayor a dos, esto dará como resultado una convergencia mas rápida (mayor velocidad) al resultado, pero no se asegura una mejor solución [Zbi96].
3.3.4 Cruza
La cruza consiste en combinar dos cromosomas de la población. Como se explicó en la
sección 3.3.1, cada cromosoma está formado por un conjunto de semiregistros. La cruza se realiza a nivel de semiregistros de la siguiente manera: se determina un punto de cruza por
medio de un número aleatorio entre 1 y n-I (n es el número de semiregistros).
Posteriormente se realiza la partición de los cromosomas en el punto determinado para crear
a los nuevos individuos. La cruza se lleva a cabo de acuerdo a una probabilidad de cruza
(Pc): se genera un número aleatorio entre cero y uno, si este número es menor a Pc se
realiza la cruza. La cruza puede tener más de un punto de cruza, esto dará al AGP una
mayor diversidad en la búsqueda de la solución y hará que el AGP pueda llegar al resultado
correcto, aunque se necesitará de un mayor número de generaciones [Zbi96]. En la figura 3.8 se muestra la cruza con dos puntos de cruza.
1 1 C2’: [ SMA 1 SMB I SM3 I SM4 I SME 1 SMF
C2: SMA SME SMC SMD SME SMF
Donde C1, C2 = cromosomas padres Cl ’ , C 2 = cromosomas nijos P1, P2 = puntos de cruza SM (I-€+ SM(A-F) = semiregistros de cada cromosoma
Figura 3.8- Generación de nuevos cromosomas mediante la cruza.
3.3.5 Mutación
Para cromosomas formados por cadenas de bits, la mutación se lleva a cabo a nivel de
bits y consiste en complementar un bit aleatoriamente de la siguiente manera: se genera un
número aleatorio entre 1 y n-1 (n es el número de semiregistros), para determinar el semiregistro que sufrirá la mutación. Después se genera otro número aleatorio entre O y 7 que indica la posición del bit a mutar. La mutación se lleva a cabo de acuerdo a una probabilidad de mutación (Pm), se genera un número aleatorio entre cero y uno, si este
61 Ennitador di arreglos embtiónicos u t i íuado al&oritinosgenéticos
07PÍrnLO III Enrutador propuesto
número es menor a Pm se realiza la mutación. En la figura 3.9 se muestra la mutación de
un bit de un cromosoma.
C: [ SMI I SM2 I SM3 I SM4 I SM5 I SM6 I
Donde C = cromosorna SM2’ = semiregistro 2 mutado bm =bit mutado
Figura 3.9.- Aplicación de la mutación a un cromosoma de la población.
3.4 Implementación del AGP
La figura 3.10 muestra el diagrama de flujo del AGP, en el se presentan los bloques
principales que realiza el programa escrito en lenguaje C. A continuación se presenta una
descripción de cada uno de los bloques que constituyen este programa.
Inicializa variables: Este bloque realiza la inicialización de las variables de entrada que
describen al árbol de multiplexores de la aplicación a enrutar a través de la lectura de tres
archivos de entrada.
a) Archivo en entrada 7 : Por medio de este archivo se le indican al programa los siguientes
parámetros: porcentajes de cruza y mutación, tamaño del arreglo embriónico, numero de multiplexores del árbol, entradas de los multiplexores del árbol y tipo de salida .de los
multiplexores (combinacional o secuenciai). Para poder referenciar un multiplexor del árbol
dentro del AE es necesario otorgarle un número de acuerdo a la posición que guarda dentro
del árbol de multiplexores. La asignación del número se realiza de izquierda a derecha y de
abajo hacia arriba (ver figura 3.7a). El listado 3.1 muestra el archivo de entrada (en letras
negrillas y cursivas) que describe los parámetros del árbol de multiplexores para el circuito votador que utilizará el AGP para realizar el enrutamiento: F1
1 2
Listado 3.1.- Archivo de entrada del AGP
62 Enmtador de anegbs em6nónicos utilkando ahoritmosgeniticos
Enrutador propuesto CaPÍlVLO 111
Carga las variables de entrada a la MC
Inicializa variables
Genera poblacibn inicial *
.......................................
EVALUAR (1)
Inicializa la MC
c. m =números entre O y 1 generados aleatoriamente
e = e + l " = " + l
. I
Calcula la aptilud del cromosoma h i+
63 Enrutador dé atreglós em6tiónicos ut ikando algontmosgenéticos
"LiU111 Enrutaáorpropuestn
El significado de los valores mostrados en el listado 3.1 es el siguiente: > Porcentaje de cruza: 0.8. 9 Porcentaje de mutación: 0.í5. > Número de filas del AE: 2, número de columnas del AE: 2 y número de multiplexores
del árbol: 3. 9 Número de niveles del árbol de multiplexores: 2 y número de multiplexores de cada
nivel: 2 7 '. > Número de multiplexores con salida secuencia1 y posición de los mismos: O '. 9 Número de multiplexores que tiene la función de salida y posición de los mismos
dentro del árbol de multiplexores: 2.. Notas:
1. El número de niveles del árbol de multiplexores se calcula contando los bloques de
muttiplexores en forma vertical desde el multiplexor inferior hasta el multiplexor que tendrá la
función de salida. En caso de haber más de una función de salida, se considerará el árbol
con el mayor número de niveles. Para el circuito votador de la figura 3.7a se tienen dos
niveles, dos rnultiplexores en el nivel uno y un multiplexor en el nivel dos
2. No todos los mutilplexores del árbol utilizarán a su salida el flip-flop de la arquitectura (ver
figura A.4 del apéndice) para retención de su valor. El flip-flop Únicamente se utiliza en
aplicaciones secuenciales o que requieran almacenamiento.
b) Archivo en entrada 2: Este archivo contiene las tres entradas de cada multiplexor del árbol de multiplexores. Estas entradas fuentes serán buscadas por el AGP dentro del arreglo
embirónico una vez que se ha realizado la propagación de las variables de entrada de la
función para determinar el enrutamiento de la aplicación. Las entradas de cada multiplexor
en este archivo siguen el siguiente orden: entrada de selección (sei), entrada uno (l) ,
entrada cero (O). El orden de los multiplexores depende de la numeración asignada para el
enrutamiento. En la figura 3.7a se muestra la numeración del árbol de multiplexores del
circuito votador. Así, para el árbol de multiplexores de la figura 3.7a, el archivo de entrada
debe contener: 'BAOBIACba', donde BAO (sel, 1, O) son las entradas del multiplexor O. B I A las entradas del multiplexor 1 y Cba las entradas del multiplexor 2.
c) Archivo en entrada 3: Este archivo contiene las variables de entrada de la función. Estas variables solo se pueden introducir por las entradas SIB y Sin de cada célula de la fila cero
del arreglo embriónico, como se explicó en la sección 3.2. El arreglo embriónico usado para
enrutar el árbol de multiplexores de la figura 3.7a es de 2x2. La fila cero contiene dos células
por las que se puede introducir las variables de la aplicación. Experimentalmente se logró determinar la asignación de las variables de entrada de la función de la siguiente manera:
'BACA', donde la variable B se introduce por SIB de la celula 00, la A por la entrada Sin de la
64 Enrutador de anegfoos em6nónicos utilizando aljloritmorgenéticor
~ P í ~ L O III Enrutudorpropuesto
célula 00, la C por SIB de la célula O1 y una copia de A por la entrada Sin de la célula 01. La
repetición de las variables de entrada (en este caso de A) le ayudan al AGP a encontrar el
mejor enrutado en menos tiempo.
Genera población inicial: Se generan números aleatorios de 8 bits (0-255) que representan
los ocho bits menos significativo del registro de configuración de una célula. Asi un
cromosoma (un miembro de la población) consiste de "n" números creados aleatoriamente
(semiregistros), donde n es el número de células en el AE. El tamaño de la población (tm) se
tomó experimentalmente de 100 individuos.
EVALUAR (7): Consiste en aplicar la función de aptitud a cada cromosoma de la población
inicial para obtener su aptitud. En este bloque se utiliza la matriz de conectividad (MC)
explicada en la sección 3.2. Se realiza la conectividad entre las células mediante la
decodificación de cada cromosoma en la población y se propagan las variables de entrada
através de la MC. La función de aptitud es la encargada de contar el número de entradas del
árbol de multiplexores dentro del AE, como se explicó en la sección 3.3.2.
Ordena la población inicial: Ordena de mayor a menor a los cromosomas de acuerdo a'su
aptitud. La tabla 3.15 muestra un ejemplo de la población ordenada. En algunos casos,
dependiendo de la complejidad del problema a resolver, los algoritmos genéticos requieren
miles de generaciones para encontrar una solución correcta. Existen dos criterios de paro en
el programa: uno es cuando se han evaluado un número determinado de generaciones y el
otro es hasta que se encuentra el va!or máximo de la función de aptitud del problema
planteado [Zbi96].
Cromosoma 1 Posición 1 Aptitud I
a
Cromosoma3 1 6 I ... ... I
Cromosoma 100 I 3 Tabla 3.15.- Población ordenada de acuerdo con la mejor aptitud.
En la figura 3.10. los bloques que se muestran después de ordenar la población inicial, describen el cuerpo principal del algoritmo genético programado (AGP), el cual
consiste en un ciclo interno que se ejecuta "tm" veces (tm = tamaño de la población). Dentro
del ciclo se realiza lo siguiente: Se seleccionan dos crornosornas padres para producir a dos nuevos individuos. Si un numero aleatorio c (Occ<l) es menor que la probabilidad de cruza
Pc (normalmente de 0.8), se realizará la cruza entre los padres seleccionados. Si otro
65 Enrutador dé urreghs emóriónicos utiíizando a.@itmosgenéiicos
C ~ P Í T L L O III Enmtadorpropwsto
número aleatorio m (O<m<l) es menor que la probabilidad de mutación Pm (elegido
experimentalmente de 0.15), se realizará la mutación de un bit de los padres seleccionados.
Estos dos nuevos cromosomas se evalúan y se insertan en una nueva población. Se cuenta
con un mecanismo que impide que un individuo sea incluido más de una vez en la nueva
población, de esta manera se garantiza que todos los individuos de la nueva población sean diferentes entre sí. AI salir del ciclo, si no se completó la población nueva debido a que se
eliminaron individuos repetidos, se generan los cromosomas faltantes de manera aleatoria.
lmprime resultados: Una vez que se ha cumplido el criterio de paro (número de
generaciones o solución correcta encontrada) , se crea un archivo de salida que contiene el
conjunto de registros de configuración de cada célula que describen a la función dentro del
AE. Este archivo es utilizado para la simulación de la aplicación en Foundation de Xilinx. A
continuación se muestra el listado de este archivo VHDL de salida proporcionado por el
AGP. ~
library EEE; use lEEE.std-logic-ll64.all; entity Mem-votador is
POH f okaux: in SJD-LOGIC; xy: in SJD-LOGlC-VECTOR (7 downto O); conf: out SJDLOGlC-VECTOR (16 downto Oj I ;
end Mem-votador; architecture Mem-votador-arch of Mem-votador is type REG is array (16 downto O) of bit; begin process(okaux,xyj
begin if ( okaux = ' O ' ) then
else conf~="01001000100000000";
case xy is when "00000000"=~conf~= "00010000000011001"; when "00000001 => conf e= "0000100100000001 1 "; when "00010000" => conf <= "00000000011011011"; when "00010001" => conf <= "00010010011101011"; when others => conf e= "01001000100000000";
end case;
end process; end if;
end Mem-votador-arch;
Listado 3.2.- Archivo de salida del AGP.
3.4.1 Ajuste de los parámetros del AGP
a) Porcentajes de cruza y de mutación.- Estos porcentajes representan la probabilidad de
llevar a cabo la cruza y la mutación, respectivamente. Dependen del tipo de problema que se
66 Enrutador de anegbs em6nónuos utifiando ohontmosgenétzcos
MPÍWLO III Enrutador propuesto
necesite resolver. Se ha tomado experimentalmente como porcentaje de cruza "Pc" igual a
0.8 y como porcentaje de mutación igual a 0.15 [Zbi96].
b) iamafio de la población.- El número de cromosomas que forman la población, se eligió de forma experimental. Se propone un tamaño de población de 100 cromosomas para todas las aplicaciones utilizadas [Zbi96].
c) Número de generaciones- El número de generaciones se determinó de forma
experimental. Se inicia tomando un número reducido de generaciones (por ejemplo IOO), y
de acuerdo a la aptitud máxima obtenida en la generación final se incrementa el valor de
este parámetro. AI incrementar el número de generaciones es posible encontrar individuos con mejor aptitud, pero se incrementa el tiempo de procesamiento.
d) Tamaño del A€.- El tamaño inicial del AE es el espacio bidimensional donde se desea
acomodar el árbol de multiplexores. Este tamaño depende de la forma del árbol de
multiplexores y se obtiene de la siguiente manera: el número de niveles del árbol de
multiplexores determina el número filas del AE, y el nivel con más multiplexores determina el
número de columnas del A€. Este tamaño puede ser reducido o aumentado para mejorar el
enrutamiento buscado por el AGP. El tamaño que utiliza el AGP para realizar el enrutamiento
de alguna aplicación no toma en cuenta a las células que servirán como repuestos en caso
de falla en el AE. Como durante la reconfiguración se utiliza la estrategia de eliminación por
filas, las células de repuesto se colocan en la parte superior del arreglo establecido, de esta
manera se puede simular la tolerancia a fallas en Foundation de Xilinx.
3.5 Resumen
En este capitulo se presentó una matriz de conectividad que representa la conexión
entre las células del arreglo embriónico. Esta matriz es utilizada para simular la propagación
de las variables de entrada a través de las conexiones habilitadas por el enrutador de E 6 de cada célula. Se demostró mediante un ejemplo que la matriz de conectividad propuesta es una buena herramienta para solucionar el problema de enrutado entre células de un AE. Se
describieron las partes que constituyen el algoritmo genético programado. Mediante un diagrama de bloques se describió el programa escrito en el lenguaje C que resuelve el enrutado de arreglos Embriónicos. Finalmente se justificó la selección de los valores de los
parámetros usados por el algoritmo genético programado.
67 Ennitador de arregbs em6nónuos u t ihando a~ontmosgenéticos
C m Í C O IV 4. RESULTADOS
Este capitulo presenta el diseño de circuitos digitales para probar el enrutador de arreglos embriónicos descrito en el capítulo 3. Dentro de las aplicaciones que se mostrarán se incluyen circuitos combinacionales y secuenciales que siguen una metodologia de diseno que va desde el planteamiento del problema mediante su tabla de verdad hasta la simulación en la plataforma de foundation de Xilinx.
4.1 Ambiente de desarrollo foundation de xilinx
Xilinx es uno de los líderes en el mercado mundial de dispositivos lógicos programables.
Su ambiente de desarrollo se llama Foundation. Esta herramienta permite realizar el diseño
de circuitos electrónicos para poder encapsularlos en Arreglos de Compuertas Programables
en campo o FPGA (por sus siglas en inglés). Para poder simular algún circuito en
Foundation es necesario proporcionar el diseño del mismo, que puede desarrollarse de tres
maneras: mediante un diagrama esquemático, mediante un archivo escrito en el lenguaje
descriptor de hardware VHDL o mediante diagramas de estados.
El proceso para desarrollar una aplicación es el siguiente:
1 . Introducir el diseño (esquemático, archivo VHDL o diagrama de estados) 2. Sintetizar el diseño del paso 1. 3. Simulación funcional. 4. Implementación para simularlo en tiempo real. 5. Descargar el diseño a un dispositivo lógico programable.
~~~ ~~
La arquitectura de la célula embriónica es la misma para cualquier aplicación. Lo que
hace particular a cada aplicación es el módulo de memoria que va dentro de cada célula
(equivalente al ADN de las células biológicas). Los diseños creados para el sistema
ernbriónico utilizan dos tipos de fuentes: para realizar la arquitectura de la célula se utilizó el editor de esquemáticos de Foundation y para implementar el módulo de memoria se ha utilizado como fuente un archivo VHDL, el cual es generado automáticamente por el
algoritmo genético programado.
El diseño de una aplicación digital basada en los arreglos ernbriónicos implica la
realización de los siguientes pasos:
1. Describir la aplicación mediante una tabla de verdad. 2. Obtener los árboles binarios de decisión ordenados de cada salida de la aplicación. 3. Transportar el árbol binario de decisión ordenado a un árbol de multiplexores. 4. Realizar el enrutamiento del árbol de multiplexores mediante el algoritmo genético
programado en un arreglo embriónico. 5. Comprobar los pasos anteriores mediante la simulación del diseño en Foundation de
Xilinx.
4.2 Reloj de 12 horas
El reloj propuesto se ha diseñado con base a contadores que indican los segundos,
minutos y horas (ver figura 4.1). Los contadores utilizados son: el contador 0-9, el contador
0-5 y el contador 0-1 1. El reloj se construye de la siguiente manera: se coloca un contador de
0-9 para llevar el conteo de las unidades de los segundos, cuando este llega a 9 genera una
señal (DR) que indica el rebose de la cuenta. Esta seiial se utiliza como pulso de reloj para ei
siguiente contador de 0-5 que lleva el conteo de las decenas de segundos. A continuación se
coloca otro contador de 0-9 para el conteo de las unidades de los minutos, después se
coloca otro contador de 0-5 para el conteo de las decenas de los minutos y por último se coloca el contador 0-11 que registra el conteo de las horas. Cuando todos los contadores llegan a su cuenta máxima el reloj se reinicia a cero para comenzar nuevamente la cuenta.
La figura 4.2 'muestra el diagrama a bloques del reloj propuesto. La señal de salida DR
representa el detector de rebose para cada contador.
11:59:59 Figura 4.1.-. Cuenta máxima del reloj de O a 12 horas.
69 Enmtadbrdé alregíos em6nónicos utifizando aboritmos genéticos
Salidas Salidas Salidas Salidas Salidas BCD BCD BCD BCD BCD
Figura 4.2.- Estructura del reloj de O a 12 horas.
Para construir una aplicación basada en los arreglos embriónicos es necesario seguir la
serie de pasos descrita en la sección 4.1. Se presentará a detalle Únicamente el diseño del
contador 0-9, de los demás diseños se mostrarán las partes más relevantes.
4.2.1 Contador 0-9
Este circuito es de tipo secuencia1 y es un contador ciclico de cero a nueve. La tabla 4.1
muestra la tabla de estados que lo describe. El estado actual del contador esta representado
por DCBA (D es el bit más significativo) y el estado siguiente por D'C'B'A'. En la tabla 4.1 se
puede notar la generación de una salida DR para detectar la cuenta máxima del contador y manejar el reioj de la siguiente etapa.
Tabla 4.1 .-Tabla de verdad para el contador 0-9.
La figura 4.3 muestra los OBDD de cada función de .salida del contador 0-9. La figura
4.4a muestra los árboles de multiplexores para cada función de salida del contador 0-9 (la función DR se enrutó por separado, ver figura 4.b). En la figura 4.4a los rectángulos con
etiqueta FF significa la presencia de un flip flop tipo D para retener el valor de salida de la función y actualizarse en cada pulso de reloj.
70 Enrutador de anegbs em6riónicos uti í íando aboritmosgenéticos
Figura 4.3.- OBDD para el contador 0-9.
I DR I.
I a) b)
Figura 4.4.- Arboles de multiplexores del contador 0-9.
El listado 4.1 muestra el archivo de entrada 1 que describe al árbol de multiplexores de
la figura 4.4a para ser enrutado mediante el programa propuesto en el capítulo 3. La
71 Enrutador& arregh em6nónuos utifuando abontmosgenétlcos
c I , w,,. -t..
(57PÍTULO IV Resu~*ldos
~.
explicación del archivo ~ se pLesentó'en-6 sección 3.4. El segundo archivo de entrada contiene las d e s del árbol de multiplexores de la figura 4.4a las cuales son: 'c01c01c01c01kclkal kbckcOkOdnfeoOgnhOnOio0joml'. El tercer archivo de entrada que contiene las variables de entrada es: '0000000000'. La colocación de ceros se debe a que
esta aplicación no contiene variables de entrada y depende de las salidas de la misma
función. por ser de tipo secuencial.
- _-_
4 4 5 4 2 4 2 10 13 14 4 2 I O 13 14
Listado 4.1 .- Archivo de entrada para enrutar el contador 0-9.
Una vez creados los tres archivos de entrada del contador 0-9, se procede a ejecutar el programa del algoritmo genético para que intente enrutar la aplicación. Se ejecuta el
programa un cierto niimero de generaciones. El programa no siempre logra enrutar la
aplicación en una ejecución. La tabla 4.2 muestra los resultados de las corridas del algoritmo
genético para enrutar las aplicaciones descritas en este capitulo.
Tabla 4.2.- Resultados de las corridas del programa del algoritmo genético.
Donde:
a) TIPO: significa si la aplicación es combinacional o secuencial. b). TAMAN0 DEL A€: indican las dimensiones del arreglo embriónico. c) No. DE MUXS.: indica el número de multiplexores del árbol. d) GENERS. TOTALES: indica el #de generaciones del algoritmo genético. e) GEN. MIN.: indica la generación mínima donde se ha encontrado el primer
cromosoma bueno (cromosoma que resuelve el enrutado). f) CROMOS. BUENOS: indica el número de cromosomas buenos cuando se logra
enrutar el problema. g) PROB. DE ENRUTAM.: indica la probabilidad de encontrar soluciones buenas, es
decir. número de soluciones buenas por cada diez corridas.
72 Ennitador de aneglbs ein6nónuos utilizando algontmosgem'ticos
UPÍTLLLO IV Qsuhdos
-- =.<_ ~. El listado 4.2 corresponde al archivo VHDL c read~SI :a l3or i t~o~genét ico .- una - . ~ vez que
ha enrutado el árbol de multiplexores de la figura 4.4a en un arreglo embriónico. El árbol de
multiplexores de la figura 4.4a se enrutó en un arreglo embriónico de 4x5. Contiene todos los registros de configuración de cada célula del arreglo para utilizarlo como memoria de la
'ibrary IEEE; me IEEE.std-Iogic-1164.aII: zntify Mem-counter9 is
Port f okaux: in STD LOGIC: xy: in STD-LO%IC-VÉCTOR (7 downto O); conf: out STD-LOGIC-VECTOR (16 downto O)) ;
end Mem-counted; architecture Mem-counted-arch of Mem-counted is type REG is array (16 downto O) of bit; begin process(okaux,xy) begin i f /okaux= 'O'ithen ion ic= "O~O~~OOO~OOOOOOOO";
else case xy is
when"00000000"=~conf~="01000000101000101"; when "00000001"=>confc= "000000001111001C0": when "00000010"=~confc= "00000100111010011"; when "00000011" => conf<= "00000000111000001": when "00000100"=~confe="00000000010110100"; when "00000101"=~conf~= "10000000100101101"; when "00000110" => confe= "11001011100100001": when '00010000" => conf <= '01110000001110010"; when "00010001"=~confc= "00100000101010101"; when '00010010'=~confC='00100001000100010"; when "00010011'=~conf<='00100000001110001*: when '00010100'=~confe= "00000010000000000", when '00010101'=>confc='00001001110001000"~
when '00100000'=~confc= '00011001000100110'; when "00100001'=~confC='01000101101110010"; when "00100010"=~conf~='00011000001110001"; when "00100011'=~conf~='00000001110000010"; when "00100100"=~confc='00000000000111001"; when "00100101"=~conf~='00000000000110001": when "00100110"=~conf~='00100000111111011"; when "00110000" => confe= "01000101011111010": when when when when when
"00110001"=~confc= "00000000010011010"; "00110010"=~confc= "00011101011110010"; "00110011"=~confc= "00000000001100110"; "00110100"=~confe="00000000000011000"; others => conf e= "01001000100000000";
end case;
end process; end if;
end Mem-counter9-arch;
Listado 4.2.- Archivo VHDL que describe la memoria del reloj de 12 horas
73 Enrutador di a r regh em6nónuos u t ikandó a&itmosgenéticos
, I , . , , , qq l ! :'<,;
KeeSu~ia*idos CaPÍTL!LO IV
La figura 4.5 muestra g/>,resultado de decodificar en forma manual los registros de
configuración para el enrutamiento del contador 0-9 realizado por el algoritmo genético en un
arreglo embriónico de 4x5.
. ~ ~ ..< I L ..
O O O O O O O O O O
Figura 4.5.- Enrutamiento del contador 0-9.
La figura 4.6 muestra la simulación del contador 0-9 donde no existen células erróneas. Se puede observar que el conteo se realiza de forma correcta y al llegar a 9 se produce un
cambio de alto a bajo en la señal DR que se utiliza como pulso de reloj para el contador siguiente.
L R I , , , , , , , . FO LKI,. , , , , , , BO
. . . . , . . . . .
BB . . . . . . . .
Figura 4.6.- Simulación del contador 0-9 con todas las células en buen estado.
74 Enmiador dé arregbs embnónuos utilizando aGontmosgenéticos
Las variables mostradas en la figura 4.6 son las siguientes:
9 9 9 9 9
9 >
CLRI.- Inicializa las células que utilizan salida secuencial. CLKI.- Proporciona el pulso de reloj para las células con salida secuencial.
DR.- Detector de rebose para indicar la cuenta máxima del contador. OKAA y 0KBB.- Utilizados para simular un error en la célula AA o BB respectivamente. XOEA. (hex)#5.- Coordenada X que proporciona la última célula. EIBUCAH. (hex).- Las entradas del arreglo embriónico por las que no se introducen variables de entrada se ajustan a ceros.
A ... (hex)&% Salidas de contador (DCBA).
La figura 4.7 muestra un error provocado en la célula AA cuando el contador está en la cuenta de 7. Este error se provoca colocando la entrada O W en bajo. Después de un
tiempo corto de establecimiento de las señales de salida del contador (provocado por la
reconfiguración de las células) el contador sigue funcionando correctamente.
CLRI CLKI. A ( hex ) #4 DR . . OKAA. . . . . . . . OKBB, . . . . . . . I
Figura 4.7.- Simulación del contador 0-9 con una fila dariada.
4.2.2 Contador 0-5
El contador 0-5 forma parte del reloj propuesto. Utiliza para su cuenta binaria 3 bits
representados por las letras CBA. Cuenta con su detector de rebose (DR) que indica la
cuenta máxima del contador. La tabla 4.3 muestra su tabla de verdad.
Tabla 4.3.- Tabla de verdad para el contador 0-5.
75 <Enrutador de arregibos em6nónicos utiluanáo a/&titmoosgem'ticos
.I *'1 , I W.-W -r CWÍTVLO rv %guítados
La figura 4 8 muestra el árbol de multiplexores para el contador 0-5 El listado 4 3
muestra el archivo de entrada necesario para enrutar el contador sobre un arreglo
embriónico,
A
B 1
O B A 1 A O 1 A O 1 A O 1 A O
3 5 3 2
4 2 5 8 9
Listado 4.3.- Archivo de
entrada para enrutar el
contador 0-5.
Figura 4.8.- Árboles de multiplexores del contador 0-5
La figura 4.9 muestra el resultado de decodificar los registros de configuración para el
enrutamiento del contador 0-5 realizado por el algoritmo genético en un arreglo embriónico
de 3x5.
I
Figura 4.9.- Enrutamiento del contador 0-5.
76 Enmtador de arreglós em6nónuos uti&ando ahoritmosgetléticos
La figura 4.10 muestra la simulación del contador 0-5. Las salidas CBA están agrupadas
en la etiqueta A. Durante la simulación se provocó un error en la célula BB colocando la señal OKBB en bajo como se muestra la figura 4.10.
. . . . , . . .
. , . . . . . .
. . . . . . . . . .
. . . . . . . .
Figura 4.10.- Simulación del contador 0-5
4.2.3 Contador 0-1 1
Este contador 0-11 también forma parte del reloj propuesto. Utiliza para su cuenta
binaria 5 bits representados por las letras EDCBA. Cuenta con su detector de rebose (DR)
que indica la cuenta máxima del contador. La tabla 4.4 muestra su tabla de verdad.
La figura 4.11 muestra los árboies de multiplexores para el contador 0-11. El enrutamiento de esta aplicación se realizó en dos partes (figura 4.11a y 4.11b), pero se
juntaron los dos archivos VHDL proporcionados por el AGP para su simulación en
Foundation de Xilinx.. Los listados 4.4a y 4.4b muestran los archivos de entrada para enrutar las dos partes de esta aplicacibn en un arreglo embriónico.
77 Enrutador de anegbs em6riónicos utiíuando a/Boritmos genéticos
* c
A B
out 3 5 1
1 A O I A O O D A 1 A O 1 A O
C
b)
1 A O
I 1 A O O B A
0.8 0.15 4 4 11 5 2 4 2 2 1 2 9 10 2 9 10
O. 8 0.15 4 4 10 4 5 3 1 1 3 6 7 9 4 1 6 7 9
b)
Listado 4.4.- Archivos de entrada
para enrutar el contador 0-1 1.
Figura 4.1 1.- Árboles de multiplexores del contador 0-1 1
La figura 4.12 y 4.13 muestran la decodificación de los registros de configuración
para el enrutamiento de las funciones de salida de la figura 4.1 l a y 4.1 1 b respectivamente
del contador 0-1 1 realizado por el algoritmo genético en un arreglo embrionico de 4x4 cada
uno.
7a Enrutador de anegbs em6nónuos utiluatdo abontmos genéticos
n
;..,*" : c . , .'\ .! . .
CaPÍrnLO I z , @pdtados
. La figura 4.14 muestra la simulación del contador 0-11. La salidas están agrupadas en 2 conjuntos. Los cuatro bits menos significativos (DCBA) representan las unidades para este contador. La salida E es el encargado de contar las decenas del contador. Cuando el
contador llega a 11 la salida DR genera la señal de rebose. En el siguiente ciclo de reloj se ha producido un error en la célula AA al poner en bajo la señal O W . Después de un
Pequeño tiempo de estabilización de las señales, el contador sigue funcionando.
. . . . . . . . . . . . . . .
E . . . . . . . . . . . DR . . . . . . . . . . OKAA . . . . . . . .
Figura 4.14.- Simulación del contador 0-1 1.
4.3 Otras aplicaciones
4.3.1 Contador ascendenteldescendente de 2 bits
Este contador es el Último circuito secuencia1 diseñado. Utiliza para su cuenta binaria 2 bits representados por las letras BA. La cuenta la realiza de la siguiente manera: cuando la
variable de control C vale uno la cuenta es de forma ascendente (O a 3) y para cuando c vale cero la cuenta es de forma descendente (3 a O). La tabla 4.5 muestra SU tabla de verdad. La figura 4.15 muestra los árboles. de multipiexores Para las Salidas de este
contador.
out f o r 1
1 A O 1 8 0
Tabla 4.5.- Tabla de verdad para el contador ascendente/descendente de 2 bits.
El listado 4.5 presenta el archivo de entrada para realizar el enrutamiento del contador
Figura 4.15.- Arboles de multiplexores del contador ascendenteldescendente de 2 bits.
en un arreglo embriónico.
80 Enrutador dé arreghs em6nóntcos ut ihando a~ontmosgem'tzos
C a P i W L O IV Kesuítaáos FI Listado 4.5.- Archivo de entrada para enrutar el
contador 5 2 4 2 2 1 ascendenteldescendente 2 9 10
de 2 bits.
La figura 4.16 muestra el resultado de decodificar los registros de configuración para el
enrutamiento del contador ascendenteldescendente de 2 bits realizado por el algoritmo genético en un arreglo embriónico de 3x3.
o O o 0 C O
Figura 4.16.- Enrutamiento del contador ascendenteldescendente de 2 bits.
Figura 4.17.- Simulación del contador ascendenteldescendente de 2 bits.
La figura 4.17 muestra la simulación del contador ascendenteldescendente de 2 bits. La salidas B' A' se encuentran agrupadas en Y. La variable de control C determina si la cuenta
es de manera ascendente (C = 1) o de manera descendente (C = O). Durante la simulación
se provocaron dos errores en filas diferentes (célula AA y célula BB). AI dañar dos filas del arreglo embriónico se hizo necesario el uso de dos filas con células de repuestos contenidas
dentro del mismo arreglo.
a i !Enrutador& aneglós em6riánicos utilizando a&itmosgcnéticos
4.3.2 Circuito votador de 3 bits
Este ejemplo es un circuito combinacional que realiza la función de votador. Los votadores son utilizados en sistemas redundantes tolerantes a fallas para comparar la salida
de los elementos replicados y de esa manera detectar y enmascarar los errores. Un circuito
votador recibe n entradas y genera una salida. El valor de la salida es verdadera cuando
recibe por lo menos L./d + 1 entradas verdaderas. En un circuito votador de 3 entradas, la
salida es alta o baja si por lo menos dos de las entradas son altas o bajas respectivamente.
La tabla 4.6 muestra su tabla de verdad. La figura 4.18 muestra el árbol de multiplexores que
describe la función del votador de 3 bits. El listado 4.6 presenta el archivo de entrada para
realizar el enrutamiento del votador en un arreglo embriónico
O. 8 0.15 2 2 3 2 2 1 o 1 2
Listado 4.6.- Archivo de entrada para enrutar el
circuito votador de 3 bits. Tabla 4.6.- Tabla de verdad Para el circuito votador de
Figura 4.1 8.- h b o l de multiplexores del circuito votador
bits. de 3 bits.
La figura 4.19 muestra el resultado de decodificar los registros de configuración para
enrutamiento del circuito votador de 3 bits realizado por el algor¡tmo genetic0 en un arreglo embriónico de 2x2.
I A C A
Figura 4.19.- Enrutamiento del circuito votador de 3 bits.
82 Enrutador di aneglos embtiónuos utilizando al&otitmosgenéticos
c,wPiTvLO I?, surto todos
La figura 4.20 muestra la simulación del circuito votador. Las entradas C, B y A no se
encuentran agrupadas en esta ocasión para ver el valor de cada una de ellas. Se provocó un
error en la célula AA haciendo uso de una fila de repuesto del arreglo embriónico para que siguiera trabajando correctamente el votador como se muestra en la figura 4.20.
Figura 4.20.- Simulación del circuito votador de 3 bits
4.3.3 Sumador paralelo de 2 bits
Este circuito realiza la suma de dos números binarios de dos bits. Los números binarios
están representados por DC y BA, de donde D y B son los bits más significativos de cada
número. La salida XYZ contiene el resultado de la suma de los dos números binarios. La
tabla 4.7 muestra su tabla de verdad. La figura 4.21 muestra los árboles de multiplexores de las salidas del sumador.
Tabla 4.7.- Tabla de verdad para el sumador
paralelo de 2 bits.
out o 2 o * t
I A O
A out 14
< B O
t A O i A O
out 10
o c B C
O B & A 8 1
Figura 4.21.- Arboles de multiplexores del sumador paralelo de 2 bits.
El listado 4.7 muestra el archivo de entrada para enrutar.el sumador en un arreglo embriónico.
83 Enrutador dé a n e g h etn6riánuos utifiandá a&xitmosgenéticos
Listado 4.7.- Archivo de I 40.': 15 entrada para enrutar el 4 5 6 3 1
sumador paralelo de 2 bits.
Figura 4.22.- Enrutamiento del sumador paralelo de 2 bits.
La figura 4.23 muestra la simulación sumador paralelo de dos bits. En la figura 4.23 los numéros binarios (DC) y (BA) están agrupados en C y A respectivamente. Las salidas XYZ
estan agrupadas en Z. Se provocó durante la simulación un error en la célula AA. Se puede notar en la figura 4.23, que la reconfiguración de las células al presentarse un error no requirió un tiempo tan largo como en las aplicaciones secuenciales.
Figura 4.23.- Simulación del sumador paralelo de 2 bits.
84 Enrutador& avegbs em6Mnicos utilizado nlgontmosgenétzcos
~esufiados ( yPÍTUL0 rv
4.3.4 Generador de Redundancia Cíclica de 4 bits (CRC-4)
L~~ errores son algo natural dentro de las comunicaciones de datos. Es Posible
desarrollar metodologíaa de transmisión de datos que proporcionen Un alto rendimiento de
detección y corrección de errores. Algunos métodos comunes para la detección de errores son: la prueba de paridad, claves de relación constante y verificación por redundancia CiCliCa
[Ha192, MorOO]. Estos métodos son muy utilizados en la comunicación de datos para reducir los errores en la trasmisión de datos. La Verificación por Redundancia Cíclica (CRC: cyclic
redundancy check) trabaja de la siguiente manera: por cada trama (cadena de caracteres)
transmitida se genera un conjunto único de dígitos de verificación, con base en el contenido
de la trama, y se añaden al final de la trama para su transmisión. El receptor a su vez, realiza un cálculo similar con la trama completa y los dígitos de verificación. Si no se han inducido
errores, siempre se obtendrá un resultado conocido; si se obtiene una respuesta distinta, se
habrá detectado un error. [Ha192, MorOO].
El CRC-4 diseñado en esta sección genera un código de redundancia ciciica de una trama de cuatro bits para la detección de errores. La tabla 4.8 muestra la tabla de verdad del
CRC-4. El listado 4.8 muestra el archivo de entrada para enrutar el CRC-4 en un arreglo embriónico.
0.8 o. 15 2 6 10 3 4 5 1 O 4 4 5 8 9
Listado 4.8.- Archivo de entrada para enrutar el CRC-4.
Tabla 4.8.- Tabla de verdad del CRC-4.
La figura 4.24 muestra los árboles de multiplexores para cada salida de esta aplicación
85 ‘Enrutadordé aneghs embnónuos utikanáo aí&vitmosgenéiicos
.. ! . .
I I
Figura 4.25.- Enrutarniento del CRC-4.
La figura 4.26 muestra la simulación del circuito CRC-4. En la figura 4.26 las entradas
(DCBA) se encuentran agrupadas en A. Las salidas X, Y, Z, y W no están agrupadas para
notar el valor de cada una de ellas. Se provocó un error en la célula AA para verificar la
propiedad de tolerancia a fallas de la aplicación en el arreglo embriónico.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 4.26.- Simulación del CRC-4
86 ‘Enrutodor& a n e g h em6nónicos utilizando a~ontmosgenéticos
4.3.5 Generador de paridad par de 4 bits
Este circuito combinacional genera el bit de paridad par de un número de cuatro bits utilizados en la transmisión de datos [Ha192]. De forma general la paridad par se calcula contando en cada número de n bits los unos que contenga. Si la cuenta de estos unos es impar el circuito deberá generar un uno, pero si la cuenta es par el circuito deberá generar un cero. La tabla 4.9 muestra su tabla de verdad, La figura 4.27 muestra el árbol de
multiplexores del generador de paridad par de 4 bits.
Tabla 4.9.- Tabla de verdad del generador de
paridad par de 4 bits. Figura 4.27.- Arbol de multiplexores del generador de paridad par
de 4 bits.
El listado 4.9 muestra el archivo de entrada para enrutar el generador de paridad par de
4 bits en un arreglo embriónico.
Listado 4.9.- Archivo de entrada para enrutar el generador de paridad
par de 4 bits. 4 8 4 2 1 L J 1 14
La figura 4.28 muestra el resultado de decodificar los registros de configuración para el enrutamiento del generador de paridad par de 4 bits realizado por el algoritmo genético en un arreglo embriónico de 4x8.
87 Enrutodoráe aneg(o5 emóriónicos utiíizando algoritmos genéticos
Figura 4.28.- Enrutamiento del generador de paridad par de 4 bits
La figura 4.29 muestra la simulación del generador de paridad par de 4 bits. Se provocó
un error en la célula AA y el circuito siguió trabajando correctamente
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . KAA . . . . . . . .
Figura 4.29.- Simulación del generador de paridad par de 4 bits.
4.3.6 Generador de paridad par de 5 bits
Este circuito genera el bit de paridad par de un número de cinco bits utilizados en la transmisión de datos [Ha192]. La tabla 4.10 muestra su tabla de verdad. La figura 4.30
muestra su árbol de multiplexores. El listado 4.10 muestra el archivo de entrada para enrutar el generador de paridad par de 5 bits en un arreglo embriónico.
88 Enrutador di anegbs embnónuos uhíkando a&ontmosgenéticos
~
Tabla 4.10.- Tabla de verdad del generador de paridad par de 5 bits
out 10
out o out 7 ww O A l I A O
,$$) 1 A O O A I
Figura 4.30.- Arbol de multiplexores del generador de paridad par de 5 bits.
O. 8 O. 15 5 6 I1 5 4 2 2 2 1 O I I O
I I Listado 4.10.- Archivo de entrada para enrutar el
generador de paridad par de 5 bits.
La figura 4.31 muestra el resultado de decodificar los registros de configuración para el enrutamiento del generador de paridad par de 5 bits realizado por el algoritmo genético en un
arreglo embriónico de 5x6.
89 (Enrutador dé arrcgíñs cmbnónicos utiliiandá a@ontrnosgcnéticos
Figura 4.31.- Enrutamiento del generador de paridad de 5 bits.
La figura 4.32 muestra la simulación del generador de paridad de 5 bits. Se provocó un
error en la célula AA y el generador siguió trabajando correctamente.
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Figura 4. 32.- Simulación del generador de paridad par de 5 bits
90 Enmtador de aneghs emóriónicos utilizando algoritmosgenéticos
4.4 Resumen
En este capítulo se presentó el diseño de circuitos digitales que fueron utilizados para
comprobar la eficacia del enrutador. de arreglos Embriónicos desarrollado en esta tesis. Nueve fueron los circuitos diseñados presentados en este capítulo de resultados.
Únicamente el contador de cero a nueve fue presentado en detalle. En el apéndice al final de este documento se presentan los diagramas esquemáticos de la célula embriónica utilizada
para realizar la simulación en la plataforma Foundation de Xilinx. Para la simulación de los ejemplos se necesitó de un arreglo bidimensional de células embriónicas con filas de
repuesto que se convirtieron en filas activas cuando se simuló una falla en una célula.
Enmtodordé aneghs emónóniros utifuando ahontmosgenéticos 91
Conclusiones Esta tesis presentó una nueva estrategia para resolver el problema de enrutamiento de
arreglos embriónicos. LOS arreglos embriónicos, junto con los algoritmos genéticos, forman parte de los sistemas bioinspirados al tomar los conceptos básicos de la biología como son:
evolución natural, adaptación y reproducción de las especies sobre un medio ambiente. La
hipótesis de la tesis ha sido probada a lo largo de este trabajo: Es posible r, -solver el
enrutado de un arreglo embriónico utilizando un algoritmo genético.
Los conceptos tomados de la embriología aplicados a los sistemas electrónicos dan una
nueva temática llamada arreglos embriónicos. La incorporación de las propiedades de
tolerancia a fallas en una arquitectura celular hacen aún rnás atractivo a este campo de
investigación.
Para implementar una aplicación en los arreglos enibriónicos es necesario obtener los
siguientes elementos: tabla de verdad, árbol de decisión binaria ordenados, árbol de
multiplexores, trasladar el árbol de multiplexores en un arreglo embriónico.
Según la arquitectura del sistema embriónico usado [OrtOOa], la conectividad limitada
entre las células del arreglo hace que a medida que crece la complejidad de la aplicación, se
vuelva rnás complicado el enrutamiento del diseño en un arreglo embriónico en forma
manual. Por tal motivo se propuso en este trabajo un enrutador automático para los arreglos
embriónicos utilizando los algoritmos genéticos.
La estrategia de la eliminación de una fila, cuando se daria una célula, fué elegida por
ser muy práctica su realización a través de la generación de las nuevas coordenadas del
arreglo y permitir con esto la reducción del uso de recursos en la implementación final de la aplicación en los arreglos lógicos programables (FPGA).
Parte importante resultó el uso de los árboles binarios de decisión ordenados, formados
a partir de la tabla de verdad de la función, porque permitió un traslado muy fácil hacia los árboles de multiplexores que describen a la aplicación. La facilidad estriba en que los árboles binarios de decisión ordenados son muy parecidos en su forma estructural a los árboles de multiplexores.
Coiicíiiiones
A través de la de diversos ejemplos y de la ejecución de un cierto número de
corridas del algoritmo genético programado, se encontró que el ajuste adecuado de 10s valoreS de los operadores genéticos, como la cruza y la mutación, permiten otra orientación
para la búsqueda de la solución.
La selección por torneo es muy sencilla de implementar y capacidad Para utilizar a toda la población de individuos, le permite realizar una mejor Selección obteniendo al
individuo con la mejor aptitud, provocando con esto que el algoritmo genético evolucione hacia una mejor solución a través de las generaciones.
El número de generaciones usado por el algoritmo genético programado para enrutar cada aplicación, fue tomado experimentalmente a través de diversas corridas, observando la
aptitud final del mejor individuo en cada ejecución del programa. Las aplicaciones con mayor
número de multiplexores necesitaron un mayor número de generaciones para lograr ‘el
enrutamiento de los mismos.
El enrutador automático desarrollado es capaz de enrutar aplicaciones de tipo combinacional y secuencia1 de una forma efectiva, práctica y considerablemente rápida con
respecto al enrutamiento en forma manual.
El arreglo embriónico donde el algoritmo genético realiza el enrutamiento de la función
puede ser de tamaño variable, es decir, se programó de manera general para poder utilizar cualquier dimensión del arreglo embriónico con tan solo modificar el número de filas y columnas del mismo.
Una de las principales características de la embriónica, es la aplicación de la tolerancia a fallas a los sistemas evolutivos para su mejor desempeño ante condiciones desfavorables
en el funcionamiento del sistema. Esto implica la adición de células de repuesto al arreglo
embriónico para ser utilizadas cuando una célula esté dañada. AI llevar a cabo las simulaciones de diversas aplicaciones en los arreglos embriónicos. mostradas en el capítulo
IV de resultados, se pudo comprobar que después de la reconfiguración de las células, al
presentarse una falla en una célula, el sistema seguió trabajando perfectamente dando los valores de salida correctos. Con todo esto se pudo observar el manejo de la tolerancia a
fallas aplicado a los arreglos ernbriónicos.
€1 algoritmo genético que resuelve el enrutamiento de los arreglos embnónicos fue programado en el lenguaje de programación C. El programa necesita de tres archivos de entrada que describan las características del árbol de multiplexores de la aplicación y
93
proporciona un archivo VHDL de salida que contiene los registros de configuración de las
células del arreglo. Este archivo VHDL es utilizado para la simulación en Foundation de
Xilinx.
Para simular una aplicación es necesario un arreglo bidimensional de células
embriónicas con un cierto número de células de repuesto para proporcionar la propiedad de
tolerancia a fallas de estos sistemas embnónicos. La arquitectura celular implementada se
muestra en el apéndice de este trabajo.
El futuro de la ernbriónica
Tal vez en los próximos años seamos testigos de la aplicación de nuevos sistemas que
puedan tomar decisiones a través del aprendizaje del medio ambiente en que se desarrollan.
La elaboración de nuevas máquinas con cierta inteligencia que puedan soportar cambios
bruscos de su entorno y poder desarrollarse a pesar de tener diversos factores en contra.
La embriónica no estará alejada de todos estos nuevos avances tecnológicos y seguirá
tomando cada día mas fuerza inspirándose en los sistemas biológicos. La perfección de la
naturaleza siempre será tomada como ejemplo para sistemas prácticos diseñados por el
hombre.
La capacidad de iutoreparación, autoreprcduccion y autoconfiguración de los sistemas
embriónicos, serán motivos de nuevos intentos por lograr una mejor aplicabilidad hacia los sistemas de alta disponibilidad.
Aportaciones
La aportación más importante obtenida en el presente trabajo es una nueva estrategia
para resolver el problema de enrutamiento de los arreglos embriónicos de tamaño variable.
La conectividad limitada que existe entre las células se hace más evidente a medida que crece la complejidad de la aplicación. Resolver el enrutamiento de manera manual se vuelve un proceso lento, tedioso y con posibles errores humanos. Ante todo esto, se propone un enrutador automático basado en los algoritmos genéticos.
La inclusión de una matriz de conectividad entre las células, permite simular la
propagación de las variables de entrada a través del arreglo embriónico. La flexibilidad de la
matriz permite simular la propagación de las variables para cualquier tamaño de arreglo, tan
94
~oidusioner
solo agregando columnas a la derechz de la matriz de acuerdo Con el m h e r o de células del
arreglo embriónico.
propiedades como: velocidad, búsqueda paralela, robustez Y la alta probabilidad de
encontrar la solución esperada, hacen muy atractivo el USO de (OS algoritmos genéticos a
problemas de enrutamiento. La representación de los registros de configuración del arreglo
embriónico en forma de cromosomas permitió el uso adecuado de los algoritmos genéticos en la resolución del problema.
El enrutador automático desarrollado permite el enrutamiento de aplicaciones de tipo
combinacional y secuencia! de una forma rápida, efectiva, y fácil de usar. La facilidad del uso
del enrutador automático va encaminada en que a partir del árbol de multiplexores de la
aplicación solo se necesitan tres archivos pequeños de entrada para poder realizar el enrutamiento. Utilizando esta herramienta se evitan los posibles errores humanos al eñ-nitar
una aplicación en forma manual.
El algoritmo genético desarrollado proporciona una gran número de soluciones de
enrutado (un promedio de 80 cromosomas útiles de una población de 100 individuos). Con
esta redundancia en las soluciones deseadas se puede cubrir aún mejor la propiedad de
tolerancia a fallas en una arquitectura celular, al poder implementar más de una solución de
enrutamiento para el arreglo embriónico en caso de que una solución deseada falle.
Trabajos futuros
El objetivo general de este trabajo fue lograr el enrutamiento de los arreglos embriónicos
mediante el uso de los algoritmos genéticos. Este objetivo se cumplió y se pudo resolver el
problema encontrando un gran número de soluciones diferentes deseadas, Uno de los trabajos futuros que le pueden dar continuidad al presente es el realizar un análisis de las soluciones deseadas y encontrar la solución óptima.
La optirnización del problema puede ir encaminada a encontrar un enrutamiento que
permita un mejor acomodo de los multiplexores del Brbol en el arreglo. Este acomodo puede
ser utilizando un menor número de filas en el arreglo embriónico, para así dejar un mayor
número de filas de repuestos para cuando falle una célula.
Realizar una interfaz gráfica a través de un lenguaje de programación que permita mostrar de manera automática los resultados del enrutamiento encontrado por el algoritmo
95
Conclusiones
genético, donde se presente la ubicación de los multiplexores con sus entradas correctas en las células asignadas.
Otro cuestionamiento por resolver en un futuro es de qué forma afecta la numeración
inicial del árbol de multiplexores para su enrutamiento. En algunos ejemplos mostrados se
presentan más de una función de salida, por lo que se complica la introducción de las
variables de entrada, y surje una pregunta ‘cúal será el mejor acomodo de las variables de
entradas para introducirlas al árbol?.
El empleo de los algoritmos genéticos para resolver el problema del enrutamiento de los arreglos embriónicos resultó ser muy efectivo, pero aun existen otros mecanismos que
posiblemente puedan resolver el mismo problema, estas herramientas son: algoritmos
evolucionarios, recocidos simulados, lógica difusa, redes neuronales, etc.
AI poder resolver el problema de enrutamiento de los arreglos embriónicos mediante
alguno o algunos de los mecanismos antes mencionados, se podrá realizar un análisis
comparativo con el uso de los algoritmos genéticos.
96
A-m
D>Uzgramas esquemáticos de una cé6ula em6riónica
I MEMOR RIA I x1[7 O] CONFIIG O]
CONTAS
Figura A.l.- Módulo de memoria.
98
Figura A.2.- Generador de coordenadas,
99
vcc
72
. NIBUS D i
SIRUS DZ
HOUT D3
M4-1 E DO
s1ausD
I O __D VOJ cis
110
"OuT- 14 i
' I si si D
M4-1 E UlüUS DO
Figura A.3.- Enrutador de Entrada / Salida.
1 O0
W C I
- G MO
L I c tolo I
i I I
E80
EBt
Figura A.4.- Elemento de procesamiento.
1 o1
a O O I u7 m r m o 0 O Z
8 E i
I!
3 ? p>
? 3 0
2
[D c
U
O o ai Q O ai U ai a. L?!
n
-7
a
(D u)
c
3 ai. e. o O Q (D
a, i? 3
+ S
9
... I ,
XY 7 XY 6 XY5 XY 4
NlBUS
x3 x2 X I xo
0 r C m
PO 1
. .
[Ahn95]
[AraOl]
[Ars96]
[Bake51
[Bar941
(Be1781
[Bli95]
[Bra021
[Car861
[Cer79]
[Cha70]
[Dei951
[Fit881
[Fog001
Ahn H. I., Han S. K., Cho T. W., “Genrouter: A Genetic Algorithm for Channel Routing Problems”, Microelectronics and VSLI, 1995, TENCON ‘95, IEE Region 10 international Conference on, 1995.
Arabas J., “Applying an evolutionary algorithm to telecomunication network design”, IEEE Transactions on evolutionary computation, August 2001.
Arslan T., D. H. Horrocks and E. Ozdemir, “Structural synthesis of cell-based VLSl circuits using a multi-objective genetic algorithm”, Electronics Letters, March 1996.
Baker J. E., “Adaptive Selection Methods for Genetic Algorithms”, Proceedings of sirts ICGA, Lawrence Erlbaum Associates Publishers, pp 101-1 11, 1985.
Bartee T. C., Data communications, networks and systems, SAMS, 1991
Bell D., “Decision Trees, Tables and Lattices”, in Batchelor B. (ed.), Patterm recognition: ideas in practice, Plenum Press, 1978.
Blickle T., Thiele L.. “A mathematical analysis of Tournament Selection”, Proceeding of sixth ICGA, Morgan Kaufmann Publishers, pp 9-16, 1995.
Bradley D. and Tyrrell A,, “lmmunotronics- Novel finite-state-machine architectures with buit-in self-test using self-nonself differentiation.” IEEE Transactions on Evolutionary Computation, Vo1.6-3, pp.227-238, June 2002.
Carlson A. B., Communication systems, Mc Graw Hill, 1986,
Cerny E., “Synthesis of Minimal Binary Decision Trees”, IEEE Trans. On Computers, Vol. 28-7, July 1979, pp. 472-482.
Chang H., Fault Diagnosis of Digital Systems, Wiley, 1970.
Deitel H. M., P. J. Deitel, Cómo programar en C/C++, Prentice Hall, 1995.
Fitzgerald J., Eason T. S., Fundamentos de Comunicación de Datos, LimUSa, I 988.
Fogel D. B., ‘What is evolutionary computation?”, IEEE Spectrum, February 2000.
Fogel, L. J.. Owens A. J., and Walsh M. J., Artificial Intelligence Through Simulated Evolution, Jhon Wiley, Chichester, UK, 1966.
Gockel N., et al, “A hybrid Genetic Algorithm for the Channel Routing Problem”, Circuits and Systems, 1996; ISCAS ‘96., Connecting the World., 1996, IEEE
International Symposium on, Volume 4,.1996.
[Go1891 Goldberg D., Genetic Algorithms in search, optimization and machine learning, Reading Massachusetts, 1989.
[Gon88] Gonzales N., Comunicaciones y Redes de Procesamiento de Datos, Mc Graw Hill, 1988.
[Gong91 Goni B. M. and Arslan T., “An Evolutionary 3D Over-the-Cell Router”, ASlClSOC Conference, 1999, Twelfth Annual IEEE International, 1999.
[Ha1921 Halsall F., Data communications, computer networks and open systems, Addison Wesley Longman, 1992.
[Han771 Hanani M., “An Optimal Evaluation of Boolean Expresions in an online query system”, Commun. ACM, Vol. 20-5. May 1977, pp. 344-347.
[Hem961 Hemmi H., et al, “Development and Evolution of Hardware Behaviors”, Lecture Notes in Comouter Science - Towards Evolvable Hardware, Vol. 1062,
[Hig96]
[Ho192]
[InaOl]
[ha991
[JacOI]
[Jho96]
[Ko97]
[Koz92]
Springer-Verlag: 1996.
Higuchi T., et al, “Evolvable Hardware and its Application to Pattern Recognition and Fault-Tolerant Systems”, Lecture Notes in Computer Science - Towards Evolvable Hardware, Vol. 1062, Springer-Verlag, 1996.
Holland J., Adaptation in natural and artificial systems, Cambridge Massachusetts, 1992.
lnagaki J., Haseyama M., Kitajima H.. “A New Genetic Algorithm for Routing the Shortest Route Via Several Designated Points”, Circuits and Systems, 2301, ISCAS 2001, The 2001 IEEE International Symposium on, Volume 2, 2001.
lnagaki J., Haseyama M., Kitajima H., “A Genetic Algorithm for Determining Multiple Routes and its Applications”, Circuits and Systems, 1999, ISCAS ‘99. Proceedings of the 1999 IEEE International Symposium on, Volume 6, 1999.
Jackson A. and Tyrrell A., ”Asynchronous Embryonics”, Proceedings of Third NASAJDoD workshop on Evolvable Hardware, IEEE Computer Society, pp.201- 210,2001.
Q. D. Jhonson, Sun R., “A genetic Algorithm for VLSI Channel Routing in the Presence of Cyclic Vertical Constraints”, Circuits and Systems, 1996., IEEE 39‘h Midwest symposium on, Volume 1, 1996.
KO K.. Tang K., Chan Ch., Man K., Kwong S., “Using genetic algorithms to design mesh networks”, IEEE Computer, August 1997.
Koza J.. Genetic Programming: on the programming of computers by means of natural selection, Massachusetts, 1992.
[ K u o ~ ~ ] Kuo F. K., Protocols and techniques for data communication networks, Prentice Hall, 1981.
[KwoOO] Kwong S.. Wing D., Tang K., Man K., ”Optimization of spare capacity in self-
healing multicast ATM network using genetic algorithm”, IEEE Transactions on industrial electronics, December 2000.
[Lafe91 Lafore R.. Turbo C, Programming for the PC. The Waite Group, Inc., 1989
[Leu981 Leung Y., Li G.. Xu Z., “A genetic algorithm for the multiple destination routing problems”, IEEE Transactions on evolutionary computation, November 1998.
[Lie961 Lienig J., “A Parallel Genetic Algorithm for two Detailed Routing Problems”, Circuits and Systems, 1996, ISCAS ‘96., Connecting the World., 1996, IEEE International Symposium on, Volume 4, 1996.
[Lie971 Lienig J., “A Parallel Genetic Algorithm for Perfomance-Driven VLSl Routing”, Evolutionary Computation, IEEE Transactions on, April 1997.
iLim971 Lim Q. and Chew H., “Joining of compacted cells using genetic algorithm”, Electronics Letters, Volume: 33 Issue: 23, November 1997.
[Lon011 Lones M.A., Tyrrell A.M., “Enzyme Genetic Programming”, in proceedings of the Congress on Evolutionary Computation 2001 (CEC2001), Seoul, Korea, May 2001.
[Man961 Mange D.. Goeke M., Madon D., et al. “Embrionics: a new family of coarse- grained FPGA with self-repair and self-reproduction properties”, in towards evolvable hardware: The evolutionary engineering approach, LNCS 1062, E. Sanchez and M. Tomassini (eds.), Springer-Verlag: Berlin, pp. 197-220, 1996.
[Man971 Man¡ N., Srinivasan B., “Using Genetic Algorithm for Slicing Floorplan Area Optimization in Circuit Design”, Systems, Man, and Cybernetics, 1997, Computational Cybernetics and Simulation., 1997 IEEE International Conference on, Volume: 3, 1997.
[Mar961 Marchal P., Nussbaum P.,’Piguet C., et al., “Embrionics: The birth of synthetic life,” in towards evolvable hardware: The evolutionary engineering approach, LNCS 1062, E. Sanchez and M. Tomassini (eds.), Springer-Verlag: Berlin, pp.
Miller J. F. and Thompson P., “Evolving Circuits on Gate Arrays”, Reconfigurable Systems (Ref. No. 1999/061), IEEE Colloquium on, 1999.
Minieka E., Optimization Algorithms for Networks and Graphs, Marcel Dekker Inc., 1978.
[MorOO] Moreno J. de J., Morales J., et al, “lmplementación de un polinomio para la evaluación del CRC16 utilizando un microcontrolador PIC1684”, 2’ Congreso de lngenieria Eléctrica y Electrónica Aplicada, Instituto Tecnológico de Durango, Durango 2000.
[Mor951 Moreno J. de J., “Sistema para la Automatización de la Iluminación en Edificios”.(Tesis M.C.; Cuernavaca, Mor.: Centro Nacional de Investigación y Desarrollo Tecnológico, Julio 95).
Noteboom R. and Al¡ H. H., “A New Genetic Algorithm for Single Row Routing”, Circuits and Systems, 1995, Proceedings., Proceedings of the 3Eth Midwest
,
166-196, 1996.
[Mi1991
[Min78]
[Not961
107
[OrtOOb]
[Paz991
[POlOl]
[Rec73]
[Ron981
[Sa1991
[San971
[Sch81]
[SchSO]
[Sch95]
[Sinal]
[SipOO]
[Swa89]
Symposium on, Volume 2, 1996.
[OrtOOa] Ortega Sánchez C.. Embrionics: A bio-inspired fault-tolerant multicellular system, The University of York, Department of Electronics Bio-inspired and Bio- Medical Engineering Group, York, England, may 2000.
Ortega Sánchez C., Mange D., Smith S. and Tyrrell A,, "Embrionics: A bio- inspired cellular architecture with fault-tolerant properties", Genetic Programming and Evolvable Machines, vol. 1-3, pp 187-215, Julio 2000.
Paz Ramos M. A., Control de un sistema MIMO por medio de técnicas difuso- genéticas, Cenidet 1999.
Politécnico de Lausana, Lausana, Suiza, Página en internet, http://diwww.epfl.ch/recherche/, 2001.
Rechenberg I . , Evolutionsstrategie: Optimierung lechnischer System nach Prinzipien der biologischen Evolution, Fromman-Holzboog Verlag, Stuttgart, 1973.
Ronald S. and Kirkby S., "Compund Optimisation. Solving Transport and Routing Problems with a Multi-Chromosome Genetic Algorithm", Evolutionary Computation Proceedings, 1998, IEEE World Crongress on Cornpütatuonal Intelligence., The 1998 IEEE International Conference on, 1998.
Saltourus M., et al, "An Efficient Evolutionary Algorithm for (Near-) Optimal Steiner Trees Calculation: an Aproach to Routing of Multipoint Connections", Computational Intelligence and Multimedia Aplications. 1999, ICCIMA '99. Proceedings, Third International Conference on, 1999.
Sanchez E., Mange D., Sipper M., et al, "Phylogeny, Ontogeny and Epigenesis: Three Sources of Biological Inspiration for SoRening Hardware", en Proceedings of Is' International Conference on Evolvable Systems: From Biology to Hardware (ICES96). LNCS 1259, Springer-Verlag, 1997, pp.35-54
Schwefel, H.-P., Numerical Optimization for Computer Models, John Wiley, Chichester. UK, 1981.
Schwartz M., Transmisión de información, modulación y ruido, Mc Graw Hill, 1990
Schnecke V., Vornberger O., "Genetic Design of VLSI-Layouts". Genetic Agorithms in Engineering Systems: Innovations and Applications, 1995, GALESIA, First International Conference on, 1995.
Sinha K.. et al, "Partitioning Routing Area into Zones with Distinct Pins". VLSl Design, 2001, 14'h International Conference on, 2001.
Sipper M., Ronald E. M. A.. "A new species of hardware", IEEE Spectrum, March 2000.
Swamy M. N. S.. Thulasiraman K.. Graphs, networks, and algorithms, Edit. John Wiley & Sons, 1989.
van971 Tanenbaum A. S., Redes de computadoras, Pearson, pp. 346400,1997,
[Tau981 Taubes G., "Tras una Máquina consciente", Discover en Espatiol. Julio 1998.
[Tom961 Tomasi W., Sistemas de comunicaciones electrónicas, Prentice may, 1996.
[TyrOlj Tyrrell A., Hollingworth G. and Smith S., "Evolutionary Strategies and Intrinsic Fault Tolerance", Proceedings of Third NASNDoD workshop on Evolvable Hardware, IEEE Computer Society, pp.98-106,2001.
[UniOl] Universidad de York, York, Inglaterra, Página en internet, http://www.vork.ac.uk/. 2001.
Pe¡77] Weide B., "A Survey of, Analysis Techniques for Discrete Algorithms", ACM computing surveys, Vol. 9-4, Dec. 1977, pp. 291-313.
[Wir76] Wirth N., Algorithms + Data Structures = programs, Prentice Hall, 1976
Po196] Wolf H. G. and Mlynski D. A,, "A New Genetic Single-Layer Routing Algorithm for Analog Transistor Arrays", Circuits and Systems, 1996, ISCAS '96., Connecting the World., 1996, IEEE International Symposium on, Volume 4, 1996.
[YouOl] Youssef H., Sait S. M., Khan S. A,, ", "An evolutionary Algorithm for Network Topology Design", Neural Networks, 2001, Proceedings, IJCNN '01, International Joint Conference on, Volume: 1, 2001.
[Zbi96] Zbigniew M., Genetic algorithms + Data structures = Evolution programs, Springer, 1996.
[Zha99] Zhang Q., Leung Y., "An orthogonal genetic algorithm for multimedia multicast routing", IEEE Transactions on evolutionary computation, April 1999.
1 o9