Algoritmo genético hecho en Java


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

24 thoughts on “Algoritmo genético hecho en Java

  1. George Albert

    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.

    Reply
    1. Alevsk Post author

      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.

      Reply
      1. George Albert

        Algun Ejemplo? Bueno espero puedas realizar una entrada o algo para mostrar lo que dices, digo si no es mucha molestia jejeje Gracias.

        Reply
  2. Ernesto

    Yo tengo una duda, ¿te equivocaste do código? no quieres revisarlo antes de postearlo 😉

    Reply
    1. Alevsk

      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

      Reply
  3. ELEMENTOR

    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

    Reply
  4. ELEMENTOR

    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

    Reply
    1. Alevsk Post author

      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

      Reply
  5. Fernando Rodriguez

    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.

    Reply
    1. Alevsk Post author

      Hola amigo, gracias por visitar mi blog :), pero por que dices que no puedes :O? explícame xD.

      salu2

      Reply
  6. rocco

    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?

    Reply
  7. Aldo Alberto

    Oye!! no puedo correr tu programa con lo del package S:
    que onda faltan archivos???

    Reply
  8. Diego Roberts

    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.

    Reply
  9. Alevsk Post author

    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

    Reply
  10. Jonathan

    Saludos, interesante, soy nuevo en esto pero quisiera q se pueda establecer un origen y un fin, crees poderme explicar como lo solucionaría?

    Reply

Leave a Reply

Your email address will not be published.