Intentando copiar la selección natural

Anthony Baillard / 24-01-2012

Traducción: Annia Domènech

Los mecanismos biológicos que permiten conseguir objetivos complejos son innumerables. No debe sorprender, por ello, que los investigadores los utilicen como fuente de inspiración en su trabajo. Esto ocurre particularmente en el campo de la inteligencia artificial, en el cual hay que suministrar a un ordenador, que es pura lógica, la capacidad de resolver problemas complejos que conllevan tomar decisiones.

Vimos en un artículo anterior (Intentando copiar el cerebro humano) que el funcionamiento de las células nerviosas del cerebro inspiró las redes de neuronas artificiales. Hoy nos dedicaremos a los algoritmos genéticos. Como su nombre indica, estas herramientas informáticas son algoritmos basados en los mecanismos de la genética y la evolución darwinianas.

Empecemos recordando brevemente los principios de la selección natural. La teoría de Darwin explica que la evolución de las especies ocurre a través de la selección de los individuos mejor adaptados al medio en el que viven, sean cuales sean las razones de su estado ventajoso: conseguir con mayor facilidad alimento, tener una resistencia superior a los depredadores, reproducirse con mayor eficiencia, etc. Esta proposición fue ratificada en el siglo XX por el descubrimiento de la existencia de mutaciones genéticas. Cuando tiene lugar la replicación del ADN (Ácido Desoxirribonucleico) en las células (su duplicación), a veces ocurren errores: se insertan o suprimen secuencias, se copia mal el contenido, etc. Por otro lado, cuando dos individuos se reproducen, mezclan sus códigos genéticos, esto es, tiene lugar una hibridación.

Dichas mutaciones e hibridaciones conllevan la aparición de nuevos códigos genéticos (genotipo) y en consecuencia de individuos cuyas características (fenotipo) pueden variar. Estos seres pueden estar mejor o peor adaptados que sus antepasados.

Son estos principios biológicos la base de los algoritmos genéticos, que se utilizan para hallar soluciones a problemas complejos. El más conocido de ellos es el del viajante. Se trata de un problema estándar que se resume así: un comercial que se desplaza en coche debe efectuar un viaje profesional en el marco del cual tiene que visitar un número x de ciudades. La ciudad de salida está fijada, y el viajero debe retornar a ella tras su tournée. Para ahorrar tiempo y dinero, quiere optar por el recorrido más corto evitando pasar dos veces por la misma urbe.

Si el problema incluye cuatro ciudades; pongamos Barcelona, Madrid, Valencia y Córdoba; la solución es sencilla: un cuadrilátero en el que cada vértice corresponde a una de ellas (lo que puede demostrarse matemáticamente). Supongamos ahora que el viajante debe visitar cincuenta ciudades. ¿Cómo encontrar la solución óptima?

La cuestión del viajante posee una combinatoria exponencial: al añadir una ciudad al problema, el número de combinaciones posibles se multiplica por el número total de ciudades. Con ello, las combinaciones aumentan tanto que no es posible estudiarlas en su integralidad para lograr resolver la cuestión en un margen de tiempo aceptable a escala humana. Aquí entran los algoritmos genéticos, cuya baza radica en su capacidad de encontrar una "buena" solución en un tiempo razonable. Veamos cómo.

El primer paso consiste en crear una población inicial. En el caso que nos ocupa, han de establecerse trayectos que pasen una única vez por cada ciudad de la lista. Como en las redes neuronales, es imprescindible disponer de una función de evaluación. En su caso se trata de una distancia, en el de los algoritmos genéticos la función puede ser comparada al grado de adaptación de un individuo a su entorno (dicho de otro modo, al problema que intentamos resolver).

En el problema del viajante, cada individuo corresponde a un itinerario posible y la función de evaluación es el coste global del mismo, que puede ser estimado adicionando los costes de todos los trayectos entre ciudades. Los mejores "individuos" son aquellos cuyo coste sea menor y serán favorecidos cuando se generen nuevas generaciones de individuos (trayectos). Una vez la población inicial creada (digamos que de un modo completamente aleatorio) se establecerán los procedimientos evolutivos: hibridación y mutación.

La hibridación se efectúa con dos individuos (progenitores) para obtener dos individuos (hijos). Cada hijo posee parte del código genético de cada progenitor. La hibridación no es sistemática, sino que está gestionada por una probabilidad que puede ser nula (los hijos son idénticos a los padres), valer 1 (todos los hijos se generan por hibridación) o tener un valor intermedio que permite la aparición de algunos híbridos mientras se conservan también los individuos de las generaciones anteriores.

La mutación provoca errores de copia con el objetivo de crear individuos completamente nuevos, que no existirían por hibridación pura. Si el individuo resultante de una mutación está inadaptado, es eliminado. La frecuencia de mutación es asimismo regida por una probabilidad, la cual no debe ser demasiado elevada para evitar que el algoritmo se parezca a una búsqueda aleatoria.

Si las mutaciones no son lo bastante frecuentes, el algoritmo puede permanecer bloqueado: la mejor solución no existía en la población inicial y no puede alcanzarse por hibridación. ¡El objetivo de las mutaciones es evitar escoger una solución únicamente porque las otras son peores! (Técnicamente hablamos de mínimos locales en oposición a un mínimo global).

El paso de una generación a la siguiente, denominada iteración, tiene lugar en tres etapas:

- A partir de una población inicial de tamaño m, m individuos son seleccionados (un mismo individuo puede ser seleccionado varias veces o ninguna según la función de evaluación).

- Los m individuos se cruzan aleatoriamente dos a dos (con hibridación o sin ella).

- Cada nuevo individuo sufre o no una mutación.

El algoritmo produce generaciones de individuos hasta que se logre el objetivo. Generalmente esta probabilidad está ligada a la función de evaluación: un individuo con un coste muy elevado está poco adaptado a su medio, por ello es deseable hibridarlo y conseguir así un individuo potencialmente mejor adaptado.

Retomemos el ejemplo del viajante. Cada individuo de nuestra población es un trayecto con un coste total. Una hibridación de dos individuos significa que los trayectos de ambos se mezclarán para obtener dos nuevos trayectos.

Ejemplo:

Trayectos de los progenitores:

1->2->3->5->4->1 y 1->3->2->4->5->1

Al hibridarse pueden dar:

1->2->3->4->5->1 y 1->3->2->5->4->1

Una mutación permitiría transformar un trayecto de un modo independiente, por ejemplo:

1->2->3->4->5->1 en 1->2->4->3->5->1

Esta mutación podría resultar ser muy importante ya que ninguna hibridación es capaz de dar lugar al camino 4->3, que forma quizás parte de la solución óptima.

La agudeza de los algoritmos genéticos reside en diversos parámetros: la creación de la población inicial, la probabilidad de hibridación, la probabilidad de mutación y el método de selección. Si los valores o las funciones escogidas no están adaptados al escenario en cuestión, es posible que el algoritmo genético no logré dar ninguna respuesta satisfactoria.

Un conocimiento previo del problema permite generar una población inicial cercana a la solución correcta, así como llegar a ésta más rápido y con mayor seguridad. La probabilidad de mutación debe mantenerse en un orden de 2-3% en la mayoría de los casos. Para la función de selección, existen numerosos métodos, por ejemplo:

- La ruleta (como en el casino) utiliza el valor de la función de evaluación como una probabilidad de selección del individuo.

- El elitismo conserva sistemáticamente un número de individuos a los que no se aplican mutaciones ni hibridaciones de modo a garantizar su presencia e influencia en toda generación consiguiente.

- El steady-state reemplaza sólo a los peores individuos de una generación por los descendientes de los mejores individuos. De este modo, la mayoría de la población "media" sobrevive de generación en generación, mejorando el conjunto de la población.

Existen numerosas variaciones de esta técnica, algunas con métodos de selección o funciones de evaluación mucho más complejos, o en las que se modifican las tasas de hibridación durante el proceso. Sin entrar en mayores disquisiciones, la idea a recordar es que los algoritmos genéticos proporcionan una solución cercana a la solución óptima en un tiempo aceptable para problemas muy complejos, y que lo hacen utilizando procedimientos parecidos a los utilizados por Darwin para describir la evolución de las especies. Como no se trata de métodos analíticos, su inconveniente es no garantizar la solución óptima, lo que los acerca todavía más a la naturaleza.

Comentarios (4)

Compartir:

Multimedia

El autor

Anthony Baillard es Ingeniero Informático y Doctor en tratamiento de imágenes e inteligencia artificial.

Ver todos los artículos de Anthony Baillard