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

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

• Eboluzioa
• Matematika

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.

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.

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.

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.

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.

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".