Holaaaaaaaaaaaaaa

Arias Portales Rosa Elena

X Ciclo Académico

TAREA Nº 10 En esta oportunidad, deberá de implementar una solución al problema del viajero utilizando algoritmos genéticos. Para resolver elProblema del Agente Viajero se codificó el cromosoma de la siguiente manera:
Ciudad1 Ciudad2 Ciudad3 ........... Ciudadn

Cromosoma del Problema del Agente Viajero

Representa el orden de las ciudadesque debe de seguir el agente para su recorrido. El tamaño de este arreglo es el número de ciudades del problema. No puede existir una ciudad que se repita en el recorrido. La función de evaluaciónde cada cromosoma esta dado por la longitud del mismo recorrido, es decir que longitud recorre el agente si sigue el orden de las ciudades que están en el cromosoma. El recorrido completo es de ir dela primera hasta la n-sima ciudad y regresar a la ciudad de partida. El tipo de Cruzamiento que se uso fue “Cruzamiento de un punto” Padre 1 Padre 2 Hijo 1* Hijo 2*
1 7 1 2 4 2 4 7 2 1 2 1 6 4 4 6 75 5 7 3 6 6 3 5 3 3 5

Después del cruzamiento, los hijos tienen un problema, existe una ciudad que se repite: La ciudad 4 en el hijo 1 y la ciudad 7 en el hijo 2 Para resolver este problema, sehizo lo siguiente: la ciudad que se repite en la parte heredada del padre 1, es reemplazada por alguna ciudad (no se encuentra en la parte de la ciudad a reemplazar) de la parte que no es heredada delpadre 2. Padre 2 Hijo 1* Hijo 2*
7 1 1 2 4 7 1 2 2 4 4 4 5 5 5 6 6 6 3 3 3

Para la mutación, se escoge aleatoriamente de la población (después del cruce) tantos individuos como la probabilidadde mutación lo indique. Se uso el tipo de mutación “Order Chaining”, el cual consiste en seleccionar aleatoriamente dos números (ciudades) y cambiarlos:

Arias Portales Rosa Elena
1 7 2 4 5 6 3X Ciclo Académico

1

7

6

4

5

2

3

Algoritmo Genético

Resultados: Problema: 7 Ciudades

Arias Portales Rosa Elena

X Ciclo Académico

Para caso se realizo 20 pruebas...