miércoles, septiembre 20, 2006

Algoritmos genéticos (I)

Muy a menudo uno se encuentra con problemas que no es capaz de resolver, o si es capaz, no dispone del tiempo suficiente. Tenemos por naturaleza la tendencia a buscar la mejor solución de todas, pero sin embargo a veces basta con conformarse con una lo suficientemente buena. Para esto surgieron los métodos heurísticos, y los algoritmos genéticos son uno de ellos.



Antes de explicar la heurística, la algoritmia y la genética, expondré un ejemplo sencillo. Supongamos que queremos comprarnos un coche y buscamos aquel que ofrezca la mejor calidad/precio. Sabemos distinguir claramente un coche más caro que otro, por su precio, y en cierta medida alguien entendido puede distinguir la calidad de dos coches en un buen número de detalles, la potencia, la capacidad, si tiene CD, el número de airbags, el ruido y muchos más.


Para resolver el problema damos un valor a cada una de estas características, de forma que podamos decidir matemáticamente si un coche es mejor que otro, según nuestro criterio (no todo el mundo tendría el mismo). Por ejemplo podríamos partir de cero y sumar 100 al valor por cada Airbag, 200 si incluye radio, 500 si trae CD y 900 si tiene MP3; podríamos sumar también los CV multiplicados por algún valor, etc. Para un coche dado, a su precio le llamamos P y a su calidad C. De esta forma, estamos buscando el coche con el mejor C/P (mayor calidad al menor precio). Acabamos de hacer un modelo matemático de nuestro problema.


Ahora lo único que tendríamos que hacer es observar todos los coches del mercado y quedarnos con aquel cuyo valor para C/P sea más alto . ¿Fácil, no? Pues supongamos que no tuviéramos tiempo para revisar todo el mercado automovilístico. Sólo tenemos tres días para elegir un coche y no podemos ver más de 6 coches al día. ¿Qué hacer? Una buena solución sería ver 18 coches cualesquiera en tres días y quedarnos con el mejor de ellos. No sería mala idea, pero quizá las haya mejores. Por ejemplo podríamos ver el primer día un coche de cada marca, de 6 marcas distintas, y anotar las dos marcas que han dado mejor C/P. El segundo día iríamos a ver 3 modelos de cada una de las dos mejores marcas, hacemos la media de los C/P de cada marca y anotamos la marca que mejor puntuación haya obtenido. Por último, el tercer día vamos a ver otros 6 nuevos modelos pero sólo de la mejor marca. Al final hemos visto 18 coches igualmente, y nos quedaremos con el que mejor C/P haya obtenido en cualquiera de los tres días. El resultado por lo general será mejor, aunque en algún caso particular aislado obtiviéramos un resultado peor que en el primer método.


Las dos posibilidades son métodos heurísticos. Esto es, métodos que intentan llegar a la mejor solución posible a través de la búsqueda y exploración de soluciones posibles. En la práctica se emplean cuando la complejidad del problema no permite resolverlo de una forma racional. La palabra heurística se deriva del griego euriskein, que significa hallar, encontrar.


Un algoritmo genético es un método heurístico que emplea toda la potencia de la teoría de la evolución para resolver problemas, obteniendo una solución más próxima a la mejor, cuando no podemos explorar todas las posibles soluciones para llegar a la mejor. Ahora viene lo entretenido del artículo. ¿Cómo se lleva a cabo un algoritmo genético? ¿Qué clases de problemas resuelve?


Primero contestaré a la segunda pregunta. Un algoritmo genético es capaz de resolver cualquier problema cuyas soluciones puedan codificarse numéricamente, y en los que podamos decidir, entre dos posibles soluciones, cual de las dos es mejor. Asombrosamente esto podría aplicarse para cualquier problema que se nos pudiese ocurrir, sólo que no es tan sencillo codificar según que tipo de soluciones (como por ejemplo las distintas posibles soluciones a la pregunta ¿Qué pieza musical clásica acompaña mejor en una cena romántica?).


Una vez que tengamos modelizado el problema se aplica el algoritmo genético. Existen numerosas variantes de los algoritmos genéticos y formas de configurarlos. El funcionamiento de un algoritmo genético consiste, al igual que en la naturaleza, en aplicar una y otra vez estos pasos tan naturales:



  • Generar una población inicial de soluciones al azar.

  • Seleccionar las mejores soluciones entre la población generada

  • Cruzar numéricamente esas soluciones entre ellas (mezclar sus cifras binarias), para generar una nueva población del mismo tamaño que la original

  • Mutar algunos individuos de la nueva población, cambiado alguna de sus cifras al azar


  • Después se repite un número determinado de veces la selección, cruce y mutación. Tras un número lo suficientemente grande de iteraciones podremos estar bastante seguros de que la población final será mejor que inicial, o al menos así ocurre en la naturaleza darwiniana.


    El próximo día explicaré más en detalle en qué consisten estos pasos y la magia que hay tras ellos. Creo que por hoy ya os he aburrido bastante

    6 comentarios:

    WinterN dijo...

    Jeje, uno tiene su bibliohgrafía, pero te aseguro que si meto algún texto que no sea mío, lo pondré como cita, o lo diré explícitamente.

    Te aseguro que queda lo más divertido del artículo, para quien le guste jugar con los números :)

    Anónimo dijo...

    Me encanta tu blog WinterN.
    Ánimo y sigue así!!!

    Unknown dijo...

    Vaya nerd estás hecho! XD

    PD: Gran blog

    carlos de la b dijo...

    Hola, saludos, sabes estoy comenzando un doctorado sobre algortimos geneticos aplicados en la arquitectura, he encontrado algunos ejemplos pero de dudosa credibilidad, sin embargo otros muy buenos como ArchiKluge, su pudises orientarme sería genial.

    saludos carlos de la b.

    Anónimo dijo...

    Me has aclarado el panorama tío eh! :D,,,es que no entre a las clases de algoritmos genéticos en mi curso de io, y pucha lo que has escrito está muy claro y entendible! SALUDOS; Y SIGUE ASÍ

    Anónimo dijo...

    Me parece muy bien la explicación.. buenisimo.!!