Download s3-fmct10 algoritmos evolutivos: caracterización y usos

ALGORITMOS EVOLUTIVOS: CARACTERIZACIÓN Y USOS
Adriana Lara L.a
a
Departamento de Matemáticas de la Escuela Superior de Física y Matemáticas del
Instituto Politécnico Nacional, Edificio 9 UPALM 07730, México D.F.,
[email protected]
RESUMEN
En este trabajo se introducen los conceptos básicos de los Algoritmos Evolutivos en general, mencionando
algunas aplicaciones con especial con énfasis en el enfoque multi-objetivo, también se hace un análisis de las
características de los problemas que son candidatos para ser tratados con estas técnicas.
1. INTRODUCCIÓN
La Computación Evolutiva es un área que surge al tratar de imitar, mediante una computadora que busca
soluciones a un problema de optimización, el proceso observado dentro de la naturaleza para la mejora de las
especies. Los algoritmos a los que hace referencia la Computación Evolutiva son conocidos en general como
Algoritmos Evolutivos y cuentan con varios paradigmas: Los Algoritmos Genéticos, que fueron propuestos
en la década de los 60´s por J. H. Holland [8][9][10] para atacar problemas en el aprendizaje de
computadoras; las Estrategias Evolutivas [6] [7] desarrolladas por Ingo Rechenberg, ahora líder del
Departamento de Biónica en la Universidad Técnica de Berlín, surgieron en 1964 en Alemania durante el
trabajo de un grupo de estudiantes para resolver complejos problemas de Ingeniería. Otros paradigmas,
también muy populares en Computación Evolutiva, son la Programación Genética y la Programación
Evolutiva, para trabajar principalmente con autómatas y programas estructurados.
2. FILOSOFÍA
Los Algoritmos Evolutivos son procedimientos inspirados en los principios de la teoría de la selección natural
de Charles Darwin, los trabajos de Gregor Mendel para la herencia y en general las ideas de la teoría de la
evolución, y los hechos probados que se desprenden de éstos. En estas técnicas:
I. Existen entidades (individuos) las cuales tienen la habilidad de reproducirse con una cierta
probabilidad; cada una de estas entidades representa una solución posible al problema que se desea
resolver. Al reproducirse dichas entidades mezclan las características propias de cada individuo con las
de otros, dando lugar a nuevos individuos cuyas características pueden mejorar, o empeorar, la posible
solución al problema. Este proceso explota la información que se tiene previamente para generar, a
partir de soluciones que ya han resultado ser buenas en términos del problema, nuevas soluciones que
nos acerquen poco a poco al óptimo.
II. A cada una de estas entidades se le asocia una habilidad (aptitud dentro del entorno) mediante la cual
se evalúa su propia supervivencia, e implícitamente la supervivencia de sus genes con el paso de las
generaciones. Esto se relaciona con el valor de la Función Objetivo 1 para la correspondiente
interpretación de la entidad en términos de qué tanto se acerca, o no, a la solución óptima del problema.
III. Existe una población que agrupa a dichas entidades, la cual se renueva generación tras generación bajo
el principio de “supervivencia del más apto”; con base en lo anterior, la Computación Evolutiva espera
una mejora en la solución de nuestro problema después de varias generaciones. Una característica
importante de dicha población es que cuenta con diversidad entre sus entidades, cuyo objetivo es tener
un muestreo representativo del espacio de búsqueda, en otras palabras la diversidad poblacional se
convierte en un mecanismo de “exploración” de posibles soluciones alejadas de las ya conocidas.
Tomando en cuenta estas ideas, e introduciendo algunos otros conceptos biológicos y de inspiración en las
teorías Neo-Darwinistas [2], han sido desarrollados múltiples algoritmos y técnicas con diversas variantes
para aproximar soluciones a un sin fin de problemas donde, en la mayoría de los casos, esta aproximación
llega a ser óptima.
3. DESCRIPCIÓN DE LAS TÉCNICAS
Los paradigmas asociados a la Computación Evolutiva han tenido diversas vertientes. Aquí presentamos
características que son comunes a la mayor parte de ellos con el fin de ejemplificar los principios básicos de la
filosofía en que estas técnicas se apoyan; haciendo algunas adaptaciones particulares a estos principios se
puede dar lugar a una gran cantidad de algoritmos. Los Algoritmos Evolutivos comienzan con una población
inicial de individuos, los cuales “evolucionan” generación tras generación aproximándose, paso a paso, a un
individuo que mejora respecto a las características en que está basada su supervivencia dentro del entorno.
Los problemas que son candidatos a tratarse mediante estas técnicas deben cumplir, entre otras cosas, lo
siguiente: Las posibles soluciones de dicho problema deben poder representarse en forma de estructuras
manejables por una computadora, es decir, cadenas binarias, números o arreglos, cadenas de caracteres o en
general algún tipo de estructura de datos. La representación es importante, de ello depende entre otras cosas
que el valor óptimo pueda alcanzarse o solo aproximarse, puesto que la representación está íntimamente
relacionada con el espacio de soluciones que se espera analizar [5]. Así, cada una de estas soluciones
representa un individuo, el cual puede tratarse de manera directa como se modeló matemáticamente dentro de
la computadora, o indirectamente mediante alguna otra codificación especial que se le asocie; por ejemplo: en
un Algoritmo Genético el vector (30, 20) puede verse como una posible solución, no necesariamente óptima,
al problema de maximización de la función F(x,y) = sen(x)+2cos(y), dentro de un cierto rango para valores de
x y de y, en este caso se diría que el vector (30,20) es el individuo y su cromosoma o codificación genética
puede ser la cadena binaria 000011110000010100 (ver figura 1). Esta doble representación puede ser
interpretada como la representación “fenotípica”, que serían las características visibles del individuo y la
representación “genotípica”, que sería la codificación genética del individuo; en donde la cadena binaria que
representa a cada una de las variables se ve como un gen y cada bit (cero o uno) se ve como un alelo de dicho
gen.
Figura 1: Cromosoma del individuo a = (20, 30), dos genes con 9 alelos cada uno.
Algunas representaciones de Algoritmos Genéticos utilizan cadenas de caracteres u otras estructuras de datos
para representar a sus cromosomas, mientras que otros tipos de Algoritmos Evolutivos denotan a los
individuos directamente con el modelado numérico de soluciones, usando una sola representación sin
“codificación genética”. También dentro de la Computación Evolutiva hay enfoques que tratan con individuos
que al codificarse representan estructuras más complejas como pueden ser autómatas [13] circuitos eléctricos
[11] o programas [12].
La población de nuestro algoritmo será entonces el conjunto de individuos que por sí mismos representan
una solución posible al problema. En términos de implementación la población es un arreglo de datos en el
1
En el área conocida como Optimización, la Función Objetivo cuantifica la relación que existe entre las
variables del problema; dicha relación se representa en términos de una función matemática que puede
maximizarse o minimizarse, según sea el caso.
cual se guardan de manera ordenada las cadenas de información genética de todos y cada uno de los
individuos, es decir los valores codificados, o no codificados, de un conjunto de posibles soluciones.
Los operadores genéticos son procedimientos que manipulan la información genética de la población para
producir nuevos individuos, producto de variaciones en los individuos de la población original. Los
operadores genéticos usados comúnmente son la mutación y la recombinación.
La Mutación puede verse como la perturbación sobre uno o más alelos (ver figura 1) de la cadena genética
del individuo; al ser un cambio aleatorio, nos transporta hacia una región del espacio de búsqueda diferente a
donde se encuentra el individuo original; esto nos ayuda a evitar que la búsqueda de soluciones se estanque en
algún óptimo local, es por eso que se dice que la mutación es el procedimiento del algoritmo que se dedica a
la exploración del espacio de búsqueda.
La mutación se puede implementar de diversas formas en diferentes Algoritmos Evolutivos, por ejemplo, en
el Algoritmo Genético, donde se usa representación binaria, dado el individuo cuyo cromosoma es
000011110000010100, se pueden producir los siguientes individuos resultados de mutaciones:
Cromosoma original:
000011110000010100
000011110000010100
Cromosoma con mutación:
001011110000010100
000011110000000101
De esta manera se puede cambiar uno o más alelos dentro de uno o más genes del cromosoma. Otro ejemplo
de mutación es el que se utiliza en las Estrategias Evolutivas, en donde dado un vector ē, en un espacio de
dimensión n, se obtiene un nuevo vector ē’ después de la adición de ruido mediante un vector de números
Gaussianos, con una media de cero y un vector controlado de desviación estándar. La mutación de uno o más
genes dentro de un cromosoma debe darse de manera esporádica, imitando a la naturaleza, pues este
mecanismo sirve para dar “saltos” grandes de una región a otra del espacio de búsqueda dando la oportunidad
a otros individuos, considerablemente diferentes a los actuales, de ser evaluados y aportar algunos de sus
genes a la población. Para controlar la frecuencia de mutaciones dentro de una población se utiliza una
función de probabilidad dentro de las generaciones, que puede irse alterando durante la búsqueda2, otra forma
de control puede introducirse determinando qué tan bruscas son las mutaciones, es decir qué tanto cambia el
gen en cada mutación lo que resulta en qué tan lejos se encuentra la nueva solución de la original. Debido a
que se introduce este operador de exploración la teoría de los algoritmos evolutivos establece que es necesario
implementar el concepto de elitismo3, de manera apropiada dependiendo del algoritmo, para garantizar la
convergencia a una solución suficientemente buena en un número finito de iteraciones del algoritmo.
La Recombinación, también conocida como cruza, es el procedimiento mediante el cual se mezclan los
genes de dos o más4 individuos, vistos como los padres, formando cadenas de cromosomas que dan origen a
nuevos individuos preservando presumiblemente los “buenos” genes que los han llevado a mejorar en
términos de la solución del problema. La recombinación es el procedimiento del algoritmo que se dedica a la
explotación de las zonas más prometedoras dentro del espacio de búsqueda. Por ejemplo, los individuos (0,0)
y (1,1) pueden recombinarse para formar a los descendientes (1,0) y (0,1) cuyos genes son una mezcla de los
genes de sus antecesores.
Una vez que se aplican los operadores genéticos a la población, es necesario determinar el conjunto de
individuos que formarán parte de la siguiente generación (ver figura 2), es decir, debe realizarse un proceso
de selección en el cual pueden, en principio, intervenir solo los individuos que resultaron de la aplicación de
los operadores genéticos a la población original o puede también hacerse una selección de entre la unión de
estos últimos con los individuos originales.
Cada uno de los individuos, es decir las soluciones posibles del problema, cuenta con un valor que determina
su aptitud de supervivencia ante el entorno. Dicho valor determina qué tan bueno es el individuo como
solución al problema en cuestión. A la determinación de estos valores se le conoce como “evaluación de la
2
Al ajuste de ciertos parámetros para guiar la búsqueda durante la ejecución del algoritmo, en función del
éxito que están teniendo las soluciones generadas, se le llama “auto-adaptación”.
3
El elitismo consiste en mantener siempre a la mejor solución independientemente del cambio generacional.
4
Normalmente se utilizan solo dos padres para la generación de los descendientes, de manera que se asemeje
a lo que ocurre en la naturaleza.
Función de Aptitud”; dado que el proceso de selección toma en cuenta esta función, en esta parte del
algoritmo, se imita el principio natural de supervivencia del más apto. Por lo dicho anteriormente, la Función
de Aptitud estará relacionada, de alguna manera, con la Función Objetivo del problema estudiado; de manera
que mientras mejor se optimiza dicha Función Objetivo con una cierta solución, el individuo tendrá mejor
aptitud para sobrevivir a lo largo de las generaciones. Una generación es como se interpreta cada iteración del
programa.
Para el proceso de selección existen muchas convenciones y técnicas diferentes que se han usado y estudiado
tanto en general como en problemas específicos. Los operadores se implementan de acuerdo a las
características del problema y al tipo de Algoritmo Evolutivo que se está utilizando en particular.
Entre las desventajas de los algoritmos aquí presentados se encuentra el poco conocimiento “a priori” para la
elección de los parámetros tales como: número de generaciones, probabilidades de mutación, tamaño de la
población etc., al igual que en la elección del tipo de cruza, mutación y selección para un problema en
particular.
Figura 2: Ciclo evolutivo del algoritmo
4. APLICACIONES Y ENFOQUE MULTI-OBJETIVO
Los Algoritmos Evolutivos, durante más de tres décadas, han sido aplicados en casi cualquier área del
quehacer humano que implique optimizar una función matemática. Después de un generalizado uso a lo largo
de todo el mundo se observó que los Algoritmos Evolutivos son candidatos naturales para atacar problemas
de optimización con más de una Función Objetivo, puesto que en este tipo de problemas la solución no se
resume a encontrar un único resultado óptimo sino en hallar una colección de valores maximales a la vez, esto
es porque algunas de las funciones objetivo pueden estar en conflicto unas con otras; los algoritmos
evolutivos se acoplan bien en este aspecto [4] ya que ellos procesan de manera simultánea una población de
individuos, los mismos que representan soluciones mejorables a cada generación. Al final de la ejecución del
Algoritmo Evolutivo la población resultante representa una buena aproximación a la solución del problema 5,
misma que puede usarse directamente para la posterior aplicación de técnicas en el área de Toma de
Decisiones.
En la vida real es complicado trabajar con problemas que no pueden caracterizarse algebraicamente o
analíticamente, problemas cuya caracterización resulta muy compleja, que tienen una Región Factible 6
geométricamente inusual, o cuyo espacio de búsqueda simplemente es muy grande. Este tipo de
complicaciones se extiende con creces al caso de problemas multi-objetivo, elevando la complejidad, sin
embargo las mencionadas características que hacen a estos problemas difíciles de manejar, con técnicas
clásicas de optimización, no representan problema alguno para los Algoritmos Evolutivos. Actualmente
podemos encontrar un número considerable de aplicaciones de los Algoritmos Evolutivos en problemas multiobjetivo [3], así como retos y avances tangibles dentro del área [1].
5
La solución de un problema multi-objetivo se conoce, en las áreas de Investigación de Operaciones y
Optimización Multi-objetivo, como el “Óptimo de Pareto”.
6
Se le llama Región Factible al espacio dónde radican las soluciones posibles del problema.
6. CONCLUSIONES
Existen varias razones para el uso de Algoritmos Evolutivos, podemos mencionar que éstos emplean el poder
de cómputo actual para aproximar o encontrar soluciones óptimas a diversos problemas, tanto de uno como de
múltiples objetivos, para los cuales no existen métodos matemáticos conocidos que nos lleven a la solución
óptima o en los que otros métodos comunes, por las características propias del problema, han fallado o no son
factibles de utilizarse. Como en el caso de otras heurísticas, estos algoritmos son útiles para problemas donde
el espacio de búsqueda es muy amplio, aunque por supuesto acotado; las ventajas de los Algoritmos
Evolutivos sobre otras heurísticas radica en que no es necesario tener gran conocimiento previo respecto al
espacio de búsqueda, ni que dicho problema cumpla condiciones de continuidad o derivabilidad en sus
funciones objetivo o en sus restricciones, tampoco es necesario que éstas sean sencillas de evaluar para un
humano. Entre los problemas apropiados para resolver con Algoritmos Evolutivos se encuentran aquellos en
los que la Región Factible no se puede caracterizar de manera sencilla, no cumple condiciones de convexidad
o no se cuenta previamente con la información, referente a ella, necesaria para aplicar otras técnicas. Existen
diversas fuentes de información para el estudio de los Algoritmos Evolutivos, artículos tanto teóricos como de
aplicaciones prácticas pueden encontrarse en “Evolutionary Computation (MIT Press Journal)” y “IEEE
Transactions on Evolutionary Computation” entre otras. Existen libros y repositorios electrónicos de
información relacionada, así como diversos congresos: GECCO, CEC, FOGA, etc., especializados en
Computación Evolutiva y temas relacionados con ella.
BIBLIOGRAFÍA
1. Ajith Abraham, Lakhmi C. Jain, Robert Goldberg (editors), “Evolutionary Multiobjective
Optimization: Theoretical Advances and Applications”, Springer 2005.
2. A. Hoffman, “Arguments on Evolution: A Paleontologist’s Perspective”. Oxford University Press,
New York, 1989.
3. Carlos A. Coello Coello & Gary B Lamont, “Aplications of Multiobjective Evolutionary
Algorithms”, Advances in Natural Computation. Vol. 1, 2004.
4. Carlos A. Coello Coello, “A comprehensive survey of evolutionary-based multiobjective
optimization techniques”, Knowledge and Information Systems, 3(1):269-308, August 1999
5. Carlos A. Coello Coello “La importancia de la representación en los Algoritmos Genéticos parte I”,
Soluciones Avanzadas, Tecnologías de la Información y Estrategias de Negocios, Año 7, No. 69, pp.
50-56, 15 de mayo 1999.
6. I. Rechenberg “Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der
Biologischen Evolution”, Frommann-Holzboog, Stuttgart, Alemania, 1973.
7. I. Rechenberg “Evolution Strategy” in Computational Intelligence Imitating Life. J. M. Zurada, R. J.
Marks II and C. J. Robinson (editors), New York: IEEE Press, 147-159.
8. J. H. Holland, “Adaptation in Natural and Artificial Systems”, Ann Arbor, MI:University of
Michigan Press, 1975.
9. J. H. Holland, “Adaptation in Natural and Artificial Systems”, Cambridge, MA: MIT Press.
10. J. H. Holland, “Genetic Algorithms”, Scientific American 267(1):66-72.
11. John R. Koza, Sameer H. Al-Sakran, Lee W. Jones, "Cross-Domain Features of Runs of Genetic
Programming Used to Evolve Designs for Analog Circuits, Optical Lens Systems, Controllers,
Antennas, Mechanical Systems, and Quantum Computing Circuits," eh, pp. 205-214, 2005
NASA/DoD Conference on Evolvable Hardware (EH'05), 2005.
12. Lawrence J. Fogel. “Artificial Intelligence through Simulated Evolution. Forty years of Evolutionary
Programming” John Wiley & Sons, Inc., New York, 1999.
13. Peter J. Angeline, David B. Fogel, Lawrence J. Fogel: A Comparison of Self-Adaptation Methods
for Finite State Machines in Dynamic Environments. Evolutionary Programming 1996: 441-449.