}

Algoritmos genéticos en busca de la solución más adecuada

2008/01/01 Galarraga Aiestaran, Ana - Elhuyar Zientzia Iturria: Elhuyar aldizkaria

Los algoritmos genéticos son una técnica de programación que imita la evolución biológica y que se utiliza para resolver problemas muy difíciles o imposibles de resolver mediante métodos convencionales. No saben muy bien por qué, pero las técnicas convencionales funcionan en problemas que fallan, por lo que son cada vez más utilizadas para resolver problemas prácticos.
Algoritmos genéticos en busca de la solución más adecuada
01/01/2008 | Galarraga Aiestaran, Ana | Elhuyar Zientzia Komunikazioa

(Foto: De archivo)
En la naturaleza, la población inicialmente existente cambia con el tiempo. De generación en generación, algunos factores hacen que los individuos que peor se adaptan desaparezcan, mientras que los que mejor se adaptan perviven. Por tanto, dentro de la población aumenta la proporción de mejores. Sin embargo, es posible que algún que no parece tan bueno continúe por tener una estrategia diferente o por azar. Y podría cruzarse con los demás, como se cruzan los demás. Por lo tanto, es posible que la característica del individuo, supuestamente mala, aparezca en la próxima generación en otros miembros.

De vez en cuando aparece otra variable: la mutación. Aunque no es muy frecuente, influye en las características de los miembros de la población. Debido a los cruces, mutaciones y agentes que apuestan por los mejores, una vez transcurrido el tiempo, la población está formada por los miembros mejor adaptados al entorno.

Así lo explicó, más o menos, Darwin en la teoría de la evolución de las especies, y es lo que hacen los algoritmos genéticos. La población inicial está constituida por las posibles soluciones a un problema. Estas posibles soluciones se seleccionan aleatoriamente y se denominan cromosomas. Los diferentes aspectos de cada cromosoma se denominan genes.

En caso de ser candidatos, se les aplica una función que mide su idoneidad. Como es normal, la mayoría de los candidatos son inadecuados, pero otros, de alguna manera, funcionan y se mantienen.

Los candidatos que han avanzado se multiplican y se cruzan. Por lo tanto, en la siguiente generación, algunos tienen varias copias y otras se han equivocado. Además, unos pocos no son exactamente iguales a los anteriores: se han mutado, es decir, se han modificado aleatoriamente algún gen.

La generación resultante es diferente a la anterior y se mide la idoneidad de estos candidatos. Así, los candidatos que no son mejores que los anteriores se descartan, los que quedan son mejores soluciones que los iniciales. Ellos se reproducen y se producen cruces e incluso mutaciones. Se evalúan los nuevos candidatos y se vuelve a elegir a los mejores, el proceso se repite cada cien o mil veces. La población resultante está formada por muy buenas soluciones al problema.

Esquema del funcionamiento de los algoritmos genéticos.

Números, letras y árboles

Para empezar a trabajar los algoritmos genéticos es necesario codificar las posibles soluciones del problema para que el ordenador pueda procesarlo. Una opción es codificar en cadenas binarias: Son cadenas formadas por 1 y 0 y el dígito que hay en cada lugar de la cadena representa el valor de un aspecto de la resolución.

Otra forma de codificar es mediante cadenas de números enteros o decimales. Como en el caso anterior, el número que hay en cada lugar indica el valor de un aspecto concreto de la resolución. Se obtiene mayor precisión y complejidad que con el código binario, ya que limita menos que usar dos números. Por otro lado, los números se pueden sustituir por letras para codificar los candidatos.

Con estos tres métodos es muy fácil definir las operaciones que realizarán al azar cruces y mutaciones entre los candidatos; es fácil poner un 1 en donde hay un 0 o viceversa; añadir o quitar un valor a un número; o sustituir una letra por otra.

Los algoritmos genéticos se basan en la teoría de la evolución de Darwin.
De archivo
Además, existen otras formas de codificar, como la que se realiza con árboles. Los datos se representan ramificados y los cambios se realizan cambiando el valor de los parches o sustituyendo algunas ramas del árbol por otras.

Selección y modificación

Codificar de una manera u otra, programar la elección de los individuos a copiar para la siguiente generación. La selección se puede realizar de diversas formas y normalmente se utilizan varias de ellas a la vez. Una de ellas es la selección elitista, es decir, la selección de los mejores de cada generación. Otra forma depende de la capacidad: a mayor capacidad, más posibilidades de elección.

Además, para garantizar la diversidad de la población, se puede utilizar una rueda de ruleta: a cada candidato le corresponde una parte de la ruleta; a mayor capacidad, mayor parte se adapta al candidato. Girando la rueda, los que tienen una parte grande tienen más posibilidades de ser elegidos, pero puede que se adapte a un candidato con poca capacidad para ser elegido para la siguiente generación. Esto garantiza que la siguiente generación no sea demasiado igualitaria.

Otra forma de garantizar esto es mediante la realización de grupos por nivel de competencia y la elección de los mejores de cada grupo, de forma que el mejor del grupo de baja capacidad avanzaría. Los equipos también se pueden hacer al azar y luego se pueden obligar a competir entre ellos, los vencedores pasan a la siguiente generación.

Un vendedor debe cruzar varios puntos y llegar al punto de partida, realizando el recorrido más adecuado. A esto se le llama problema del vendedor y no se puede resolver con métodos convencionales, pero se resuelve bien mediante algoritmos genéticos.
De archivo

Existen otros métodos de selección: selección escalonada, jerárquica... En cualquier caso, el objetivo es que los candidatos de la siguiente generación sean de media mejores que los anteriores. Además, a los candidatos seleccionados para la siguiente generación se les realizan algunos cambios aleatorios con la esperanza de que aparezcan mejores individuos.

Existen dos formas de realizar los cambios: mutación y cruce. La mutación es cambiar un aspecto concreto, un gen. El cruce consiste en canjear parte del código por otro candidato. El "niño" así formado tiene en común las características de los dos "padres". Se trata, por tanto, de una recombinación entre los cromosomas paternos y maternos en la reproducción sexual.

A favor y en contra

Mediante la selección, la mutación y el cruce, de generación en generación, los algoritmos genéticos van acercándose a la solución del problema. En muchos casos, el algoritmo genético no será suficiente para soltar el problema, pero puede dar soluciones razonablemente buenas, y aplicando los métodos habituales a esta población final se puede obtener la mejor solución.

Una de las ventajas de los algoritmos genéticos es que son “ciegos”, es decir, que no saben nada del problema que tienen que resolver. Puede que más que una ventaja parezca una desventaja, pero es muy buena, ya que no rechaza desde el principio a ningún candidato con mal aspecto. Además, el crucero y la mutación crean sorprendentes soluciones. De alguna manera, los prejuicios no afectan a los algoritmos genéticos, sólo les importa avanzar.

El diseño de horarios es realmente complejo, y para ello los algoritmos genéticos son una gran herramienta.
P. Gene
Además, trabajan en paralelo, es decir, por diferentes vías a la vez. La mayoría de los algoritmos trabajan en serie y sólo pueden avanzar en una dirección en cada ocasión. Cuando se dan cuenta de que han tomado el camino equivocado, tienen que abandonar todo el trabajo y empezar de nuevo. Sin embargo, los algoritmos genéticos no tienen este problema y son especialmente eficaces en la resolución de problemas con muchas soluciones posibles.

Tienen más ventajas pero también algunos inconvenientes. La primera es la dificultad de escribir la definición del problema. La codificación de los candidatos no es sencilla y a veces cuesta mucho escribir la función que mide la capacidad. El tamaño de la población, la frecuencia de mutaciones y cruces, así como el tipo y la fuerza de la selección, son factores muy importantes en los algoritmos genéticos, que si no se diseñan bien, no avanzan.

Apps

A pesar de sus limitaciones, se utilizan para resolver problemas como acústica, ingeniería aeroespacial, astronomía y astrofísica, química, mercado financiero, juegos, geofísica, ingeniería de materiales, matemáticas, biología molecular, telecomunicaciones, etc.

Por ejemplo, en 2002 investigadores de la Universidad Kobe de Japón utilizaron algoritmos genéticos para diseñar una sala de música. Partieron de una sala en forma de caja de zapatos y definieron los parámetros que debía tener para conseguir la mejor acústica. El algoritmo dio dos resultados, ambos en forma de host, que parecen tener una acústica espectacular. Según los investigadores, son como el Grosser Musikvereinsaal de Viena, el mejor del mundo.

Los algoritmos genéticos se utilizan para el diseño de péptidos, entre otras muchas aplicaciones.

Por su parte, la NASA los ha utilizado en el diseño de envases, pero también en el estudio de enanas blancas y en el diseño de horarios. De hecho, los algoritmos genéticos son muy eficaces para la realización de horarios tanto en empresas, aeropuertos y escuelas.

En las escuelas, por ejemplo, es un problema el horario adecuado. Se requiere un profesor por aula y un profesor no puede estar en dos aulas simultáneamente. Por supuesto, cada profesor tiene que dar su tema y, tal vez, algunos temas mejor que se den a una hora y no a otra (no conviene poner a última hora las matemáticas, la física, etc.). Además, hay que tener en cuenta las preferencias o necesidades del profesorado. Dado que hay que tener en cuenta tantos factores, en los grandes centros es muy difícil conseguir un buen programa horario. Pues bien, los algoritmos genéticos son perfectos.

Los expertos no tienen duda de que, a pesar de que son relativamente nuevos (los primeros aparecieron en la década de 1960), han tenido un rápido desarrollo y, según la matemática Mª Teresa Iglesias, "no hay que detenerlos".

Mª Teresa Iglesias: "El objetivo de los algoritmos genéticos es adaptarse al entorno"
Mª Teresa Iglesias, profesora del departamento de Matemáticas por la Universidad de La Coruña, impartió recientemente en la Facultad de Ciencia y Tecnología de la UPV/EHU la conferencia "Matemáticas evolutivas: algoritmos genéticos", "La mujer, ¿innovadora de la ciencia?" Dentro de las jornadas. Tras la charla tuvimos la oportunidad de hablar con esta innovadora científica.
En su discurso ha afirmado que los algoritmos genéticos son muy buenos para resolver problemas que no tienen una solución sencilla, aunque por sí mismos no siempre maximizan.
Eso es. La evolución tampoco tiende al máximo sino a adaptarse. La evolución produce individuos que se ajustan bien a un determinado entorno, lo mismo que los algoritmos genéticos. Por ejemplo, en comparación con los hombres y mujeres de hace mil años, nos adaptamos mejor que ellos en la sociedad actual, pero no nos llevaríamos tan bien si de repente nos despertáramos en aquella época... Las soluciones que proporcionan los algoritmos genéticos no siempre serán las mejores, pero se adaptarán muy bien a una situación concreta.
(Foto: A. Galarraga)
Además no se utilizan solos. Normalmente se utilizan inicialmente y, una vez que se ha conseguido un conjunto de soluciones relativamente buenas, se sigue con los métodos tradicionales.
Sin embargo, no siempre funcionan. Si no me equivoco, investigas por qué ocurre eso.
Sí, algunas funciones ( deceptive functions ) engañan de alguna manera al algoritmo y lo alejan del óptimo. Antiguamente se pensaba que los algoritmos genéticos no funcionaban con estas funciones, pero ahora vemos que con unos sí y con otros no. Es difícil saber por qué, y en nuestro grupo trabajamos justo en ello; tratamos de aclarar qué características hacen que una función sea difícil de optimizar mediante algoritmos genéticos. Y ya hemos encontrado algunas.
Sin embargo, todavía queda mucho por investigar. Son relativamente nuevos y, como en muchos casos funcionan bien, los informáticos los utilizan, aunque todavía no hay una base teórica sólida. Pero lo que nos toca es trabajar los fundamentos teóricos.
Galarraga de Aiestaran, Ana
Servicios
238
2008
1.
032
Matemáticas; Evolución
Artículo
Otros

Gai honi buruzko eduki gehiago

Elhuyarrek garatutako teknologia