1. Algoritmo Genético para: TSP-Clásico¶

Un vendedor parte de la ciudad de residencia (0: ciudad inicio), luego recorre todas las ciudades una sola vez, y retorna a la ciudad de residencia.

Importación de librería¶

In [ ]:
import ag_lbpt.util as util

Configuración de algoritmo genético¶

In [ ]:
#--------------------------------------------------------------------------------------------------------------------------------------
# INPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# ArchicoTSPcsv = 'tsp_10c.csv' : Archivo de datos (coordenadas 2D (x,y)) en formato csv
# Iteraciones = 10              : cantidad de veces que se ejecuta el AG
# Generaciones = 100            : Cantidade de generaciones que itera el AG
# Poblacion = 250               : Cantidad de pobladores del AG
# ProbMutacion = 0.1            : Probabilidad de mutación
# TipoMutacion = 'Permuta'      : El individuo mutante se consigue por permutación de atributos
# TipoCruce = 'Complemento'     : la operación cruce es eligiendo M atributos de primer ancestro y el resto por complemento
# GenUnico = True               : Los genes tiene valores únicos o distintos
# IniciFijo = True              : El primer gen siempre es 1. La ciudad de partida siempre es 1
# IniciFinFijo = False          : Es falso ya que el parametro anterior es True
# N = 10                        : Cantidad de ciudades
# PobElite = 2                  : Indidivuos de la élite
#--------------------------------------------------------------------------------------------------------------------------------------
# OUTPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# AG        : Objeto algoritmo genético
# Solución  : Cromosoma solución al problema
# Costo     : Costo que implica dicha solución 
#--------------------------------------------------------------------------------------------------------------------------------------

AG, Solucion, Costo = util.agTSP('tsp_10c.csv', 10, 100, 250, 0.1, 'Permuta',
                                   'Complemento', True, True, False, 10, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

Solucion:  [0, 9, 4, 6, 8, 2, 1, 5, 7, 3]
Costo:  127.95003663555944

Gráfico de evolución del costo¶

In [ ]:
AG.GraficaCosto()

Gráfico de la ruta TSP encontrada¶

In [ ]:
AG.GraficaRutaExternaTSP(util.TSP, Solucion)

2. Algoritmo Genético para: TSP-Inicio-Fin-Definido¶

Un vendedor parte de la ciudad de residencia (0: ciudad inicio), luego recorre n-2 ciudades una sola vez, finaliza su recorrido siempre en la n-ésima ciudad, y retorna a la ciudad de residencia.

In [ ]:
#--------------------------------------------------------------------------------------------------------------------------------------
# INPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# ArchicoTSPcsv = 'tsp_10c.csv' : Archivo de datos (coordenadas 2D (x,y)) en formato csv
# Iteraciones = 10              : cantidad de veces que se ejecuta el AG
# Generaciones = 100            : Cantidade de generaciones que itera el AG
# Poblacion = 250               : Cantidad de pobladores del AG
# ProbMutacion = 0.1            : Probabilidad de mutación
# TipoMutacion = 'Permuta'      : El individuo mutante se consigue por permutación de atributos
# TipoCruce = 'Complemento'     : la operación cruce es eligiendo M atributos de primer ancestro y el resto por complemento
# GenUnico = True               : Los genes tiene valores únicos o distintos
# IniciFijo = False             : False, porque el parametro siguente es True
# IniciFinFijo = True           : El primer gen = 1, último gen = N
# N = 10                        : Cantidad de ciudades
# PobElite = 2                  : Indidivuos de la élite
#--------------------------------------------------------------------------------------------------------------------------------------
# OUTPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# AG        : Objeto de algoritmo genético
# Solución  : Cromosoma solución al problema
# Costo     : Costo que implica dicha solución 
#--------------------------------------------------------------------------------------------------------------------------------------

AG, Solucion, Costo = util.agTSP('tsp_10c.csv', 10, 100, 250, 0.1, 'Permuta',
                                   'Complemento', True, False, True, 10, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

Solucion:  [0, 7, 5, 1, 2, 8, 6, 4, 3, 9]
Costo:  132.93118671921917
In [ ]:
AG.GraficaCosto()
In [ ]:
AG.GraficaRutaExternaTSP(util.TSP, Solucion)

3. Algoritmo Genético para: TSP-Inicio-Fin-Indefinido¶

Un vendedor parte de una ciudad (indefinida), luego recorre todas las ciudades una sola vez, y retorna a la ciudad de residencia.

In [ ]:
#--------------------------------------------------------------------------------------------------------------------------------------
# INPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# ArchicoTSPcsv = 'tsp_10c.csv' : Archivo de datos (coordenadas 2D (x,y)) en formato csv
# Iteraciones = 10              : cantidad de veces que se ejecuta el AG
# Generaciones = 100            : Cantidade de generaciones que itera el AG
# Poblacion = 250               : Cantidad de pobladores del AG
# ProbMutacion = 0.1            : Probabilidad de mutación
# TipoMutacion = 'Permuta'      : El individuo mutante se consigue por permutación de atributos
# TipoCruce = 'Complemento'     : la operación cruce es eligiendo M atributos de primer ancestro y el resto por complemento
# GenUnico = True               : Los genes tiene valores únicos o distintos
# IniciFijo = False             : El gen inicio puede ser cualquiera
# IniciFinFijo = False          : El primer y último gen puede ser cualquiera
# N = 10                        : Cantidad de ciudades
# PobElite = 2                  : Indidivuos de la élite
#--------------------------------------------------------------------------------------------------------------------------------------
# OUTPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# AG        : Objeto de algoritmo genético
# Solución  : Cromosoma solución al problema
# Costo     : Costo que implica dicha solución 
#--------------------------------------------------------------------------------------------------------------------------------------

AG, Solucion, Costo = util.agTSP('tsp_10c.csv', 10, 100, 250, 0.1, 'Permuta',
                                   'Complemento', True, False, False, 10, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

Solucion:  [0, 3, 7, 5, 1, 2, 8, 6, 4, 9]
Costo:  127.95003663555947
In [ ]:
AG.GraficaCosto()
In [ ]:
AG.GraficaRutaExternaTSP(util.TSP, Solucion)

Luis Beltran Palma Ttito, luis.palma@unsaac.edu.pe (autor)

Dennis Iván Candia oviedo, dennis.candia@unsaac.edu.pe (coautor)

Carlos Ramón Quispe Onofre, carlos.quispe@unsaac.edu.pe(coautor)

Willian Zamalloa Paro, willian.zamalloa@unsaac.edu.pe(coautor)

José Mauro Pillco Quispe, jose.pillco@unsaac.edu.pe(coautor)