Diferencia entre revisiones de «Algoritmo memético»
m (Texto reemplazado: «<div align="justify">» por «») |
|||
| (No se muestran 4 ediciones intermedias de 3 usuarios) | |||
| 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 |
}} | }} | ||
| − | '''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. |
| − | + | ||
| − | 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. |
| − | * | + | ===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. |
| − | *Los métodos del | + | |
| − | *El | + | A continuación se mencionan algunos de los propuestos: |
| − | *El [[Solis West]] ( | + | *El GLS Based Memetic Algorithm propuesto en (Holstein and Moscato, [[1999]]). |
| − | *La búsqueda Tabú ([[Glover and Laguna]], [[1997]]), | + | *Genetic Local Search (Aarts and Verhoeven, [[1997]]) para resolver problemas del viajante del comercio. |
| − | *El [[Recocido Simulado]] ( | + | *El Algorítmo memético con Búsqueda local basada en el Operador de Cruce (AMCR) (Molina Cabrera, [[2007]]). |
| − | *La [[Búsqueda Local Guiada]] ( | + | *[[Algoritmo híbrido]] con múltiples colonias (ACOR) (Herrera et al., [[2009]]). |
| − | + | ||
| − | 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 | + | |
| − | + | ===Representantes=== | |
| + | *Los [[Método Descenso/Ascenso|métodos del Descenso/Ascenso]] ([[Luenberguer]], [[1984]]) | ||
| + | *Los [[Método de Cuasi-Newton|métodos de Cuasi-Newton]] (Luenberguer, 1984) | ||
| + | *Los [[Gradiente de una función|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: | 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: |
| − | + | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==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]] [[Category:Algoritmos]] |
última versión al 17:11 20 jun 2019
| ||||
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)
Sumario
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.
