Sacrificio cortoplacista adaptativo 2opt (SCA_2opt): Una heurística inspirada en el pensamiento sistémico
Sacrifice short-term adaptive 2-opt (SCA_2opt): A heuristic inspired by systems thinking
Rave, Jorge Iván P.; Álvarez, Patricia Jaramillo
http://dx.doi.org/10.1590/S0103-65132013005000033
Production, vol.24, n1, p.26-40, 2014
Resumen
Se detalla el origen de dos noveles heurísticas para el TSP simétrico, inspiradas en el pensamiento sistémico: Sacrificio Cortoplacista Adaptativo 2-opt (SCA_2opt) y SCA_2_opt_r. Estas surgen del análisis sistémico de la regla de decisión Vecino más cercano, identificándosele el arquetipo "Soluciones contraproducentes". El SCA se basa en que el agente viajero renuncie en un momento dado a una ciudad inmediatamente cercana, y se traslade hacia la segunda ciudad más cercana disponible. A partir de ello, se continúa con la regla del vecino más cercano. Cada que se realiza el SCA (búsqueda global) se efectúa una búsqueda local 2_opt. Considerando el binomio eficacia y eficiencia, las dos heurísticas se muestran prometedoras en comparación multicriterio contra 19 metaheurísticas. Se evidencia que el pensamiento sistémico es un campo de inspiración viable para el desarrollo de métodos de optimización combinatoria; se plasman preguntas emergentes para desarrollos futuros, que permitan continuar integrando elementos de la optimización clásica con el pensamiento sistémico; áreas tradicionalmente vistas como antagónicas, pero cuyo diálogo se muestra favorable en este artículo.
Palabras clave
Sacrificio cortoplacista adaptativo. TSP. Metaheurísticas. Análisis multicriterio. Pensamiento sistémico
Abstract
Outlining two novice heuristics for the symmetric TSP, inspired systemic thinking: Sacrifice short-term adaptive 2-opt (SCA2opt) and SCA_2opt_r. These arise from the systemic analysis of the rule of decision, nearest neighbour, identifying the archetype "Counterproductive solutions". SCA relies on that agent traveler, renounces at any given time immediately to a nearby city, and moves towards the second nearest available city. From there, it continues with the nearest neighbour rule. Each is the SCA (global search) operates a local search 2opt. Where as the binomial effectiveness and efficiency, the two new heuristics are shown promising in comparison multicriteria against 19 metaheuristics. It is evident that systemic thinking is a field of inspiration viable for the development of combinatorial optimization methods; emerging questions for future developments are expressed, enabling to continue to integrate elements of the classical optimization with the systemic thought; areas traditionally seen as antagonistic, but whose dialogue is favourable in this article.
Keywords
Sacrifice short-term adaptive. TSP. Metaheuristics. Multicriteria analysis. Systems thinking
References
BAHILL, T.; GISSING, B. Re-evaluating systems engineering concepts using systems thinking. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, v. 28, n. 4, p. 516-527, 1998. http://dx.doi.org/10.1109/5326.725338
BERBIELA, J. La inteligencia artificial aplicada a la gestión de la tesorería. Revista Real Academia de Ciencias Exactas, Físicas y Naturales, v. 92, n. 4, p. 435-439, 1998. Monográfico: Problemas complejos de decisión.
BENTLEY, J. Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing, v. 4, n. 4, p. 387-411, 1992. http://dx.doi.org/10.1287/ijoc.4.4.387
CARTER, A.; RAGSDALE, C. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, v. 175, n. 1, p. 246-257, 2006. http://dx.doi.org/10.1016/j.ejor.2005.04.027
DANTZIG, G.; FULKERSON, R.; JOHNSON, S. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, v. 2, n. 4, p. 393-410, 1954.
DISTEFANO, M.; HAARTH, R.; IRIARTE, E. Modelación de sistemas tecnológicos en la formación básica de los ingenieros. In: CONGRESO TECNOLOGÍAS APLICADAS A LA ENSEÑANZA DE LA. ELECTRÓNICA - TAEE, 2006, Madrid. Actas... Universidad Nacional de Cuyo, 2006.
DORIGO, M.; GAMBARDELLA, M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In: INTERNATIONAL CONFERENCE ON MACHINE LEARNING, 1995, Tahoe City. Proceedings... Tahoe City, 1995. p. 252-260.
DORIGO, M.; GAMBARDELLA, M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, v. 1, n. 1, p. 53-66, 1997. http://dx.doi.org/10.1109/4235.585892
DOS SANTOS, J. P. Q. Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço. 73 f. Dissertação (Mestrado em Engenharia Elétrica)-Universidade Federal do Rio Grande do Norte, Natal, 2009.
FLOOD, M. The Traveling Salesman Problem. Operations Research, v. 4, p. 61-75, 1956. http://dx.doi.org/10.1287/opre.4.1.61
GOLDEN, B. et al. Approximate traveling salesman algorithms. Operations research, v. 28, p. 694-711, 1980. http://dx.doi.org/10.1287/opre.28.3.694
GÓMEZ, M.; LEÓN, F. Planeación de Rutas de Distribución utilizando el Algoritmo Heurístico 2-Optimal: Implementación Computacional. INVURNUS, v. 6, n. 1, p. 15-20, 2011.
HANSEN, P.; MLADENOVIC, N. Variable neighbourhood search. In: GLOVER, F.; KOCHENBERGER, G. A. (Eds.). Handbook of Metaheuristics. Kluwer, 2003.
JEONG, S.; KIM, K.; LEE, Y. The efficient search method of simulated annealing using fuzzy logic controller. Expert Systems with Applications, v. 36, p. 7099-7103, 2009. http://dx.doi.org/10.1016/j.eswa.2008.08.020
JÜNGER, M.; REINELT, G.; RINALDI, G. The Traveling Salesman Problem. In: BALL, M. O. et al. (Eds.). Handbook in Operations Research and Management Science. North-Holland, 1995. v. 7, p. 225-330.
KARABOGA, D.; GORKEMLI, B. A combinatorial Artificial Bee Colony algorithm for traveling salesman problem. In: INTERNATIONAL SYMPOSIUM ON INNOVATIONS IN INTELLIGENT SYSTEMS AND APPLICATIONS - INISTA, 2011, Istanbul. Proceedings... Istanbul, 2011. p. 50-53.
LETELIER, M. et al. Competencias sustentables para el desempeño profesional en ingeniería. Revista Facultad de Ingeniería - Universidad de Tarapacá, v. 13, n. 2, p. 91-96, 2005.
LIU, Y. A hybrid scatter search for the probabilistic traveling salesman problem. Computers and Operations Research, v. 34, n. 10, p. 2949-2963, 2007. http://dx.doi.org/10.1016/j.cor.2005.11.008
LUO, X.; YANG, Y.; LI, X. Solving TSP with Shuffled Frog-Leaping Algorithm. In: INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS DESIGN AND APPLICATIONS, 2008, Kaohsiung City. Proceedings... IEEE, 2008. p. 228-232.
MARTI, R. Procedimientos metaheurísticos en optimización combinatoria. Matemátiques. v. 1, n. 1, p. 1-60, 2003.
MORALES, R. et al. Paralelización de un Algoritmo de Búsqueda Local Iterada para el Problema del Agente Viajero. In: CONGRESO INTERNACIONAL DE CÓMPUTO EN OPTIMIZACIÓN Y SOFTWARE - CICOS, 2011, Cuernavaca. Memorias... UAEM México, 2011.
NGUYEN, H. et al. Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, v. 37, n. 1, p. 92-99, 2007. http://dx.doi.org/10.1109/TSMCB.2006.880136
PÉREZ, J. Heurística inspirada en el análisis sistémico del "Vecino más cercano", para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio. 2011. 130 f. Tesis (Magíster en ingeniería de sistemas)-Facultad de Minas, Universidad Nacional de Colombia, Medellín, 2011a.
PÉREZ, J. Modelación lineal en ingeniería industrial: Una mirada sistémica. Medellín: Editorial Universidad de Antioquia, 2011b. (Colección Ciencia y Tecnología).
REINELT, G. TSPLIB. A traveling salesman problem library. ORSA Journal on Computing, v. 3, n. 4, p. 376-384, 1991. http://dx.doi.org/10.1287/ijoc.3.4.376
SALLABI, O.; EL-HADDAD, Y. An Improved Genetic Algorithm to Solve the Traveling Salesman Problem. World Academy of Science, Engineering and Technology, n. 52, p. 471-474, 2009.
SENGE, P. La Quinta Disciplina: El arte y la práctica de la organización abierta al aprendizaje. Buenos Aires: Ediciones Granica S.A., 1998. 490 p.
TEODOROVIC, D. Swarm intelligence systems for transportation engineering: Principles and applications. Transportation Research Part C, n. 16, p. 651-667, 2008. http://dx.doi.org/10.1016/j.trc.2008.03.002
VELAYUDHAN, P. et al. Empirical Analysis of Randomness in Ant Colony Optimization Algorithms Applied to the Traveling Salesman Problem. International Journal of Information Systems for Logistics and Management, v. 2, n. 2, p. 69-76, 2007.
WANG, J.; WANG, W. Research on ACO with Multiple Nests' Cooperation for Narrow TSP. In: INTERNATIONAL CONFERENCE ON BIO-INSPIRED COMPUTING: THEORIES AND APPLICATIONS, 3., 2008, Adelaide. Proceedings... 2008. IEEE, 2008. p. 143-147.
WHITLEY, D.; HAINS, D.; HOWE, A. A Hybrid Genetic Algorithm for the Traveling Salesman Problem Using Generalized Partition Crossover. In: PARALLEL PROBLEM SOLVING FROM NATURE - PPSN, 11., 2010, Poland. Lecture Notes in Computer Science, v. 6238, p. 566-575, 2010.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email