Una hiperheurística para la solución del Problema del Viajante Asimétrico (página 2)
Enviado por Jos� Carlos D�az D�az
3.3.3 Operador 2-Opt
Este movimiento está diseñado en [20], el cual tiene la siguiente estructura, sea la ruta S0 formada como sigue:
S0 = a0, a1, … , ai-1, ai, ai+1, ai+2, … , aj-1, aj, aj+1, … , an-1, an, a0
donde i y j son las posiciones seleccionadas para realizar el movimiento (Figura 2.5a). El movimiento consiste en invertir la subruta formada desde el nodo ai hasta el nodo aj, por tanto la nueva solución vecina formada S1 queda como sigue:
S1 = a0, a1, … , ai-1, aj, aj-1, aj-2, … , ai+2, ai+1, ai, aj+1, … , an-1, an, a0
como se muestra en la Figura 2.5b.
2.5a 2.5b
Fig. 2.5 Operador 2-Opt.
Computacionalmente este operador realiza O(n3) operaciones. Por sus características, de que invierte una subruta completa, no aporta buenos resultados cuando la solución a la cual se le aplica es de buena calidad. Desde el punto de vista de tiempo de ejecución es más ineficiente que los dos operadores anteriores pues la cantidad de costos de aristas a evaluar depende del tamaño de la subruta invertida.
Este operador es utilizado también en el Problema del Viajante Simétrico, pero mucho más eficiente en este caso por la simetría de la matriz de costos.
3.3.4 Operador 3-Opt
Este movimiento está diseñado en [7, 15 y 20] realizando O(n3) operaciones. La forma en que busca soluciones vecinas se describe a continuación.
Sea la ruta S0 formada como sigue:
S0 = a0, a1, … , ai-1, ai, ai+1, … , aj-1, aj, aj+1, … , ak-1, ak, ak+1, … , an-1, an, a0
donde i , j y k son las tres posiciones seleccionadas para realizar la búsqueda (Figura 2.6a). El movimiento consiste en intercambiar las subruta formadas desde el nodo ai+1 hasta el nodo aj, y la del nodo aj+1 hasta el nodo ak, formándose la nueva solución vecina S1 de la siguiente forma:
S1 = a0, a1, … , ai-1, ai, aj+1, … , ak-1, ak,ai+1, … , aj-1, aj, ak+1, … , an-1, an, a0
como se muestra en la Figura 2.6b.
2.4a 2.4b
Fig. 2.4 Operador 3-Opt.
3.3.5 Operador 4-Opt
Este movimiento está diseñado en [7 y 15], donde en [15] se aplican varias variantes del movimiento pero para el problema del viajante simétrico. El operador, teniendo en cuenta variantes de mejora para el PVA se describe como sigue:
Sea la ruta S0 formada por:
S0 = a0, a1, … , ai-1, ai, ai+1, … , aj-1, aj, aj+1, … , ak-1, ak, ak+1, … , az-1, az, az+1, … ,an-1, an, a0
donde i, j, k y z son las cuatro posiciones seleccionadas para realizar la búsqueda (Figura 2.7a). El movimiento consiste en intercambiar las subruta formadas desde el nodo ai+1 hasta el nodo aj, y la del nodo ak+1 hasta el nodo az, formando la nueva solución vecina S1 la siguiente forma:
S1 = a0, a1, … , ai-1, ai, ak+1, … , az-1, az , aj+1, … , ak-1, ak, ai+1, … , aj-1, aj, az+1, … ,an-1, an, a0
como se muestra en la Figura 2.7b.
2.7a 2.7b
Fig. 2.7 Operador 4-Opt.
Éste es el algoritmo de búsqueda más costoso, es O(n4). Para problemas con más de 100 ciudades sus tiempos computacionales son muy altos.
3.4 Diseño de la hiperheurística
En el segundo epígrafe se explicó el funcionamiento de las hiperheurísticas en general y de las ventajas de estas con respecto a las metaheurísticas. Para el funcionamiento de la hiperheurística aquí diseñada, se necesitan dos listas de contadores: una para los algoritmos constructivos y la otra para los operadores de búsquedas. Su diseño es el siguiente:
- Aplicar el método constructivo de su lista que tenga mayor contador para obtener una solución inicial S0.
- Aplicarle el método de búsqueda de su lista que mayor contador tenga.
- Mientras este método mejore los resultados obtenidos incrementar en uno su contador y continuar aplicándolo hasta que quede atrapado en un óptimo local. Hacer tabú este operador y disminuir su contador en uno. Si cumple con los criterios de parada ir al paso 5. Si todos los operadores de búsqueda son tabú retornar al paso 1.
- Aplicar a la solución actual el operador de búsqueda no tabú que tenga mayor contador y volver al paso 3.
- Fin.
Existen dos variantes para el funcionamiento de la hiperheurística, consiste en construir dos listas de algoritmos constructivos: una lista es con los algoritmos GRASP, Vecino más cercano, Aleatorio y Goloso; la segunda es formada por las distintas variantes de la técnica de Remiendos.
Teniendo en cuenta las conclusiones que aporta la bibliografía revisada los métodos de tipo patche son más eficientes (se corrobora en el diseño de experimento realizado que se explica en el próximo capítulo). Es por ello que si el número m de ciclos disjuntos generados por la solución AP es tal que m!>1000 entonces solo se utilizará la variante de métodos constructivos de tipo patche y la cota superior de soluciones analizadas es 1000. Se tiene en cuenta que se van almacenando la secuencia en la cual los ciclos se van tomando para la construcción de las soluciones por las variantes del método patche de forma tal de garantizar que no se repitan soluciones.
En el caso que m!<<1000, por ejemplo m =4, y la mejor solución obtenida por los métodos de tipo patche está muy alejada de la cota AP, se aplica la hiperheurística con los otros métodos constructivos para intentar mejorar la solución.
Para evaluar métodos de tipo heurístico los cuales buscan las soluciones de forma no determinística, se debe, primeramente, realizar un diseño de experimento, y a este aplicarle un análisis estadístico que demuestre la calidad de estos métodos. Las instancias utilizadas del PVA son tomadas de una biblioteca de varias fuentes, llamada TSPLIB [33] que se encuentra publicada en Internet, donde para cada instancia es conocido su mejor valor (el valor óptimo).
El objetivo de este epígrafe es realizar un diseño de experimento a los algoritmos constructivos, a los de búsqueda y a la hiperheurística diseñada, aplicándoselos a cada instancia. Se utilizan dos parámetros a comparar: los mejores valores encontrados y el tiempo de ejecución. Posteriormente se realiza un análisis estadístico a estos datos.
4.1 Resultado de los métodos constructivos
El diseño de experimento a estos métodos consiste en analizar los resultados obtenidos sin aplicarles búsquedas locales. A cada instancia se le realizan 30 corridas, donde la cantidad de iteraciones realizadas en cada método es igual al tamaño n de cada instancia, si n£ 100. Si n>100 el número de iteraciones máxima es 100.
La Tabla 4.1 muestra el análisis estadístico del exceso (en por ciento) de calidad de solución y tiempo de ejecución de la CPU respectivamente, teniendo en cuenta la media obtenida de los costos y tiempos en las 30 corridas de cada instancia. Por columnas se muestran: los métodos constructivos (Heurística Constructiva), y para cada sección se muestran por columna el mejor (Mín.), y el peor (Máx.) valor encontrado, la media (Media) y el rango de los valores esperados (Q1 y Q3) respectivamente.
Tabla 4.1 Eficiencia de los métodos constructivos.
Heurística Constructiva
Sobre el Costo Óptimo (%)
Tiempo (seg.)
Mín.
Máx.
Media
Q1
Q3
Mín.
Máx.
Media
Q1
Q3
GRASP
9.3
284.1
78.7
46.1
101.1
0
362
52.7
0.1
22.1
Aleatoria
75.9
772.3
280.3
194.4
339.3
0
2.916
0.539
0.004
0.281
Vecino más cercano
1.07
40.03
20.64
14.49
29.49
0
339.2
50.2
0.1
20.8
Golosa
2.57
150.38
62.92
47.56
76.7
0
183
23.7
0
10
Remiendo Aleatorio
0.14
73.33
20.26
2.97
25.79
0
2.727
0.455
0.003
0.184
Remiendo Mayor a Menor
0.14
83.00
23.18
6.83
25.66
0
16.1
1.191
0.003
0.183
Remiendo Menor a Mayor
0.34
126.23
26.69
7.08
28.13
0
17.93
1.290
0.002
0.186
La Tabla 4.1 muestra que las respectivas técnicas de tipo remiendo generan soluciones buenas (destacando la Aleatoria y la de Mayor a Menor) en tiempos pequeños comparándolas con los otras, aunque el método del vecino más cercano genera soluciones con mucha calidad pero su tiempo de ejecución es alto. El otro algoritmo que le sigue es el Goloso pero presenta la misma deficiencia en tiempo, esto sucede también con la metaheurística GRASP. El método que obtiene las soluciones más malas es el Aleatorio.
4.2 Resultado de los métodos de búsquedas
Este diseño de experimento consiste en buscar 30 soluciones aleatorias para cada instancia y a cada solución obtenida se le aplicó los distintos métodos de búsqueda.
La Tabla 4.2 muestra el análisis estadístico del exceso (en por ciento) de calidad de solución y tiempo de ejecución de la CPU respectivamente, teniendo en cuenta la media obtenida de los costos y tiempos en las 30 corridas de cada instancia (mostrados en el Anexo 2). Por columnas se muestran: los operadores de búsquedas implementados (Heurística de Búsquedas), y para cada sección se muestran por columna el mejor (Mín.), y el peor (Máx.) valor encontrado, la media (Media) y el rango de los valores esperados (Q1 y Q3) respectivamente. Así, por ejemplo, el valor Min = 0 para 2-Opt significa que al menos en una instancia en todas las corridas se obtuvo el óptimo.
Tabla 4.2 Eficiencia de los métodos de búsquedas.
Heurística de Búsquedas
Sobre el Costo Óptimo (%)
Tiempo (seg.)
Mín.
Máx.
Media
Q1
Q3
Mín.
Máx.
Media
Q1
Q3
Primera Mejora
Mover Nodo
11.8
99.64
37.54
20.72
43.4
0
64.17
4.67
0.05
0.37
Intercambiar Nodo
18.03
155.03
55.66
41.5
69.56
0.001
14.948
1.171
0.019
0.173
2-Opt
0
84.18
42.18
17.51
62.86
0
12.41
3.21
0.22
5.08
3-Opt
0.4
19.84
12.65
7.54
16.41
0
12.81
2.8
0.21
4.53
4-Opt
0.57
20.56
14.89
12.03
19.38
0
111.8
29.3
1.7
45.6
Esta tabla muestra que, según el experimento realizado, la eficiencia de estos operadores (más eficiente a menos eficiente), por sus valores encontrados con respecto al óptimo, está determinada por el siguiente orden: 3-Opt, 4-Opt, Mover Nodo, 2-Opt e Intercambiar Nodo. Los tiempos de ejecución de ellos muestran un orden de los métodos por sus resultados: Intercambiar Nodo, 3-Opt, 2-Opt, Mover Nodo y 4-Opt respectivamente. Los métodos Mover Nodo y Intercambiar Nodo tienen un diseño de experimento más amplio, por lo ya explicado anteriormente.
4.3 Análisis de la hiperheurística
Como se habló en el epígrafe anterior, se propusieron dos variantes para el diseño de la hiperheurística. En el experimento se tuvo en cuenta la segunda variante, o sea, la que utiliza las distintas variantes de la técnica de remiendos.
En la Tabla 4.3 se muestran los resultados de un análisis estadístico hecho con 30 corridas a cada instancia del PVA, incluyendo un problema real (el atsp37) de la Industria Textil. Siendo conocido su valor óptimo. Por columnas se muestran: las instancias (Instancias), su tamaño (N), su costo óptimo (Costo Óptimo), su cota AP (Cota AP) y para cada sección se muestran por columna el mejor (Mín.), y el peor (Máx.) valor encontrado, la media (Media) y el rango de los valores esperados (Q1 y Q3) respectivamente.
Tabla 4.3 Resultados de la hiperheurística.
Instancias
N
Costo
Óptimo
Cuota
AP
Costos
Tiempos (seg.)
Mín.
Máx.
Media
Q1
Q3
Mín.
Máx.
Media
Q1
Q3
br17
17
39
0
0
0
0
0
0
0
0
0
0
0
ft53
53
6905
5931
0
13.84
3.2
1.11
3.24
12.29
90
60.15
60.29
64.73
ft70
70
38673
37978
0.96
3.62
2.24
1.35
3.09
60.5
324
111.3
77.2
104
ftv33
34
1286
1185
0
5.28
0.91
0
1.76
0.58
120
49.8
2.21
120.11
ftv35
36
1473
1381
0.13
0.13
0.13
0.13
0.13
60
64
60.58
60.11
60.41
ftv38
39
1530
1438
0.13
0.91
0.2
0.13
0.13
60
66
61
60.3
61.12
ftv44
45
1613
1521
0.62
4.27
3.61
3.78
4.03
60
94
63.3
60.25
62.82
ftv47
48
1776
1652
0
1.74
0.65
0.45
0.78
2.22
68
54.26
60.02
62.46
ftv55
56
1608
1435
0
4.1
1.58
1.36
2.19
16.89
84
64.49
60.31
70.49
ftv64
65
1839
1721
0
5.49
1.68
0.65
2.59
48.96
112
85.89
72.35
102.06
ftv70
71
1950
1766
1.02
4.82
2.9
2.10
3.48
60.1
658
131.6
78.6
137.6
ftv170
171
2755
2631
3.99
16.73
8.2
5.29
10.81
60.01
64
61.84
60.31
63.19
kro124
100
36230
33978
8.95
10.01
12.43
10.77
14.35
60.01
64
61.84
60.26
62.82
p43
43
5620
148
0
0.16
0.03
0
0.03
0.59
65
47.32
28.78
62.32
rbg323
323
1326
1326
0
0.9
0.1
0
0
8.02
86
27.41
16.12
28.7
rbg358
358
1163
1163
0
1.54
0.26
0
0.68
14.27
82
35.3
14.35
66.35
rbg403
403
2465
2465
0
0.32
0.08
0
0.32
2.64
88
41.77
5.79
64.88
rbg443
443
2720
2720
0
0
0
0
0
12.59
54
28.67
24.44
36.38
ry48p
48
14422
12517
0.16
3.76
2.04
1.07
2.82
60
66
62
60.34
62.83
atsp37
38
1137
1098
0
0
0
0
0
0.1
0.9
0.26
0.12
0.29
Los resultados obtenidos muestran que la hiperheurística desarrollada obtiene en el 60% de las instancias sus valores óptimos. El valor medio, salvo en una instancia (kr124p) no sobrepasa el 3.2%. Los tiempos obtenidos muestran que la media del tiempo máximo no excede el minuto, pudiendo ser menor pues en ocasiones se estaban corriendo otras aplicaciones al mismo tiempo.
- Solución del problema
Las conclusiones para este trabajo son las siguientes: El estudio bibliográfico realizado respecto a la actualidad de métodos y algoritmos e instancias del PVA, señaló que básicamente los primeros grandes estudios realizados son de [7], el cual fue punto de partida para la implementación de la hiperheurística propuesta del PVA. No existe en la bibliografía actual, según la revisión consultada, estudios realizados de hiperheurísticas propuestas para el PVA, puesto que no se ha demostrado a partir de los diseños de experimento realizados que no existe un algoritmo para el PVA que claramente supere a otros para todas las instancias del mismo, es útil pensar en un método que guíe al usuario inexperto en el tema. A partir de los algoritmos existentes fueron construidos nuevos híbridos y aplicadas nuevas variantes de búsqueda local.
Los resultados obtenidos en el diseño de experimento realizado sobre la base de un subconjunto de las mismas instancias descritas en la literatura por [33], demuestra que la hiperheurística da resultados aceptables teniendo en cuenta calidad de la soluciones y en los tiempos de ejecución.
La aplicación realizada es fácilmente ejecutable en una PC personal, para ser utilizados por los usuarios, por ejemplo, en la Industria Textil para el teñido de telas (sin necesitar el uso un software profesional que lo resuelva, los cuales son en algunos caso costoso).
A continuación se proponen las siguientes recomendaciones a realizar en trabajos futuros de esta temática: Implementar el método de Held-Karp (HK) [17 y 18], el cual da una cuota HK que está más cerca al costo óptimo (la cuota AP≤HK), para instancias del PVA. Implementar también generadores de instancias representativas para el PVA, para mejorar el diseño de experimento realizado, puesto que no solo incide el tamaño de la instancia sino las características de la matriz, tal es así que el diseño de experimento realizado a las instancias más grande (rgb323, rgb358, rgb403 y rgb443), donde se obtuvo el óptimo fácilmente, las matrices contienen un conjunto de elementos igual a cero, no así en el resto de los casos.
Hacer un estudio más profundo de la implementación de esta hiperheurística, con sus heurísticas combinadas para el PMB. Implementar una minería de heurísticas a los problemas abordados, para realizar sobre esto una hiperheurística y buscar un buen generador de números aleatorios, ya que la eficiencia de estos algoritmos depende en cierta medida del generador utilizado.
- Conclusiones
- Referencias
- Aho Alfred V., Hopcroft John E. and Ullman Jeffrey D.: "Data Structures and Algorithms", Addison-Wesley, Massachusetts, 1983.
- Aho Alfred V., Hopcroft John E. and Ullman Jeffrey D.: "The Design and Analysis of Computer Algorithms", Addison–Wesley Series in Computer Science and Information Processing, 1974.
- Ahuja Ravindra K., Özlem Ergun, James B. Orlin and Abraham P. Punnen, "Estudio de técnicas de búsqueda por vecindad a muy gran escala", Departamento de ingeniería industrial y de sistemas Universidad de Florida Gainesville, FL 32611, USA, , 11 de octubre de 2000.
- Burke Edmund K., Cowling Peter I. and Ralf Keuthen, "Effective Local and Guided Variable Neighborhood Search Methods for the Asymmetric Traveling Salesman Problem", Automated Scheduling, Optimization, and Planning Group (ASAP), School of Computer Science & IT, University of Nottingham, Jubilee Campus, Nottingham, NG8 1BB, UK.
- Burke, E.K., Cowling, P.I., Keuthen, R.: "Embedded local search and variable neighborhood search heuristics applied to the traveling salesman problem", University of Nottingham, Technical Report, 2000.
- Christofides N., A. Mingozzi, P. Toth and C. Sandi: "Combinatorial optimization", Wiley, Chichester, pp.: 131-149, 1989.
- Cirasella Jill, Jonson David S., McGeoch Lyle A. and Zhang Weixiong: "The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Test", ALENEX 2001 Proceedings, Springer Lecture Notes in Computer Science 2153, pp.: 32-59.
- Cormen, Leiserson, Rivest: "Introducción a la Algorítmica", The MIT Press-Mc Graw Hill, 1990, pp.:199 – 215.
- Cowling P., Kendall G. and Soubeiga E., "A Hyperheuristic Approach to Scheduling a Sales Summit", In E. Burke and W. Erben (Eds.) PATAT 2000, Springer Lecture Notes in Computer Science no. 2079, 2001, pp.: 176–190.
- Dowsland Kathryn A., Soubeiga Eric and Burke Edmund: "Solving a shipper rationalisation problem with a simulated Annealing based hyperheuristic", The University of Nottingham, The School of Computer Science and IT, UK, .
- Fazle Baki: "Solvable cases of the traveling salesman problem", MBA thesis, Faculty of Administration, University of New Brunswick, NB, Canada, 1995.
- Feo, T.A., Resende, M.G.C.: "Greedy Randomized Adaptive Search Procedures", Journal of Global Optimization, 6, 1995, pp.: 109–133.
- Folk, M y Zoellick, B.: "Estructura de Archivos", Addison–Wesley, Reading, MA, 1992, pp.: 420 – 423.
- Garey Michael and Johnson David: "Computers and intractability: A Guide to the Theory NP–Completeness", W. H. Freeman and Co., San Francisco, California, 1979.
- Glover Fred: "Finding a best traveling salesman 4–Opt move in the same time as a best 2–Opt move", Journal of Heuristics, 2, 1996, pp.: 169–179.
- Goldberg, D.: "Genetic Algorithms in Search, Optimization & Machine Learning", Addison–Wesley, 1989.
- Held M. and Karp R. M.: "The Traveling Salesman Problem and minimum spanning trees", Operation Research 18, 1970, pp.: 1138-1162.
- Held M. and Karp R. M.: "The Traveling Salesman Problem and minimum spanning trees: Part II", Math. Prog. 1, 1971, pp.: 6-25.
- Johnson D. S. and McGeoch L. A.: "The travelling salesman problem: a case study", In E. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, pp.: 215–310. John Wiley & Sons, Chichester, 1997.
- Kanellakis, P.C., Papadimitriou, C.H.: "Local search for the asymmetric traveling salesman problem", Operation. Research. 28, 1980, pp.: 1086–1099.
- Khalimsky E.: "Topological structures in computer science", J. Appl. Math. Simulation, 1, 1987, pp.: 25–40.
- Kolohan, F., Liang, M.: "A tabu search approach to optimization of drilling operations", Comp. in Eng. 31, 1996, pp.: 371–374.
- Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. and Shmoys D.B.: "The traveling Salesman Problem: A guide tour of combinatorial optimization", Wiley, Chichester, 1985.
- Lipschults, Seymour: "Estructura de Datos teoría y problemas", Schaum–McGraw–Hill, 1988, pp.: 315 – 357.
- Maldonado F., Ciurlizza A., Radillo R. and Ponce de León E.: "Optimization of the color sequence in the dyeing process: industrial applications", Journal of the Society of Dyers and Colorists, Vol. 116, pp. 359-362, November 2000.
- Maldonado F., Radillo R., Baldoquín G. and Ruiz A.: "Optimization of the color sequence in the dyeing process: washing the equipments", en revision by Journal of the Society of Dyers and Colorists, October 2003.
- Mañas José A., "Análisis de Algoritmos: Complejidad", , Noviembre, 1997.
- Marcos Moreno J. and Moreno José A.: "Heurísticas en Optimización", Dirección General Universidades, Gobierno de Canarias, 1999.
- Melian Belen, Moreno Perez Jose A. and Moreno Vega J. Marcos, "Metaheurísticas: una visión global", DEIOC, Universidad de La Laguna, 2003, pp.: 7–28.
- Morales L., Maldonado F., Radillo R. and Ciurlizza A.: "Optimization of the color sequence in the process of fabric dyeing", Journal of the Society of Dyers and Colorists, Vol. 112, pp.: 361-363, December 1996.
- Nemhauser, G. L. and Rinooy Kan: "Handbooks in Operations Research and Management Science", Volume 1, Elsevier Science Publisher B. V., 1989.
- Papadimitriou, C., Steiglitz, K.: "Combinatorial optimization: Algorithms and complexity", Prentice Hall, 1982.
- Reinelt, G.: "TSPLIB – A traveling salesman problem library", ORSA–Journal of the Computing 3, 1991, pp.: 376–384, http://www.research.att.com/~dsj/chtsp/.
- Trujillo José M. y Díaz José A.: "Métodos Económicos-Matemáticos", Tomo I, Parte 2, Ediciones ENSPES, La Habana, 1983.
- Verdegay José Luis: "Algoritmos heurísticos", http://decsai.ugr.es/~verdegay/kef5_5.htm, 03/03/05.
María Gulnara Baldoquín de la Peña
José Carlos Díaz Díaz
Departamento de Matemática General, Facultad de Ingeniería Industrial, Instituto Superior Politécnico José Antonio Echevarria, Cuba.
,
Corresponde al autor. Trabajo de tesis de grado optando por el titulo de Ingeniero Informático
| Página siguiente |