John Henry Holland fue un científico norteamericano, profesor de psicología, ingeniería eléctrica y de computación. Fue el pionero de lo que a la postre se llamaría “algoritmos genéticos”. Holland, desde pequeño, se preguntó cómo es que los organismos se hacían cada vez mejores. Muchos años después, ya teniendo un doctorado, salió con la idea de algo que eventualmente se llamó el “algoritmo genético”, partiendo de la base de que todo ocurre por las interacciones locales entre individuos, y entre estos lo que les rodea. Probablemente un libro que tuvo una gran influencia en el científico fue “La teoría genética de la selección natural”, del evolucionista R.A. Fischer. Ahí Holland aprendió que la evolución es una forma de adaptación mucho más poderosa que el aprendizaje simple y a partir de ahí, desarrolló programas para demostrar su idea.
Holland se planteó dos objetivos:
- Imitar de alguna manera los procesos de adaptación de los sistemas naturales
- Diseñar programas, sistemas que podríamos llamara artificiales, que tengan los mecanismos de los sistemas naturales estudiados
El algoritmo genético busca hacer evolucionar una población de individuos, sometiéndola a acciones azarosas, parecidas a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio -probablemente la parte más difícil- en función del cual se decide qué individuos son los mejor adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.
De acuerdo a la Wikipedia:
Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:
- Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.
- Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de “buena” es la solución que se está codificando.
- Condición de término: El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:
- Selección Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
- Recombinación o Cruzamiento La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
- Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
- Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente
John Hollander
Pero ¿cómo aplicar esto en el mundo real de un programa? El siguiente ejemplo, aunque trivial, nos puede ayudar a entender esto.
Dados los dígitos del 0 al 9, y los operadores +,-,* y /, hallar una secuencia que represente un número objetivo. >Los operadores se aplicarán de izquierda a derecha como se van leyendo.
Por ejemplo, dado el número objetivo 23, la secuencia 6+5*4/2+1 sería una posible solución. Si se busca el 75.5, entonces 5/2+9*7-5 sería una posible solución. Nótese que los operadores se aplican de izquierda a derecha y no usando precedencia de operadores.
Teniendo el problema definido, pasamos a codificarlo. Como queremos hacerlo a partir de un algoritmo genético, nuestros cromosomas serán una cadena de bits. Podemos representar los números y sus operadores así:
- 0: 0000
- 1: 0001
- 2: 0010
- 3: 0011
- 4: 0100
- 5: 0101
- 6: 0110
- 7: 0111
- 8: 1000
- 9: 1001
- +: 1010
- -: 1011
- *: 1100
- /: 1101
Los genes 1110 y 1111 no se usan y serán ignorados si son detectados en el algoritmo.
Para la solución ‘6+5*4/2+1’ podemos representar esto como:
0110 1010 0101 1100 0100 1101 0010 1010 0001
6 + 5 * 4 / 2 + 1
Estos son los genes que forman el cromosoma 011010100101110001001101001010100001, que es la solución.
Cabe decir que si hallamos la cadena:
0010 0010 1010 1110 1011 0111 0010
2 2 + ?? – 7 2
estaríamos realmente representando la operación 2 + 7.
Llegamos pues a la parte más difícil, la de hallar una función de aptitud (fitness), la cual se acerque lo más posible al resultado que queremos (el número objetivo). En este proyecto usaremos una puntuación de aptitud que es inversamente proporcional a la diferencia entre la solución y el valor decodificado que representa el cromosoma hallado. Si por ejemplo, el número objetivo es 42, el cromosoma 011010100101110001001101001010100001 tiene una puntuación de aptitud de 1/(42-23) o 1/19. Si la solución se adhiere al valor objetivo, podrías encontrar algo como 1/(42-42), lo cual nos daría una división entre cero. Podemos desde luego considerar este caso para no caer en un error y que el sistema se detenga.
Otro punto importante es el de tener que usar todos los genes en el cromosoma que dé el resultado. Así, si el número objetivo es 42, + 6 * 7 / 2 no da el resultado correcto aunque contenga la subcadena 6 * 7.
Para entender las ideas, no hay mejor idea que intentarlas, siguiendo la máxima adjudicada a Benjamín Franklin: Si me lo dices lo olvido, si me lo enseñas lo recuerdo, si me involucras aprendo. Sin embargo, si se desea experimentar, se puede descargar el código en C, Java o Delphi y ver cómo fue programado (ver referencias).
Como un bono a quien haya llegado hasta este punto, hace tiempo escribí un libro sobre Vida Artificial, recursión y temas afines. En algún momento se explora el algoritmo genético. El libro se puede comprar en formato Kindle por menos de 6 dólares y si lo hacen, se los agradecería. Sin embargo, lo pongo a disposición gratuita por siete días a los primeros 100 lectores que quieran descargarlo. Lo que ocurra primero. Este es el enlace.
Referencias:
AI-Junkie
Wikipedia
Código en Delphi
Código en Java
Código en C