Ha pasado bastante tiempo desde que no publico algún código mío, esta vez quiero compartir con ustedes un algoritmo genético hecho en Java que tuve que hacer para mi clase de Sistemas Inteligentes 😀 en el modulo de computación evolutiva, para los que no sepan que es un algoritmo genético, por aca tienen mas información.
El problema resuelto fue el problema del viajante o TSP, nuestro problema consiste básicamente en que tenemos n ciudades, que están conectadas entre si, todas con todas (n*n caminos) y existen varios objetivos, en mi caso tengo que minimizar la distancia recorrida.
Los pasos de todo algoritmo genético deben de ser
- Generar población
- Seleccionar a los individuos mas aptos (Torneo, selección por ruleta, etc)
- Cruzarlos (recombinacion)
- Mutación
Esto se realiza durante n generaciones y el objetivo es que cada generación los individuos sean mejores que los anteriores (aunque no siempre es así xD). Ahora les muestro un ejemplo de como es que funciona, supongamos que generamos nuestra población inicial la cual consiste en un camino que tiene que tomar el viajante, tiene como restricción que no puede repetir ciudades por las que ha pasado antes y el recorrido termina en la ciudad de la que partimos, ejemplo:
Batemans-Bay-Outreach Ashfield Bateau-Bay Bankstown Armidale Blackett Bega | Bathurst Bidwill | Bradbury Airds Albury Batemans-Bay-Outreach 120.68747174103011
Podemos ubicar las ciudades en un plano cartesiano y verlas como si fueran puntos, desde esa perspectiva es posible sacar la distancia total del recorrido aplicando distancia euclidiana entre los puntos.
Después de eso podemos realizar una selección, entre los métodos mas comunes están el de selección por ruleta o el de selección por torneo, en este ultimo tan solo tenemos que ordenar la lista de caminos de menor a mayor y en mi caso elegir n * 3 individuos que representaran a los padres de la siguiente generación, ahora, en este punto es importante saber cuales tenemos que elegir ya que en probabilidad es poco posible que si cruzamos los 2 individuos mejor adaptados de la generación salga uno aun mas adaptado, por el contrario podría “des evolucionar” el hijo, es por eso que yo recomiendo, si vemos la población como si estuviera ordenada en una pila, tomar de los de arriba (los mejores adaptados) y algunos de en medio.
En este punto ya tenemos a los que serán los padres, ahora debemos de cruzarlos, existen varias técnicas de cruza como recombinación en 1 punto, recombinación en 2 puntos, corte y empalme, Recombinación uniforme y uniforme media y Recombinación de cromosomas ordenados, mas información aqui.
En mi caso yo utilice recombinación en 2 puntos y después aplique un algoritmo de mi creación para corregir el camino en caso de que hubiera ciudades repetidas en el.
minCutPoint: 6 maxCutPoint: 9 Padres: Batemans-Bay-Outreach Ashfield Bateau-Bay Bankstown Armidale Blackett Bega | Bathurst Bidwill | Bradbury Airds Albury Batemans-Bay-Outreach 120.68747174103011 Airds Bankstown Albury Armidale Ashfield Batemans-Bay-Outreach Bathurst | Bega Bateau-Bay | Bidwill Bradbury Blackett Airds 122.0081148734119 Hijos sin verificar: Batemans-Bay-Outreach Ashfield Bateau-Bay Bankstown Armidale Blackett Bega | Bega Bateau-Bay | Bradbury Airds Albury Batemans-Bay-Outreach 0.0 Airds Bankstown Albury Armidale Ashfield Batemans-Bay-Outreach Bathurst | Bathurst Bidwill | Bidwill Bradbury Blackett Airds 0.0 F1Extract = | Bathurst Bidwill | F2Extract = | Bega Bateau-Bay | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Cruza hijo 1: Batemans-Bay-Outreach Ashfield Bateau-Bay Bankstown Armidale Blackett Bega | Bega Bateau-Bay | Bradbury Airds Albury Batemans-Bay-Outreach 0.0 Batemans-Bay-Outreach Ashfield Bateau-Bay Bankstown Armidale Blackett Bathurst | Bega Bateau-Bay | Bradbury Airds Albury Batemans-Bay-Outreach 0.0 Batemans-Bay-Outreach Ashfield Bidwill Bankstown Armidale Blackett Bathurst | Bega Bateau-Bay | Bradbury Airds Albury Batemans-Bay-Outreach 0.0 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Cruza hijo 2: Airds Bankstown Albury Armidale Ashfield Batemans-Bay-Outreach Bathurst | Bathurst Bidwill | Bidwill Bradbury Blackett Airds 0.0 Airds Bankstown Albury Armidale Ashfield Batemans-Bay-Outreach Bega | Bathurst Bidwill | Bidwill Bradbury Blackett Airds 0.0 Airds Bankstown Albury Armidale Ashfield Batemans-Bay-Outreach Bega | Bathurst Bidwill | Bateau-Bay Bradbury Blackett Airds 0.0
Aqui lo que hago es generar aleatoriamente 2 puntos de corte (minCutPoint y maxCutPoint), las ciudades entre esos 2 puntos serán los cromosomas que se insertaran en los hijos, después de eso checamos cada uno de los alelos para verificar que no esta repetido, en caso de que asi sea, remplazo la ciudad repetida por la primera ciudad no repetida del conjunto de cromosomas original del padre, lo que me asegura que siempre tendre caminos validos 🙂
Y por ultimo pero no menos importante la mutación, esta parte es bastante sencilla, genero 2 puntos aleatorios e intercambio los cromosomas de lugar, si el camino resultante es mas optimo que el original entonces el individuo evolucionara, de lo contrario se quedara igual.
Este procedimiento se realiza n generaciones, y al final esperamos tener el camino mas optimo que el viajero podría tomar.
Les dejo mi codigo fuente, espero le sirva a alguien
salu2
PD cualquier duda postearla en comentarios, gracias
Hola Buena informacion, tengo una duda espero me puedas ayudar como realizo una asignacion de tipo a una variable en tiempo de ejecucion ejemplo
una variable nombre;
Como le asigno un tipo que pueda ser String, int, float, double, char, etc.
Hola en lenguajes de tipado sencillo como PHP, javascript, etc, solo tienes que asignarle el valor y listo (dato tipo int o float o el que quieras) en otros lenguajes como C o Java, creo que no es posible hacer eso, pero puedes utilizar reflection que te sirve para crear objetos dinamicamente en base al nombre de la clase man.
Algun Ejemplo? Bueno espero puedas realizar una entrada o algo para mostrar lo que dices, digo si no es mucha molestia jejeje Gracias.
Yo tengo una duda, ¿te equivocaste do código? no quieres revisarlo antes de postearlo 😉
Hola Ernesto que bueno tenerte por aqui xD, segun yo esta correcto, pero si puedes indicarme en que parte esta mal para corregirlo xD.
salu2
oygan una duda como agrego o de donde sales esas otras librerias, esque me eh ayado otros codigos asi pero al pasarlos en netbeans dice que esas librerias no estan
A YA YA LE AYE JAJAJA PERO AHORA MI DUDA ES QUE AL EJECUTARLO SOLO TE PIDE QUE METAS NUMEROS EN EL SIGUIENTE FORMATO ((1,2 (1,3)) Y SOLO APARECE CADENA VALIDA Y DE AHI QUE? QUE DEVE DE MOSTRAR O CUANTAS DEBES DE INTRODUCIR O CUAL ES EL OBJETIVO DE TANTO CODIGO ESPERO PUEDAS RESOLVER MI DUDA O DECIRME COMO SE DEVE DE UTILIZAR GRACIAS
Hola, gracias por visitar mi blog, tal como comentas, introduces las coordenadas de las ciudades por medio de entrada estándar (por consola) y después el algoritmo tratara de encontrar el camino mas optimo cumpliendo la restricción de visitar todas las ciudades solo 1 vez y regresar a la ciudad de origen :), esa parte también te la indica por medio de la consola (imprime cual es el individuo mas optimo de cada generación).
salu2
Que pena pero a mi no me ejecuta esa parte del código queria preguntarte el porque gracias
Woooww!!! si que eres todo un genio, la verdad a mi me gustaria ser asi como tu lastima que no puedo :s jajajaja
Saludos y pues la verdad soy un novato en esto de programacion.
Yo comienzo poquito a programar en netbeans y pues la verdad no entendi mucho. Pero en fin espero poderle entender algun dia….
Saludos que esten bien.
Hola amigo, gracias por visitar mi blog :), pero por que dices que no puedes :O? explícame xD.
salu2
supongamos que tenemos un pais y estados, como hariamos para que los estados diferenciar estadosde los que colinden unos con otros? es decir si le pidieramos que asiganara diferentes colores y que ningun estado tuviera el color de uno con el que hace frontera?
Oye!! no puedo correr tu programa con lo del package S:
que onda faltan archivos???
Hola me intereza mucho el proyecto de la solucion de viajante
pero no puedo ver las clases.
me las podias enviar al este correo;
[email protected]
[email protected]
Hola me intereza mucho el proyecto de la solucion de viajante
pero no puedo ver las clases.
me las podias enviar al este correo;
[email protected]
[email protected]
Gracias
HOLA, me interesa mucho lo de inteligencia artificial; y he elaborado varios Software que implementen algoritmos.. me gustaría conocer el código para ver como desenlazas el contexto. Mi correo es [email protected] . Me interesaría conocerlo y espero tu respuesta un saludo.
Hola me interesa aprender AI a partir de tu codigo me podrias enviar a mi mail?
Slds
Me interesa el programa completo, me seria de mucha ayuda. Si puedes enviarlo a mi email te estaria agradecido. Este es mi e-mail: [email protected]
Hola saludos,
Parece que los enlaces a las clases no existen.
Podrias enviarlas a mi correo
Muchas gracias por tu aporte y felicidades
[email protected]
Holap me interesa mucho el proyecto del viajante pero no puedo ver las clases me puedes enviar al correo [email protected] o volver a subirlos.
Gracias por compartir 🙂
Hola a todos, he actualizado la publicación y colocado unos nuevos enlaces de donde pueden descargar el código del algoritmo genético en Java, los archivos están en mi repositorio de Github por lo que no debería de haber problema en el futuro.
salu2
No puedo descargarlo, me lo podrias enviar a mi correo xfa [email protected] completo se seria de mucha utilidad, gracias por compartir
Saludos, interesante, soy nuevo en esto pero quisiera q se pueda establecer un origen y un fin, crees poderme explicar como lo solucionaría?