×

A sensitive metaheuristic for solving a large optimization problem. (English) Zbl 1132.68709

Geffert, Viliam (ed.) et al., SOFSEM 2008: Theory and practice of computer science. 34th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 19–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-77565-2/pbk). Lecture Notes in Computer Science 4910, 551-559 (2008).
Summary: A metaheuristic for solving complex problems is proposed. The introduced Sensitive Robot Metaheuristic (SRM) is based on the Ant Colony System optimization technique. The new model relies on the reaction of virtual sensitive robots to different stigmergic variables. Each robot is endowed with a particular stigmergic sensitivity level ensuring a good balance between search diversification and intensification. Comparative tests are performed on large-scale NP-hard robotic travel problems. These tests illustrate the effectiveness and robustness of the proposed metaheuristic.
For the entire collection see [Zbl 1131.68008].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bixby, B., Reinelt, G.: (1995), http://nhse.cs.rice.edu/softlib/catalog/tsplib.html
[2] Bonabeau, E.; Dorigo, M.; Tehraulaz, G., Swarm intelligence from natural to artificial systems (1999), Oxford, UK: Oxford University Press, Oxford, UK · Zbl 1003.68123
[3] Dorigo, M.; Gambardella, L. M., Ant Colony System: A cooperative learning approach to the Traveling Salesman Problem, IEEE Trans. Evol. Comp., 1, 53-66 (1997) · doi:10.1109/4235.585892
[4] Fischetti, M.; Gonzales, J. J.S.; Toth, P., A Branch-and-Cut Algorithm for the Symmetric Generalized Travelling Salesman Problem, Oper. Res., 45, 3, 378-394 (1997) · Zbl 0893.90164 · doi:10.1287/opre.45.3.378
[5] Golden, B. L.; Assad, A. A., A decision-theoretic framework for comparing heuristics, European J. of Oper. Res., 18, 167-171 (1984) · Zbl 0546.90069 · doi:10.1016/0377-2217(84)90182-6
[6] Grassé, P.-P., La Reconstruction du Nid et Les Coordinations Interindividuelles Chez Bellicositermes Natalensis et Cubitermes sp. La Thorie de la Stigmergie: Essai dinterpretation du Comportement des Termites Constructeurs, Insect Soc., 6, 41-80 (1959) · doi:10.1007/BF02223791
[7] Helsgaun, K., An effective implementation of the lin-kernighan TSP heuristic, European Journal of Operations Research, 126, 106-130 (2000) · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2
[8] Johnson, D. S.; McGeoch, L. A., Local Search in Combinatorial Optimization, chapter The Traveling Salesman Problem: A Case Study in Local Optimization, 215-310 (1997), New York: John Wiley & Sons, New York · Zbl 0947.90612
[9] Johnson, D. S.; McGeoch, L. A., The Traveling Salesman Problem and its Variations, chapter Experimental Analysis of Heuristics for the STSP, 369-443 (2002), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1113.90356
[10] Pintea, C-M., Pop, C.P., Chira, C.: The Generalized Traveling Salesman Problem solved with Ant Algorithms. J.UCS (in press, 2007)
[11] Renaud, J.; Boctor, F. F., An efficient composite heuristic for the Symmetric Generalized Traveling Salesman Problem, Euro. J. Oper. Res., 108, 3, 571-584 (1998) · Zbl 0944.90068 · doi:10.1016/S0377-2217(97)00142-2
[12] Snyder, L.V., Daskin, M.S.: A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem. INFORMS, San Antonio, TX (2000) · Zbl 1116.90091
[13] Theraulaz, G.; Bonabeau, E., A brief history of stigmergy, Artificial Life, 5, 2, 97-116 (1999) · doi:10.1162/106454699568700
[14] White, T.: Expert Assessment of Stigmergy: A Report for the Department of National Defence, http://www.scs.carleton.ca/arpwhite/stigmergy-report.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.