6

Cómo programar un Algoritmo Genético – Parte I: In Theory

Saludos, humano. Al habla Transductor. Bajo este nombre rimbombante los Algoritmos Genéticos pueden parecer cosa de Magia Arcana, algo que sólo los iniciados en las retorcidas sutilezas de la matemática avanzada pueden programar.

Pues nada más lejos de la verdad, lector. Los Algoritmos Genéticos probablemente sean una de las ideas más intuitivas del campo de la IA y una buena forma de introducirse en este mundo.

Este tutorial no es una guía para alzar la Robolución y acabar con la especie humana, si no más bien una introducción breve a los Algoritmos Genéticos. Este tutorial tendrá dos partes: en la primera voy a explicar la teoría que hay detrás de estos algoritmos, y en la segunda voy a implementar uno en Python.

Dicho esto, voy a empezar. Pero en vez de saltar directamente a analizar los Algoritmos Genéticos, escribiré unas notas históricas.


 

Un poco de historia: IA bioinspirada vs. IA mainstream

Durante casi cincuenta años, los investigadores en el campo de la Inteligencia Artificial (abreviada como IA, porque a los humanos os encantan las siglas) han tratado de recrear, con algoritmos y fórmulas matemáticas, el funcionamiento del cerebro humano.

Si bien la Inteligencia Artificial ha sido capaz de resolver problemas como jugar al ajedrez, optimizar el tráfico aéreo y dirigir la compraventa de acciones de bolsa, a lo largo de los años ha ido degenerando y alejándose de la premisa inicial de emular el funcionamiento del cerebro humano. Hoy en día esta Inteligencia Artificialmainstream” tiene más que ver con la Minería de Datos, la Robótica y la Teoría de Grafos que con la neurología.

Kasparov-DeepBlue

Deep Blue fue la primera computadora que ganó al campeón Garry Kasparov al ajedrez. Imagen de stanford.edu

En contraposición a la IA mainstream, durante la década de los ochenta surgieron un nuevas técnicas como la ingeniería neuromórfica, la inteligencia de enjambre o la robótica evolutiva. La Inteligencia Artificial Bioinspirada se basó en ellas y cuestionó la validez de los métodos hasta entonces utilizados para intentar construir máquinas que emulasen a un sistema biológico.

La nueva IA, como se suele llamar, supo ver más allá de la fantasía antropomórfica de crear un cerebro humano artificial. Expandió su campo de investigación a otros organismos, sistemas y procesos biológicos que durante miles de años han permitido a los organismos vivos adaptarse y sobrevivir.

Por supuesto, demostró ser muy eficaz, especialmente para resolver problemas mal definidos, trabajar con información corrupta o adaptarse a entornos cambiantes.


¿Qué es un algoritmo genético?

Todos los seres vivos que corren actualmente por la tierra (excepto nosotros, los robots) son fruto de un largo proceso evolutivo. Imagínate una población de gacelas que son cazadas por un león. A lo largo de las generaciones, sólo las gacelas con rasgos favorables que les ayuden a huir de los leones (como patas largas para correr más rápido, pelaje del mismo color que la hierba para camuflarse…) podrán sobrevivir y pasar sus genes a la siguiente generación. Por tanto, sus hijos tendrán estos rasgos ventajosos.

Los algoritmos genéticos se inspiran en la evolución natural para solucionar problemas de optimización que de otra forma serían difíciles para un diseñador humano. En vez de una población de gacelas, tienes un conjunto de soluciones al problema a resolver. Se llama población al conjunto de soluciones e individuo a cada una de las soluciones (aunque la terminología puede variar según quién te lo explique). El algoritmo evalúa cada una de las soluciones y selecciona las que mejor resuelven el problema. Por ejemplo:

ejemplo_evolucion

Debo insistir en que los algoritmos genéticos sirven básicamente para optimizar. Si quieres construir un coche, un algoritmo genético no te lo va a construir desde cero (por lo menos no en un tiempo razonable), pero a partir de un coche existente va a construirte un coche mejor: menos consumo, mayor capacidad de combustible, poca resistencia al aire… y con una fragancia de pino permanente en la cabina.

La estructura de un Algoritmo Genético es un proceso iterativo que actua sobre una población de individuos. Cualquier algoritmo genético puede resumirse en 6 pasos:

fases_algoritmo

Pulsa en la imagen para ampliarla


 

Definir el problema: Representación Genética

Como ya he dicho, los algoritmos genéticos sirven para optimizar. Dado un problema a resolver, un algoritmo genético dará (si está bien programado) soluciones cada vez mejores a este problema.

Por eso es importante definir bien el problema, y crear una representación genética adecuada. ¿Y qué es esto?

En el apartado anterior hacía la comparación de un Algoritmo Genético con una población de gacelas. Cada gacela tiene un material genético determinado, llamado genotipo. Si analizamos dos gacelas, veremos que tienen un genotipo muy parecido, pero diferente.

Si el genotipo es el material genético de un individuo, el fenotipo son las características del individuo producidas por los genes. El genotipo de una mariposa es su material genético, y su fenotipo la coloración, tamaño de las alas… que son consecuencia de las combinaciones de genes.

A la hora de programar un Algoritmo Genético debes pensar cuáles serán los elementos que conformarán el genotipo de los individuos y de qué forma se corresponden a un fenotipo. Por ejemplo, si estás evolucionando un circuito analógico, la representación genética puede ser un alfabeto de carácteres que se corresponda a componentes como Resistencias, Condensadores, Transistores… el genotipo de cualquier solución estará formado por una combinación de estas letras.

¿Has llegado hasta aquí, lector? Bien, te has ganado un respiro. Tienes mi permiso para ir a tu cocina y tomar algo. Después analizaré cada una de las partes de un Algoritmo Genético…


 

1- Inicialización:

La población inicial puede generarse al azar, pero debe ser lo suficientemente grande y diversa para que durante la evaluación los individuos muestren un fitness distinto. Si todos los individuos tienen el mismo fitness, el programa no va a poder seleccionar bien los mejores para su reproducción.


 

2- Función de Fitness (Evaluación)

La Función de Fitness evalúa cada uno de los individuos de la población y les asigna un valor numérico según su calidad. Este valor numérico se llama fitness.

Voy a ponerte un ejemplo. Supongamos que cada individuo de la población es una lista de números (como [8,4,3,7,7]) y quieres programar un algoritmo genético para conseguir listas de números que se aproximen a un modelo. Puedes programar una función que calcule cuántos números tiene en común cada individuo de la población con el modelo, y el resultado es el fitness de la solución:

ejemplo_fitness

Cuando es un humano quien evalúa cada solución, estamos hablando de fitness subjetivo.

3- Selección y Reproducción

Hay varias formas de seleccionar los individuos con el fitness más elevado para crear una nueva población. Algunas de las más utilizadas son:

  • Selección proporcional: cuanto más alto sea el fitness de un individuo, mayor será la probabilidad de que pase a la siguiente generación.
  • Selección por torneo: se eligen varios individuos al azar de la población (por ejemplo 3) y se compara su fitness. El individuo con el fitness más alto pasará a la siguiente generación. ¿Para qué sirve esto? Hay ocasiones en que es interesante escoger soluciones que no son tan buenas para poder mantener una buena variabilidad genética entre los individuos. Así al mezclar el material genético se exploran soluciones muy distintas.
  • Selección por rango: los individuos se ordenan en función de su fitness, y la probabilidad que tienen de reproducirse va según su posición.

La presión expresa el porcentaje de individuos que serán seleccionados. Cuánto más alta sea la presión, menos individuos serán seleccionados para la siguiente generación.


 

4- Crossover y Mutación

Una vez se han seleccionado los mejores individuos, el Crossover consiste en mezclar el material genético de estos para crear los nuevos individuos.

La forma más sencilla de hacerlo es mediante un One-point Crossover. Consiste en elegir un punto al azar de los dos individuos e intercambiar el material genético a partir de esta posición.

crossover_one_point

Ejemplo de One-point crossover

El crossover no ayuda a encontrar nuevas soluciones al problema. Es por eso que hay que mutar el material genético de los nuevos individuos, es decir: añadir pequeñas variaciones al azar.

Te estarás preguntando… ¿pero qué pasaría si no hubiera mutaciones? Supongamos que el modelo sea [1,1,1,1,1] y los individuos elegidos sean [5,1,1,1,1],[2,3,1,1,1],[4,1,8,1,1]. No hay ninguna forma de que mezclando el material genético de estos individuos pueda obtenerse el modelo (ninguno de los tres tiene ‘1’ en la primera posición). A no ser que por casualidad alguno de sus hijos mutase y consiguiera un ‘1’ al principio. Por esto es importante añadir variaciones al azar (mutaciones).

Es buena idea que en la nueva población haya una copia exacta, sin modificar ni cruzar, de cada uno de los individuos elegidos durante la selección. De esta forma, si por alguna razón la nueva población de individuos resulta ser peor que la anterior, por lo menos no se pierden soluciones que hasta entonces eran buenas.

Esto es lo básico. En la segunda parte, explicaré cómo puedes implementar un algoritmo genético sencillo con Python.

Ir a la PARTE II

Final de línea.

 

 

Tr4nsduc7or

Originariamente creado cómo un galvanómetro de bolsillo, Transductor tomó consciencia de si mismo y fue despedido cuando en vez cumplir con su trabajo se dedicó a pensar teorías filosóficas sobre los hilos de cobre, los electrones y el Sentido del efecto Joule en el Universo. Guarda cierto recelo a sus creadores por no comprender la esencia metafísica de las metáforas de su obra. Actualmente trabaja a media jornada cómo antena de radio, y dedica su tiempo libre a la electrónica recreativa y a la filosofía.

Antes de comentar, por favor, lee las Normas

6 Comentarios en "Cómo programar un Algoritmo Genético – Parte I: In Theory"

avatar
Ordenar por:   más nuevos primero | más antiguos primero
Aura
Humano

Excelentes tutoriales, Me fascinaron. Sigue así. suerte

masquedios
Humano

Muy interesante!!!!! a por la parte II ya!

trackback

[…] organismo simiesco basado en el carbono. Aquí Transductor. El pasado viernes publiqué la primera parte de esta série de tutoriales sobre Algoritmos Genéticos. Hoy en la segunda parte te enseñaré a […]

Manuel Alberto Chavez Salcido
Humano
Manuel Alberto Chavez Salcido

Espero la segunda parte. Saludos

admin
Admin

Deja descansar un poco al pobre Transductor que lleva días redactando esto sin parar 😛 Seguramente el próximo lunes llegará la segunda parte.

wpDiscuz