- Esteban García Carmona
- Emilio Porras Mejía
- Felipe Miranda Arboleda
Todo el código utilizado puede ser encontrado en los archivos code.ipynb, hormigas.py y ga.py
En el mundo de las redes neuronales y los algoritmos bioinspirados existen, al igual que en la naturaleza, muchos medios de alcanzar un objetivo (en este caso, minimizar una función; en la naturaleza: comer, reproducirse, adaptarse, sobrevivir). Por lo mismo, se trabajará utilizando diferentes tipos de optimizaciones para analizar qué ventajas y diferencias tienen entre ellas. Las que se utilizarán son: Método de descenso por gradiente con condición inicial aleatoria, algoritmos evolutivos, optimización de partículas y evolución diferencial. Además, se desea observar qué diferencias resultan de usar métodos de uso de lógica matemática, como descenso por gradiente a diferencia de los que puedan obtenerse de los bioinspirados.
Para el análisis de las optimizaciones, se usarán dos funciones: La función de la Griewank [1] y la función Rosenbrock [2].
Es una función de d variables
Por lo general se evalua en
Puede ser engañoso dado que tiene múltiples mínimos locales. Su mínimo global es
Es una función para n variables en
La función se evalúa en el dominio del hipercubo
Para generar los algoritmos genéticos, se utilizó la librería PyGAD de Python. En estos algoritmos, tenemos una serie de individuos con alguna cualidad que varía (es decir, muta). De manera paralela a la naturaleza, los que mejor se adaptan son los que sobreviven. Así, se empiezan a simular múltiples generaciones y quedan los mejores individuos (gracias al elitismo, que permite la sucesión de un individuo de una generación a otra sin alteraciones), generando generaciones con características variadas (por ejemplo, con el uso del crossover que es la combinación de padres para engendrar un nuevo individuo) y demás.
Para generar los algoritmos por optimización de partículas, se usó la librería PySwarms de Python. En este algoritmo se trabaja cobre un espacio de búsqueda utilizando una cantidad alta de partículas y se les altera su posición y velocidad dependiendo del análisis de la optimización de cada punto en que se hallen.
Para generar el método de la evolución diferencial, se usó el código de 兔子爱读书, usuario del foro de programación japonés csdn.ne. Este genera una mejora en la posición teniendo múltiples soluciones candidatas y creando nuevas con base en estas. En caso de que una mejor solución se genere, se guarda. En caso contrario, se descarta.
Es un algoritmo iterativo que toma pasos opuestos de la dirección del gradiente. Así, se logra tomar la vía del descenso más agudo, lo que puede llevar a alcanzar un mínimo, es decir, un punto en donde, sin importar dónde nos movamos, será el menor de los valores. Es de tener en cuenta que no necesariamente lleva al mínimo global (es decir, de todo el dominio), sino, posiblemente, a un mínimo global (un sector perteneciente al dominio).
Inicialmente se trabajó utilizando el método del descenso por gradiente. Como se puede observar, este sufre un problema: como lo que hace es bajar según lo que le diga la gradiente de la función, termina decantándose en el primer mínimo local que halle. En este caso, se ubicó en punto inicial cercano al mínimo global. Sin embargo, como se puede observar a continuación en la figura 1, el algoritmo se acomoda al mínimo global más cercano. Esto quiere decir que funcionaría mejor con funciones de talante no decreciente o no creciente (es decir, funciones monótonas), porque de esta manera podría navegar con mayor facilidad a través de la función hasta llegar a un mínimo.
figura 1: Griewank Descenso por gradiente
Los algoritmos genéticos tuvieron un desempeño variado.
El algoritmo evolutivo usado fue el de PyGAD. En este, a pesar de que se trabajó usando 200 generaciones, llegó en uno de los primeros a lo que consideró el mínimo en
figura 2: gen vs fit en PyGAD
En la figura 3 podemos observar lo que sucede con la función, que se acomoda en un mínimo local en vez de continuar buscando otras opciones.
figura 3: Descenso 2D pyGAD griewank
En cuanto a la optimización de partículas, se observó (figura 4) que de manera similar encontró rápidamente un mínimo local en
figura 4: gen vs fit en PySwarms 2D griewank
Se puede observar en la figura 5 a continuación cómo funcionó esto. Varias partículas permanecieron en el punto y las que rondaban su zona, no se continuaron desplazando. Se debería intentar utilizar más partículas pero esto llevaría a un gasto más alto de recuersos.
figura 5: Descenso 2D Swarms griewank
En la evolución diferencial se obtuvo los mejores resultados. Se puede observar en la figura 6 su fitness. En este se logró hallar un valor cercanísimo al mínimo global en 2D con
figura 6: gen vs fit 2d ED griewank
En la figura 7 se puede observar que este método recorre mucho terreno y no se queda tan solo con el primer o segundo mínimo local que halla. Recorre gran parte de la gráfica entre
figura 7: gen vs fit 2d ED griewank
Realizamos un ejemplo de Griewank por descenso por gradiente 3D y uno de evolución diferencial, dado que fue el que mejor funcionó.
Se puede observar a continuación en la figura 8 cómo luce Griewank en un mapa de calor. Para interpretarla, se debe observar que los valores
figura 8: 4D griewank
Usando Evolución diferencial, con 200 iteraciones se llegó a lo siguiente:
punto mínimo:
figura 9: gen vs fit ed 3D
Y en la figura 10 se puede observar los puntos que toma y cómo va variando su valor:
figura 10: ED 3D Griewank
En descenso por gradiente, utilizando 300 epochs se llegó al resultado: El punto mínimo es
Podemos ver en la figura 11 que su comportamiento es mucho menos errático que el de los algoritmos heurísticos. En este se sigue una línea concreta de valores según el contraflujo de su gradiente.
figura 11: Gradiente 3D
Se evidenció mucha dependencia para del punto inicial y el Learning Rate para encontrar el mínimo. la figura a continuación contempla 5 partículas, cada una simbolizando una aplicación de descenso por gradiente con un punto inicial randomizado diferente y siendo la mejor aproximación al mínimo
Para este método, como se aprecia en la figura 12, se utilizaron 250 iteraciones, mostrando que necesita de muchas más iteraciones para ser eficiente.
figura 12: Imagen animada Descenso Por Gradiente de función de Rosenbrock
El la figura 13 a continuación se puede apreciar una aproximación mucho mejor al mínimo con 3 variables, y 10000 iteraciones.
figura 13: Codigo Descenso Por Gradiente de función de Rosenbrock de 3 variables
En la implementación de la optimización de partículas para la función de Rosenbrock, se utilizaton 10 partículas para encontrar el mínimo global. Con unas 100 iteraciones, las partículas se acercaron considerblemente al mínimo de
figura 14: Imagen animada optimización de partículas de función de Rosenbrock
En la figura 15 a continuación se evidencia que el costo del movimiento de las partículas se acentó antes de llegar a la iteración 100, alrededor de la iteración 82, incluso acentandose mucho antes y sin variar por la mayoría de las iteraciones.
Lo cuál indica que dadas más iteraciones, aunque el costo se haya acenturado, las partículas podrían encontrar de manera mucho más precisa el mínimo global de la función.
figura 15: Imagen del costo optimización de partículas de función de Rosenbrock
A continuación se muestran las imágenes animadas de
Incluso con 150 iteraciones, las partículas no tuvieron un buen acercamiento al mínimo global, siendo los puntos encontrados en
figura 16: Imagen animada optimización de partículas de función de Rosenbrock en XZ
figura 17: Imagen animada optimización de partículas de función de Rosenbrock en YZ
El algoritmo evolutivo utilizado para evaluar Rosenbrock fue el implementado en PyGad. Este fue implementado con 200 iteraciones, pero como se puede apreciar en la figura 18 a continuación, encontró una aproximación considerable del mínimo desde muy temprano.
figura 18: Imagen animada Algoritmo Evolutivo de función de Rosenbrock
La aproximación encontrada por el algoritmo implementado en PyGAD fue
figura 19: Imagen animada Algoritmo Evolutivo de función de Rosenbrock
Utilizando el algoritmo descrito en la introducción, se puede evidenciar que, aunque no es el más rápido en encontrar un mínimo, es el más preciso para encontrarlo con una precisión de
figura 20: Imagen animada Evolución diferencial de función de Rosenbrock
- Es de notarse que la velocidad en la que los algoritmos heurísticos se desplazan es muy alta. Logran visitar muchos puntos en esta clase de funciones que tienen cientos o miles de mínimos.
- El descenso por gradiente debe ser modificado para evitar que caiga en mínimos locales. Es un método muy interesante y útil, con unas bases matemáticas limpias. Sin embargo, se tendría que ejecutar cientas de veces desde muchos puntos iniciales para poder vencer funciones con muchos mínimos locales, tales como Griewank.
- En esta ocasión, para la función de Griewank, el método que mejor se comportó fue el de evolución diferencial, que fue capaz de recorrer rápidamente muchos mínimos locales hasta hallar el mínimo global en
$(0,0)$ . - Se observó un desempeño general más alto en la función de Griewank usando los algoritmos bioinspirados, especialmente el de evolución diferencial, al de descenso por gradiente. Se vio tanto en
$R^2$ como en$R^3$ . Además, logró estos resultados superiores con un uso menor de epochs o iteraciones. Esto se puede deber a que este método matemático sufre a la hora de evaluar funciones con una cantidad tan basta de mínimos locales. - El en caso de Rosenbrock, se puede notar que el desempeño de descenso por gradiente es muy afectado por el punto inicial, el learning rate y la cantidad de iteraciones que se le definan, incluso sin tener muchos mínimos locales en los que pueda caer. Con ciertos puntos iniciales encuentra en muy pocas iteraciones el punto mínimo sin ningún problema, o dependiendo del learning rate, puede o encontrarlo o no encontrarlo nunca.
- En el caso de rosenbrock, por no tener muchos mínimos locales, como Griewank, es mucho más útil y confiable, aunque no sea ni el más rápido ni el más preciso en encontrar el mínimo.
- Al experimentar con tantos métodos de optimización, se evidencia que todos son útiles y no necesariamente uno siempre es mejor que otro, pero sí se debe tener en cuenta qué tipo de función se quiere analizar con ellos para saber cuál es el mejor a implementar en futuros proyectos.
Se debe resolver el problema del vendedor viajero para varias ciudades principales de Colombia. El objetivo es hallar un camino que, pasando por cada ciudad por lo menos una vez, minimice el costo definido por la suma del valor de la hora del vendedor, el costo de los peajes y el costo del combustible.
Se solucionó el problema por dos vías diferentes: Algoritmos genéticos (GA) y Colonia de hormigas (AC).
- Creamos la base de datos de las ciudades a visitar con sus respectivas coordenadas [4].
| Cod Mun | Municipio | Cod Dep | Departamento | Latitud | Longitud |
|---|---|---|---|---|---|
| 63001 | Armenia | 63 | Quindio | 4,5338889 | -75,6811111 |
| 8001 | Barranquilla | 8 | Atlantico | 10,9638889 | -74,7963889 |
| 11001 | Bogota D.C. | 25 | Cundinamarca | 4,6 | -74,0833333 |
| 68001 | Bucaramanga | 68 | Santander | 7,1297222 | -73,1258333 |
| 13001 | Cartagena | 13 | Bolivar | 10,3997222 | -75,5144444 |
| 54001 | Cucuta | 54 | Norte de Santander | 7,8833333 | -72,5052778 |
| 17001 | Manizales | 17 | Caldas | 5,07 | -75,5205556 |
| 5001 | Medellin | 5 | Antioquia | 6,2913889 | -75,5361111 |
| 23001 | Monteria | 23 | Cordoba | 8,7575 | -75,89 |
| 76520 | Palmira | 76 | Valle del Cauca | 3,5394444 | -76,3036111 |
| 66001 | Pereira | 66 | Risaralda | 4,8133333 | -75,6961111 |
| 52001 | Pasto | 52 | Narino | 1,214670737 | -77,27864742 |
| 8758 | Soledad | 8 | Atlantico | 10,9172222 | -74,7666667 |
| 76834 | Tulua | 76 | Valle del Cauca | 4,0866667 | -76,2 |
| 20001 | Valledupar | 20 | Cesar | 10,4769444 | -73,2505556 |
-
Procedemos a construír la matriz de costos. La entrada i,j de esta matriz contendrá el costo en pesos de ir de la ciudad i a la ciudad j. Éste, a su vez es la suma del salario por horas del vendedor, costo de los peajes y el costo del combustible en valores del 2023.
Costo hora del vendedor: El salario promedio de un conductor en colombia es de $6.827/hora [5].
Costo de los peajes: Se estableció el costo de los peajes, el tiempo estimado de viaje y la distancia para cada par de ciudades.
figura 21: Ejemplo de peajes, tiempo y distancia entre dos ciudades
figura 22: Ejemplo de costo de peajes entre dos ciudades
Utilizando la página Viaja por Colombia [6] (que explícitamente provee toda la información necesaria), obtuvimos las siguientes matrices correspondientes a cada uno de éstos parámetros:
| Armenia | Barranquilla | Bogota D.C. | Bucaramanga | Cartagena | Cucuta | Manizales | Medellin | Monteria | Palmira | Pereira | Pasto | Soledad | Tulua | Valledupar |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0,00 | 968,00 | 282,00 | 594,00 | 903,00 | 804,00 | 96,00 | 268,00 | 663,00 | 180,00 | 48,00 | 559,00 | 968,00 | 180,00 | 949,00 |
| 968,00 | 0,00 | 979,00 | 585,00 | 120,00 | 657,00 | 894,00 | 702,00 | 353,00 | 1252,00 | 1050,00 | 1631,00 | 0,00 | 1252,00 | 295,00 |
| 282,00 | 979,00 | 0,00 | 407,00 | 1050,00 | 557,00 | 302,00 | 443,00 | 832,00 | 464,00 | 318,00 | 845,00 | 979,00 | 464,00 | 867,00 |
| 594,00 | 585,00 | 407,00 | 0,00 | 650,00 | 198,00 | 508,00 | 404,00 | 717,00 | 769,00 | 559,00 | 1140,00 | 585,00 | 769,00 | 449,00 |
| 903,00 | 120,00 | 1050,00 | 650,00 | 0,00 | 731,00 | 831,00 | 640,00 | 276,00 | 1063,00 | 849,00 | 1434,00 | 120,00 | 1063,00 | 365,00 |
| 804,00 | 657,00 | 557,00 | 198,00 | 731,00 | 0,00 | 694,00 | 598,00 | 795,00 | 954,00 | 747,00 | 1329,00 | 657,00 | 954,00 | 525,00 |
| 96,00 | 894,00 | 302,00 | 508,00 | 831,00 | 694,00 | 0,00 | 194,00 | 600,00 | 258,00 | 54,00 | 424,00 | 894,00 | 258,00 | 860,00 |
| 268,00 | 702,00 | 443,00 | 404,00 | 640,00 | 598,00 | 194,00 | 0,00 | 405,00 | 425,00 | 215,00 | 802,00 | 702,00 | 425,00 | 745,00 |
| 663,00 | 353,00 | 832,00 | 717,00 | 276,00 | 795,00 | 600,00 | 405,00 | 0,00 | 825,00 | 621,00 | 1203,00 | 353,00 | 825,00 | 433,00 |
| 180,00 | 1252,00 | 464,00 | 769,00 | 1063,00 | 954,00 | 258,00 | 425,00 | 825,00 | 0,00 | 210,00 | 388,00 | 1252,00 | 0,00 | 1116,00 |
| 48,00 | 1050,00 | 318,00 | 559,00 | 849,00 | 747,00 | 54,00 | 215,00 | 621,00 | 210,00 | 0,00 | 582,00 | 1050,00 | 210,00 | 913,00 |
| 559,00 | 1631,00 | 845,00 | 1140,00 | 1434,00 | 1329,00 | 424,00 | 802,00 | 1203,00 | 388,00 | 582,00 | 0,00 | 1631,00 | 388,00 | 1493,00 |
| 138800,00 | 0,00 | 979,00 | 585,00 | 120,00 | 657,00 | 894,00 | 702,00 | 353,00 | 1252,00 | 1050,00 | 1631,00 | 0,00 | 1252,00 | 295,00 |
| 49600,00 | 193300,00 | 464,00 | 769,00 | 1063,00 | 954,00 | 258,00 | 425,00 | 825,00 | 0,00 | 210,00 | 388,00 | 1252,00 | 0,00 | 1116,00 |
| 949,00 | 295,00 | 867,00 | 449,00 | 365,00 | 525,00 | 860,00 | 745,00 | 433,00 | 1116,00 | 913,00 | 1493,00 | 295,00 | 1116,00 | 0,00 |
| Tiempo viaje | Armenia | Barranquilla | Bogota D.C. | Bucaramanga | Cartagena | Cucuta | Manizales | Medellin | Monteria | Palmira | Pereira | Pasto | Soledad | Tulua | Valledupar |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Armenia | 0,00 | 18,05 | 5,61 | 9,91 | 17,05 | 14,91 | 1,97 | 5,25 | 14,70 | 2,79 | 1,00 | 9,61 | 18,05 | 2,79 | 14,77 |
| Barranquilla | 18,05 | 0,00 | 17,95 | 9,17 | 2,03 | 12,22 | 16,72 | 12,03 | 6,12 | 18,98 | 16,17 | 26,00 | 0,00 | 18,98 | 5,58 |
| Bogota D.C. | 5,61 | 17,95 | 0,00 | 7,60 | 19,17 | 11,50 | 5,83 | 8,17 | 15,50 | 8,68 | 6,08 | 15,16 | 17,95 | 8,68 | 12,82 |
| Bucaramanga | 9,91 | 9,17 | 7,60 | 0,00 | 11,82 | 4,95 | 8,77 | 8,20 | 11,80 | 14,08 | 9,87 | 19,60 | 9,17 | 14,08 | 7,15 |
| Cartagena | 17,05 | 2,03 | 19,17 | 11,82 | 0,00 | 13,34 | 15,27 | 11,80 | 5,10 | 19,47 | 15,90 | 26,00 | 2,03 | 19,47 | 6,92 |
| Cucuta | 14,91 | 12,22 | 11,50 | 4,95 | 13,34 | 0,00 | 13,45 | 11,38 | 14,47 | 17,15 | 14,52 | 24,00 | 12,22 | 17,15 | 9,60 |
| Manizales | 1,97 | 16,72 | 5,83 | 8,77 | 15,27 | 13,45 | 0,00 | 3,72 | 11,56 | 3,95 | 1,17 | 7,34 | 16,72 | 3,95 | 13,32 |
| Medellin | 5,25 | 12,03 | 8,17 | 8,20 | 11,80 | 11,38 | 3,72 | 0,00 | 7,42 | 7,75 | 4,08 | 14,48 | 12,03 | 7,75 | 11,55 |
| Monteria | 14,70 | 6,12 | 15,50 | 11,80 | 5,10 | 14,47 | 11,56 | 7,42 | 0,00 | 14,52 | 12,12 | 21,97 | 6,12 | 14,52 | 7,88 |
| Palmira | 2,79 | 18,98 | 8,68 | 14,08 | 19,47 | 17,15 | 3,95 | 7,75 | 14,52 | 0,00 | 4,13 | 7,27 | 18,98 | 0,00 | 16,83 |
| Pereira | 1,00 | 16,17 | 6,08 | 9,87 | 15,90 | 14,52 | 1,17 | 4,08 | 12,12 | 4,13 | 0,00 | 9,50 | 16,17 | 4,13 | 14,27 |
| Pasto | 9,61 | 26,00 | 15,16 | 19,60 | 26,00 | 24,00 | 7,34 | 14,48 | 21,97 | 7,27 | 9,50 | 0,00 | 26,00 | 7,27 | 23,37 |
| Soledad | 18,05 | 0,00 | 17,95 | 9,17 | 2,03 | 12,22 | 16,72 | 12,03 | 6,12 | 18,98 | 16,17 | 26,00 | 0,00 | 18,98 | 5,58 |
| Tulua | 2,79 | 18,98 | 8,68 | 14,08 | 19,47 | 17,15 | 3,95 | 7,75 | 14,52 | 0,00 | 4,13 | 7,27 | 18,98 | 0,00 | 16,83 |
| Valledupar | 14,77 | 5,58 | 12,82 | 7,15 | 6,92 | 9,60 | 13,32 | 11,55 | 7,88 | 16,83 | 14,27 | 23,37 | 5,58 | 16,83 | 0,00 |
| Costo Peajes | Armenia | Barranquilla | Bogota D.C. | Bucaramanga | Cartagena | Cucuta | Manizales | Medellin | Monteria | Palmira | Pereira | Pasto | Soledad | Tulua | Valledupar |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Armenia | 0,00 | 138800,00 | 55400,00 | 72600,00 | 164500,00 | 87700,00 | 39700,00 | 57500,00 | 134200,00 | 49600,00 | 15300,00 | 78500,00 | 138800,00 | 49600,00 | 100000,00 |
| Barranquilla | 138800,00 | 0,00 | 142500,00 | 88100,00 | 33500,00 | 68700,00 | 117500,00 | 112400,00 | 41000,00 | 193300,00 | 141900,00 | 222200,00 | 0,00 | 193300,00 | 49300,00 |
| Bogota D.C. | 55400,00 | 142500,00 | 0,00 | 55100,00 | 130800,00 | 42600,00 | 45400,00 | 74800,00 | 137900,00 | 104900,00 | 70700,00 | 133900,00 | 142500,00 | 104900,00 | 103700,00 |
| Bucaramanga | 72600,00 | 88100,00 | 55100,00 | 0,00 | 76400,00 | 15100,00 | 51300,00 | 70100,00 | 86600,00 | 127100,00 | 75700,00 | 156000,00 | 88100,00 | 127100,00 | 49300,00 |
| Cartagena | 164500,00 | 33500,00 | 130800,00 | 76400,00 | 0,00 | 57000,00 | 136400,00 | 107000,00 | 54500,00 | 200600,00 | 149200,00 | 229500,00 | 33500,00 | 200600,00 | 37600,00 |
| Cucuta | 87700,00 | 68700,00 | 42600,00 | 15100,00 | 57000,00 | 0,00 | 66400,00 | 85200,00 | 67200,00 | 142200,00 | 90800,00 | 171100,00 | 68700,00 | 142200,00 | 29900,00 |
| Manizales | 39700,00 | 117500,00 | 45400,00 | 51300,00 | 136400,00 | 66400,00 | 0,00 | 29400,00 | 106100,00 | 75800,00 | 24400,00 | 104700,00 | 117500,00 | 75800,00 | 78700,00 |
| Medellin | 57500,00 | 112400,00 | 74800,00 | 70100,00 | 107000,00 | 85200,00 | 29400,00 | 0,00 | 90700,00 | 93600,00 | 42200,00 | 122500,00 | 112400,00 | 93600,00 | 97500,00 |
| Monteria | 134200,00 | 41000,00 | 137900,00 | 86600,00 | 54500,00 | 67200,00 | 106100,00 | 90700,00 | 0,00 | 170300,00 | 118900,00 | 199200,00 | 41000,00 | 170300,00 | 47800,00 |
| Palmira | 49600,00 | 193300,00 | 104900,00 | 127100,00 | 200600,00 | 142200,00 | 75800,00 | 93600,00 | 170300,00 | 0,00 | 51400,00 | 38600,00 | 193300,00 | 0,00 | 154500,00 |
| Pereira | 15300,00 | 141900,00 | 70700,00 | 75700,00 | 149200,00 | 90800,00 | 24400,00 | 42200,00 | 118900,00 | 51400,00 | 0,00 | 80300,00 | 141900,00 | 51400,00 | 103100,00 |
| Pasto | 78500,00 | 222200,00 | 133900,00 | 156000,00 | 229500,00 | 171100,00 | 104700,00 | 122500,00 | 199200,00 | 38600,00 | 80300,00 | 0,00 | 222200,00 | 38600,00 | 183400,00 |
| Soledad | 138800,00 | 0,00 | 142500,00 | 88100,00 | 33500,00 | 68700,00 | 117500,00 | 112400,00 | 41000,00 | 193300,00 | 141900,00 | 222200,00 | 0,00 | 193300,00 | 49300,00 |
| Tulua | 49600,00 | 193300,00 | 104900,00 | 127100,00 | 200600,00 | 142200,00 | 75800,00 | 93600,00 | 170300,00 | 0,00 | 51400,00 | 38600,00 | 193300,00 | 0,00 | 154500,00 |
| Valledupar | 100000,00 | 49300,00 | 103700,00 | 49300,00 | 37600,00 | 29900,00 | 78700,00 | 97500,00 | 47800,00 | 154500,00 | 103100,00 | 183400,00 | 49300,00 | 154500,00 | 0,00 |
Costo del combustible: El recorrido se hará en un Mini Cooper 1.6, cuyo rendimiento es de 8,35 litros / 100 km [7]. Además, el costo promedio de un litro de gasolina corriente en Colombia es de $2.747,31/litro [8].
Importamos las tablas de tiempo de viaje, costo de los peajes y distancia entre ciudades. Para así calcular la siguiente matriz de costos totales en pesos:
| Armenia | Barranquilla | Bogota D.C. | Bucaramanga | Cartagena | Cucuta | Manizales | Medellin | Monteria | Palmira | Pereira | Pasto | Soledad | Tulua | Valledupar |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.0 | 484086.92267999996 | 158390.37857 | 276519.39869 | 488048.897655 | 373928.47954 | 75171.62696 | 154821.05318 | 386649.35525499994 | 109939.39929999999 | 33138.218479999996 | 272342.285215 | 484086.92267999996 | 109939.39929999999 | 418535.755365 |
| 484086.92267999996 | 0.0 | 489627.626915 | 284902.81522499997 | 74886.8562 | 302841.99294499995 | 436731.38418999995 | 355567.88026999997 | 163759.57590499998 | 610085.74202 | 493162.99425 | 773854.0279349999 | 0.0 | 610085.74202 | 155067.773575 |
| 158390.37857 | 489627.626915 | 0.0 | 200351.15669499998 | 502543.99425 | 248886.51444499998 | 154480.32627 | 232200.960555 | 434579.62032 | 270600.13864 | 185157.48242999997 | 431240.645325 | 489627.626915 | 270600.13864 | 390112.273795 |
| 276519.39869 | 284902.81522499997 | 200351.15669499998 | 0.0 | 306205.39025 | 94314.92623 | 227708.18558 | 218759.15553999998 | 331638.676045 | 399633.056065 | 271317.30521499994 | 551325.6389 | 284902.81522499997 | 399633.056065 | 201113.822865 |
| 488048.897655 | 74886.8562 | 502543.99425 | 306205.39025 | 0.0 | 315763.86143499997 | 431280.009935 | 334374.8464 | 152632.20626 | 577374.299255 | 452510.226865 | 735962.15209 | 74886.8562 | 577374.299255 | 168573.980525 |
| 373928.47954 | 302841.99294499995 | 248886.51444499998 | 94314.92623 | 315763.86143499997 | 0.0 | 317427.01719 | 300072.69022999995 | 348359.996075 | 478131.01729 | 361290.12759499997 | 639821.111665 | 302841.99294499995 | 478131.01729 | 215874.40212499996 |
| 75171.62696 | 436731.38418999995 | 154480.32627 | 227708.18558 | 431280.009935 | 317427.01719 | 0.0 | 99300.11468999999 | 322660.35099999997 | 161951.94933 | 44775.21079 | 252075.94324 | 436731.38418999995 | 161951.94933 | 366919.97109999997 |
| 154821.05318 | 355567.88026999997 | 232200.960555 | 218759.15553999998 | 334374.8464 | 300072.69022999995 | 99300.11468999999 | 0.0 | 234263.495925 | 244004.413625 | 119375.24277499999 | 405334.06877 | 355567.88026999997 | 244004.413625 | 347255.136825 |
| 386649.35525499994 | 163759.57590499998 | 434579.62032 | 331638.676045 | 152632.20626 | 348359.996075 | 322660.35099999997 | 234263.495925 | 0.0 | 458683.35762499995 | 344100.87908499996 | 625157.8531549999 | 163759.57590499998 | 458683.35762499995 | 200927.126705 |
| 109939.39929999999 | 610085.74202 | 270600.13864 | 399633.056065 | 577374.299255 | 478131.01729 | 161951.94933 | 244004.413625 | 458683.35762499995 | 0.0 | 127769.59085 | 177239.63937999998 | 610085.74202 | 0.0 | 525409.23966 |
| 33138.218479999996 | 493162.99425 | 185157.48242999997 | 271317.30521499994 | 452510.226865 | 361290.12759499997 | 44775.21079 | 119375.24277499999 | 344100.87908499996 | 127769.59085 | 0.0 | 278667.52407 | 493162.99425 | 127769.59085 | 409963.84150499996 |
| 272342.285215 | 773854.0279349999 | 431240.645325 | 551325.6389 | 735962.15209 | 639821.111665 | 252075.94324 | 405334.06877 | 625157.8531549999 | 177239.63937999998 | 278667.52407 | 0.0 | 773854.0279349999 | 177239.63937999998 | 685441.7648049999 |
| 32102800.788 | 0.0 | 489627.626915 | 284902.81522499997 | 74886.8562 | 302841.99294499995 | 436731.38418999995 | 355567.88026999997 | 163759.57590499998 | 610085.74202 | 493162.99425 | 773854.0279349999 | 0.0 | 610085.74202 | 155067.773575 |
| 11446906.425999999 | 44665970.880499996 | 270600.13864 | 399633.056065 | 577374.299255 | 478131.01729 | 161951.94933 | 244004.413625 | 458683.35762499995 | 0.0 | 127769.59085 | 177239.63937999998 | 610085.74202 | 0.0 | 525409.23966 |
| 418535.755365 | 155067.773575 | 390112.273795 | 201113.822865 | 168573.980525 | 215874.40212499996 | 366919.97109999997 | 347255.136825 | 200927.126705 | 525409.23966 | 409963.84150499996 | 685441.7648049999 | 155067.773575 | 525409.23966 | 0.0 |
-
Se implementaron algoritmos genéticos por medio de python [9] y se obtuvo el siguiente gif que representa la evolución de la mejor ruta a lo largo de las generaciones:
figura 23: Mapa de Colombia con recorridos
Con lo que la mejor ruta encontrada por los algoritmos genéticos fue:
Pasto -> Palmira -> Tulua -> Armenia -> Pereira -> Medellin -> Manizales -> Bogota D.C. -> Bucaramanga -> Cucuta -> Valledupar -> Soledad -> Barranquilla -> Cartagena -> Monteria
Con un costo de: $1.586.600 COP
-
Se implementó colonia de hormigas por medio de python [10] y se obtuvo el siguiente gif que representa la evolución de la mejor ruta que descubren 100 hormigas:
figura 24: Mapa de Colombia con recorridos de hormigas
Con lo que la mejor ruta encontrada por la colonia de hormigas fue:
Pereira -> Armenia -> Palmira -> Tulua -> Manizales -> Pasto -> Bogota D.C. -> Bucaramanga -> Cucuta -> Valledupar -> Soledad -> Barranquilla -> Cartagena -> Monteria -> Medellin
Con un costo de: $2.013.640 COP
-
Ambos algoritmos lograron solucionar el problema con resultados mucho mejores que el azar o un análisis a priori.
-
Los algoritmos genéticos se desempeñaron mejor que las colonias de hormigas, pero se sospecha que se debe a la capacidad de cómputo limitada que solo permitió simular 100 hormigas.
-
Recorrer todas las ciudades deseadas por poco más de un millón y medio de pesos parece muy razonable, más aún teniendo en cuenta que se escogió un vehículo que no tiene un rendimiento de combustible destacable.
-
[1] "Virtual Library of Simulation Experiments" (2013). Griewank Function [Online]. Available: https://www.sfu.ca/~ssurjano/griewank.html
-
[2] "Virtual Library of Simulation Experiments" (2013). Rosenbrock Function [Online]. Available: https://www.sfu.ca/~ssurjano/rosen.html
-
[3] "Towards Data Science" (Mar 31 2020). Optimization — Descent Algorithms [Online]. Available: https://towardsdatascience.com/optimization-descent-algorithms-bf595f069788
-
[4] “Geoportal del DANE - Codificación Divipola,” geoportal.dane.gov.co. https://geoportal.dane.gov.co/geovisores/territorio/consulta-divipola-division-politico-administrativa-de-colombia/ (accessed Mar. 10, 2023).
-
[5] “Salario para Conductor en Colombia - Salario Medio,” Talent.com. https://co.talent.com/salary?job=conductor#:~:text= (accessed Mar. 10, 2023).
-
[6] S. O. C. S.A.S, “Peajes en Colombia [2022],” Viaja por Colombia. https://viajaporcolombia.com/peajes/ (accessed Mar. 10, 2023).
-
[7] “Consumo Gasolina: 8,35 l/100km - Mini, Mini Cooper, Mini Cooper 1.6,” www.spritmonitor.de. https://www.spritmonitor.de/es/detalle/125236.html?cdetail=1 (accessed Mar. 10, 2023).
-
[8] “Colombia precios de la gasolina, 06-marzo-2023,” GlobalPetrolPrices.com. https://es.globalpetrolprices.com/Colombia/gasoline_prices/#:~:text=El%20valor%20medio%20durante%20este (accessed Mar. 10, 2023).
-
[9] M. Kukreja, “Travelling-Salesman-Problem-with-Genetic-Algorithm,” GitHub, Oct. 10, 2022. https://github.com/manpreet1130/Travelling-Salesman-Problem-with-Genetic-Algorithm (accessed Mar. 10, 2023).
-
[10] R. Zhang, “ant-colony-tsp,” GitHub, Feb. 27, 2023. https://github.com/ppoffice/ant-colony-tsp (accessed Mar. 10, 2023).
-
Algunas funciones extraídas y modificadas de las notas de Juan David Ospina en su curso Redes Neuronales y Algoritmos Bioinspirados de la UNAL-med semestre 2023-1.
- PyGAD
- PySwarms
- https://programmerclick.com/article/13428601/ (versión en español, código extraído de csdn.ne)