Ediciones ENI Editorial | líder en informática
Algoritmos genéticos
Presentación del capítulo
La naturaleza ha encontrado la manera de resolver algunos problemas aparentemente sin solución. De esta manera, la vida está presente prácticamente en todos los lugares de la Tierra, desde lugares congelados hasta las fosas submarinas (que tienen las temperaturas más bajas y las presiones más elevadas) pasando por el aire.
Este éxito se explica por la potencia de la evolución biológica. Este hecho permite adaptar constantemente las diferentes especies de la mejor manera posible, para poder colonizar.
Los informáticos han imaginado cómo esta evolución se podría utilizar para responder a problemas complejos. De esta manera aparecieron los algoritmos genéticos.
En una primera parte, se explican los principios subyacentes a la evolución biológica. Son necesarios para entender el funcionamiento global y la inspiración de los algoritmos genéticos.
A continuación se presenta el funcionamiento de estos, al principio de manera global con un ejemplo y después volviendo a las principales etapas, con las correctas prácticas y las trampas que hay que evitar. También se explicará la co-evolución (la evolución conjunta de dos especies).
Los algoritmos genéticos se pueden utilizar en muchos dominios de aplicación, que se presentarán. A continuación...
Evolución biológica
Los algoritmos genéticos se basan en la evolución biológica. Si bien no es necesario entender todos sus detalles, es importante entender la fuente de inspiración de estos algoritmos.
1. El concepto de evolución
La evolución biológica se estudió a partir de finales del siglo 18. En efecto, las pruebas de esta evolución se acumulan y los científicos quieren entender los fenómenos subyacentes.
A comienzos de siglo 19 aparece la paleontología (el término se utiliza desde 1822), ciencia que estudia los fósiles y las formas de vida que han desaparecido en la actualidad. Los científicos encuentran muchos esqueletos y los clasifican. Estos presentan muchas características comunes entre ellos o con formas de vida actuales. Por lo tanto, parece evidente que ha habido una continuidad y que las especies han sido progresivamente modificadas a lo largo de la historia.
Además, las sociedades basadas en la ganadería eran numerosas. Después de mucho tiempo, sabemos seleccionar los mejores individuos para mejorar la producción ganadera de una especie (como la leche de las vacas) o simplemente por puro placer. De esta manera, las razas de perros, gatos o caballos son más numerosas y con mayores diferencias. Es evidente que un animal es parecido a sus padres, aunque no es totalmente idéntico a ellos, y que seleccionando los mejores padres podemos obtener nuevas razas. Los caniches, los pastores alemanes, los cockers y los labradores descienden todos del lobo gris (Canis Lupus), domesticado durante la prehistoria. Es la intervención humana la que ha modelado todas estas razas.
Para terminar, los grandes descubridores iban de isla en isla y descubrían nuevas especies. Parecía que los individuos que vivían en las islas más cercanas también eran más parecidos físicamente. Por el contrario, eran mucho más diferentes a los individuos de otros continentes. Por lo tanto, las especies habían evolucionado de manera diferente, pero gradual.
Por lo tanto, la evolución biológica ya no era un tabú durante el siglo 19, sino una realidad científica. Sin embargo, faltaba por saber cómo había tenido lugar esta evolución.
2. Los causas de las mutaciones
Darwin (1809-1882) y Lamarck (1744-1829)...
Evolución artificial
La evolución biológica que hemos visto anteriormente se llama "incorpóreo": en efecto, los principios de reproducción, supervivencia o selección no indican cómo se debe almacenar o transmitir la información, ni siquiera lo que debe evolucionar.
Por lo tanto, despierta el interés de dominios muy diversos, ya sea del ámbito de la economía, la sociología, la música, etc... La informática no es una excepción y esta evolución biológica se puede utilizar para crear una evolución artificial, que permita resolver problemas irresolubles con los métodos más clásicos.
1. Principios
Por lo tanto, los algoritmos evolutivos van a partir de una población de soluciones potenciales para un problema. Cada uno se evalúa, para asignarle una nota, llamada Fitness. Cuando más fuerte sea la Fitness de una solución, más prometedora es.
A continuación, se seleccionan los mejores individuos y se reproducen. Se utilizan dos operadores artificiales: el cruce entre dos individuos, llamado crossover y de las mutaciones aleatorias.
A continuación se aplica una etapa de supervivencia para crear la nueva generación de individuos.
Por lo tanto, el proceso es el siguiente:
Aparecieron diferentes variantes en los años 60 de manera independiente. Holland puso a punto los algoritmos genéticos, pero también hablamos de programación evolutiva (Fogel) o de estrategias de evolución (Rechenbert y Bäck). Algunos años más tarde aparecieron la evolución gramatical (Ryan, Collins y O’Neill) y la programación genética (Koza).
Todos estos algoritmos, normalmente recogidos bajo el nombre genérico de algoritmos genéticos, se basan en este principio de evolución y este bucle generacional. Las diferencias se centran principalmente a nivel de las representaciones y de los operadores.
2. Convergencia
La convergencia hacia la solución óptima se demuestra de manera teórica. Sin embargo, nada indica el tiempo necesario para converger hacia esta solución, que por lo tanto...
Primeras fases del algoritmo
Antes de pasar al cálculo de las generaciones, hay que empezar crear la primera. Para esto, será necesario hacer opciones sobre las representaciones y después, inicializar los individuos de la población inicial. Además, será necesario seleccionar su función de evaluación.
1. Elección de las representaciones
Como sucede con muchas de las técnicas de inteligencia artificial, la elección de las representaciones es primordial para limitar el espacio de búsqueda y para hacerlo lo más adaptado posible al algoritmo elegido.
a. Población e individuos
La población contiene una lista de individuos. El lenguaje informático utilizado impone algunas veces la representación de esta lista. Para facilitar la etapa de reproducción, es más fácil seleccionar una estructura de datos con un acceso directo a un individuo como una tabla, respecto a un acceso por recorrido como una lista.
Los individuos contienen una lista de genes. De nuevo aquí el formato exacto de esta lista se determina en parte por el lenguaje. Un acceso directo a uno de los elementos no es obligatorio.
b. Genes
La representación de los genes es aquella sobre la que hay que pasar la mayor parte del tiempo. Tradicionalmente, se trata de una lista ordenada de valores. Esto significa que para todos los individuos, el primer gen tiene el mismo significado (en nuestro ejemplo anterior, los peones se almacenaban en el mismo orden).
Sin embargo, en algunos casos puede ser más adecuado seleccionar una representación en la que la posición de los genes es variable, adaptándose a los operadores. Cada gen contiene el nombre de la variable asociada y el valor (por ejemplo, longitud y altura para un objeto).
Además, es importante reflexionar bien sobre las variables necesarias para resolver el problema. Se desaconseja tener demasiados valores a optimizar y por lo tanto, es necesario verificar que no hay variables redundantes, cuyos valores pudieran ser resultado de otros.
Para terminar, es más complejo para un algoritmo genético resolver un problema, en el que los diferentes genes están relacionados entre ellos. Una analogía puede ser la de la diferencia...
Creación de las generaciones siguientes
Una vez que se crea la primera población y se evalúa, hay que seleccionar los diferentes operadores para pasar a la generación siguiente:
-
Selección de los padres entre los adultos.
-
Operadores de crossover y de mutación para crear los descendientes.
-
Supervivencia para crear la nueva población a partir de los adultos y de los descendientes creados.
1. Selección de las padres
La selección consiste en determinar cuáles son los individuos que merecen ser elegidos como padres para la generación siguiente. Es necesario que en proporción, los mejores padres se reproduzcan más que los padres con un Fitness más bajo, pero cada uno debe tener una probabilidad no nula de reproducirse.
En efecto, haciendo mutar o crecer las soluciones "malas" en apariencia, podemos encontrar una correcta solución a un problema.
Los padres se pueden seleccionar de diversas maneras, deterministas o estocásticas. Las selecciones estocásticas (que hacen intervenir a una parte de azar), son las más utilizadas.
Una de las soluciones más habituales es utilizar una ruleta sesgada: cuanto más adaptado es un individuo, más sección de la ruleta. Por lo tanto, los individuos siguientes tendrán una parte cada vez más pequeña. Entonces un sorteo indica cuál es el individuo elegido.
Estadísticamente, los que tienen Fitness más elevadas tendrán más hijos, pero todos tendrán al menos una oportunidad de reproducirse, aunque esta sea baja.
La parte de la ruleta de cada individuo se puede determinar por el rango de este, teniendo el primero siempre la misma parte respecto a la segunda o su Fitness. En este último caso, las proporciones cambian en cada generación y un individuo mucho más adaptado que el resto de su población, tendrá muchos más descendientes para transmitir rápidamente sus genes. Al contrario, en una población uniforme donde las diferencias de Fitness son bajas, la ruleta dará casi a cada individuo la misma oportunidad de reproducirse.
La segunda solución, después de la ruleta, es utilizar el torneo: se elijen al azar dos individuos y el más adaptado es el que se reproducirá. Por lo tanto, los individuos más adaptados ganarán...
Coevolución
La coevolución es un fenómeno biológico formalizado en 1964, como consecuencia de un estudio de dos biólogos sobre los cruces entre plantas y algunas mariposas. En efecto, demostraron que las dos especies habían evolucionado conjuntamente: las mariposas comían de la planta, que ha desarrollado mecanismos para defenderse (veneno o protecciones físicas). Las mariposas desarrollaron medios para resistir a estos venenos o defensas.
Por lo tanto, se trata de un curso sin fin entre las dos especies, intentando superponer periodos de avances para asegurar su propia supervivencia y no pueden parar de evolucionar. Las dos especies en competición se han desarrollado y han evolucionado más rápido, que si cada una hubiera evolucionado de manera independiente.
Esta coevolución es la que se observa en todos los sistemas "presa - depredador". De esta manera, hay un flujo evolutivo entre los hackers, que intentan romper la seguridad de los sistemas informáticos, y los responsables de la seguridad, que intentan repeler e impedir los ataques. Cada campo debe evolucionar constante y rápidamente, para intentar conservar una ventaja sobre el otro campo y contrarrestar cualquier nueva amenaza/defensa establecida.
Esta presión evolutiva se puede utilizar en nuestro beneficio en un algoritmo genético. De esta manera, se puede hacer evolucionar no a una población...
Dominios de aplicación
El equipo de John Holland de la universidad del Michigan, empezó a trabajar en los algoritmos genéticos en los años 60. Sin embargo, esta tecnología solo empezó a conocerse a partir de año 1975, con la publicación de su libro.
Entonces, los algoritmos evolutivos en general empezaron a tocar muchos dominios. Para que sean eficaces, es suficiente con responder a algunas restricciones:
-
El número de soluciones potenciales debe ser muy grande.
-
No hay método exacto que permita obtener una solución.
-
Una solución casi óptima es aceptable.
-
Se puede evaluar la calidad de una solución potencial.
Si se cumplen estas cuatro restricciones, entonces un algoritmo genético puede ser una solución correcta para encontrar una respuesta al problema que, aunque no pueda ser garantía de ser la mejor, en todo caso será aceptable y esto en un tiempo razonable.
Los encontramos en dominios de la ingeniería y el diseño. En efecto, en la actualidad cada vez es más difícil crear piezas que respondan a las restricciones y que minimicen o maximicen algunas características (menos materia prima, consumo más bajo, potencia más importante, mejor resistencia, etc...). De esta manera, las carrocerías de los coches se pueden crear por medio de un algoritmo genético para hacerlas más aerodinámicas....
Implementación
Ahora nos vamos a interesar por la implementación en Java de un algoritmo genético genérico, que se utiliza aquí para resolver dos problemas abordados anteriormente:
-
El viajante de comercio, que consiste en encontrar la ruta más corta para unir un conjunto de ciudades.
-
El laberinto, dando la sucesión de instrucciones que hay que seguir para ir desde la entrada hasta la salida.
El código que se propone aquí está disponible para su descarga. El programa que contiene la función main es una aplicación de consola.
1. Implementación genérica de un algoritmo
a. Especificaciones
Queremos codificar un motor genérico para un algoritmo genético, que a continuación se aplica a dos problemas diferentes, escribiendo el menor código posible para pasar de uno al otro.
Por lo tanto, es importante fijar correctamente las necesidades. El proceso evolutivo en sí mismo, el corazón del sistema, se ocupa de inicializar la población y después, lanza la evaluación y selección de los padres y la creación de los descendientes y para terminar, la supervivencia. A continuación nos centramos en la evaluación, hasta que se alcance un criterio de parada.
Por lo tanto, se va a definir dos criterios de parada posibles: se alcanza la Fitness que queríamos o se alcanza el número máximo de generaciones. En los dos problemas, se trata de minimizar la función de evaluación: el número de kilómetros para el viajante de comercio o la distancia a la salida para el laberinto. Por lo tanto, se fija un Fitness mínimo a alcanzar.
Se podría adaptar el algoritmo para permitir maximizar el valor de adaptación, pero como nuestros dos problemas buscan minimizar el Fitness, no lo haremos aquí.
Los diferentes argumentos del algoritmo se definen en una clase aparte. A continuación, tendremos interfaces o clases abstractas para los individuos y los genes. En efecto, se trata de las únicas dos clases que hay que redefinir para cada caso. Para el problema de salida del laberinto, necesitamos tener genomas de tamaño variable (la lista de las instrucciones), por lo que el algoritmo debe permitir gestionarlo.
Para aligerar el corazón del sistema de la gestión del caso a resolver, llevamos a una fábrica...
Resumen
Los algoritmos genéticos (o más normalmente los algoritmos evolutivos), están inspirados en las diferentes búsquedas realizadas en biología de la evolución.
Entonces tenemos una población de individuos cada una compuesta por un genoma, que es una lista de genes. Estos individuos se evalúan respecto a la calidad de la solución de un problema dado, que representan (es lo que se llama su fenotipo).
Los mejores individuos se seleccionan para ser reproductores. Se crean nuevas soluciones a partir de uno o varios padres. En caso de que intervengan varios padres se realiza un crossover, es decir, un cruce entre la información genética de los diferentes padres.
A continuación los genomas de los descendientes sufren mutaciones aleatorias, que representan los errores de copiado que tiene lugar durante la reproducción. Cada descendiente, aunque sean parecidos a sus padres, es potencialmente diferente.
A continuación, esta nueva generación debe sobrevivir para formar parte de la población de la generación siguiente. Volvemos a ejecutar el proceso hasta alcanzar las soluciones óptimas o casi óptimas.
De esta manera, los algoritmos genéticos permiten resolver muchos problemas para los que no existe solución matemática conocida y cuyo espacio de búsqueda es demasiado vasto para una búsqueda exhaustiva....
