Diferencia entre revisiones de «Algoritmo memético»
| Línea 1: | Línea 1: | ||
| − | |||
{{Definición | {{Definición | ||
| − | |nombre= Algoritmo | + | |nombre= Algoritmo memético |
|imagen= | |imagen= | ||
|tamaño= | |tamaño= | ||
| − | |concepto= | + | |concepto=Población de agentes que alternan períodos de auto-mejora |
}} | }} | ||
| − | + | <div align="justify"> | |
| − | '''Algoritmo | + | '''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== | ==Definición== | ||
| − | Ante el amplio desarrollo obtenido por los métodos meta heurísticos y heurísticos tradicionales | + | 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 | + | 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étodo Descenso/Ascenso|métodos del Descenso/Ascenso]] ([[Luenberguer]], [[1984]]) |
| − | *Los métodos de | + | *Los [[Método de Cuasi-Newton|métodos de Cuasi-Newton]] (Luenberguer, 1984) |
| − | *Los métodos del Gradiente ( | + | *Los [[Gradiente de una función|métodos del Gradiente]] (Luenberguer, 1984) |
| − | *El | + | *El [[método Simplex de Nelder y Mead]] (Nelder and Mead, [[1965]]) |
| − | *El [[Solis West]] ( | + | *El [[Solis West]] (Solis and West, [[1981]]) |
| − | *La búsqueda Tabú ([[Glover and Laguna]], [[1997]]), | + | *La [[búsqueda Tabú]] ([[Glover and Laguna]], [[1997]]), |
| − | *El [[Recocido Simulado]] ( | + | *El [[Recocido Simulado]] (Kirkpatrick et Al., [[1983]]), |
| − | *La [[Búsqueda Local Guiada]] ( | + | *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 | + | 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: | Algunos ejemplos los constituyen: | ||
| − | *Los [[Algoritmos Genéticos]] | + | *Los [[Algoritmos Genéticos]] (AGs) (Goldberg, [[1998]]) |
*La [[Búsqueda Dispersa]] (Laguna and Martí, [[2003]]) | *La [[Búsqueda Dispersa]] (Laguna and Martí, [[2003]]) | ||
| − | *La [[Evolución | + | *La [[Evolución Diferencial]] (Storn and Price, [[1997]]) |
*[[Algoritmos Basados en Estimación de Distribuciones]] (Lozano et al., [[2006]]) | *[[Algoritmos Basados en Estimación de Distribuciones]] (Lozano et al., [[2006]]) | ||
*La [[Optimización basada en las Colonias de Hormigas]] (Dorigo and Caro, [[1999]]) | *La [[Optimización basada en las Colonias de Hormigas]] (Dorigo and Caro, [[1999]]) | ||
*[[Sistemas de Partículas]] (Kennedy and Eberhart, [[1995]]) | *[[Sistemas de Partículas]] (Kennedy and Eberhart, [[1995]]) | ||
*La [[Optimización Basada en Mallas Variables]] (VMO) (Puris, [[2009]]) | *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 | + | 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 | + | Numerosas han sido las denominaciones para este tipo de modelos que combinan ambos enfoques: [[Algoritmo híbrido|Algoritmos Híbridos]], [[Algoritmo Genético Locale|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: |
| − | + | ||
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. | 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: | A continuación se mencionan algunos de los propuestos: | ||
| − | *El | + | *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 | + | *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) | + | *[[Algoritmo híbrido]] con múltiples colonias (ACOR) (Herrera et al., [[2009]]). |
| − | + | ||
==Fuentes== | ==Fuentes== | ||
| − | *Holstein, D. and P. A. Moscato (1999). Memetic algorithms using guided local search: A case study. | + | *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 | + | *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 | + | *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 | + | *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. |
| − | + | ||
[[Category:Informática]] | [[Category:Informática]] | ||
Revisión del 12:20 24 feb 2014
| ||||
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 (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 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:
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 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).
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.
