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

Si te gusto comparte ...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

21 pensamientos en “Algoritmo genético hecho en Java

  1. George Albert
    Internet Explorer 9.0 Windows 7

    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.

    Responder
    1. Alevsk Autor
      Google Chrome 17.0.963.56 Mac OS

      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.

      Responder
      1. George Albert
        Internet Explorer 9.0 Windows 7

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

        Responder
    1. Alevsk
      Google Chrome 17.0.963.65 Mac OS

      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

      Responder
  2. ELEMENTOR
    Google Chrome 17.0.963.79 Windows Vista

    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

    Responder
  3. ELEMENTOR
    Google Chrome 17.0.963.79 Windows Vista

    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

    Responder
    1. Alevsk Autor
      Google Chrome 17.0.963.79 Windows 7

      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

      Responder
  4. Fernando Rodriguez
    Google Chrome 18.0.1025.162 Windows 7

    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.

    Responder
  5. rocco
    Firefox 16.0 Windows 7

    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?

    Responder
  6. Diego Roberts
    Google Chrome 35.0.1916.114 Windows 7

    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.

    Responder
  7. Alevsk Autor
    Google Chrome 39.0.2171.65 Mac OS

    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

    Responder

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *