Algoritmo memético

Algoritmo memético Concepto: Población de agentes que alternan períodos de auto-mejora

Algoritmo memético. 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.

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.

Algoritmo memético

El objetivo de los Algoritmos meméticos es hacer que ambos 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 Algoritmos meméticos 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 Algorítmo memético con Búsqueda local basada en el Operador de Cruce (AMCR) (Molina Cabrera, 2007).
• Algoritmo híbrido con múltiples colonias (ACOR) (Herrera et al., 2009).

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.

Mecanismos de Exploración

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 Búsqueda local permite abordar la necesidad de precisión durante todo el proceso, a diferencia de un Algoritmo de población 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 han sido las denominaciones para este tipo de modelos que combinan ambos enfoques: Algoritmos Híbridos, Algoritmos Genéticos Locales, etc. (Moscato, 1999) emplea el término Algoritmos Meméticos para denominar a estos procedimientos, así como plantea la siguiente descripción de los mismos:

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 múltiples colonias para problemas de optimización continua. CD de Memoria del VI Congreso Español sobre Metaheurísticas. Algoritmos Evolutivos y Bioinspirados (MAEB'09). Málaga: 465-472.