Skip to main content

Algoritmos Metaheurísticos

Project description

Algoritmos Metaheurísticos para el problema TSP


La presente librería implementa los siguientes algoritmos metaheurísticos:

  1. Algoritmo genéticos
  2. Colonia de hormigas
  3. Algoritmo tabú
  4. Selección clonal
  5. Recocido simulado

Propósito del la librería

La presente liberería, fue creada con motivo educativos, y únicamente resuelve el problema de TSP, tomando en cuenta las siguientes consideraciones:

  1. Los algoritmos metaheurísticos utilizan un vector con N elementos, para guardar la ruta a seguir en las N ciudades.
  2. Los valores del vector nunca se repiten, el primer valor siempre es 1 (se asume que el vendedor parte de la ciudad 1)
  3. Los datos de entrada deben ser del tipo TSP (coordenadas de ciudades en 2D)
  4. Los archivos TSP pueden ser descargados de TSPLIB http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
  5. Tambien es posible utilizar de entrada Matrices de Distancias en archivo Excel, sin cabecera y sin indice (en caso de usar matriz de distancias, no es posible graficar la ruta)

luis.palma@unsaac.edu.pe, Luis Beltran Palma Ttito, Universidad Nacional de San Antonio Abad del Cusco


Problema TSP "Travelling Salesman Problem" (Problema del Vendedor Viajante)

Un viajero de comercio parte de una ciudad y las distancias a otras ciudades son conocidas, ¿cuál es la ruta óptima que debe seguir para visitar todas las ciudades y volver a la ciudad de partida?


Pasos previo al uso de la libería

Paso 1: Para un adecuado funcionamiento, debe actualizar el gestionador de paquetes "pip"

!pip install --upgrade pip

Paso 2: Instalación del la librería de algoritmos metaheuristicos

!pip install -i https://test.pypi.org/simple/ meta-lbpt==1.0.0

Paso 3: Importación de librerías

from meta_lbpt.ag import AlgoritmoGenetico
from meta_lbpt.ch import ColoniaHormiga
from meta_lbpt.at import AlgoritmoTabu
from meta_lbpt.sc import SeleccionClonal
from meta_lbpt.rs import RecocidoSimulado

1. Algoritmo genético

Paso 1.1. Ejecutar el algoritmo genético con TSP

# Parametros: Generaciones, Población, ProbMutación, PoblacionElite
# burma14.tsp: Archivo que contiene las N ciudades en formato TSP (coordenadas 2D)
AG = AlgoritmoGenetico(100, 500, 0.05, 2)
Solucion, Costo, Aptitud = AG.EjecutarTSP('burma14.tsp')
print('Ruta encontrada por el algoritmo genético: ', Solucion)
print('Costo: ', Costo)
print('Aptitud: ', Aptitud)
Ruta encontrada por el algoritmo genético:  [1, 2, 10, 9, 11, 8, 13, 7, 12, 6, 5, 4, 3, 14]
Costo:  32.44685100783281
Aptitud:  0.03081963176514712

Paso 1.2. Graficar la ruta solución

AG.GraficaRuta()

Paso 1.3 Gráfica la evolución de costo

AG.GraficaCosto()

Paso 1.4. Ejecutar el algoritmo genético con Matriz de Distancias

# Parametros: Generaciones, Población, ProbMutación, PoblacionElite
# burma14.tsp: Archivo que contiene las N ciudades en formato TSP (coordenadas 2D)
AG = AlgoritmoGenetico(100, 500, 0.05, 2)
Solucion, Costo, Aptitud = AG.EjecutarDistancia('distancia.xlsx', 'Hoja1')
print('Ruta encontrada por el algoritmo genético: ', Solucion)
print('Costo: ', Costo)
print('Aptitud: ', Aptitud)

2. Colonia de hormigas

Paso 2.1. Ejecutar el algoritmo colonia de hormigas con TSP

# Parametros: Iteraciones, PoblacionHormigas, Coef. evaporación, Coef. aprendizaje
# burma14.tsp: Archivo que contiene las ciudades en formato TSP
CH = ColoniaHormiga(50, 150, 0.061, 0.65)
Solucion, Costo = CH.EjecutarTSP('burma14.tsp')
print('Mejor ruta encontrada por la colonia de hormigas: ', Solucion)
print('Costo: ',Costo)
Mejor ruta encontrada por la colonia de hormigas:  [1, 2, 3, 4, 5, 6, 12, 14, 7, 13, 9, 11, 10, 8]
Costo:  32.76917155355312

Paso 2.2. Gráfica la ruta solución

CH.GraficaRuta()

Paso 2.3. Gráfica la evolución de costo

CH.GraficaCosto()

Paso 2.4. Ejecutar el algoritmo colonia de hormigas con Matriz de Distancias

# Parametros: Iteraciones, PoblacionHormigas, Coef. evaporación, Coef. aprendizaje
# burma14.tsp: Archivo que contiene las ciudades en formato TSP
CH = ColoniaHormiga(50, 150, 0.061, 0.65)
Solucion, Costo = CH.EjecutarDistancia('distancia.xlsx', 'Hoja1')
print('Mejor ruta encontrada por la colonia de hormigas: ', Solucion)
print('Costo: ',Costo)

3. Algoritmo tabú

Paso 3.1. Ejecutar el algoritmo tabú con TSP

# Parametros: Ciclos
burma14.tsp: Archivo que contiene ciudades en formato TSP
AT = AlgoritmoTabu(20)
Solucion, Energia= AT.EjecutarTSP('burma14.tsp')
print('Mejor ruta encontrada por algorítmo tabú: ', Solucion)
print('Energía: ', Energia)
Mejor ruta encontrada por algorítmo tabú:  [1, 8, 13, 7, 12, 6, 5, 4, 3, 14, 2, 10, 9, 11]
Energía:  31.226915109427544

Paso 3.2. Graficar la ruta solución

AT.GraficaRuta()

Paso 3.3. Graficar la evolución de costo

AT.GraficaEnergia()

Paso 3.4. Ejecutar el algoritmo tabú con TSP con Matriz de Distancias

# Parametros: Ciclos
burma14.tsp: Archivo que contiene ciudades en formato TSP
AT = AlgoritmoTabu(20)
Solucion, Energia= AT.EjecutarDistancia('distancia.xlsx', 'Hoja1')
print('Mejor ruta encontrada por algorítmo tabú: ', Solucion)
print('Energía: ', Energia)

4. Selección clonal

Paso 4.1. Ejecutar el algoritmo selección clonal con TSP

#Parametros: Iteraciones, Población, CantClones, CantIndividuoAltaAfinidad, ProbMutacion, IncProbMutacion
burma14.tsp: Archivo con datos de ciudades en formato TSP
SC = SeleccionClonal(30, 150, 10, 5, 0.8, 1.38)
Solucion, Afinidad = SC.EjecutarTSP('burma14.tsp')
print('Ruta solución: ', Solucion)
print('Afinidad: ', Afinidad)
Ruta solución:  [1, 9, 10, 2, 14, 3, 4, 5, 6, 12, 7, 13, 11, 8]
Afinidad:  32.81277804469343

Paso 4.2. Graficar la ruta solución

SC.GraficaRuta()

Paso 4.3. Graficar la evolución de costo

SC.GraficaAfinidad()

Paso 4.4. Ejecutar el algoritmo selección clonal con Matriz de Distancias

#Parametros: Iteraciones, Población, CantClones, CantIndividuoAltaAfinidad, ProbMutacion, IncProbMutacion
burma14.tsp: Archivo con datos de ciudades en formato TSP
SC = SeleccionClonal(30, 150, 10, 5, 0.8, 1.38)
Solucion, Afinidad = SC.EjecutarDistancia('distancia.xlsx', 'Hoja1')
print('Ruta solución: ', Solucion)
print('Afinidad: ', Afinidad)

5. Recocido simulado

Paso 5.1. Ejecutar el algoritmo recocido simulado con TSP

# Parametros: TempInicial, TempFinal, ConstanteDecremento, TiempoEnfriamiento, Cte. Bolztman
burma14.tsp: Archivo con ciudades en formato TSP
RS = RecocidoSimulado(0.99, 0.02, 0.99, 44, 0.97)
Solucion, Costo = RS.EjecutarTSP('burma14.tsp')
print('Mejor solución obtenido por enfriamiento simulado: ',Solucion)
print('Costo: ',Costo)
Mejor solución obtenido por enfriamiento simulado:  [1, 10, 9, 11, 8, 13, 7, 14, 12, 6, 5, 4, 3, 2]
Costo:  31.828317520454547

Paso 5.2. Graficar la ruta solución

RS.GraficaRuta()

Paso 5.3. Graficar la evolución de costo

RS.GraficaEnergia()

Paso 5.4. Ejecutar el algoritmo recocido simulado con Matriz de Distancias

# Parametros: TempInicial, TempFinal, ConstanteDecremento, TiempoEnfriamiento, Cte. Bolztman
burma14.tsp: Archivo con ciudades en formato TSP
RS = RecocidoSimulado(0.99, 0.02, 0.99, 44, 0.97)
Solucion, Costo = RS.EjecutarDistancia('distancia.xlsx', 'Hoja1')
print('Mejor solución obtenido por enfriamiento simulado: ',Solucion)
print('Costo: ',Costo)

En caso de existir consultas, remítase al email: luis.palma@unsaac.edu.pe, Luis Beltran Palma Ttito (autor)

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

meta_lbpt-1.0.0.tar.gz (12.2 kB view details)

Uploaded Source

Built Distribution

meta_lbpt-1.0.0-py3-none-any.whl (15.8 kB view details)

Uploaded Python 3

File details

Details for the file meta_lbpt-1.0.0.tar.gz.

File metadata

  • Download URL: meta_lbpt-1.0.0.tar.gz
  • Upload date:
  • Size: 12.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.0.0 CPython/3.12.1

File hashes

Hashes for meta_lbpt-1.0.0.tar.gz
Algorithm Hash digest
SHA256 81c6b3fb73a9c4deacec23bf6deeccdd5a18f7beff5bbfd1ee8b4ff60c5bafc9
MD5 12573e47106827eeaa3a1541d5841317
BLAKE2b-256 da9afcea42e54065539fcf879c4c460e38cd1b987a31d317a8d0c7dfba761c84

See more details on using hashes here.

File details

Details for the file meta_lbpt-1.0.0-py3-none-any.whl.

File metadata

  • Download URL: meta_lbpt-1.0.0-py3-none-any.whl
  • Upload date:
  • Size: 15.8 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.0.0 CPython/3.12.1

File hashes

Hashes for meta_lbpt-1.0.0-py3-none-any.whl
Algorithm Hash digest
SHA256 5c4b3a34db15f19d44d688d486da2821422760ac53a723ce98bed20d58e3f681
MD5 ae2ebc470d9a72a65aa3e3b36af9ce82
BLAKE2b-256 be9a5d0f08a41a685310d40a8c1734e2d4c9f1d5906e3a06f815194be8674c50

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page