Algoritmos Metaheurísticos
Project description
Algoritmos Metaheurísticos para el problema TSP
La presente librería implementa los siguientes algoritmos metaheurísticos:
- Algoritmo genéticos
- Colonia de hormigas
- Algoritmo tabú
- Selección clonal
- 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:
- Los algoritmos metaheurísticos utilizan un vector con N elementos, para guardar la ruta a seguir en las N ciudades.
- Los valores del vector nunca se repiten, el primer valor siempre es 1 (se asume que el vendedor parte de la ciudad 1)
- Los datos de entrada deben ser del tipo TSP (coordenadas de ciudades en 2D)
- Los archivos TSP pueden ser descargados de TSPLIB http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/
- 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
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
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
Algorithm | Hash digest | |
---|---|---|
SHA256 | 81c6b3fb73a9c4deacec23bf6deeccdd5a18f7beff5bbfd1ee8b4ff60c5bafc9 |
|
MD5 | 12573e47106827eeaa3a1541d5841317 |
|
BLAKE2b-256 | da9afcea42e54065539fcf879c4c460e38cd1b987a31d317a8d0c7dfba761c84 |
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
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c4b3a34db15f19d44d688d486da2821422760ac53a723ce98bed20d58e3f681 |
|
MD5 | ae2ebc470d9a72a65aa3e3b36af9ce82 |
|
BLAKE2b-256 | be9a5d0f08a41a685310d40a8c1734e2d4c9f1d5906e3a06f815194be8674c50 |