Ediciones ENI Editorial | líder en informática
Algoritmos genéticos
Presentación del capítulo
La naturaleza ha encontrado la manera de resolver ciertos problemas que parecían imposibles de resolver. La vida es posible, de este modo, casi en cualquier lugar, tanto por tierra, como en glaciares y hasta en las fosas submarinas (que presentan temperaturas y presiones muy elevadas) pasando por el aire.
Este éxito se explica por la potencia de la evolución biológica. Permite a las diversas especies adaptarse continuamente a los medios que necesita colonizar.
Los informáticos han pensado cómo podría utilizarse esta evolución para resolver problemas complejos. Así es como aparecen los algoritmos genéticos.
En una primera sección se explican los principios subyacentes a la evolución biológica. Son necesarios para comprender el funcionamiento global y la inspiración de los algoritmos genéticos.
A continuación, se presenta su funcionamiento, primero de manera global con un ejemplo y, a continuación, explorando las principales etapas, con buenas prácticas y los principales problemas que se deben evitar. También se explicará la coevolución (evolución conjunta de dos especies).
Estos algoritmos pueden utilizarse en los muchos campos de aplicación que se presentan. A continuación, se proponen dos ejemplos de implementación, en lenguaje C#.
Este capítulo termina...
Evolución biológica
Los algoritmos genéticos están basados en la evolución biológica. Si bien no es necesario comprender todos los detalles de este campo, sí es importante comprender 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 XVIII. En efecto, las pruebas de esta evolución se acumulaban, y los científicos querían comprender los fenómenos subyacentes.
Es a primeros del siglo XIX cuando aparece la paleontología (el término se empleó a partir de 1822), ciencia que se interesa en los fósiles y en formas de vida desaparecidas en la actualidad. Los científicos encontraban muchos esqueletos y los clasificaban. Estos presentaban muchas similitudes entre ellos, o con formas de vida actuales. Parecía evidente que había habido una continuidad, y que las especies se habían modificado progresivamente a lo largo de los milenios.
Además, las empresas de cría eran numerosas. Se sabía, desde hacía tiempo, seleccionar los mejores individuos de una manada para mejorar la producción de una especie (como la leche en las vacas), o simplemente por placer. Las razas de perros, de gatos o de caballos eran también numerosas y muy diferentes entre sí. Era evidente que un animal era similar a sus progenitores, si bien no era totalmente idéntico a ellos, de modo que seleccionando a los progenitores adecuados, era posible 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.
Por último, los grandes descubridores iban de isla en isla y descubrían nuevas especies. Parecía que los individuos situados en islas próximas también eran próximos físicamente entre sí. Por el contrario, eran muy distintos de los individuos de otro continente. Las especies habían evolucionado, por lo tanto, de manera diferente pero gradual.
La evolución biológica no era más que un tabú hasta el siglo XIX, pero una realidad científica. Sin embargo, faltaba saber cómo había podido tener lugar esta evolución....
Evolución artificial
La evolución biológica vista antes se denomina "inmaterial": en efecto, los principios de reproducción, de supervivencia o de selección no necesitan, como ocurre con la información, almacenarse o transmitirse, ni siquiera evolucionar.
Los investigadores de campos muy diversos, ya sea en economía, en sociología, en música... se han interesado en ella. La informática no es ajena, y esta evolución biológica puede utilizarse para crear una evolución artificial que permita resolver problemas que los métodos clásicos no permiten resolver.
1. Los principios
Los algoritmos evolutivos partirán de una población de soluciones potenciales a un problema. Cada una de ellas se evaluará para atribuirle una puntuación, llamada fitness. Cuanto mayor sea la fitness de una solución, más prometedora será.
A continuación, se seleccionan los mejores individuos y se reproducen. Se utilizan dos operadores artificiales: el cruce entre dos individuos, llamado crossover, y las mutaciones aleatorias.
Se aplica una etapa de supervivencia para crear la nueva generación de individuos.
El proceso es el siguiente:
En los años 60 aparecieron distintas variantes de manera independiente. Los algoritmos genéticos los creó Holland, pero hablamos también de programación evolutiva (Fogel) o de estrategias evolutivas (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, a menudo agrupados bajo el nombre genérico de algoritmos genéticos, se basan en el principio de evolución y este bucle generacional. Las diferencias se encuentran, principalmente, en la representación y en los operadores.
2. Convergencia
La convergencia hacia una solución óptima se demuestra teóricamente. Sin embargo, nada precisa el tiempo necesario para converger hasta alcanzar esta solución, que puede ser superior a lo aceptable.
Es importante, por lo tanto, seleccionar...
Primeras fases del algoritmo
Antes de pasar al cálculo de las generaciones, hay que empezar creando la primera. Para ello, vamos a tener que escoger entre varias representaciones, y a continuación inicializar los individuos de la población inicial. Además, habrá que escoger su función de evaluación.
1. Elección de la representación
Como con muchas técnicas de inteligencia artificial, la elección de la representación es primordial para limitar el espacio de búsqueda y para lograr que esté lo mejor adaptada posible al algoritmo seleccionado.
a. Población e individuos
La población contiene una lista de individuos. Es el lenguaje informático utilizado el que impone, en ocasiones, la representación de esta lista. Para simplificar la etapa de reproducción, es más sencillo seleccionar una estructura de datos con un acceso directo a un individuo, como por ejemplo un array, respecto a un acceso por recorrido, como una lista.
Los individuos contienen una lista de genes. También en este caso la forma exacta de esta lista estará, en parte, determinada por el lenguaje. No es obligatorio disponer de un acceso directo a cada uno de los individuos.
b. Genes
La representación de los genes requiere la mayor reflexión. Tradicionalmente, se trata de una lista ordenada de valores. Esto significa que para todos los individuos el primer gen tiene siempre el mismo significado (en nuestro ejemplo anterior, las fichas se almacenaban en orden).
En ciertos casos, puede resultar útil escoger una representación en la que el lugar de los genes sea variable, adaptando los operadores. Cada gen contiene, entonces, el nombre de la variable asociada y el valor (por ejemplo, anchura y altura para un objeto).
Además, es importante reflexionar bien acerca de las variables necesarias para resolver el problema. Se desaconseja tener demasiados valores para optimizar y conviene verificar que no existen variables redundantes, cuyos valores podrían depender de los demás.
Por último, es más complejo para un algoritmo genético resolver un problema en el que los distintos genes estén vinculados entre sí. Es posible establecer una analogía entre la diferencia...
Creación de las siguientes generaciones
Una vez creada y evaluada la primera población, hay que seleccionar los distintos operadores para pasar a la siguiente generación:
-
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 los descendientes creados.
1. Selección de los padres
La selección consiste en determinar cuáles son los individuos que merecen ser seleccionados como padres para la siguiente generación. Para ello, hace falta que, en proporción, los mejores padres se reproduzcan más que los padres con una fitness más baja, pero cada uno debe tener igualmente una probabilidad no nula de reproducirse.
En efecto, en ocasiones, es haciendo mutar o cruzando soluciones en apariencia menos ventajosas como se puede obtener una buena solución a un problema.
Los padres pueden seleccionarse de diversas maneras, deterministas o estocásticas. Las selecciones estocásticas (en las que interviene una parte de azar) son las más utilizadas.
Una de las soluciones más comunes consiste en utilizar una ruleta sesgada: cuanto más adaptado esté un individuo, mayor será su porción en la rueda. Los siguientes individuos tendrán una parte más pequeña progresivamente. Echándolo a suertes se indicará, a continuación, qué individuo ha sido seleccionado.
Estadísticamente, los individuos con una fitness mayor tendrán más hijos, aunque todos tienen al menos una opción de reproducirse, incluso aunque sea poco probable.
La parte de la ruleta de cada individuo puede determinarse mediante el rango de este; el primero tendrá siempre la misma parte respecto al segundo, o mediante su fitness. En este último caso, las proporciones cambiarán con cada generación y un individuo mucho más adaptado que los demás de la población tendrá muchos más descendientes, para transmitir rápidamente sus genes. Por el contrario, en una población uniforme en la que las diferencias en fitness sean débiles, la ruleta dará a cada individuo más o menos la misma probabilidad de reproducirse.
La segunda solución, además de la ruleta, consiste en utilizar...
Coevolución
La coevolución es un fenómeno biológico formalizado en 1964, tras un estudio de dos biólogos acerca de los vínculos existentes entre algunas plantas y ciertas mariposas. En efecto, demostraron que ambas especies habían evolucionado conjuntamente: las mariposas se comían la planta, que había desarrollado mecanismos para defenderse (algún veneno o alguna protección física). Las mariposas habrían desarrollado medios para resistir a estos venenos o a estas defensas.
Se trata, por lo tanto, de una carrera sin fin entre ambas especies, que intentan tener ventaja la una sobre la otra, para asegurar su propia supervivencia, sin poder dejar de evolucionar. Las dos especies en competición se habían desarrollado y habían evolucionado más deprisa que si cada una hubiera evolucionado sin esta interacción.
Esta coevolución se observa en todos los sistemas "presa - depredador". De este modo, existe una carrera evolutiva entre los hackers, que intentan penetrar la seguridad de los sistemas informáticos, y los responsables de seguridad, que intentan rechazar e impedir estos ataques. Cada campo debe evolucionar de manera constante, y rápidamente, para intentar conservar cierta ventaja sobre el otro campo, y contrarrestar cualquier amenaza/defensa implementada.
Esta presión evolutiva puede utilizarse para nuestra ventaja...
Dominios de aplicación
El equipo de John Holland de la Universidad de Michigan comenzó a trabajar con algoritmos genéticos en los años 60. Sin embargo, esta tecnología empezó a conocerse a partir de 1975 tras la publicación de su libro.
Los algoritmos evolutivos, en general, han comenzado a aplicarse en varios dominios. Para que sean eficaces, basta con responder a algunas restricciones:
-
El número de soluciones potenciales debe ser muy grande.
-
No existe un método exacto que permita obtener una solución.
-
Es aceptable una solución casi óptima.
-
Es posible evaluar la calidad de una solución potencial.
Si se cumplen estas cuatro restricciones, entonces un algoritmo genético puede ser una buena solución para encontrar una respuesta al problema que, si bien no puede garantizarse que sea la mejor, será en cualquier caso válida, y se obtendrá en un tiempo razonable.
Los encontramos, en primer lugar, en los dominios de la ingeniería y del diseño. En efecto, en la actualidad es cada vez más complicado crear piezas que respondan a las restricciones y minimicen o maximicen ciertas características (menos materia prima, consumo menor, mayor potencia, más resistencia...). De este modo, las carrocerías de los coches pueden crearse mediante algoritmos genéticos para hacerlas más aerodinámicas.
Su segundo gran...
Implementación
A continuación, nos centraremos en la implementación en C# de un algoritmo genético genérico que se utiliza en este caso para resolver dos problemas expuestos anteriormente:
-
El hombre de negocios, que consiste en encontrar la ruta más corta para recorrer un conjunto de ciudades.
-
El laberinto, dando la secuencia de instrucciones que deben seguirse para ir desde la entrada hasta la salida.
El código propuesto a continuación está disponible para su descarga y es compatible con .NET 4.5 o superior, ASP.Net 1.0, y Windows 8 o superior. El programa que contiene la función Main es una aplicación de consola para Windows.
1. Implementación genérica de un algoritmo
a. Especificaciones
Queremos codificar un motor genérico para un algoritmo genético, que se aplicará a continuación para resolver dos problemas diferentes, escribiendo la menor cantidad de código posible para pasar de uno al otro.
Es importante, por lo tanto, fijar bien los requisitos. El proceso evolutivo en sí mismo, el núcleo del sistema, se ocupa de inicializar la población y, a continuación, lanza la evaluación, la selección de los progenitores y la creación de los descendientes y, por último, la supervivencia. Se repite el bucle en base a la evaluación, hasta que se alcanza algún criterio de parada.
Vamos a definir dos criterios de parada posibles: se alcanza la fitness deseada o bien se alcanza un número máximo de generaciones. En ambos problemas, se trata de minimizar la función de evaluación: el número de kilómetros para el hombre de negocios o la distancia hasta la salida para el laberinto. Se fija, por lo tanto, una fitness mínima a alcanzar.
Podríamos, de hecho, adaptar el algoritmo para permitirle maximizar el valor de adaptación, pero como nuestros dos problemas buscan minimizar la fitness, no lo haremos aquí.
Los distintos parámetros del algoritmo se definen en una clase a parte. Tenemos, a continuación, interfaces o clases abstractas para los individuos y los genes. En efecto, son las dos únicas clases que es necesario redefinir para cada caso. Para el problema de salir del laberinto, necesitamos genomas de tamaño variable (la lista de instrucciones); el algoritmo debe permitir gestionar...
Resumen
Los algoritmos genéticos (o más genéricamente los algoritmos evolutivos) están inspirados en las diversas investigaciones llevadas a cabo en biología acerca de la evolución.
Se parte de una población de individuos, cada uno compuesto por un genoma, que es una lista de genes. Estos individuos se evalúan respecto a la calidad de la solución a un problema determinado que representan (lo que denominamos su fenotipo).
Los mejores individuos se seleccionan para actuar como reproductores. Se crean, a continuación, nuevas soluciones a partir de uno o varios progenitores. En caso de que intervengan varios progenitores, se realiza un crossover, es decir, un cruce entre la información genética de los distintos progenitores.
Los genomas de los descendientes sufrirán, a continuación, mutaciones aleatorias, que representan los errores de copia que podrían haber tenido lugar durante la reproducción. Cada descendiente, si bien es similar a sus progenitores, es potencialmente diferente.
Esta nueva generación debe, a continuación, sobrevivir, para formar parte de la población de la generación siguiente. Se repite el proceso hasta alcanzar soluciones óptimas o casi óptimas.
Los algoritmos genéticos permiten, así, resolver numerosos problemas para los que no existe una solución matemática conocida, y cuyo espacio...
