Algoritmo genético

Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes 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, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados. Los algoritmos genéticos se enmarcan dentro de los algoritmos evolutivos, que incluyen también las estrategias evolutivas, la programación evolutiva y la programación genética.

Funcionamiento

Los algoritmos genéticos funcionan entre el conjunto de soluciones de un problema llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados los genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), son generadas aplicando los operadores genéticos repetidamente, siendo estos los operadores de selección, cruzamiento y mutación.

Población: conjunto de soluciones potenciales, donde la población inicial puede ser elegida aleatoriamente. Cambia con el tiempo pero su tamaño se mantiene.

Fenotipo: conjunto de rasgos observables de un organismo.

Genotipo: conjunto de genes de un organismo.

Individuo: elemento de la población que representa una solución.

Cromosoma: cadenas de genes que representan un individuo.

Gen: es una unidad de información dentro de un cromosoma.

Se pueden considerar tres tipos básicos de representación o codificación de los genes:

• Binaria: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un número binario.
• Entera: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un número entero.
• Real: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un número real.

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (recombinación, mutación) y de cómo se realiza la selección de individuos para formar la nueva población. En general, el diagrama de flujo consiste de los siguientes pasos:

Generar población inicial: 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.

Evaluar individuos: 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 algoritmo genético 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 algoritmo genético un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población.

Selección: después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que tiene derecho a tener descendientes y cuantos. Existen varios mecanismos de selección, las más frecuentemente utilizadas son presentadas a continuación.

• Selección de ruleta: es también conocida como Selección proporcional a la función de desempeño. Sea N el número de individuos existentes y  el desempeño del i-ésimo individuo. La probabilidad asociada a su selección está dada por: Esta selección permite que los mejores individuos sean elegidos con una mayor probabilidad, pero al mismo tiempo permite a los peores individuos ser elegidos, lo cual puede ayudar a mantener la diversidad de la población, en contraste con la selección por truncamiento. Un problema de la selección de ruleta se presenta cuando existe una pequeña fracción de la población (en el límite, sólo un individuo) que posee una medida de desempeño excesivamente superior al resto. Esto provoca pérdida de diversidad y puede conducir a convergencia prematura pues la mayor parte de los individuos seleccionados será una copia de los pocos predominantes. En este caso es preferible utilizar selección basada en ranking o selección por torneo.
• Selección por truncamiento: en esta selección las soluciones candidatas son ordenadas según su función de desempeño, y una proporción p (por ejemplo =1/2, 1/3, 1/4,...) de los individuos con mejor desempeño es seleccionada y reproducida 1/p veces. Esta selección es menos sofisticada que la mayoría de los métodos de selección, y generalmente no es usada en la práctica.
• Selección basada en ranking: en esta selección los individuos se ordenan según su medida de desempeño y luego son asignados con una segunda medida de desempeño, inversamente proporcional a su posición en el ranking (esto es, otorgando una mayor probabilidad a los mejores). Los valores de esta segunda asignación pueden ser lineales o exponenciales. Finalmente, los individuos son seleccionados proporcionalmente a esta probabilidad. Este método disminuye el riesgo de convergencia prematura que se produce cuando se utiliza selección de ruleta en poblaciones con unos pocos individuos con medidas de desempeño muy superiores a las del resto.
• Selección por torneo: esta selección se efectúa mediante un torneo (comparación) entre un pequeño subconjunto de individuos elegidos al azar desde la población. Los beneficios de este tipo de selección son la velocidad de aplicación (dado que no es necesario evaluar ni comparar la totalidad de la población) y la capacidad de prevenir, en cierto grado, la convergencia prematura. La principal desventaja es la necesidad de establecer el parámetro correspondiente al tamaño del subconjunto.

Recombinación: 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.

• Recombinación en un punto: se selecciona un punto en el vector del primer parental. Todos los datos más allá de este punto en el vector del organismo se intercambiarán entre los dos organismos parentales. Los organismos resultantes son los hijos.
• Recombinación en dos puntos: la recombinación en dos puntos requiere seleccionar dos puntos en los vectores de los organismos parentales. Todos los datos entre los dos puntos se intercambian entre los organismos parentales, creando dos organismos hijos.
• Corte y empalme: otra variante de recombinación, el enfoque "cortar y empalmar", ocasiona un cambio de la longitud de los vectores de los hijos. la razón para esta diferencia es que se selecciona un punto de corte diferente para cada vector parental
• Recombinación uniforme: en el esquema de recombinación uniforme, los bits del vector se comparan individualmente entre ambos padres. Los bits se intercambian con una probabilidad fijada, usualmente 0.5.
• Recombinación uniforme media: en el esquema de recombinación uniforme media, exactamente la mitad de los bits que son diferentes se intercambian. Por esto se necesario calcular la distancia de Hamming (número de bits diferentes). Este número se divide entre dos, y el número resultante es la cantidad de bits diferentes que tiene que ser intercambiada entre los parentales.
• Recombinación de cromosomas ordenados: dependiendo de cómo representa la solución el cromosoma, un cambio directo puede no ser posible. Un caso de ello se da cuando el cromosoma es una lista ordenada, como la lista ordenada de las ciudades visitadas en el problema del viajero. Un punto de recombinación se selecciona en los padres. Puesto que el cromosoma es una lista ordenada, un cambio directo introduciría duplicados y extraería candidatos necesarios de la lista. En cambio, el cromosoma hasta el punto de cruzamiento se retiene para cada padre. La información después del punto de cruzamiento se ordena como está ordenada en el otro padre. Por ejemplo, si nuestros dos padres son ABCDEFGHI e IGAHFDBEC y nuestro punto de cruzamiento se establece después del cuarto carácter, entonces los hijos que resultan serían ABCDIGHFE e IGAHBCDEF.

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.

Desventajas y Limitaciones

Entre otras podemos mencionar:

• Para problemas de alta complejidad la función de evaluación puede tornarse demasiado costosa en términos de tiempo y recursos. Por ejemplo existen casos en la vida real para los cuales recrear una simulación de la solución propuesta por una iteración puede tardarse muchos días y consumir gran cantidad de procesamiento y recursos asociados.
• Se pueden tener casos en los cuales dependiendo los parámetros que se utilizan para la evaluación el algoritmo podría no llegar a converger en una solución óptima o bien termine en una convergencia prematura con resultados no satisfactorios (la convergencia prematura podría significar una convergencia en un óptimo local o punto arbitrario afectando los resultados a largo plazo) .
• Se dice que no poseen una buena escalabilidad con la complejidad, por ejemplo para sistemas que están compuestos de muchas variables, componentes o elementos su respectivo espacio de búsqueda crece de manera exponencial debido entre otras cosas a las relaciones que puedan surgir, por lo tanto el problema del diseño de una aeronave debe desglosarse en representaciones simples como perfiles aerodinámicos tomando en cuenta que la recombinación de los elementos puede perjudicar el rendimiento individual.
• La "mejor" solución lo es solo en comparación a otras soluciones por lo que no se tiene demasiado claro un criterio de cuando detenerse ya que no se cuenta con una solución específica.
• No es recomendable utilizarlos para problemas que buscan respuesta a problemas que convergen en soluciones simples como Correcto/Incorrecto ya que el algoritmo difícilmente convergerá y el resultado será tan válido como escogerlo al azar.
• El diseño, la crea de la función de aptitud, la selección de los criterios de mutación entre otros, necesitan de cierta pericia y conocimiento del problema para obtener buenos resultados.

Como saber si es posible usar un Algoritmo Genético

• La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:
• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora

Motivación

Si les interesa este tema no se pierdan los próximos post donde mostrare como programar un algoritmo genético para resolver varios problemas entre ellos estaremos dándole solución al Problema del viajante (descripción), al Problema de la mochila (descripción) entre otros. Para la codificación utilizaremos el programa Octave (descargar aqui) considerado el equivalente libre de MATLAB (descargar aqui).

Referencias

J. H. Holland. University of Michigan Press, Ann Arbor. 1975. Adaptation in Natural and Artificial Systems.

 D. E. Goldberg. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. 1989. Genetic Algorithms in Search, Optimization and Machine Learning.