Abstract
Recently, a number of studies have attempted to characterize the interaction between objectives and decision variables in multiobjective problems. In this paper, we continue this line of research by focusing specifically on quantifying observable differences in the ease of optimizing extreme solutions (i.e. solutions on the limits of the Pareto front). We propose an evolutionary path length correlation (EPLC) measurement in the decision variable space that is computed by tracing the evolutionary history of solutions on the Pareto front. We draw on the length scale measure and extend the well-known fitness distance correlation to multiobjective optimization problems. Here, the overarching goal is to investigate the emergent dynamics of specific problem–algorithm combinations, rather than the characterization of the search landscape per se. We evaluate the efficacy of the EPLC using benchmark continuous multiobjective problems and combinatorial problems with controllable objective interactions and known Pareto optima. In some problems, observable differences in the convergence to extreme solutions in each objective can be captured using the EPLC. Our results go some way towards furthering our understanding of how specific algorithms traverse the landscape, given interactions between both decision variables and objectives.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aguirre, H.E., Tanaka, K.: Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur. J. Oper. Res. 181(3), 1670–1690 (2007)
Bradstreet, L., Barone, L., While, L., Huband, S., Hingston, P.: Use of the WFG toolkit and PISA for comparison of MOEAs. In: Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making, MCDM 2007, pp. 382–389. No. MCDM (2007)
Collard, P., Gaspar, A., Gaspar, A., Clergue, M., Escazut, C.: Fitness distance correlation, as statistical measure of genetic algorithm difficulty, revisited. In: Proceedings of the European Conference on Artificial Intelligence, pp. 650–654. Wiley (1998)
Daolio, F., Liefooghe, A., Verel, S., Aguirre, H., Tanaka, K.: Problem features versus algorithm performance on rugged multiobjective combinatorial fitness landscapes. Evol. Comput. 25(4), 555–585 (2017)
Deb, K.: Multi-objective optimisation using evolutionary algorithms: an introduction. In: Wang, L., Ng, A., Deb, K. (eds.) Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer, London (2011). https://doi.org/10.1007/978-0-85729-652-8_1
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multiobjective optimization. In: Abraham, A., Jain, L., Goldberg, R. (eds.) Evolutionary Multiobjective Optimization. Advanced Information and Knowledge Processing. Springer, London (2005). https://doi.org/10.1007/1-84628-137-7_6
Garrett, D., Dasgupta, D.: Multiobjective landscape analysis and the generalized assignment problem. In: Maniezzo, V., Battiti, R., Watson, J.-P. (eds.) LION 2007. LNCS, vol. 5313, pp. 110–124. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92695-5_9
Hart, E., Ross, P.: Gavel-a new tool for genetic algorithm visualization. IEEE Trans. Evol. Comput. 5(4), 335–348 (2001)
Hoos, H.H., Stützle, T.: Stochastic local search: foundations and applications. Elsevier (2004)
Huband, S., Hingston, P., Barone, L.: A review of multi-objective test problems and a scalable test problem toolkit a review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evolution. Comput. 10(2006), 477–506 (2006), http://ro.ecu.edu.au/ecuworks/2022
Jiang, S., Cai, Z., Zhang, J., Ong, Y.S.: Multiobjective optimization by decomposition with Pareto-adaptive weight vectors. In: Proceedings - 2011 7th International Conference on Natural Computation, ICNC 2011, vol. 3, pp. 1260–1264 (2011)
Jones, T., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 184–192 (1995)
Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: survey and perspectives. Evol. Comput. 27(1), 3–45 (2019)
Knowles, J., Corne, D.: Instance generators and test suites for the multiobjective quadratic assignment problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds.) EMO 2003. LNCS, vol. 2632, pp. 295–310. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36970-8_21
Liefooghe, A., Daolio, F., Verel, S., Derbel, B., Aguirre, H., Tanaka, K.: Landscape-aware performance prediction for evolutionary multi-objective optimization. IEEE Trans. Evolution. Comput. (2019)
Miettinen, K.: Nonlinear multiobjective optimization. Intl. Ser. in Operations Research & Management Science: 12, Springer, New York (1998). https://doi.org/10.1007/978-1-4615-5563-6
Morgan, R., Gallagher, M.: Analysing and characterising optimization problems using length scale. Soft. Comput. 21(7), 1735–1752 (2015). https://doi.org/10.1007/s00500-015-1878-z
Moser, I., Gheorghita, M., Aleti, A.: Identifying features of fitness landscapes and relating them to problem difficulty. Evol. Comput. 25(3), 407–437 (2017)
Müller, C.L., Sbalzarini, I.F.: Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis. In: Di Chio, C., et al. (eds.) EvoApplications 2011. LNCS, vol. 6624, pp. 294–303. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20525-5_30
Muñoz, M.A., Sun, Y., Kirley, M., Halgamuge, S.K.: Algorithm selection for black-box continuous optimization problems: a survey on methods and challenges. Inf. Sci. 317, 224–245 (2015)
Paquete, L., Stützle, T.: A study of stochastic local search algorithms for the biobjective qap with correlated flow matrices. Eur. J. Oper. Res. 169(3), 943–959 (2006)
Poli, R., Vanneschi, L.: Fitness-proportional negative slope coefficient as a hardness measure for genetic algorithms. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, pp. 1335–1342. ACM (2007)
Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. (CSUR) 41(1), 6 (2009)
Tian, Y., Cheng, R., Zhang, X., Jin, Y.: Platemo: a MATlab platform for evolutionary multi-objective optimization. IEEE Comput. Intell. Mag. 12, 73–87 (11 2017)
Verel, S., Liefooghe, A., Jourdan, L., Dhaenens, C.: On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives. Eur. J. Oper. Res. 227(2), 331–342 (2013)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)
Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000)
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
Herring, D., Pakravan, D., Kirley, M. (2022). Analysing Multiobjective Optimization Using Evolutionary Path Length Correlation. In: Long, G., Yu, X., Wang, S. (eds) AI 2021: Advances in Artificial Intelligence. AI 2022. Lecture Notes in Computer Science(), vol 13151. Springer, Cham. https://doi.org/10.1007/978-3-030-97546-3_38
Download citation
DOI: https://doi.org/10.1007/978-3-030-97546-3_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-97545-6
Online ISBN: 978-3-030-97546-3
eBook Packages: Computer ScienceComputer Science (R0)