Los algoritmos genéticos o cómo optimizar siguiendo las reglas de la naturaleza

Gran parte de los problemas a los que te enfrentas a diario se pueden clasificar como problemas de optimización. Estos problemas son del tipo: qué combinación de autobuses me permitirá llegar más rápido al trabajo o cuál sería el mejor material para fabricar el ala de un avión de modo que se minimice la resistencia aerodinámica, lo típico. En función de la naturaleza del problema, encontrar estas soluciones óptimas pueden ser sencillas o casi imposibles. Antes de abandonar toda esperanza ante este último caso, uno puede echar un vistazo a qué ha hecho la naturaleza para afrontar este infierno previamente.

En la década de los setenta, siguiendo esta línea de pensamiento, John Henry Holland  (1929-2015) ideó los algoritmos genéticos. De este forma se iniciaba una de las primeras ramas de la inteligencia artificial. Con esto dicho, el siguiente paso lógico es definir qué es un algoritmo. Un algoritmo es una receta con una serie de pasos para resolver un problema y la novedad considerada por el doctor Holland, por la cual se añade la coletilla de “genéticos”, es introducir conceptos propios de la evolución de las especies, cuya esencia es la supervivencia del óptimo.

Los principios que rigen estos algoritmos se toman prestados de la evolución darwiniana y se resumen en tres: nacer, relacionarse y reproducirse.

darwinmeme

El primer paso, el nacimiento, consiste en la inicialización de una gran cantidad de soluciones, entre decenas y cientos de miles, de forma aleatoria que cubran todo el rango de posibilidades. En el ejemplo del material del ala, se consideraría un alto número de materiales desde el cartón hasta los materiales cerámicos. De esta forma se habría generado nuestra primera generación de posibles soluciones.

El siguiente paso en esta receta sería considerar la relación entre soluciones y el proceso de selección. Un subconjunto de la generación actual es seleccionada para dar lugar a la siguiente . Esta selección se lleva a cabo considerando el parámetro que queramos optimizar, en nuestro caso el coeficiente de resistencia del material. Sin tener mucha idea de aerodinámica, es de esperar que en este paso, el cartón y materiales similares se desechen como posibles soluciones. En contraposición, esperaríamos que el cobre, el aluminio y el titanio sobrevivieran.

Por último, la reproducción o generación de la segunda generación de soluciones, que se produce cruzando las soluciones previamente seleccionadas e incluso pueden sufrir mutaciones. Si queremos una imagen de este paso en nuestro ejemplo, podríamos imaginarlo como la generación de aleaciones entre distintos materiales.

Estas soluciones crías se convertirán en soluciones progenitoras en una segunda iteración del algoritmo, acercándonos cada vez a la solución óptima. Existen diferentes formas de terminar este proceso evolutivo: predefinir el número de generaciones que se van a crear, que se encuentre una solución que satisface nuestras necesidades o que reviente el ordenador.

Son numerosos los ámbitos en los que se aplica este tipo de algoritmos, como puede ser generar la mejor trayectoria posible para un brazo robótico, el comportamiento de los jugadores “controlados por la máquina” en los videojuegos o el problema más interesante e importante del momento, calcular los parámetros cosmológicos que describen nuestro Universo :).

Referencias

Existen muchísimas referencias sobre este tema, tanto del formalismo matemático como de sus implementaciones en distintos lenguajes de programación. Mi favorita por la sencillez es la siguiente:

  • Kumar, M., Husain, M., Upreti, N., & Gupta, D. (2010). Genetic algorithm: Review and application.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s