Algoritmos genéticos locales

Resumen

En la industria y la ciencia existen una serie de problemas reales de optimización de difícil solución que se caracterizan por su complejidad computacional (son NP-duros) y porque los algoritmos exactos disponibles para abordarlos son ineficientes o simplemente imposibles de aplicar, Las metaheurísticas (MHs) [1 - 3] constituyen una familia de métodos aproximados de propósito general consistentes en procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda asociado a este tipo de problemas. Las MHs se han aplicado sobre problemas de campos muy diversos de la actividad humana, mostrando su capacidad para proporcionar soluciones aceptablemente buenas (no necesariamente óptimas) en un tiempo razonable. Existe un grupo de MHs que siguen paradigmas bien diferenciados y que habitualmente se citan como referentes clásicos, ya que disponen de unos antecedentes históricos muy consolidados. Este grupo incluye Enfriamiento Simulado, Búsqueda Tabú, Búsqueda Local con Multiarranque Aleatorio, Búsqueda Local Iterativa, Búsqueda de Vecindario Variable, Procedimientos de Búsqueda Ávidos Aleatorios y Adaptativos, Algoritmos Evolutivos y Búsqueda Dispersa. Hay dos factores importantes a la hora de diseñar MHs: intensificación y diversificación [1]. La diversificación generalmente se refiere a la habilidad de visitar muchas regiones diferentes del espacio de búsqueda, mientras que la intensificación se refiere a la habilidad de obtener soluciones de alta calidad en esas regiones. Un algoritmo de búsqueda debe alcanzar un equilibrio táctico entre estos dos factores, de alguna forma conflictivos, para resolver exitosamente el problema tratado. Los métodos de búsqueda local (BL) son algoritmos especialmente diseñados para ofrecer una alta intensificación. Dada una solución inicial, son capaces de explorar eficaz y eficientemente la región del espacio asociada, alcanzar la base de atracción de un óptimo local y aproximarse a él con un alto grado de precisión, consumiendo pocos recursos computacionales. Para ello, el método de BL empieza desde la solución dada, e iterativamente intenta reemplazar la solución actual por otra cercana, que sea mejor. En la actualidad, los métodos de BL, reciben una atención especial. De hecho, existe una categoría de MHs, estado del arte de muchos problemas, para las cuales las técnicas de BL son un componente fundamental [1 - 5]. Su modo de operación se resume básicamente en generar, de alguna forma, soluciones que la técnica de BL optimizará. A este tipo de MHs las llamaremos MHs basadas en BL. Los Algoritmos Genéticos (AGs) [6, 7] son MHs inspiradas en los procesos genéticos de los organismos naturales y en los principios de la evolución natural de poblaciones. Su idea básica es mantener una población de cromosomas, los cuales representan soluciones candidatas a un problema concreto, que evolucionan con el tiempo a través de un proceso de competición y variación controlada. En su formulación inicial, los AGs utilizaban el alfabeto binario para codificar las soluciones, sin embargo, también se han tenido en cuenta otro tipo de codificaciones como la real [8 - 12], dando lugar a los AGs con codificación real (AGCRs). Uno de los componentes más importantes de los AGs es el operador de cruce, método capaz de combinar la información de los individuos de la población. De hecho, se puede considerar como una de las características que definen y diferencian a los AGs de otros algoritmos basados en la evolución natural. El operador de cruce es un elemento determinante del equilibrio entre intensificación y diversificación mantenido por el AG. Por ello, se ha considerado frecuentemente como pieza clave para hacer AGs más efectivos. En los últimos años, el atractivo de los AGs como procedimientos de búsqueda ha motivado el diseño de AGs específicos que actúan como métodos de BL (es decir, pretenden proveer una alta intensificación). De hecho, se han presentado varias propuestas de AGs con este propósito [13 - 19]. A este tipo de MHs las denominaremos Algoritmos Genéticos Locales (AGLs). Los AGLs son una novedosa categoría de MHs basadas en poblaciones para proveer intensificación. Éstos presentan dos características muy interesantes: 1) Los AGLs pueden producir un rendimiento superior al de los métodos clásicos de BL. [14] argumenta que los AGLs pueden recorrer caminos complejos que llevan a soluciones de gran calidad, que las técnicas clásicas de BL no pueden seguir. 2) Los AGLs pueden mejorar los resultados de las MHs basadas en BL. Los AGLs pueden asumir fácilmente el papel de los métodos de BL en las MHs que los usan, obteniendo de esta forma, una nueva clase de MHs que podemos denominar como MHs basadas en AGLs. De hecho, en la literatura han aparecido varios ejemplos de Algoritmos Meméticos que usan un AGL en el lugar del método clásico de BL [14 - 17, 20]. La importancia actual de las MHs basadas en BL en la resolución de problemas de optimización complejos justifica la investigación de nuevas propuestas de MHs basadas en AGLs capaces de mejorar su rendimiento. En la actualidad, ésta es una línea de investigación prometedora y atractiva. En esta memoria, profundizaremos en el estudio de los AGLs y su uso dentro de MHs. En particular, diseñaremos nuevos modelos de AGLs y MHs basadas en éstos, que luego compararemos con MHs basadas en BL y otros algoritmos de optimización presentes en la literatura. Referencias: [1] Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35(3):268-308 [2] Glover F, Kochenberger G (eds) (2003) Handbook of Metaheuristics. Kluwer Academic Publishers [3] Siarry P, Michalewicz Z (eds) (2008) Advances in Metaheuristics for Hard Optimization. Natural Computing, Springer [4] Ribeiro CC, Hansen P (2002) Essays and Surveys in Metaheuristics. Kluwer Academic Publishers [5] Voß S, Osman IH, Roucairol C (1999) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers Norwell [6] Goldberg DE (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co. [7] Holland JH (1975) Adapatation in Natural and Artificial Systems. The University of Michigan Press [8] Davis L (1991) Handbook of Genetic Algorithms. Van Nostrand Reinhold [9] Deb K, Beyer H (2001) Self-adaptive genetic algorithms with simulated binary crossover. Evol. Comput. 9(2):195-219 [10] Deb K (2005) A population-based algorithm-generator for real-parameter optimization. Soft Comput. 9:236-253 [11] Herrera F, Lozano M, Verdegay JL (1998) Tackling real-coded genetic algorithms: operators and tools for behavioral analysis. Artif. Intell. Rev. 12(4):265-319 [12] Michalewicz Z (1992) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag [13] Herrera F, Lozano M (2000) Gradual distributed real-coded genetic algorithms. IEEE Trans. Evol. Comput. 4(1):43-63 [14] Kazarlis SA, Papadakis SE, Theocharis JB, Petridis V (2001) Microgenetic algorithms as generalized hill-climbing operators for GA optimization. IEEE Trans. Evol. Comput. 5(3):204-271 [15] Lozano M, Herrera F, Krasnogor N, Molina D (2004) Real-coded memetic algorithms with corssover hill-climbing. Evol. Comput. 12(3):273-302 [16] Mutoh A, Tanahashi F, Kato S, Itoh H (2006) Efficient real-coded genetic algorithms with flexible-step crossover 126(5):654-660 [17] Noman N, Iba H (2008) Accelerating differential evolution using an adaptive local search. IEEE Trans. Evol. Comput. 12(1):107-125 [18] Potts JC, Giddens TD, Yadav SB (1994) The development and evaluation of an improved genetic algorithm based on migration and artificial selection. IEEE Trans. Syst., Man, Cybern. 24:73-86 [19] Tsutsui S, Ghosh A, Corne D, Fujimoto Y (1997) A real coded genetic algorithm with an explorer and an exploiter population. In: Bäck T (ed) Proc. of the Int. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers, pp 238-245 [20] O'Reilly UM, Oppacher F (1995) Hybridized crossover-based search techniques for program discovery. In: Proc. of the World Conf. on Evolutionary Computation, 2, pp 573-578 [21] Gang P, Iimura I, Nakayama S (2007) Application of genetic recombination to genetic local search in TSP. Int. J. Inf. Technol. 13(1):57-66 [22] Lima CF, Pelikan M, Sastry K, Butz M, Goldberg DE, Lobo FG (2006) Substructural neighborhoods for local search in the bayesina optimization algorithm. In: Proc. of the Int. Conf. on Parallel Problem Solving from Nature, LNCS, vol 4193, pp 232-241 [23] Sastry K, Goldberg DE (2004) Designing competent mutation operators via probabilistic model building of neighborhoods. Proc of the Conf. on Genetic and Evolutionary Computation, LNCS, vol 3103, pp 114-125