The Multi-Funnel Structure of TSP Fitness Landscapes: A Visual Exploration

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9554
• 期：1
• 页码：1-13
• 全文大小：1,029 KB
• 参考文献：1.Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Concorde TSP solver (2003). http://​www.​math.​uwaterloo.​ca/​tsp/​concorde.​html
  2.Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15, 82–92 (2003)MathSciNet CrossRef MATH
  3.Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2007)MATH
  4.Boese, K.D., Kahng, A.B., Muddu, S.: A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. 16, 101–113 (1994)MathSciNet CrossRef MATH
  5.Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex System, 1695 (2006)
  6.Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exper. 21(11), 1129–1164 (1991)CrossRef
  7.Hains, D.R., Whitley, L.D., Howe, A.E.: Revisiting the big valley search space structure in the TSP. J. Oper. Res. Soc. 62(2), 305–312 (2011)CrossRef
  8.Helsgaun, K.: An effective implementation of the LinKernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106–130 (2000)MathSciNet CrossRef MATH
  9.Iclanzan, D., Daolio, F., Tomassini, M.: Data-driven local optima network characterization of QAPLIB instances. In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, GECCO 2014, pp. 453–460. ACM, New York (2014)
  10.Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498–516 (1973)MathSciNet CrossRef MATH
  11.Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the traveling salesman problem. Complex Syst. 5, 299–326 (1991)MathSciNet MATH
  12.Möbius, A., Freisleben, B., Merz, P., Schreiber, M.: Combinatorial optimization by iterative partial transcription. Phys. Rev. E 59(4), 4667–4674 (1999)CrossRef
  13.Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)CrossRef MATH
  14.Ochoa, G., Chicano, F., Tinos, R., Whitley, D.: Tunnelling crossover networks. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 449–456. ACM (2015)
  15.Ochoa, G., Tomassini, M., Verel, S., Darabos, C.: A study of NK landscapes’ basins and local optima networks. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pp. 555–562. ACM (2008)
  16.Ochoa, G., Verel, S., Daolio, F., Tomassini, M.: Local optima networks: a new model of combinatorial fitness landscapes. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes. ECC, vol. 6, pp. 233–262. Springer, Heidelberg (2014)CrossRef
  17.Reinelt, G.: TSPLIB-a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991). http://​www.​iwr.​uni-heidelberg.​de/​groups/​comopt/​software/​TSPLIB95/​ MathSciNet CrossRef MATH
  18.Verel, S., Ochoa, G., Tomassini, M.: Local optima networks of NK landscapes with neutrality. IEEE Trans. Evol. Comput. 15(6), 783–797 (2011)CrossRef
  19.Wales, D.J., Miller, M.A., Walsh, T.R.: Archetypal energy landscapes. Nature 394, 758–760 (1998)CrossRef
  20.Whitley, D., Hains, D., Howe, A.: Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings Genetic and Evolutionary Computation Conference, GECCO 2009, pp. 915–922. ACM, New York (2009)
  21.Whitley, D., Hains, D., Howe, A.: A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol. 6238, pp. 566–575. Springer, Heidelberg (2010)
  
• 作者单位：Gabriela Ochoa (18)
  Nadarajen Veerapen (18)
  Darrell Whitley (19)
  Edmund K. Burke (18)
  
  18. Computing Science and Mathematics, University of Stirling, Stirling, Scotland, UK
  19. Department of Computer Science, Colorado State University, Fort Collins, USA
  
• 丛书名：Artificial Evolution
• ISBN：978-3-319-31471-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We use the Local Optima Network model to study the structure of symmetric TSP fitness landscapes. The ‘big-valley’ hypothesis holds that for TSP and other combinatorial problems, local optima are not randomly distributed, instead they tend to be clustered around the global optimum. However, a recent study has observed that, for solutions close in evaluation to the global optimum, this structure breaks down into multiple valleys, forming what has been called ‘multiple funnels’. The multiple funnel concept implies that local optima are organised into clusters, so that a particular local optimum largely belongs to a particular funnel. Our study is the first to extract and visualise local optima networks for TSP and is based on a sampling methodology relying on the Chained Lin-Kernighan algorithm. We confirm the existence of multiple funnels on two selected TSP instances, finding additional funnels in a previously studied instance. Our results suggests that transitions among funnels are possible using operators such as ‘double-bridge’. However, for consistently escaping sub-optimal funnels, more robust escaping mechanisms are required.