Tsp. algoritmo genetico

Solo disponible en BuenasTareas
  • Páginas : 2 (284 palabras )
  • Descarga(s) : 0
  • Publicado : 7 de septiembre de 2012
Leer documento completo
Vista previa del texto
Agente Viajero (TSP)
Una persona debe visitar n ciudades, teniendo como punto de partida y de llegada la misma ciudad, visitando solamente una vez cada ciudady haciendo el recorrido mínimo de distancia (KMS.)
A continuación se encuentra una tabla con las distancias entre las 7 ciudades elegidas:
  | Acarigua 1 |Barcelona 2 | Barinas 3 | Barquisimeto 4 | Caracas 5 | Ciudad Bolívar 6 | Pto. Ordaz 7 |
Acarigua 1 | 0 | 599 | 184 | 80 | 341 | 724 | 831 |
Barcelona 2 |599 | 0 | 783 | 679 | 310 | 296 | 403 |
Barinas 3 | 184 | 783 | 0 | 264 | 525 | 908 | 1012 |
Barquisimeto 4 | 80 | 679 | 264 | 0 | 363 | 804 | 911 |
Caracas5 | 341 | 310 | 525 | 363 | 0 | 591 | 698 |
Ciudad Bolívar 6 | 724 | 296 | 908 | 804 | 591 | 0 | 107 |
Pto. Ordaz 7 | 831 | 403 | 1012 | 911 | 698 | 107 | 0|

Punto de Partida y Llegada: Acarigua

Ruta Optima N°1 de Ciudades: 1 4 3 5 2 6 7
Recorrido KMS.: 80+264+525+310+296+107+831: 2413KMS

Ruta Óptima N°2de Ciudades: 1 3 4 5 2 6 7
Recorrido KMS.:184+264+363+310+296+107+831: 2355KM

CODIFICACION DE CROMOSOMA:
1 | 2 | 3 | 4 | 5 | 6 | 7 |

CRUZAMIENTO DE UNPUNTO
1 | 4 | 3 | 5 | 2 | 6 | 7 |
Padre 1
1 | 3 | 4 | 5 | 2 | 6 | 7 |
Padre 2


1 | 4 | 3 | 5 | 2 | 6 | 7 |
Hijo 1
1 | 3 | 4 | 5 | 2 | 6 | 7 |Hijo 2

Hijo 1: 80+264+525+310+296+107+831: 2413KMS.
Hijo 2: 184+264+363+310+296+107+831: 2355KMS.

Para evitar la convergencia prematura realizamos unamutación. Elegimos de forma de aleatoria la selección de cualquier de las dos ciudades e intercambiamos sus posiciones, dando asa lugar a una nueva ruta.
tracking img