Algoritmos meméticos adaptativos

El investigador Davis, en el libro escrito el año 1991 titulado “Algoritmos genéticos”, ha demostrado que hibridar los algoritmos evolutivos con otras técnicas puede incrementar sustancialmente su eficiencia de búsqueda; los algoritmos evolutivos obtenidos mediante la hibridación con técnicas de búsqueda local son denominados algoritmo meméticos. En palabras del investigador Schewefel, en el libro escrito el año 1981 titulado “Optimización numérica de modelos computacionales”, los métodos de búsqueda local son métodos que definen un proceso de transformación que, partiendo de una solución determinada, generan una o varias soluciones en un entorno cercano. Así pues, partiendo de una primera solución, denominada solución actual, se puede obtener un conjunto de soluciones directamente alcanzables mediante una única aplicación de dicho método. A este conjunto de soluciones accesibles se les denomina vecindario de la primera solución. Para obtener una solución adecuada, estas técnicas siguen un proceso iterativo en el que, dada una solución actual, buscan una mejor solución dentro de su vecindario que se convierte en la nueva solución actual. Este proceso continúa hasta que se genera un número máximo de soluciones, o se alcanza un óptimo local, este óptimo es una solución para la cual no existe ninguna solución dentro de su vecindario que la mejore.

Por su parte, en palabras de los autores del libro “Computación evolucionaría” Back, Fogel y Michalewicz escrito el año 1997, los algoritmos evolutivos fueron inspirados por la teoría de la evolución de Darwin. Según la teoría darwiniana, la evolución de las especies se produce por tres conceptos: replicación, variación y selección natural. La población se mantiene mediante replicación, y la variación introduce diversidad en la población, mediante una serie de diferencias entre los descendientes y sus progenitores, generando nuevos individuos aplicando un mecanismo de recombinación sexual de dos individuos, en el que el nuevo individuo hereda características de ambos. Debido a los recursos limitados y a los agentes externos o depredadores, este proceso se desarrolla en un ambiente hostil en el que los individuos de la misma o distintas especies compiten entre sí y sólo los más adaptados sobreviven. Esto implica que los más adaptados tendrán mayores posibilidades de tener descendencia y, por tanto, de dejar su herencia genética a las generaciones consecutivas, conduciendo a un proceso en el que la población va evolucionando obteniendo cada vez mejores individuos.

Las técnicas de búsqueda local y algoritmos evolutivos, presentan un especial énfasis en uno de estos componentes de la búsqueda. Las principales diferencias, que suponen tanto ventajas como desventajas, entre los métodos de búsqueda local y algoritmos evolutivos se deben a que los primeros potencian en su búsqueda la explotación de las mejores soluciones, ya que la nuevas soluciones son variaciones de la mejor encontrada hasta el momento, mientras que los algoritmos evolutivos potencian más el factor de exploración, con las nuevas soluciones, al generarse mediante combinación de más de un individuo, presentan mayor diversidad respecto a cualquiera de sus progenitores. Por tanto, el proceso de exploración de vecinos de la búsqueda local permite obtener soluciones precisas de forma muy eficiente, mediante una alta explotación de las soluciones encontradas; mientras que los algoritmos evolutivos como los algoritmos genéticos, al mantener simultáneamente una población de múltiples soluciones, realizan una exploración simultanea de varias regiones, pudiendo obtener una amplia búsqueda en dominios complejos. Según Michalewicz, en el libro escrito el año 1996 titulado “Programas evolucionarios = Algoritmos genéticos + Estructuras de datos”, el uso combinado de un algoritmo evolutivo junto con una búsqueda local posee propiedades beneficiosas al proceso de búsqueda, y ha sido presentado bajo distintos nombres: Algoritmos híbridos, algoritmos genéticos locales, etc. La incorporación de la búsqueda local permite abordar la necesidad de precisión durante todo el proceso. A diferencia de un algoritmo evolutivo, en el que el ajuste fino de las soluciones se produce sólo en las etapas finales, la búsqueda local permite aplicarlo durante todo el proceso de búsqueda. Dentro de la gran variedad de algoritmos híbridos existentes existe una variedad denominada algoritmos meméticos.