Algoritmos Genéticos (AGs)

dna

Una vez más, volvemos con un post que está más enfocado a ser didáctico que interesante y que en esta ocasión trata con la Computación Evolutiva; en concreto con Algoritmos Genéticos. Para todos aquellos que estudien informática este tema deberá, como mínimo, sonarles de algo y es que se trata de un método de resolución de problemas muy utilizado además de interesante por su propia naturaleza.

La Computación Evolutiva es una rama de estudio de la Inteligencia Artificial que involucra problemas de optimización combinatoria. La peculiaridad de este tema es que la búsqueda de soluciones se inspira en la evolución biológica.

La Computación Evolutiva surgió en los años 60 y poco a poco ha ido variando en diferentes corrientes que han desembocado en una serie de paradigmas, estrechamente relacionados entre sí, que resuelven problemas de diferentes ámbitos y con distintas representaciones. El paradigma más conocido y estudiado es el de los Algoritmos Genéticos, de ahora en adelante, AGs. Además existen otros como las Estrategias Evolutivas y la Programación Evolutiva. Hay muchos documentos en la red con amplia información sobre AGs y la Computación Evolutiva en general; con esta entrada solo pretendo dar una pequeña introducción al tema.

Podemos definir los AGs como métodos adaptativos, cuyo mayor uso está en los problemas búsqueda y optimización de parámetros. Están basados en la reproducción sexual y el principio de supervivencia de los individuos más aptos. Según Goldberg “los AGs son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas”. Veamos paso a paso cómo podemos utilizar y cómo funcionan estos algoritmos.

Los individuos

Un individuo representará una posible solución al problema que se pretenda resolver por medio de un AG. La representación del individuo puede variar pero en general se trata de una serie de parámetros cuyo conjunto se suele llamar cromosoma; el de un individuo en concreto se llama genotipo. El valor que representa el genotipo se denomina fenotipo y el que se puede obtener a partir de éste será la aptitud. Como ejemplo supongamos que queremos optimizar una función real f(x) y que el valor 17.8 es una posible solución. Si utilizamos una codificación binaria de los individuos, 001000010 sería el genotipo, el valor representado por esta cadena, 17.8 será el fenotipo y el valor f(17.8) sería la aptitud. La representación de cada individuo la elegimos nosotros.

La evaluación de un individuo

Para saber cómo es de bueno un cierto individuo utilizaremos un método que dependerá del problema que queramos resolver; en cualquier caso, el método que utilicemos para evaluar a los individuos se llama fitness. Mediante el fitness estableceremos la base con la que se obtiene la aptitud de los individuos y, según nuestros intereses, podremos determinar qué individuos son mejores soluciones a nuestro problema y cuáles peores.

La población

Ahora que sabemos qué es un individuo y de qué se compone, vamos a ver la población. Para hallar una solución se parte de un conjunto inicial de individuos, generado aleatoriamente, ésto es lo que se conoce como población. De esta manera lo que vamos a tener es un conjunto de posibles soluciones a nuestro problema que vamos a hacer evolucionar en base a una serie de operadores de manera que en cada iteración del AG habremos obtenido una población distinta, es decir, una nueva generación.

Operadores de selección

Para obtener una nueva generación de individuos, habrá que utilizar un método de selección tal y como ocurre en la naturaleza. Existen varias metodologías y en general se basan en la elección según la aptitud de los individuos que conforman la población. Las más utilizadas son las siguientes:

  • Selección por ruleta: Es el método más utilizado y en el que la probabilidad de que se escojan individuos con mejor aptitud es elevada. Supongamos que tenemos una tarta que vamos a repartir entre todos los individuos. A cada uno de ellos le daremos el trozo mayor o menor según su aptitud de manera que el mejor individuo es el que se lleva el trozo más grande. Ahora digamos que cada uno pinta su porción de un color y la devuelve al plato, quedando la tarta como al principio solo que cortada en en trozos de distintos tamaños y de colores. Para seleccionar cada individuo supongamos que la tarta es ahora una ruleta de casino. Al lanzar la bola sobre la ruleta parará sobre una porción de un cierto color. El dueño de la porción sobre la que pare la bola es el seleccionado. Es común utilizar el siguiente algoritmo para implementar este operador:
1 - Se calcula la suma de todos los fenotipos de los individuos
2 - Se genera un número aleatorio r en el intervalo [0,suma].
3 - Se van sumando de nuevo los fenotipos uno a uno, ordenadamente, y el individuo que supere el valor r es el seleccionado.
  • Selección por torneos: Se trata de comparar los individuos y existen dos versiones: determinística y probabilística. En la determinística se escoge un conjunto de individuos de la población aleatoriamente y de estos individuos se selecciona el más apto para que pase a la siguiente generación. La versión probabilística se diferencia en que no se escoge siempre al más apto sino que se escoge una probabilidad p y según ésta se escogerá al mejor individuo o al peor para compensar. Siempre se puede jugar con esta selección ampliando o disminuyendo el conjunto escogido para el torneo.

Es importante comentar que la selección de uno u otro método determinará la búsqueda del AG. En caso de que siempre se escojan individuos con los mejores valores estaremos buscando una solución en función a la población inicial. De otro modo quedan más posibilidades abiertas.

Operadores de Cruce

Después de seleccionar los individuos, éstos deben ser combinados para producir la descendencia que formará la futura generación. La importancia de esta operación es muy elevada y va a determinar el correcto funcionamiento del AG. Para explicar esta sección supondremos que el cromosoma de los individuos está formado por una cadena de caracteres binarios. Veamos los distintos métodos.

  • Cruce a un punto (SPX): Una vez seleccionados dos individuos, se cortan sus cromosomas por un punto aleatorio y se mezclan de manera que si el cromosoma del primer individuo se corta en A+B y el segundo en C+D se generan dos nuevos individuos de cromosomas A+D y B+C respectivamente.
  • Cruce a dos puntos (DPX): Es una generalización del caso anterior de manera que en lugar de cortar el cromosoma en un punto se corta en dos. Así un individuo A+B+C y otro D+E+F formarían los individuos A+E+C y D+B+F.
  • Cruce uniforme (UPX): Todos los genes tienen, en un principio, la misma probabilidad de ser escogidos. Si tenemos, por ejemplo, 5 genes para cada padre se genera aleatoriamente una máscara de 0 y 1. Esta máscara determina qué genes de qué padre forman el hijo de modo que donde haya un 1 se pondrá el gen de primer padre y donde haya un 0 el gen del segundo padre.
  • Cruce para codificaciones no binarias: En caso de que los individuos no estén representados, como hemos supuestos en un principio, con una codificación binaria sino con reales o enteros, pueden definirse otros métodos de cruce basados la media, la media geométrica o la expansión.

La mutación

Esta operación se suele utilizar conjuntamente con el cruce aunque se puede insertar también en la selección. Principalmente se trata de tomar el genotipo del individuo y cambiarlo en base a una probabilidad. Generalmente esta probabilidad es muy baja, de un 0.01%. La operación puede variar según la representación; en caso de utilizar una codificación binaria del genotipo se puede simplemente negar un bit aleatorio; si trabajamos con codificación real podemos sumar 1 o multiplicar por un número próximo a 1.

El Algoritmo Genético Simple

Una vez hemos visto los conceptos y los posibles operadores, vamos a definir cómo es la estructura de un Algoritmo Genético Simple. A continuación podéis ver el pseudocódigo de uno de estos algoritmos.

Inicializar población actual aleatoriamente
MIENTRAS no se cumpla el criterio de terminación
       crear población temporal vacía
  MIENTRAS población temporal no llena
        seleccionar padres
        cruzar padres con probabilidad Pc
        SI se ha producido el cruce
             mutar uno de los descendientes con probabilidad Pm
             evaluar descendientes
             añadir descendientes a la población temporal
        SINO
             añadir padres a la población temporal
        FIN SI
  FIN MIENTRAS
  aumentar contador generaciones
  establecer como nueva población actual la población temporal
FIN MIENTRAS

En resumen

Y hasta aquí ha llegado la introducción a esta metodología de resolución de problemas. Sabed que en la actualidad es una práctica de mucho peso la utilización de estos algoritmos y que su uso no se queda en la computación.

Si he escrito alguna barbaridad o hay algún error en esta entrada, dejad un comentario. Comentaros también que tengo un ejemplo de uso en C. Si a alguien le interesa echarle un vistazo que me lo diga y lo subo al blog.

EDIT: He subido el ejemplo. Entrad a verlo en https://just4cool.wordpress.com/2010/01/27/algoritmos-geneticos-un-ejemplo-simple/

Anuncios

15 pensamientos en “Algoritmos Genéticos (AGs)

  1. hola amigo, de verdad bueno el post, me resolvió muchas dudas, aunq sería de verdad mucho mejor si pudieras subir un ejemplo completo hecho en c++ o c, es q me gustaría hacer una implementación de un AG simple para la otimización de funciones (maximizar). saludos y muchas gracias de antemano, de verdad agradecería una pronta respuesta

  2. Acabo de ver tu comentario. Si te sigue interesando avísame de nuevo y te envio por correo un ejemplo de un algoritmo genético codificado en C.

    Un saludo !

  3. Hola !!
    A mi también me ha gustado mucho tu post, aunque estaría muy agradecida si pudieses mandarme algún ejemplo de algún algoritmo genético completo en c ó c++ de mediana complejidad.Me parece muy interesante el tema.

  4. Muy bueno el post. Me gustaria que me envies algun ejemplo de codigos de complejidad simple y mediana. Desde ya muchas gracias

  5. En cuanto tenga un rato te envío un ejemplo de optimización en C. Me alegro de que te haya gusto el post.

    Un saludo !

  6. muy buen portal me puedes enviar el codigo en c porfa soy nuevo en el tema y me gustaria saber mas de el saludos!!

  7. Disculpa, podrias enviarme el ejemplo del algoritmo genetico programado en C?, estoy estudiando GA’s en mi maestria y me seria de mucha utilidad.

  8. Otro que lleva poco tiempo en esto de los algoritmos evolutivos, agentes inteligentes y redes neuronales. Si me pudieras mandar tambien el ejemplo al mail.

    Un saludo.

  9. En cuanto pueda te lo envío que me pillas un poco liado !! Pero no hay problema, es un ejemplo bastante sencillo que básicamente codifica lo que explico en la entrada.

    Un saludo !

  10. Perdona , debe de resultarte ya pesado, pero si tuvieras algun emjemplo del algoritmo o cualquier cosas que creas que me puede ayudar , ya que estoy realizando el proyecto fin de carrera sobre una apicacion real de algoritmo egenetico por ejemplo aplicado al metro calculando rutas mas cortas en tiempo segun los cruces de lienas

  11. Pingback: 10 consejos para dar consejos | Mati, una profesora muy particular

  12. Pingback: 10 consejos para dar consejos | Dominican Republic

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 )

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 )

Google+ photo

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

Conectando a %s