Algoritmos genéticos y metaheuristicas

En la tesis doctoral de García, publicada el año 2008 con el título “Algoritmos genéticos locales”, se indica que 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 problemas no polinomiales duros, y porque los algoritmos exactos disponibles para abordarlos son ineficientes o simplemente imposibles de aplicar. En el libro de Siarry y Michalewicz, publicado el año 2008 con el título “Avances en metaheurísticas para la optimización dura”, se menciona que las metaheurísticas 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 metaheurísticas se han aplicado sobre problemas de campos muy diversos de la actividad humana, mostrando su capacidad para proporcionar soluciones aceptablemente buenas, no necesariamente optimas, en un tiempo razonable.

Según Blum y Roli, en el artículo escrito el año 2003 con el título “Metaheurísticas de optimización combinatoria: Descripción y comparación conceptual”, existen dos factores importantes a la hora de diseñar metaheurísticas: Intensificación y diversificación. 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 son algoritmos especialmente diseñados para ofrecer una alta intensificación. Dada una solución inicial, son capaces de explorar de manera eficaz y eficiente 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 búsqueda local empieza desde la solución dada, e iterativamente intenta reemplazar la solución actual por otra cercana, que sea mejor.

En el libro de Holland, publicado el año 1975 con el título “Adaptación en sistemas naturales y artificiales”, complementado con el libro de Goldberg, publicado el año 1989 con el título “Algoritmos genéticos en búsqueda, optimización y aprendizaje automático”, se menciona que los algoritmos genéticos son metaheurísticas 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, las cuales representan soluciones candidatas a un problema concreto, que evoluciona con el tiempo a través de un proceso de competencia y variación controlada. En su formulación inicial, los algoritmos genéticos utilizaban el alfabeto binario para codificar las soluciones, sin embargo, también se han tenido en cuenta otro tipo de codificaciones como la codificación real, planteada por Deb en el año 2005 en el artículo titulado “Generador de algoritmos basado en poblaciones para la optimización de parámetros reales”, dando lugar a los algoritmos genéticos con codificación real. Uno de los componentes más importantes de los algoritmos genéticos es el operador de apareamiento, 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 algoritmos genéticos de otros algoritmos basados en la evolución natural. El operador de apareamiento es un elemento determinante del equilibrio entre intensificación y diversificación mantenido por el algoritmo genético. Por ello, se ha considerado frecuentemente como pieza clave para hacer algoritmos genéticos efectivos. En los últimos años, el atractivo de los algoritmos genéticos como procedimiento de búsqueda ha motivado el diseño de algoritmos genéticos específicos que actúan como métodos de búsqueda local, es decir se pretende proveer una alta intensificación. A este tipo de metaheurísticas se las denomina algoritmos genéticos locales. Los algoritmos genéticos locales son una novedosa categoría de metaheurísticas basadas en poblaciones para proveer intensificación.

Los algoritmos genéticos locales, como metaheurísticas, presentan dos características muy interesantes: (1) Los algoritmos genéticos locales pueden producir un rendimiento superior al de los métodos clásicos de búsqueda local. Kazarlis y sus colegas, en el artículo escrito el año 2001 con el título “Algoritmos micro-genéticos como operadores generalizados de ascenso de colinas para la optimización de algoritmos genéticos” argumentan que los algoritmos genéticos locales pueden recorrer caminos complejos que llevan a soluciones de gran calidad, que las técnicas clásicas de búsqueda local no pueden seguir. (2) Los algoritmos genéticos locales pueden mejorar los resultados de las metaheurísticas basadas en búsqueda local. Los algoritmos genéticos locales pueden asumir fácilmente el papel de los métodos de búsqueda local en las metaheurísticas que los usan, obteniendo de esta forma, una nueva clase de metaheurísticas que pueden ser denominadas como metaheurísticas basadas en algoritmos genéticos locales. De hecho, en la literatura han aparecido varios ejemplos de algoritmos meméticos que usan un algoritmo genético local en el lugar del método clásico de búsqueda local, reportada el artículo de Noman e Iba, publicado el año 2008 con el título “Acelerando la evolución diferencial con el uso de una búsqueda local adaptativa”. La importancia actual de las metaheurísticas basadas en búsqueda local en la resolución de problemas de optimización complejos justifica la investigación de nuevas propuestas de metaheurísticas basadas en algoritmos genéticos locales capaces de mejorar su rendimiento.