El algoritmo genético simple (AGS)

En el libro Mathematical Foundations of Programming, Holland propone una manera de seleccionar individuos y de cruzarlos. Actualmente existen muchas otras propuestas, pero las de Holland constituyen aún hoy la base de muchos desarrollos teóricos y prácticos en el área. Goldberg en "On Computable Numbres with Application to the Entscheidungsproblem" publicado en Proceedings of the London Mathematical Society, retomó el algoritmo de Holland y lo popularizó llamándolo algoritmo genético simple (AGS). En éste se considera que los códigos genéticos están en binario. Explicado con detalle el proceso de un AGS es:

1. Decidir cómo codificar el dominio del problema.
2. Generar un conjunto aleatorio (población inicial) de N posibles soluciones codificadas al problema. A ésta se le llamará la población actual.
3. Calificar cada posible solución (individuo) de la población actual.
4. Seleccionar dos individuos de la población actual con una probabilidad proporcional a su calificación.
5. Lanzar una moneda al aire (con probabilidad pc cae cara).
6. Su cayó cara mezclar los códigos de los dos individuos seleccionados para formar dos híbridos, a los que llamaremos nuevos individuos.
7. Si cayó cruz llamamos a los individuos seleccionados nuevos individuos.
8. Por cada bit de cada nuevo individuo lanzar otra moneda al aire (con probabilidad pm cae cara).
9. Si cae cara cambiar el bit en turno por su complemento.
10. Si cae cruz el bit permanece inalterado.
11. Incluir a los dos nuevos individuos en una nueva población.
12. Si la nueva población tiene ya N individuos, llamarla población actual y regresar al paso 3, a menos que se cumpla alguna condición de terminación.
13. Si no, regresar al paso 4.

En el algoritmo se utiliza el término "lanzar una moneda al aire" para decir un experimento de Bernoulli (aquel en el que pueden ocurrir exclusivamente dos eventos posibles, uno con probabilidad p y otro con probabilidad 1-p). Es decir, el lanzamiento de una moneda "extraña" en la que no necesariamente ambas caras son equiprobables.

La condición de terminación, a la que se hace referencia en el paseo 12, puede definirse de muchas maneras. Se puede fijar un número máximo de generaciones que se pretende ejecutar el algoritmo, o puede decidirse hacer alto cuando la mayoría de la población, digamos el %85, tenga una calificación que este dentro de 0.6 desviaciones estándar de la media. En fin, opciones hay muchas. Generalmente depende del problema o de las preferencias personales la decisión acerca de cuándo es conveniente detenerse.

Algoritmos genéticos parte III

Cruzamiento.

En el contexto de los algoritmos genéticos reproducirse significa que, dados dos individuos seleccionados en función de su grado de adaptación, éstos pasen a formar parte de la siguiente generación o, al menos, mezclen sus códigos genéticos para generar hijos que posean un código híbrido. Es decir, los códigos genéticos de los individuos se cruzan. Existen muchos mecanismos de cruzamiento todos ellos tienen por objeto que el código de un individuo A y el de un individuo B, previamente seleccionados, se mezclen, es decir, se fragmenten y recombinen para formar nuevos individuos con la esperanza de que éstos hereden de sus progenitores las características deseables. El mecanismo de cruzamiento más común es el llamado cruzamiento de un punto.

Mutación.

Algunas veces, muy pocas de hecho, la ADN-polimerasa (la enzima encargada de replicar el código genético), se equivoca y produce una mutación, una alteración accidental en el código genético de los seres vivos.

Ocasionalmente algunos elementos del código de ciertos individuos de un algoritmo genético se alteran a propósito. Éstos se seleccionan aleatoriamente en lo que constituye el símil de una mutación. El objetivo es generar nuevos individuos, que exploren regiones del dominio del problema que probablemente no se han visitado aún. Esta exploración no presupone conocimiento alguno, no es sesgada. Aleatoriamente se buscan nuevas soluciones posibles que quizá superen las encontradas hasta el momento. Esta es una de las características que hacen aplicables los algoritmos genéticos a gran variedad de problemas: no presuponer conocimiento previo acerca del problema a resolver ni de su dominio, no sólo en la mutación sino en el proceso total. De hecho, el problema a resolver sólo determina la función de evaluación y la manera de codificar las soluciones posibles (la semántica de los códigos genéticos de los individuos). El resto de los subprocesos que constituyen el algoritmo son independientes y universalmente aplicables.

Algoritmos genéticos parte II

Evaluación de la población

Al igual que en la naturaleza, en los algoritmos genéticos es necesario establecer algún criterio que permita decidir cuáles de las soluciones propuestas en una población son mejores respecto del resto de las propuestas y cuáles no lo son. Es necesario establecer, para cada individuo, una medida de desempeño relativa a la población a la que pertenece.

Para determinar cuáles de estos individuos corresponden a buenas propuestas de solución y cuáles no, es necesario calificarlos de alguna manera. Cada individuo de cada generación de un algoritmo genético recibe una calificación o, para usar el término biológico, una medida de su grado de adaptación (fitness). Éste es un número real no negativo tanto más grande cuanto mejor sea la solución propuesta por dicho individuo. El objetivo de este número es que permita distinguir propuestas de solución buenas de aquellas que no lo son. Si el problema a resolver consiste en maximizar una función, entonces la calificación asignada a un individuo determinado debe indicar que tan alto es el valor de la función en el elemento de su dominio codificado por el individuo. Si, en cambio, el problema es determinar la ruta más corta entre dos puntos, la calificación deberá ser tanto más alta cuanto más corto sea el camino codificado en el individuo que esté siendo calificado.

Evidentemente, al hablar de que a cada individuo de la población se le asigna una y sólo una calificación, se está hablando de una función que se denomina función de adaptación, cuya evaluación puede no ser sencilla y es, de hecho, lo que en la mayoría de los casos consume más tiempo en la ejecución de un algoritmo genético. Hay que tener en cuenta que se evalúa una vez en cada individuo de cada generación. Si un AG es ejecutado con una población de tamaño 1000 durante 100 generaciones, la función es evaluada 10,000 veces. Además, puede darse el caso de que la función de evaluación no tenga una regla de correspondencia explícita, esto es, una expresión algebraica, y puede ocurrir incluso que la función cambie de generación en generación.

Selección.

Una vez calificados todos los individuos de una generación, el algoritmo debe, al igual que lo hacen la naturaleza y el hombre, seleccionar a los individuos más calificados, mejor adaptados al medio, para que tengan mayor oportunidad de reproducción. De esta forma se incrementa la probabilidad de tener individuos "buenos" (con alta calificación) en el futuro. Si de una determinada generación de individuos se seleccionaran sólo aquellos con una calificación mayor o igual que cierto número c para pasarlos a la siguiente generación, es claro que en ésta la calificación promedio superará c y por tanto al promedio de la generación anterior. La selección ocasiona que haya más individuos buenos, explota el conocimiento que se ha obtenido hasta el momento, procurando elegir lo mejor que se haya encontrado, elevando así el nivel de adaptación de toda la población.

En principio podría parecer que es conveniente tener una estrategia de selección estricta para que mejore rápidamente la población y converja el algoritmo, es decir, que la población se acumule alrededor de una genotipo óptimo. Esto no es cierto. Lo que ocurrirá es que la población se acumulará rápidamente alrededor de algún individuo que sea bueno, comparativamente con el resto de los individuos considerados a lo largo de la ejecución del algoritmo, pero este individuo puede no ser el mejor posible. A esto se le suele llamar convergencia prematura. No se puede asegurar pero sí procurar que lo anterior no ocurra. Además de la explotación es necesario que exista exploración. El AG debe, no sólo seleccionar de entre lo mejor que ha encontrado, sino procurar encontrar mejores individuos. A esto se dedican los operadores que serán descritos a continuación, los que aseguran que en todo momento exista cierto grado de variedad en la población, procurando con ello que no se "vicie".

En la estrategia de selección normalmente se incluye un elemento extra que sirve de "ancla". Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este individuo se pierda y no forme parte de la siguiente generación. Para evitar lo anterior se fuerza la selección de los mejores n individuos de la generación para pasar intactos a la siguiente. A esta estrategia se le denomina elitismo y puede ser generalizada especificando que permanezcan en la población los n mejores individuos de las pasadas k generaciones.

Algoritmos genéticos

Un poco de biología.

Cada individuo de cada una de las especias que habitan en nuestro planeta poseen ciertas características que lo identifican. Si hablamos de seres humanos, cada uno posee cierta estatura, cierto color de ojos y de cabello y cierto tipo sanguíneo, entre otras muchas. Estas características "externas", aunque algunas de ellas no se puedan ver, como el tipo sanguíneo, constituyen lo que se denomina el fenotipo de un individuo. Cada una de estas características es igual a la correspondiente de alguno de los antecesores del individuo, es decir, nos son dadas por herencia, o por lo menos nos es dada cierta predisposición a ella (como la diabetes, por ejemplo). El fenotipo es resultado de la interacción del medio ambiente en que se desarrolla un individuo y la herencia que éste recibe de sus ancestros. La herencia impone ciertos límites o predisposiciones que, al sumarse con el medio, generan el fenotipo. A veces el medio no importa, por ejemplo, no puede intervenir en nuestro color de ojos (hasta donde mi conocimiento sabe), pero en otras influye de manera determinante. Si se posee cierta predisposición a padecer enfermedades cardiovasculares pero se tiene una excelente condición aeróbica desde pequeño, posiblemente éstas nunca se padezcan. El fenotipo de cada individuo está determinado por las proteínas que produce, y esto a su vez está definido en la información genética de cada una de sus células.

La información acerca de cuáles proteínas se producirán está contenida en los cromosomas del individuo. En cada célula somática (aquellas que constituyen el organismo) existen dos juegos de cromosomas que definen las mismas características; un juego es aportado del padre del individuo y el otro lo es de la madre. Un ser humano posee 23 pares de cromosomas.

Hay células especiales llamadas gametos, que intervienen en la reproducción (los espermatozoides y los óvulos humanos pertenecen a esta categoría). Los gametos no se reproducen por mitosis como el resto de las células, el proceso de división se llama en este caso meiosis. En la mitosis las ćelulas producidas son diploides, mientras que en la meiosis el resultado, los gametos, son haploides, sólo tienen un juego de cromosomas.

Partiendo de una célula diploide el proceso meiótico se realiza de la siguiente manera:

1. Se duplica el número de cromosomas en la célula, esto es, se hace una copia de cada cromosoma. Al final quedan dos juegos correspondientes al padre y dos a la madre.
2. Se cruzan un juego de cromosomas del padre con uno de la madre, formándose dos juegos de cromosomas híbridos. El resultado es un juego de cromosomas puros del padre, un juego puro de la madre y dos juegos de cromosomas híbridos.
3. Se divide la célula dos veces y al final del proceso quedan cuatro células haploides: una con cromosomas puros del padre, una con cromosomas puros de la madre y dos con cromosomas híbridos.

Algoritmos genéticos.

En la naturaleza las características de los seres vivos, incluso aquéllas que los hacen óptimos para habitar en su medio, están determinadas por las proteínas que producen. A su vez, como hemos visto, estas proteínas (o más bien, los aminoácidos que las forman) se codifican en el material genético contenido en cada una de las células del individuo. Así pues, la naturaleza ha mapeado cada posible solución al problema de crear un individuo óptimo en una secuencia particular de bases que producirá ciertas proteínas, ha codificado el dominio del problema (todos los posibles individuos) mapeándolo al conjunto de todas las posibles secuencias de nucleótidos.

Así, para un algoritmo genético lo primero que se requiere es determinar en qué espacio se encuentran las posibles soluciones al problema que se pretende resolver. En caso de tener un problema de optimización de una función cuyo dominio es un subconjunto de los números reales, entonces este subconjunto es al que nos referimos. Pero el algoritmo opera sobre "códigos genéticos", sobre genotipos que se deberán mapear al espacio de soluciones. Es decir, es necesario codificar de alguna manera el dominio del problema para obtener estructuras manejables que puedan ser manipuladas por el AG (algoritmo genético). Cada una de estas estructuras constituye el equivalente al genotipo de un individuo en términos biológicos. El elemento del dominio del problema al que se mapea este genotipo es el análogo al fenotipo. Es frecuente que el código de los elementos del dominio del problema utilice un alfabeto binario (0 o 1).

Una vez que se ha definido la manera de codificar los elementos del dominio del problema y se conoce la forma de pasar de un elemento a su código y viceversa, es necesario fijar un punto de partida. Los algoritmos genéticos manipulan conjuntos de códigos en generaciones sucesivas. Nuevamente haciendo una analogía, manipulan poblaciones de códigos. En éstas un código puede aparecer más de una vez. El algoritmo se encargará de favorecer la aparición en la población de códigos que correspondan a elementos del dominio que estén próximos a resolver el problema. En resumen, el algoritmo recibirá como entrada una población de códigos y a partir de ésta generará nuevas poblaciones, donde algunos códigos desaparecerán mientras que otros, que se mapean en mejores soluciones posibles, aparecen con más frecuencia hasta que se encuentra una satisfactoria o hasta que se cumple alguna otra condición de terminación. Para establecer una base nemotécnica, los códigos en una población, es decir, los elementos de ésta serán llamados individuos y a los códigos en general, ya no en el contexto exclusivo de una población, se les denominará indistintamente cromosomas, genotipo, genoma o código genético, por analogía con los términos biológicos de donde surgen.

Computación evolutiva

¡Hola a todos!, esta es mi primera entrada en el blog de este año (ya se que es muy tarde pero no había tenido tiempo para escribir esta entrada), les traigo aquí unas notas que tomé de mi curso de computación evolutiva espero sean de su agrado.

La computación evolutiva constituye un conjunto de técnicas heurísticas utilizadas para resolver problemas de diversos tipos, en los que podemos encontrar comúnmente problemas de búsqueda y optimización. La característica principal de estos problemas es la gran cantidad de variables que pueden estar involucradas junto con un enorme espacio de posibles soluciones, a veces tan grande como el número de átomos que constituyen el universo.

Los mecanismos de estos algoritmos se inspiran en el proceso de la evolución biológica, se retoman conceptos como genotipo y fenotipo, los cuales son los principales componentes de la unidad fundamental "el individuo", y como motor de variabilidad se identifican procesos genéticos como la reproducción y la mutación, así como la adaptabilidad del individuo en su entorno.

Estas técnicas se han aplicado en distintas disciplinas y ramas del conocimiento desde aplicaciones en inteligencia artificial hasta problemas en ingeniería, debido a que es posible encontrar soluciones relativamente buenas en un periodo corto de tiempo.

Aquí les ofrezco una pequeña introducción a la computación evolutiva, donde les mostraré los fundamentos, teoría y aplicaciones de las principales técnicas evolutivas como son: los agoritmos genéticos, estrategias evolutivas, programación evolutiva y programación genética.