Una estrategia de interconexionado de circuitos basada en algoritmos genéticos
- Fernández-Pampillón Cesteros, Ana
- Gómez Albarrán, María de las Mercedes
- Sánchez Pérez, Juan Manuel
ISSN: 0214-932X
Año de publicación: 1996
Volumen: 29
Número: 3
Páginas: 3-15
Tipo: Artículo
Otras publicaciones en: Informática y automática: revista de la Asociación Española de Informática y Automática
Resumen
El interconexionado de circuitos es un problema de búsqueda de caminos mínimos, resuelto mediante algoritmos que poseen complejidades elevadas. Los algoritmos genéticos son algoritmos robustos de búsqueda adaptativa, utilizados en procesos de optimización y búsqueda compleja. El objetivo de este trabajo es optimizar un algoritmo de interconexión clásico (Lee), combinándolo con un algoritmo genético. Este algoritmo genético ayuda a reducir el espacio de búsqueda y las complejidades del algoritmo de Lee. El algoritmo que proponemos, AGOL (Algoritmo Genético para la Optimización del algoritmo de Lee) obtiene, si existe, un camino óptimo entre los nodos del circuito que se van a interconectar, superando el inconveniente de los algoritmos genéticos que se conforman con cuasi-soluciones. Finalmente, presentamos un estudio de la complejidad temporal para el algoritmo clásico de Lee, el algoritmo genético y AGOL.