Resumen de Una estrategia de interconexionado de circuitos basada en algoritmos genéticos

Ana Fernández-Pampillón Cesteros , María de las Mercedes Gómez Albarrán , Juan Manuel Sánchez Pérez

• español

  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.

• English

  Circuit routing is a problem of searching the shortest path and it is solved using high complexity algorithms. Genetic algorithms (GAs) are tough algorithms of adaptive searching, used in optimization and complex searching processes. The goal of our work is to improve a classic routing algorithm (Lee) combining it with a GA. This GA helps to reduce search space and complexities of Lee algorithm. The algorithm we propose (AGOL) obtains, if it exists, the shortest path between the circuit nodes that we are interconnecting, while overcoming the GAs drawback: finding quasi-solutions. Finally, we present a study about temporal complexity of Lee algorithm, our GA and AGOL.