Algoritmo memético

Algoritmo Memético

Algoritmo Memético (AM) es una población de agentes que alternan períodos de auto-mejora (mediante búsqueda local) con periodos de cooperación y competición (mediante selección).

Definición

Ante el amplio desarrollo obtenido por los métodos meta heurísticos y heurísticos tradicionales estos pueden ser subdivididos en dos grandes grupos, con características muy distintivas, por un lado están los mecanismos de explotación de las soluciones o métodos de Búsqueda Local (BL) y por otro los mecanismos de exploración de las soluciones o Algoritmos Poblacionales (APs).

Los primeros logran con rapidez soluciones precisas en las inmediaciones del punto inicial, poseyendo una gran tendencia a quedar atrapados en óptimos locales y no el óptimo global, el cual constituye la mejor solución dentro del espacio de búsqueda. Además estos mecanismos poseen una gran dependencia del punto inicial siendo algunos de sus representantes:

• Los métodos del Descenso/Ascenso (Luenberguer, 1984)
• Los métodos de Cuasi-Newton (Luenberguer, 1984)
• Los métodos del Gradiente (Luenberguer, 1984)
• El método Simplex de Nelder y Mead (Nelder and Mead, 1965)
• El Solis West (Solis and West, 1981)
• La búsqueda Tabú (Glover and Laguna, 1997),
• El Recocido Simulado (Kirkpatrick et Al., 1983),
• La Búsqueda Local Guiada (Voudouris and Tsang, 1995), etc.

Por otra parte los mecanismos de exploración de las soluciones poseen gran independencia de la naturaleza del espacio de soluciones pudiendo atravesar el espacio de búsqueda con múltiples máximos o mínimos locales y alcanzando una solución global, pero a su vez presentan inconvenientes para alcanzar soluciones precisas con rapidez pues no aprovechan las características locales del espacio de búsqueda.

Algunos ejemplos los constituyen:

• Los Algoritmos Genéticos (AGs) (Goldberg, 1998)
• La Búsqueda Dispersa (Laguna and Martí, 2003)
• La Evolución Diferencial (Storn and Price, 1997)
• Algoritmos Basados en Estimación de Distribuciones (Lozano et al., 2006)
• La Optimización basada en las Colonias de Hormigas (Dorigo and Caro, 1999)
• Sistemas de Partículas (Kennedy and Eberhart, 1995)
• La Optimización Basada en Mallas Variables (VMO) (Puris, 2009)

Ante a estos dos criterios (exploración y explotación) se ha demostrado que el uso combinado de estas, posee propiedades beneficiosas durante el proceso de búsqueda, pues la incorporación de BL permite abordar la necesidad de precisión durante todo el proceso, a diferencia de un AP en el que el ajuste fino de las soluciones solo se produce en las etapas finales. En los últimos años se han venido desarrollando algoritmos que buscan abordar el problema de la búsqueda (búsqueda global pero con capacidad de alcanzar soluciones precisas rápidamente aprovechando las ventajas de la búsqueda local).

Numerosas ha sido las denominaciones para este tipo de modelos que combinan ambos enfoques: Algoritmos Híbridos, Algoritmos Genéticos Locales, etc. Moscato (Moscato, 1999) emplea el término Algoritmos Meméticos para denominar a estos procedimientos, así como plantea la siguiente descripción de los mismos:

El objetivo de los AMs es hacer que ambas componentes: La Búsqueda Local y el Algoritmo Poblacional trabajen de forma cooperativa para conseguir una sinergia entre ambos que permita mejorar el proceso de búsqueda. Numerosos han sido los diseños de AMs planteados.

A continuación se mencionan algunos de los propuestos:

• El GLS_Based_Memetic_Algorithm propuesto en (Holstein and Moscato, 1999)
• Genetic_Local_Search (Aarts and Verhoeven, 1997) para resolver problemas del viajante del comercio
• El AM con BL basada en el Operador de Cruce (AMCR- ) (Molina Cabrera, 2007)
• Algoritmo híbrido con múltiples colonias (ACOR) (Herrera et al., 2009)

Fuentes

• Holstein, D. and P. A. Moscato (1999). Memetic algorithms using guided local search: A case study. . New Ideas in Optimization.
• Aarts, E. and G. Verhoeven (1997). HandBook of Evolutionary Computation, Oxford University Press.
• Molina Cabrera, D. (2007). Algoritmos Meméticos con Aplicación Adaptativa de la Búsqueda Local para Optimización Continua. Departamento de Ciencias de la Computación e Inteligencia Artificial. Granada, Universidad de Granada: 258.
• Herrera, F., P. Cardoso, et al. (2009). ACOR híbrido con multiples colonias para problemas de optimizacion continua. CD de Memoria del VI Congreso Español sobre Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB'09). Málaga: 465-472.