Algoritmos Genéticos
Como estudiante de Ingeniería en Sistema Computacionales he encontrado una gran pasión por el tema de Algoritmos Evolutivos, hace poco tiempo leí una serie de libros relacionados con el tema y tomé nota de esas lecturas. Aquí les presento esas notas con referencias completas de los libros consultados, en esta ocasión el post es enfocado al paradigma más conocido dentro de los algoritmos evolutivos: Algoritmo Genéticos.
Introducción
Durante los últimos treinta años ha crecido el interés en sistemas basados en los principios de la evolución y herencia naturales, para resolver cierto tipo de problemas, dichos sistemas mantienen una población de soluciones potenciales, tienen algún proceso de selección basado en la aptitud de los individuos y algunos operadores “genéticos”. Las Estrategias Evolutivas son un tipo de esos sistemas i.e., algoritmos que imitan los principios de evolución natural para problemas de optimización por parámetros. La programación evolutiva de Fogel es una técnica por búsqueda a través de un espacio de pequeñas máquinas de estados finitos. Otro tipo de sistemas basados en la evolución natural son los Algoritmos Genéticos de Hollman. En 1990 Koza propusó otro tipo de sistemas, la Programación Genética, para buscar el programa computacional más apto para resolver un problema en particular. [1, pp. 1].
Orígenes
Los algoritmos genéticos son una técnica de búsqueda y optimización basada en los principios de la genética y la selección natural.Un algoritmo genético mantiene una población de varios individuos que evolucionan a un estado, bajo reglas especificadas, para maximizar la “aptitud” (i.e., maximizar el costo de una función). [2]Los algoritmos genéticos únicamente maximizan, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero) ,i.e. si el problema es minimizar una función f esto es equivalente a maximizar una función g donde g = -f:
Una definición bastante completa de un algoritmo genético es la propuesta por J. Koza [3, pp. 819]:
Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caractéres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta funci\’on matem\’atica que refleja su aptitud.
Estos algoritmos son muy probablemente los tipo de algoritmos evolutivos más ampliamente conocidos al día de hoy, recibiendo notable atención en todo el mundo. Probablemente el primer predecesor de éstos algoritmos surgió del trabajo de Fraser, un biólogo quien quería simular el proceso de evolución, con especial énfasis en la interacción de la epistasis(Un fenómeno, en el cual, las características de un gen son modificados por uno ó más genes) con selección. Trabajos similares a los de Fraser fueron resumidos por Goldberg [4, pp. 89-103].
Sin embargo, los algoritmos genéticos en su forma usual fueron desarrollados por Holland, científico computólogo y psicólogo de la Universidad de Michigan. En 1975 él resumió su trabajo en “adaptive and reproductive plans” un libro que sirve como el punto inicial de las primeras aplicaciones e implementaciones de algoritmos genéticos [4]. Mientras los biólogos intentaban simular evolución usando algoritmos genéticos, Holland estudiaba como éste tipo de algoritmos podrían ser combinados con problemas que ocurren en campos de aplicación práctica [5, pp. 106-107].
Los AG’s toman prestado cierto vocabulario de la genética. Se habla de individuos (o genotipos) en una población, algunas veces esos individuos son llamados cadenas o cromosomas, esto podría ser un poco confuso, para aclararlo veamos la siguiente explicación:
Cada célula de todo organismo de una especie dada acarrea un cierto número de cromosomas ( el hombre, por ejemplo, tiene 46 de ellos), sin embargo, aquí se hablará de individuos con un solo cromosoma, i.e. cromosomas haploides. Los cromosomas a su vez están formados de genes (también conocidos como características, caracteres ó decodificadores) organizados en sucesión lineal; cada gen controla la herencia de una o más características. Los genes de ciertas características esta colocados en ciertos lugares del cromosoma, a esta posición se le conoce como loci(posición dentro de la cadena).
Cada característica de los individuos (como el color de su cabello) puede manifestarse de diferentes maneras, se dice entonces que el gen puede estar en varios estados, llamados alelos.
Cada genotipo(un único cromosoma) representaría una posible solución a un problema, un proceso de evolución se ejecuta sobre una población de cromosomas correspondientes a una búsqueda a través de un espacio de soluciones potenciales. Por lo que una búsqueda requiere balancear dos objetivos (aparentemente conflictivos): explotar las mejores soluciones y explorar el espacio de búsqueda [6 pp. 61-73].
El Algoritmo Genético Canónico
El AG comienza, como cualquier otra técnica de optimización, definiendo las variables de optimización, la función mediante la cual se evaluarán las variables y el costo. Éste termina también como otros algoritmos de optimización, haciendo pruebas de convergencia. En la fase intermedia, sin embargo, el algoritmo es un poco diferente. En la figura 1 se muestra una ruta a través de los componentes de un algoritmo genético “canónico” o estándar [2, pp. 52].
Estructura general de un algoritmo genético
El siguiente paso es generar una población inicial compuesta por cadenas ó cromosomas de longitud L, generalmente ésta se inicia aleatoriamente, diversas formas de inicializar una población pueden encontrarse en [3]. Cada miembro de dicha población es representado de acuerdo al problema, pero podemos encontrar tres tipos de representaciones comunes [7]:
- Representación Binaria: Cada gen es un valor de 0 ó 1.
- Representación Entera: Cada gen es un valor entero.
- Representación Real: Cada gen es un valor real.
Operadores Genéticos
Después de crear la población inicial, cada cromosoma es evaluado y se le asigna un valor de aptitud. Es importante distinguir entre lo que se conoce como una función de evaluación y una función aptitud; la función de evaluación, o función objetivo, proporciona una medida del desempeño con respecto a un conjunto de parámetros. La función aptitud transforma esa medición en asignación de oportunidades de reproducción para el individuo. La evaluación de una cadena es independiente de la evaluación de cualquier otra cadena. La aptitud, sin embargo, es siempre definida con respecto a otros miembros de la población actual.
Selección
La selección es la etapa del algoritmo genético en la cual individuos o cromosomas se eligen de una población para su posterior reproducción (recombinación y/o cruce).
Fundamentalmente, pueden considerarse 3 esquemas de selección, aunque existe múltiples esquemas distintos a estos, así como innumerables combinaciones de aspectos de estos tres mecanismos fundamentales. A continuación se describe cada uno de ellos:
Ruleta o Seleccion proporcional: Con este método la probabilidad que tiene un cromosoma de reproducirse es proporcional a su valor de función de evaluación, es decir, a su adaptación. Una vez calculadas estas probabilidades, la selección de los individuos para reproducirse es aleatoria según estos valores. El algoritmo propuesto por Goldberg(1989) es el siguiente:
- Construcción de la ruleta: Calcular el valor de aptitud eval(u)
para cada cromosoma de la población actual
(i=1, … , tamp), donde tamp corresponde al tamaño de la población.
- Calcular el valor total de la aptitud de la población
- Calcular la probabilidad de selección
de cada cromosoma
- La ruleta gira tamp veces, cada vez seleccionamos un cromosoma para una nueva población de la siguiente forma:
- Generar un número aleatorio flotante r del rango [0 ... 1].
- Si
entonces seleccionar el primer cromosoma
Obviamente con este algoritmo, algunos cromosomas serán elegidos en distintas ocasiones.
Selección por ranking: Desarrollado por Whitley en 1989, el método consiste en calcular las probabilidades de reproducción atendiendo a la ordenación de la población por el valor de aptitud en vez de simplemente el valor de la función, la aptitud esta definida por:, donde
es la evaluación asociada con el cromosoma i , y
es la evaluación promedio de todos los cromosomas en la población [8]. Una vez realizada esta evaluación, se simula un proceso de selección natural, los individuos son acomodados de acuerdo a la función de aptitud, en esta etapa los mejores individuos son elegidos de la población actual y el resto son eliminados. Esta selección natural ocurre cada generación o iteración del algoritmo. La decisión del número de cromosomas elegidos es algo arbitrario, sin embargo, dejando que solo unos pocos cromosomas sobrevivan para la siguiente generación limita los genes disponibles para producir descendientes, almacenando demasiados cromosomas permite que los cromosomas con baja aptitud reproduzcan sus características en la siguiente generación.
Selección por torneo: Un esquema ideal de selección debería ser simple de codificar, y eficiente para arquitecturas paralelas y no paralelas, más aún, un esquema de selección debería ser capaz de ajustar su influencia de selección acorde a su dominio. El uso de selección por torneo ha ido en incremento debido a que satisface los criterios anteriores[9]. La idea es simple, se elige un número de individuos de una población(normalmente 2, torneo binario), se selecciona el mejor individuo de este grupo para un nuevo procesamiento genético, la selección se realiza tantas veces como se desee (por lo general hasta que a partir de ellos, sea posible realizar el proceso de apareamiento). El método puede aplicarse con reemplazo o sin reemplazo, en el primer caso los individuos seleccionados del actual torneo son candidatos para participar en otro torneos, por otro lado en un torneo sin reemplazo los individuos son seleccionados una sola vez.
Una comparación de complejidad entre estos tres esquemas de selección puede verse en [10].
Operador Mutación
El operador de mutación fue introducido por Holland como un operador que ocasionalmente cambia bits individuales de cromosomas invirtiéndolos, la probabilidad de mutación por bit es muy pequeña en un AG. Algunos valores comúnes son:
y
. En últimos estudios, algunos investigadores formularon algunas reglas heurísticas indicando que el rendimiento es cada vez mayor tanto para poblaciones grandes (tamp > 200) combinadas con una probabilidad de mutación grande
como también para poblaciones de pequeño tamaño
combinadas con una probabilidad de mutación pequeña
.
Valores pequeños de mutaciones, como Holland indica, garantiza que un individuo producido por mutación no difiera demasiado genéticamente de su antecesor. Esta declaración es cierta para el espacio de genotipos, pero como Bäck señala, solo es compatible con una codificación estándar(binaria) no para una representación con números reales [11].
El gen a mutar es seleccionado aleatoriamente del número total de genes (tamp * L) de la población actual.
Recombinación o Cruce
La recombinación es considerado como el operador más importante de los algoritmos genéticos. La idea es que segmentos útiles de diferentes padres podrían ser combinadas con el fin de dar a un nuevo individuo los beneficios de combinaciones de bits de ambos padres. De esta forma, más y más segmentos de aptitud alta se esperan que emergan, finalmente llegando a una total solución [5, pp. 97-106].
La recombinación es claramente un operador sexual(necesita dos cromosomas o individuos para llevarse a cabo) que con una probabilidad selecciona dos individuos padres de la población, los recombina para formar dos nuevos individuos y descarta uno de los resultantes.
Valores comunes de son los propuestos por De Jong(1975) con
y J.J Grefenstette(1985) con una
.
El operador de cruce permite realizar una exploración de toda la información almacenada hasta el momento en la población y combinarla para crear mejores individuos.
El tradicional método de cruce propuesto por Holland se conoce como one-point crossover:
Se elige una posición de cruce 1, … , L-1 dentro de la cadena de bits al azar y se intercambian los bits a la derecha de esa posición entre ambos individuos. Sin embargo, éste método parece ser claramente inferior a los otros métodos con respecto al desempeño de los resultados.
Cruce de n puntos: Es una generalización del método anterior. Se seleccionan varias posiciones (n) en las cadenas de los progenitores y se intercambian los genes a ambos lados de estas posiciones.
Cruce Uniforme: Es radicalmente diferente a la técnica de un punto, cada gen de los descendientes es creado copiando el correspondiente gen de uno o del otro padre, elegido de acuerdo a una máscara de cruce generada aleatoriamente. Cuando existe un 1 en la máscara de cruce, el gen es copiado del primer padre, y cuando la posición de la mascara contiene un 0, el gen es copiado del segundo padre. El proceso es repetido intercambiando a los padres para generar el segundo descendiente. Para cada par de padres se genera una máscara nueva, los descendientes por lo tanto, contienen una mezcla de genes de cada padre. El número de puntos de cruce efectivos no es fijo, pero la media podría ser (donde L) es la longitud de los cromosomas).
Cruce heurístico: Éste operador propuesto por Wright \cite {Wright}, es único debido a las siguientes razones:
- Utiliza valores de la función objetivo para determinar la dirección de la búsqueda
- Produce únicamente un descendiente
- Podría no producir ningún descendiente
El operador genera un descendiente de dos padres
y
de acuerdo siguiente regla:
Donde r es un número aleatorio entre 0 y 1, y el padre no es peor que
, es decir,
para problemas de minimización.
Es posible que el operador genere un descendiente no viable. En tal caso otro valor aleatorio es generado y otro descendiente creado, si después de w intentos una nueva solución viable no es encontrada, el operador no hace más intentos y no produce ningún descendiente.
Después de que el proceso de selección, mutación y recombinación está completo, la siguiente población puede ser evaluada; este proceso formará una generación o ciclo en la ejecución de un algoritmo genético.
En cuanto el criterio de parada, generalmente viene determinado por criterios a priori sencillos, como un número máximo de generaciones o un tiempo máximo de resolución, o más eficientemente por estrategias relacionadas con indicadores del estado de evolución de la población, como por la pérdida de diversidad dentro de la población o por no haber mejora en un cierto número de iteraciones, siendo por lo general una condición mixta lo más utilizado, es decir, limitar el tiempo de ejecución a un número de iteraciones y tener en cuenta algún indicador del estado de la población para considerar la convergencia antes de alcanzar tal limitación.
Hasta Aqui llega esta breve introducción, esperando a que los aliente a meterse más en este campo, para esto les recomiendo un gran sitio del Dr. Carlos Coello actual investigador del CINVESTAV en el IPN y que resolvió algunas de mis dudas.
De antemano me disculpo si por ahí se me fué alguna expresión mal, es dificil trabajar sin LaTeX directamente. Saludos!!
Bibliografía:
[1] Zbigniew Michalewicz. Genetic algorithms + data structures = evolution programs (3rd ed.). Springer-Verlag, London, UK, 1996.
[2] Randy L. Haupt and Sue Ellen Haupt. Practical Genetic Algorithms. Wiley-Interscience, 2004.
[3] John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems). The MIT Press, 1 edition, December 1992.
[4] David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1 edition, January 1989.
[5] John H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992.
[6] L.B. Booker. Improving Search in Genetic Algorithms. Morgan Kaufmann Publishers, 1987.
[7] Rafael Caballero Fern ́ndez. Algoritmos gen ́ticos para la resoluci ́n de problemas de programación por metas entera. aplicación a la economía de la educación.
[8] Darrell Whitley. A genetic algorithm tutorial. Statistics and Computing, 4(2), June 1994.
[9] Brad L. Miller, Brad L. Miller, David E. Goldberg, and David E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9, 1995. [10]Thomas Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, 1996. [11]Alden H. Wright. Genetic algorithms for real parameter optimization. In Foundations of genetic algorithms. Morgan Kaufmann, San Mateo, CA, 1991.
Uno de los mayores problemas que enfrentan las personas con diabetes es la isquemia, complicación asociada a los vasos sanguíneos que impide la circulación adecuada de la sangre, principalmente en las extremidades inferiores del individuo. En consecuencia, es común que se presenten infecciones, en cuyos casos más severos podrían conducir a la amputación.
