Algoritmos Genéticos – Ejemplo
Para descargar el programa con el algoritmo genético que se muestra en esta entrada, lo podeis descargar pinchando AQUI.
Como ya se vio en el post "¿Que es la Computación Evolutiva?", los algoritmos genéticos son un tipo de algoritmos evolutivos que sirven para resolver problemas de optimización y que se diferencia principalmente de los demás tipos de algoritmos evolutivos por la forma de representar a los individuos, que lo hace por medio de cadenas binarias (Arrays binarios).
En esta entrada vamos a poner un ejemplo de como obtener el máximo de la función que se muestra a continuación en el rango de [0-15] utilizando un algoritmo genético (el argumento del seno de la función se da en radianes). En este ejemplo que ponemos, esta función sera la "Función de Fitness" o función de calidad que utilizaremos en este problema, ya que la 'x' que maximize esta función, sera la mejor solución al problema.
Antes de ver como solucionar el problema, vamos a mostrar en la siguiente imagen la gráfica de esta función para comprobar que el máximo de esta función para el intervalo [0-15] es "x=11" y de esta forma podremos ver lo "bueno o malo" que son los algoritmos genéticos:
El primer "problema" que se nos plantea es "como representar a los individuos" que tendremos en este algoritmo genético. Pues en este caso es muy sencillo y el problema esta planteado adrede para ello. Como en los algoritmos genéticos los individuos se representan con cadenas binarias es muy intuitivo que si queremos encontrar el máximo entre el intervalo [0-15] representemos a los individuos como "números binarios" en este caso como números binarios de longitud 4. Con un numero binario de 4 bits podremos representar 16 números (2^4=16) con lo cual decimos que "los individuos van a estar representados por un cromosoma de longitud 4". Ejemplo:
Una vez llegado a este punto en el que tenemos definida la función de fitness y como representar a los individuos, tenemos que ver: como generamos la primera generación de individuos, como los emparejamos y como mutan. Para realizar todas estas cosas se generará un conjunto de números aleatorios con los que trabajaremos y que veremos su significado a continuación. Para ello y antes de nada deberemos definir con que numero de individuos queremos trabajar, la probabilidad de generación del cromosoma, la probabilidad de emparejamiento y la probabilidad de mutación. Para ver de forma detallada todo este proceso y siguiendo el pseudocódigo mostrado en la entrada de "¿Que es la Computación Evolutiva?" vamos a definir todas estas cosas y ver de forma detallada el transcurso del algoritmo:
-
- Longitud del cromosoma: 4
- Conjunto de elementos del cromosoma: {0,1}
- Número de individuos de la población: 2
-
Para la creación de la primera generación:
3.1.- Probabilidad del elemento '0': num aleatorio < 0.5
3.2.- Probabilidad del elemento '1': num aleatorio >0.5 - Probabilidad de emparejamiento: 0.7
- Probabilidad de mutación: 0.3
El conjunto de números aleatorios con los que vamos a trabajar va a ser el siguiente:
En primer lugar vamos a obtener los dos primeros individuos que van a formar la generación inicial. Para obtener los cromosomas de los dos individuos vamos a utilizar los 8 primeros números aleatorios (4 por individuo). Si el numero aleatorio es menor que 0.5 pondremos el elemento '0' al cromosoma y si es mayor que 0.5 le daremos valor '1'. A continuación mostramos como generamos los individuos:
Una vez que conocemos los individuos, aplicamos la función de fitness para que nos diga que individuo es el mejor de los dos y cuanto mejor es uno que otro para ver posteriormente que probabilidad de emparejamiento tiene cada uno:
Como vemos ambos individuos son muy parecidos porque tienen una calidad similar aunque el individuo 2 es un poco mejor que el individuo 1 ya que lo que pretendemos es encontrar el máximo de la función. Ahora pasamos a calcular las probabilidades de cada individuo para el emparejamiento y esto lo hacemos con una regla de tres simple:
Lo que pretendemos con esto es ver que individuos seleccionamos para emparejarse. Para ello cogeremos los dos siguientes números aleatorios y si están dentro de los rangos de selección, ese individuo sera apto para el emparejamiento (en el caso de que haya emparejamiento es esa generación). Esto quiere decir que si sacamos un número aleatorio dentro del intervalo [0-0.48) el individuo 1 se emparejará y si otro numero aleatorio esta en el intervalo [0.48-1] tambien sera apto el individuo 2 para emparejarse. A continuación vemos si son aptos para emparejarse o no:
Con esto vemos que los dos individuos son aptos para el emparejamiento, pero ¿habrá emparejamiento en esta generación?. Para ver si en esta generación hay emparejamiento hay que ver si el siguiente numero aleatorio esta dentro de la probabilidad de emparejamiento que la definimos como 0.7, lo que quiere decir que si el número aleatorio esta en el rango [0-0.7) habrá emparejamiento y si esta entre [0.7-1] no habrá emparejamiento. Esto lo mostramos a continuación:
Vemos que en esta generación hay emparejamiento y que además los dos individuos se van a emparejar, así que ahora hay que ver como se emparejan estos dos individuo. Para ello hay que calcular el "punto de corte" del cromosoma sobre el que se va ha hacer el intercambio. Como se muestra a continuación se ve que hay 3 puntos de corte en el cromosoma para que se puedan emparejar:
Esto quiere decir que volvemos a crear rangos de selección y seleccionaremos uno de los tres puntos de corte para el emparejamiento. Esta selección del punto de corte lo mostramos a continuación:
Con todo lo calculado podemos ya generar unos nuevos individuos. Dado que hemos seleccionado como punto de corte al tercer cromosoma, querrá decir que el primer individuo tendrá como valor de la última posición del cromosoma el valor de la ultima posición del cromosoma del individuo 2, lo que quiere decir que el emparejamiento dará como resultado dos nuevos individuos con el intercambio en los valores del cromosoma. Esta intercambio lo mostramos a continuación:
Ya por último queda ver si alguno de los individuos sufrirá alguna mutación. Para ello cogemos un número aleatorio por cromosoma (8 números aleatorio, 4 por cada individuo) y vemos si esta dentro de la probabilidad de mutación, es decir, que si el numero aleatorio esta dentro del rango [0-0.3) el elemento del cromosoma mutará a su complementario y sino esta en ese rango no habrá mutación. A continuación vemos las mutaciones que se producen:
Llegados a este punto ya tenemos una nueva generación de individuos creada que es una generación en la cual tenemos un individuo (individuo 2 con x=1) que es un individuo "mejor" que los de la generación anterior ya que su valor aplicando la función de fitness es de 1,41 tal y como se muestra a continuación:
Tambien vemos que el individuo 1 es peor individuo que sus progenitores. Como podréis observar solamente con una única generación no nos hemos acercado al mejor individuo que seria el individuo con valor x=11 con lo cual necesitaríamos más individuos y hacer esto con muchas más generaciones, es decir repetir este proceso 'n' veces y en la generación 'n' coger el mejor individuo.
Para que podais "jugar" y ver lo bueno o lo malo que son los algoritmos genéticos se os ha compartido un programa hecho en JAVA (un ".jar" que lo podeis descargar en el enlace del principio de la entrada) en el que se puede resolver este problema poniendo los individuos que se quieran, las generaciones que se quieran, en mas rangos de la función, es decir con individuos representados con más cromosomas y cambiando las probabilidades de emparejamiento y mutación. Tambien se pueden ver todos los detalles y pasos que da el algoritmo genético en cada generación realizada. A continuación os muestro una imagen del programa tras una ejecución:
Cuando hagais alguna ejecución de este programa (tener paciencia para ejecuciones largas porque no lo hice con threads y tarda un poco en dar los resultados) vereis que en la mayoría de las ocasiones no da el mejor resultado por muchas generaciones que le pongáis y por mucho que varieis las probabilidades de emparejamiento y mutación. Como se comento en la entrada "¿Que es la Computación Evolutiva?" los algoritmos genéticos dan unos resultados "decentes" pero no dan (en la mayoría de los casos) el mejor resultado al problema, aunque pueda dar un resultado bastante bueno o no. En esta entrada se ha explicado paso por paso como funciona un algoritmo genético pero CUIDADO para resolver los problemas que tengáis que resolver plantearos otras opciones antes de utilizar un algoritmo genético porque seguramente no sea el algoritmo genético la mejor opción salvo que no tengáis ni idea de abordar el problema.
BIBLIOGRAFÍA
Este problema fue propuesto en la asignatura de “Inteligencia Artificial” impartida en el segundo curso de la carrera de Ingeniería Informática en la Escuela Universitaria de Informática de la UPM.
Hola rochard
primero que todo felicitarte lo publicaste en el 2014 y aun es funcional, es necesario modificarle algunas cosas ya que es algo educativo, pero explicas muy bien el concepto de genético «algoritmo». felicidades y muchas gracias
Hola me puedes ayudar con un ejemplo de programación evolutiva, algoritmos genéticos y programación genética?
gracias.
Buenas tardes, tengo una consulta, mi individuo tiene 5 genes, entonces tendrá 4 puntos de corte.
Punto de corte 1 = [0.0 a 0.25), punto de corte 2 = [0.25 a 0.50), punto de corte 3 = [0.50 a 0.75) y punto de corte 4 = [0.75 a 1]
En caso de que se emparejen cojo el siguiente numero aleatorio y veo en que rango de algun punto de corte cae, y los genes que se intercambian son los siguientes a ese punto de corte, es decir.
Si cae en el punto de corte 4, cambio el gen 5. Si cae en el punto de corte 3, cambio el gen 4 y el 5. Si cae en el punto de corte 2, cambio los genes 3, 4 y 5. Y si cae en el punto de corte 1 cambio los genes 2, 3 , 4 y 5.
Mi pregunta es, en caso de que no me haya confundido hasta ahora, ¿nunca cambiamos el gen 1?.
Buen Día:
Excelente AG.
En este momento estoy abordando los algoritmos culturales propuestos por Reynolds, pero estoy confundido con el inicio del espacio de creencia; es posible una ayuda frente a esta inquietud.
Mil Gracias.
Muchas gracias por la explicación C:
Tu articulo es muy interesante. ¿ Como podria usar esta tecnica para saber que enfermedad E tiene un paciente sabiendo que sufre unos sintomas ABCD ? Es decir de una tabla de sintomas que pueden tener cientos de enfermedades de esa tabla cual seria la enfermedad que mas se asemeja a esos sintomas
Hola, para el problema de enfermedades que planteas sería mejor una red bayesiana
TENGO VARIAS PREGUNTAS:
-TU EJEMPLO DICE QUE A LA HORA DE SELECCIONAR INDIVIDUOS PARA EL EMPAREJAMIENTO, GENERE NUMEROS ALEATORIOS Y SI ALGUN NUMERO ESTA EN EL INTERVALO DE ALGUN INDIVIDUO, ESTE SERA APTO PARA EL EMPAREJAMIENTO, :
1. QUE PASA SI, POR EJEMPLO, DE 5 INDIVIDUOS SOLO 3 SON OPTIMOS PARA EL EMPAREJAMIENTO,¿COMO SERIAN LAS PAREJAS?
2. EN EL CASO QUE ALGUNOS NO SEAN APTOS PARA EL EMPAREJAMIENTO, ¿ES POSIBLE UNA REDUCCION DE POBLACION?
Gracias 😀
Gracias amigo, tu ejemplo me ha servido bastante para poder entender los algoritmos geneticos, Saludos desde México 😀
Probe esa funcion con los algoritmos geneticos que proporciona el MATLAB y se llego al resultado exacto
saludos
huaraz city
podrias facilitar el codigo fuente para ver el desarrollo ,por que es muy interesante.
HOLA BUENO YO QUERIA UNA AYUDA CON AG NECESITO CON FUNCIONES O PUERTAS LOGICAS SERA QUE ME PUEDEN AYUDAR GRACIAS
Hola. Muy interezante el tema. Quisiera profundizar respecto a los algoritmos geneticos algun libro que podrias recomendar muchas gracias y saludos.
Hola con respecto a el problema lo que utilizas en tu código puede ser adaptado a otro problema de algoritmos genéticos ??? obviamente modificando algunas cosas ??? y excelente trabajo
Hola Jepcc.
Lo mas importante es que sepas representar bien a los individuos y definir bien la función de Fitness. Una vez que tengas eso bien definido es muy sencillo implementar el algoritmo evolutivo (que puedes ver el pseudocódigo en esta entrada: http://jarroba.com/computacion-evolutiva-ejemplo-con-un-algoritmo-genetico/). Sobre reutilizar o no el código dependerá de la estructura de datos que represente a los individuos, pero lo fundamental es que tengas claro el pseudocódigo de un algoritmo genético que eso si que sera común para todos los casos sea cual sea la representación de los individuos.
SL2
Buenas, estamos comenzando a investigar sobre los algoritmos genéticos. El problema a resolver es en un tablero de 4×4, tenemos 2 individuos que aparecen al principio 2 o 4 y el cruce tiene que llegar al 2048. Podemos usar algoritmos genéticos para resolverlo?
Gracias Sl2.
Hola Gabriela.
Con los datos que me das no sabría decirte si los algoritmos genéticos son la mejor solución para resolver tu problema.
Mírate el algoritmo del backtracking o el de «divide y vencerás» que son algoritmos bastante buenos para la resolución de problemas con tableros, pero ya te digo que con la información que me das no sabría decirte como abordar el problema, aunque si sabes modelas bien el problema los algoritmos genéticos deberían de funcionarte.
Saludos
Hola, quiero saber una cosa:
«..números aleatorios y si están dentro de los rangos de selección, ese individuo sera apto para el emparejamiento»
que pasaría si esos dos números aleatorios no están dentro del rango? claro esta que no son aptos para el emparejamiento, pero qué tendría que hacerse en ese caso.
Gracias
Hola Alex.
Lo primero decirte que este ejemplo es un ejemplo «didáctico» por lo tanto lo hice con el fin de ver «el concepto» y no las excepciones que pueden surgir. Dicho esto te cuento algunas cosas:
1.- Para abordar un problema de este tipo tienes que coger un población mayor. Yo en este ejemplo cogí dos individuos para no complicar el ejemplo, pero lo suyo seria haber cogido una población mayor.
2.- Tienes que definir bien cuales van a ser tus puntos de parada; si lo vas ha hacer por número de generaciones o por la función de fitness.
3.- Si se llega al problema que planteas, quiere decir que no vas a tener una nueva generación y por tanto el resultado de tu problema será aquel individuo que mejor función de fitness tengas en ese momento, es decir en el ejemplo seria el individuo con «x=4», pero claro ese individuo es «bastante malo».
4.- Como ya he dicho esto es un ejemplo didáctico, por tanto coge un número más alto de individuos y así no deberías tener el problema que planteas.
SL2
hola, muy interesante.
Yo estoy trabajando con algoritmos memeticos recién estoy empezando para una materia, me gustaría si me puedes recomendar algo por ahí para entenderlos algo así como lo que tu hiciste.
Muchas gracias
Hola Edwin.
Sobre Algoritmos Meméticos (y como diria Bart Simpson) se que existen y poco más. Nunca he trabajado con ellos ni me he puesto a mirarlos. En mi caso todo lo que he aprendido sobre computación evolutiva a sido a través de lo que me enseñaron en la universidad y a través de lo que he ido leyendo en Papers. La mejor forma de aprender sobre estos temas de IA es la de leer Papers. Al principio cuesta muchísimo leer papers y entenderlos pero a la larga es la mejor forma de aprender. Algo que recomendarte en concreto no podría decirte, asi que intente buscar papers que hablen sobre ese tema para aprender.
SL2
hola buenas tardes despues de varios años aqui estoy viendo su programa pero quisera ver el codigo fuente me lo puede pasar de ante mano muchas gracias y bendiciones
Estimado, antes que todo te agradezco tan interesante explicación, por otro lado, me surge una duda respecto a la cantidad y el rango en el que te das el conjunto de números aleatorios al principio. ¿Cuál es el criterio que se utilizó para esto?
Muchas gracias,
Hola Eduardo. Para el ejemplo he cogido un conjunto de números aleatorios mayor del que necesitaba como puedes ver. Para estos casos tienes dos opciones, coger un conjunto de números aleatorios muy grande (muchísimo mayor de lo que estimes que vas a necesitar) o ir generando los números aleatorios según los vas necesitando como he hecho en el proyecto que he compartido. Esta segunda opción es la mejor para no tener que crearte una estructura de datos muy grande desde el principio.
SL2
Excelente, muy agradecido por vuestra respuesta…
Saludos,
Eduardo
que tal saludos, en que lenguaje de programación y versión esta hecho este prejecto
Saludos, quisiera saber cual es el criterio para definir en 70% y 30% la probabilidad de emparejamiento y mutación.
Gracias
Hola Mauricio.
La probabilidad de emparejamiento y mutación no son mas que dos parámetros que debes ajustar en tu algoritmo genético para alcanzar la mejor solución posible. En este ejemplo puse eso valores porque son mas o menos unos valores «lógicos» en la naturaleza, pero vamos que eso lo debes ir ajustando tu en función de las necesidades de tu problema, de hecho en el programa esos valores los puedes cambiar e ir haciendo pruebas.
SL2
bien, gracias por la aclaración.
Definitivamente excelente, pero es posible tener acceso al código fuente para ver el desarrollo?
Hola Manolo. Ya tienes el proyecto entero en GitHub, pulsando en el enlace de arriba del todo.
Nose si te valdrá de mucho el código ya que esta hecho sin utilizar ninguna librería especifica de IA y a parte al hacer la GUI se «ensucia» un poco el código.
SL2
que tal saludos, en que lenguaje de programacion y version esta hecho este proyecto esta muy bueno
Hola Luis. Este proyecto esta hecho en java y utilizando las interfaces de JavaFX
SL2
Excelente!! Saludos 🙂