ALGORITMOS GENÉTICOS PARA RESOLVER PROBLEMAS DE BÚSQUEDA
Un enfoque de los principios y mecanismos de evolución genética para resolver problemas de búsqueda y optimización.
Autores: Sandra Rosa Arroyo Paredes, Gladys Choque Ulloa, Redy Rivas Idme
Aumentar la rentabilidad, la eficacia de un proceso o reducir gastos son problemas de negocio que pueden interpretarse como un problema de optimización. La computación evolutiva nos brinda algoritmos de optimización inspirados en procesos biológicos, tal como la evolución genética. Esta consiste en alcanzar una solución a un problema partiendo de un conjunto inicial de soluciones o individuos, llamado población. Cada uno de estos individuos representa una posible solución al problema. Estos individuos evolucionarán y se adaptarán en mayor medida tras el paso de cada generación a la solución mas óptima, tomando como base los esquemas propuestos por científicos como Darwin sobre la selección natural [1].
Evolución y mecanismos evolutivos
Los principios básicos de la evolución genética se basan cronológicamente en las siguientes observaciones:
Propuesta de un ancestro común entre hombres y simios (Lecrerc).
Enunciado de la primera teoría evolutiva, la cual enfatiza la influencia de la naturaleza en el cambio o las características de las especies (Lamarck).
Propuesta de la teoría evolutiva más aceptada, donde se desarrolla el principio de variación, herencia y selección (Darwin).
Planteamientos sobre la herencia genética (Mendel).
Desarrollo de la teoría de la herencia genética, basada en células germinales lo que actualmente se conocen como cromosomas (Weissman).
Estos principios evolutivos desarrollados por diferentes científicos, han dado pase a la definición de los siguientes mecanismos evolutivos que son fundamentos base en la configuración de los parámetros de los algoritmos genéticos:
Co-evolución: evolución conjunta de dos o más especies tanto mutualista y depredador-presa, que se influyen mutuamente.
Selección natural: proceso mediante el cual algunos individuos de una población son seleccionados para reproducirse, generalmente en base a su aptitud.
Mutación: generados por errores de copiado o influencias externas, como exposición a sustancias químicas o radiación. Es una forma de generar diversidad, pero difícil de predecir si tendrá impacto positivo o negativo en las especies.
Migración: se genera en una especie cuando sufre separación geográfica durante un tiempo largo y sus genes divergen.
Deriva genética: el fin de la diversidad en los cromosomas puede llevar a la completa extinción de una especie. El exceso de ciertos alelos en los sobrevivientes pueden generar que los alelos subrepresentados sean eliminados.
A finales de la década de los 60, John Holland desarrolló una técnica que imita en su funcionamiento la selección natural, dejando la interpretación metafórica [2] representada en la Figura 1.
Figura 1. Interpretación de la Computación evolutiva, partiendo de las teorías de la Evolución natural.
En la evolución natural, se considera un ambiente que soporta una cantidad limitada de individuos que luchan por la supervivencia y reproducción, de generación en generación. Los cuales son influenciados por condiciones de adaptación, determinados por el entorno donde viven, y se relacionan con la capacidad de alcanzar sus objetivos de supervivencia y reproducción.
En la computación evolutiva, se considera una cantidad limitada de posibles soluciones que deben evaluarse y reducirse buscando soluciones óptimas, de iteración en iteración. Dichas soluciones candidatas serán evaluadas considerando funciones objetivos que permitan llegar a la calidad de solución requerida.
¿Qué son los algoritmos genéticos?
“Los Algoritmos Genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas” [3].
Proceso de análisis de un algoritmo genético
Figura 2. Estructura o flujo del algoritmo genético, considerando la terminología de las teorías de evolución genética.
Interpretación en un caso práctico
Para un negocio de supermercados, un problema es expandirse con una cadena de tiendas a un nuevo país, asegurando localizaciones óptimas entre ellas. Los encargados del área de expansión han investigado diferentes zonas de donde han encontrado 60 opciones tienda. Han extraído información sobre la cantidad de habitantes a la redonda que puedan ir caminando ha realizar sus compras y las distancias máximas (coordenadas geográficas) entre las posibles tiendas. Esta información es entregada para su análisis y obtención de la combinación mas óptima de la futura cadena de 10 tiendas que permita asegurar la máxima cantidad de clientes y asi mismo cubrir distancias máximas entre cada posible tienda.
Para resolver este problema con algoritmos genéticos podemos realizar la siguiente interpretación:
Población inicial, se puede partir con 100 soluciones iniciales.
Características del individuo (cromosoma), seria un arreglo de 60 elementos (cantidad de opciones de tiendas) y de donde 10 de ellos serán elegidos (cantidad de tiendas que la empresa aperturará).
Evaluación considerando las funciones objetivos de asegurar la máxima cantidad de clientes y el cubrir distancias máximas entre las tiendas.
Considerando la estructura del algoritmo genético de la Figura 2, se partiría de una población inicial de 100 soluciones iniciales, donde cada uno de ellos es representado por cromosoma. Dicho cromosoma es representado por un arreglo de 60 elementos y que según las características deseadas solo 10 de ellos tomarían el valor de 1 si es que a tienda es elegida y 0 si no lo es. Estas soluciones pasarían por múltiples generaciones, siendo cada una de ellas se evaluadas en base a las funciones objetivos requeridas, así mismo se pueden aplicar cruzamiento y/o mutación entre las soluciones para agregar mayor diversidad, y seguir realizando este procedimiento por mas generaciones hasta encontrar la solución mas optima.
Conclusión
Los algoritmos genéticos están indicados para resolver todo tipo de problemas que se puedan expresar como un problema de optimización donde definamos una representación adecuada para las soluciones y función a optimizar. Estos algoritmos dependen de muchos parámetros, que según cada problema pueden direccionar o no a resultados óptimos, por lo que la exploración es sumamente importante.
"La naturaleza se ocupa de lo que funciona. La naturaleza propaga lo que sobrevive. Tiene poco tiempo para la contemplación erudita, y nos hemos unido a ella en su búsqueda expeditiva de la mejora" David E.Goldberg [3].
Referencias
[1] Darwin, C. (1859). On the Origin of Species by Means of Natural Selection. John Murray, London.
[2] Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. Republished by the MITpress, 1992.
[3] Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning.