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
Hashes for meta_lbpt-1.0.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c4b3a34db15f19d44d688d486da2821422760ac53a723ce98bed20d58e3f681 |
|
MD5 | ae2ebc470d9a72a65aa3e3b36af9ce82 |
|
BLAKE2b-256 | be9a5d0f08a41a685310d40a8c1734e2d4c9f1d5906e3a06f815194be8674c50 |