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