Abstract
Fitness landscape analysis has gained quite some attention in understanding the behaviour of metaheuristics. Swarm intelligence is a type of metaheuristics that has grown considerably on the algorithmic side over the past decade. Nevertheless, only little attention has been paid to understanding the behaviour of algorithms on different fitness landscapes, especially in combinatorial optimization. Our aim in this paper is to re-motivate the importance of this issue. Moreover, by considering particle swarm optimization (PSO), we present a first investigation on its adaptation to three variants of the travelling salesman problem and how its performance is correlated with the ruggedness of the problem instances. The results show that PSO performance deteriorates with the increase in the number of cities and the ruggedness of the instances.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aiex, R.M., Resende, M.G., Ribeiro, C.C.: TTT plots: a Perl program to create time-to-target plots. Optim. Lett. 1(4), 355–366 (2007). https://doi.org/10.1007/s00291-020-00604-x
de Armas, J., Lalla-Ruiz, E., Tilahun, S.L., Voß, S.: Similarity in metaheuristics: a gentle step towards a comparison methodology. Natural Comput. 21, 265–287 (2021). https://doi.org/10.1007/s11047-020-09837-9
Bernardino, R., Paias, A.: Heuristic approaches for the family traveling salesman problem. Int. Trans. Oper. Res. 28(1), 262–295 (2021). https://doi.org/10.1111/itor.12771
Boese, K.D., Kahng, A.B., Muddu, S.: A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. 16(2), 101–113 (1994). https://doi.org/10.1016/0167-6377(94)90065-5
Camacho Villalón, C.L., Stützle, T., Dorigo, M.: Grey wolf, firefly and bat algorithms: three widespread algorithms that do not contain any novelty. In: Dorigo, M., et al. (eds.) ANTS 2020. LNCS, vol. 12421, pp. 121–133. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60376-2_10
Cárdenas-Montes, M.: Creating hard-to-solve instances of travelling salesman problem. Appl. Soft Comput. 71, 268–276 (2018). https://doi.org/10.1016/j.asoc.2018.07.010
Caserta, M., Voß, S.: Metaheuristics: intelligent problem solving. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics. Annals of Information Systems, vol. 10, pp. 1–38. Springer, Boston (2009). https://doi.org/10.1007/978-1-4419-1306-7_1
Chen, W.N., Zhang, J., Chung, H., Zhong, W.L., Wu, W.G., Shi, Y.: A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Trans. Evol. Comput. 14(2), 278–300 (2010). https://doi.org/10.1109/tevc.2009.2030331
Daniel, W.W.: Applied Nonparametric Statistics. PWS-KENT Pub, Boston (1990)
Dokeroglu, T., Sevinc, E., Kucukyilmaz, T., Cosar, A.: A survey on new generation metaheuristic algorithms. Comput. Industr. Eng. 137, 106040 (2019). https://doi.org/10.1016/j.cie.2019.106040
Engelbrecht, A.P., Bosman, P., Malan, K.M.: The influence of fitness landscape characteristics on particle swarm optimisers. Nat. Comput. (2021). https://doi.org/10.1007/s11047-020-09835-x
Glover, F.: A template for scatter search and path relinking. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 1–51. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0026589
Glover, F., Sörensen, K.: Metaheuristics. Scholarpedia 10(4), 6532 (2015). https://doi.org/10.4249/scholarpedia.6532
Goldbarg, E.F.G., Goldbarg, M.C., de Souza, G.R.: Particle swarm optimization algorithm for the traveling salesman problem. In: Greco, F. (ed.) Traveling Salesman Problem, pp. 75–96. InTech (2008). https://doi.org/10.5772/5580
Goldbarg, E.F.G., de Souza, G.R., Goldbarg, M.C.: Particle swarm for the traveling salesman problem. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2006. LNCS, vol. 3906, pp. 99–110. Springer, Heidelberg (2006). https://doi.org/10.1007/11730095_9
Greistorfer, P., Voß, S.: Controlled pool maintenance for metaheuristics. In: Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization via Memory and Evolution, pp. 387–424. Kluwer Academic Publishers (2005). https://doi.org/10.1007%2F0-387-23667-8_18
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). https://doi.org/10.1057/jors.2010.116
Huang, Y., Li, W., Tian, F., Meng, X.: A fitness landscape ruggedness multiobjective differential evolution algorithm with a reinforcement learning strategy. Appl. Soft Comput. 96, 106693 (2020). https://doi.org/10.1016/j.asoc.2020.106693
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN 1995 - International Conference on Neural Networks. IEEE (1995). https://doi.org/10.1109/icnn.1995.488968
Kennedy, J., Eberhart, R.: A discrete binary version of the particle swarm algorithm. In: IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation. IEEE (1997). https://doi.org/10.1109/icsmc.1997.637339
Liefooghe, A., Daolio, F., Verel, S., Derbel, B., Aguirre, H., Tanaka, K.: Landscape-aware performance prediction for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 24(6), 1063–1077 (2019)
Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982). https://doi.org/10.1109%2Ftit.1982.1056489
Lu, Y., Hao, J.K., Wu, Q.: Solving the clustered traveling salesman problem via TSP methods. arXiv preprint arXiv:2007.05254 (2020). https://doi.org/10.48550/arXiv.2007.05254
Malan, K.M., Engelbrecht, A.P.: Characterising the searchability of continuous optimisation problems for PSO. Swarm Intell. 8(4), 275–302 (2014). https://doi.org/10.1007/s11721-014-0099-x
Malan, K.M., Engelbrecht, A.P.: Quantifying ruggedness of continuous landscapes using entropy. In: 2009 IEEE Congress on Evolutionary Computation. IEEE (2009). https://doi.org/10.1109/cec.2009.4983112
Malan, K.M., Engelbrecht, A.P.: Ruggedness, funnels and gradients in fitness landscapes and the effect on PSO performance. In: 2013 IEEE Congress on Evolutionary Computation. IEEE (2013). https://doi.org/10.1109/cec.2013.6557671
Malan, K.M., Engelbrecht, A.P.: A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf. Sci. 241, 148–163 (2013). https://doi.org/10.1016/j.ins.2013.04.015
Malan, K.M., Engelbrecht, A.P.: Fitness landscape analysis for metaheuristic performance prediction. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes. ECC, vol. 6, pp. 103–132. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-41888-4_4
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4), 337–352 (2000). https://doi.org/10.1109/4235.887234
Merz, P., Freisleben, B.: Memetic algorithms for the traveling salesman problem. Complex Syst. 13(4), 297–346 (2001)
Ochoa, G., Veerapen, N.: Deconstructing the big valley search space hypothesis. In: Chicano, F., Hu, B., García-Sánchez, P. (eds.) EvoCOP 2016. LNCS, vol. 9595, pp. 58–73. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30698-8_5
Ochoa, G., Veerapen, N.: Mapping the global structure of TSP fitness landscapes. J. Heurist. 24(3), 265–294 (2017). https://doi.org/10.1007/s10732-017-9334-0
Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Suárez Araujo, C.P. (eds.) Recent Advances in Intelligent Engineering Systems. SCI, vol. 378, pp. 161–191. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23229-9_8
Poursoltan, S., Neumann, F.: Ruggedness quantifying for constrained continuous fitness landscapes. In: Datta, R., Deb, K. (eds.) Evolutionary Constrained Optimization. ISFS, pp. 29–50. Springer, New Delhi (2015). https://doi.org/10.1007/978-81-322-2184-5_2
PyPI: mlrose, 13 March 2022. https://pypi.org/project/mlrose/
Reeves, C.R.: Landscapes, operators and heuristic search. Ann. Oper. Res. 86, 473–490 (1999). https://doi.org/10.1007/bf01165154
Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991). https://doi.org/10.1287/ijoc.3.4.376
Richter, H.: Fitness landscapes: from evolutionary biology to evolutionary computation. In: Richter, H., Engelbrecht, A. (eds.) Recent Advances in the Theory and Application of Fitness Landscapes. Emergence, Complexity and Computation, vol. 6, pp. 3–31. Springer, Heidelberg (2014). https://doi.org/10.1007%2F978-3-642-41888-4_1
Shi, Y., Eberhart, R.: A modified particle swarm optimizer. In: 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360). IEEE (1998). https://doi.org/10.1109/icec.1998.699146
Sun, Y., Ernst, A., Li, X., Weiner, J.: Generalization of machine learning for problem reduction: a case study on travelling salesman problems. OR Spectrum 43(3), 607–633 (2020). https://doi.org/10.1007/s00291-020-00604-x
Sutton, A.M., Whitley, D., Lunacek, M., Howe, A.: PSO and multi-funnel landscapes: how cooperation might limit exploration. In: Keijzer, M. (ed.) Genetic and Evolutionary Computation Conference, pp. 75–82. Association for Computing Machinery, New York (2006). https://doi.org/10.1145/1143997.1144008
Sörensen, K.: Metaheuristics-the metaphor exposed. Int. Trans. Oper. Res. 22(1), 3–18 (2015). https://doi.org/10.1111/itor.12001
Varadarajan, S., Whitley, D., Ochoa, G.: Why many travelling salesman problem instances are easier than you think. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 254–262. ACM (2020). https://doi.org/10.1145/3377930.3390145
Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. In: Ghosh, A., Tsutsui, S. (eds.) Advances in Evolutionary Computing: Theory and Applications, pp. 3–44. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-642-18965-4_1
Vaz, A.I., Vicente, L.N.: PSwarm: a hybrid solver for linearly constrained global derivative-free optimization. Optim. Methods Softw. 24(4–5), 669–685 (2009). https://doi.org/10.1080/10556780902909948
Voß, S.: Tabu search: applications and prospects. In: Du, D., Pardalos, P.M. (eds.) Network Optimization Problems, vol. 2, pp. 333–353. World Scientific, Singapore (1993). https://doi.org/10.1142/9789812798190_0017
Voss, S.: Book review: Marco Dorigo and Thomas Stützle: Ant colony optimization. Math. Methods Oper. Res. 63(1), 191–192 (2006). https://doi.org/10.1007/s00186-005-0050-4
Wang, K.P., Huang, L., Zhou, C.G., Pang, W.: Particle swarm optimization for traveling salesman problem. In: Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693), pp. 1583–1585. IEEE (2003). https://doi.org/10.1109/icmlc.2003.1259748
Watson, J.P.: Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. Ph.D. thesis, Colorado State University (2003)
Watson, J.P.: An introduction to fitness landscape analysis and cost models for local search. In: Handbook of Metaheuristics, pp. 599–623. Springer, US (2010). https://doi.org/10.1007/978-1-4419-1665-5_20
Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63(5), 325–336 (1990). https://doi.org/10.1007/bf00202749
Wright, S.: The roles of mutation, inbreeding, crossbreeding and selection in evolution. In: Proceedings of the Sixth International Congress of Genetics, vol. 1, pp. 356–366 (1932)
Xin, B., Chen, J., Pan, F.: Problem difficulty analysis for particle swarm optimization. In: Proceedings of the First ACM/SIGEVO Summit on Genetic and Evolutionary Computation - GEC 2009, pp. 623–630. ACM Press (2009). https://doi.org/10.1145/1543834.1543919
Yang, X.-S. (ed.): Recent Advances in Swarm Intelligence and Evolutionary Computation. SCI, vol. 585. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-13826-8
Acknowledgement
Malek Sarhani was supported by the Alexander von Humboldt Foundation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Nourmohammadzadeh, A., Sarhani, M., Voß, S. (2022). Fitness Landscape Ruggedness Impact on PSO in Dealing with Three Variants of the Travelling Salesman Problem. In: Simos, D.E., Rasskazova, V.A., Archetti, F., Kotsireas, I.S., Pardalos, P.M. (eds) Learning and Intelligent Optimization. LION 2022. Lecture Notes in Computer Science, vol 13621. Springer, Cham. https://doi.org/10.1007/978-3-031-24866-5_31
Download citation
DOI: https://doi.org/10.1007/978-3-031-24866-5_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24865-8
Online ISBN: 978-3-031-24866-5
eBook Packages: Computer ScienceComputer Science (R0)