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

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

Importación de librerías¶

In [ ]:
import ag_lbpt.util as util

Ejecucuín de algoritmo genético¶

In [ ]:
#--------------------------------------------------------------------------------------------------------------------------------------
# INPUT
#--------------------------------------------------------------------------------------------------------------------------------------
# ArchicoTSPcsv = 'ms_10c.csv'  : Archivo de datos (matriz de distancias) 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.agTSPmd('ms_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.95003664599997

Evolución de costo¶

In [ ]:
AG.GraficaCosto()

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

Un vendedor parte de la ciudad de residencia (1: 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 = 'md_10c.csv'  : Archivo de datos (matriz de distancias) 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.agTSPmd('ms_10c.csv', 10, 100, 250, 0.1, 'Permuta',
                                   'Complemento', True, False, True, 10, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

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

3. Algoritmo Genético para: Matriz-Distancia-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 = 'md_10c.csv'  : Archivo de datos (matriz de distancias) 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.agTSPmd('ms_10c.csv', 10, 100, 250, 0.1, 'Permuta',
                                   'Complemento', True, False, False, 10, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

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

4. Algoritmo Genético para: Matriz-Asimétrica 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 = 'ma_17c.csv'  : Archivo de datos (matriz asimétrica) en formato csv
# Iteraciones = 10              : cantidad de veces que se ejecuta el AG
# Generaciones = 300            : Cantidade de generaciones que itera el AG
# Poblacion = 100               : 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 = 17                        : 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.agTSPmd('ma_17c.csv', 10, 300, 100, 0.1, 'Permuta',
                                   'Complemento', True, False, False, 17, 2)
print('Solucion: ', Solucion)
print('Costo: ', Costo)

Solucion:  [9, 7, 11, 2, 13, 12, 15, 6, 4, 3, 14, 5, 0, 8, 16, 1, 10]
Costo:  56.0

Gráfica de la evolución de costo¶

In [ ]:
AG.GraficaCosto()

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)