×

Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem. (English) Zbl 1432.90131

Summary: The random walk’ correlation matrix of multi-objective combinatorial optimization problems utilizes both local structure and general statistics of the objective functions. Reckoning time of correlation, or the random walk of lag 0, is quadratic in problem size \(L\) and number of objectives \(D\). The computational complexity of the correlation coefficients of mNK is \(O(D^2 K^2 L)\), and of mQAP is \(O(D^2 L^2)\), where \(K\) is the number of interacting bits. To compute the random walk of a lag larger than 0, we employ a weighted graph Laplacian that associates a mutation operator with the difference in the objective function. We calculate the expected objective vector of a neighbourhood function and the eigenvalues of the corresponding transition matrix. The computational complexity of random walk’s correlation coefficients is polynomial with the problem size \(L\) and the number of objectives \(D\). The computational effort of the random walks correlation coefficients of mNK is \(O(2^K L D^2)\), whereas of mQAP is \(O(L^6 D^2)\). Numerical examples demonstrate the utilization of these techniques.

MSC:

90C27 Combinatorial optimization
90C29 Multi-objective and goal programming
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aguirre HE, Tanaka K (2007) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res 181(3):1670-1690 · Zbl 1123.90063 · doi:10.1016/j.ejor.2006.08.004
[2] Aleti A, Moser I, Grunske L (2017) Analysing the fitness landscape of search-based software testing problems. Autom Softw Eng 24(3):603-621 · doi:10.1007/s10515-016-0197-7
[3] Alyahya K, Rowe JE (2019) Landscape analysis of a class of NP-hard binary packing problems. Evol Comput 27(1):47-73 · doi:10.1162/evco_a_00237
[4] Angel E, Zissimopoulos V (2002) On the hardness of the quadratic assignment problem with metaheuristics. J Heuristics 8(4):399-414 · doi:10.1023/A:1015454612213
[5] Barnes JW, Dimova B, Dokov SP, Solomon A (2003) The theory of elementary landscapes. Appl Math Lett 16(3):337-343 · Zbl 1046.90095 · doi:10.1016/S0893-9659(03)80054-X
[6] Basseur M, Goeffon A (2015) Climbing combinatorial fitness landscapes. Appl Soft Comput 30:688-704 · doi:10.1016/j.asoc.2015.01.047
[7] Biyikoglu T, Leydold J, Stadler PF (2007) Laplacian eigenvectors of graphs: Perron-Frobenius and Faber-Krahn type theorems. Springer, New York · Zbl 1129.05001 · doi:10.1007/978-3-540-73510-6
[8] Blot A, Hoos HH, Kessaci ME, Jourdan L (2018) Automatic configuration of bi-objective optimisation algorithms: impact of correlation between objectives. In: International conference on tools with artificial intelligence (ICTAI). IEEE, pp 571-578
[9] Cela E (1997) The quadratic assignment problem. Springer, Dordrecht · Zbl 0909.90226
[10] Cheng R, Li M, Li K, Yao X (2017) Evolutionary multiobjective optimization based multimodal optimization: fitness landscape approximation and peak detection. Trans Evol Comput. IEEE
[11] Chicano F, Whitley LD, Alba E (2011) A methodology to find the elementary landscape decomposition of combinatorial optimization problems. Evol Comput 19(4):597-637 · doi:10.1162/EVCO_a_00039
[12] Chicano F, Luque G, Alba E (2012) Autocorrelation measures for the quadratic assignment problem. Appl Math Lett 25(4):698-705 · Zbl 1244.90126 · doi:10.1016/j.aml.2011.09.053
[13] Chung FRK (1994) Spectral graph theory, vol. 92. CBMS
[14] Daolio F, Liefooghe A, Verel S, Aguirre HE, Tanaka K (2015) Global vs local search on multi-objective NK-landscapes: contrasting the impact of problem features. In: Conference on genetic and evolutionary computation (GECCO). ACM, pp 369-376
[15] Daolio F, Liefooghe A, Verel S, Aguirre HE, Tanaka K (2017) Problem features versus algorithm performance on rugged multiobjective combinatorial fitness landscapes. Evol Comput 25(4). MIT · doi:10.1162/evco_a_00193
[16] Das KC (2004) The Laplacian spectrum of a graph. Comput Math Appl 48:715-724 · Zbl 1058.05048 · doi:10.1016/j.camwa.2004.05.005
[17] Draskoczy B (2010) Fitness distance correlation and search space analysis for permutation based problems. Evolutionary Computation in Combinatorial Optimization EvoCOP, pp 47-58. Springer
[18] Ehrgott M (2005) Multicriteria optimization. Springer, Berlin · Zbl 1132.90001
[19] Fontana W, Stadler PF, Bornberg-Bauer EG, Griesmacher T, Hofacker IL, Tacker M, Tarazona P, Weinberger ED, Schuster P (1993) RNA folding and combinatory landscapes. Phys Rev E 47(3):20-83 · doi:10.1103/PhysRevE.47.2083
[20] Garrett JD (2008) Multiobjective fitness landscape analysis and the design of effective memetic algorithms. Ph.D. thesis, University of Memphis
[21] Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput OR 13(5):533-549 · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[22] Happel R, Stadler PF (1996) Canonical approximation of fitness landscapes. Complexity 2(1):53-58 · doi:10.1002/(SICI)1099-0526(199609/10)2:1<53::AID-CPLX11>3.0.CO;2-W
[23] Herrmann S, Ochoa G, Rothlauf F (2016) Coarse-grained barrier trees of fitness landscapes. Parallel problem solving from nature—PPSN XIV, pp 901-910
[24] Horn RA, Johnson CR (2013) Matrix analysis. Cambridge University Press, Cambridge · Zbl 1267.15001
[25] Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, Oxford
[26] Kauffman S, Weinberger E (1989) The NK model of rugged fitness landscapes and its application to the maturation of the immune response. J Theor Biol 141(2):211-245 · doi:10.1016/S0022-5193(89)80019-0
[27] Knowles JD, Corne D (2003) Instance generators and test suites for the multiobjective quadratic assignment problem. Evolutionary multi-criterion optimization (EMO), pp 295-310 · Zbl 1036.90542
[28] Koopmans T, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53-76 · Zbl 0098.12203 · doi:10.2307/1907742
[29] Lankaites Pinheiro R, Landa-Silva D, Atkin J (2017) A technique based on trade-off maps to visualise and analyse relationships between objectives in optimisation problems. J Multi-Criteria Dec Anal 24(1-2):37-56 · doi:10.1002/mcda.1604
[30] Li R, Emmerich MT, Eggermont J, Back T, Schutz M, Dijkstra J, Reiber JH (2013a) Mixed integer evolution strategies for parameter optimization. Evol Comput 21(1):29-64 MIT · doi:10.1162/EVCO_a_00059
[31] Li J, Guo J-M, Shiu WC (2013b) On the second largest Laplacian eigenvalues of graphs. Linear Algebra Appl 438:2438-2446 Elsevier · Zbl 1258.05071 · doi:10.1016/j.laa.2012.10.047
[32] Liefooghe A, Derbel B, Verel S, Aguirre H, Tanaka K (2017) A fitness landscape analysis of Pareto local search on bi-objective permutation flowshop scheduling problems. Evolutionary multi-criterion optimization (EMO). Springer
[33] Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3):303-325 MIT · doi:10.1162/1063656041774956
[34] Mohar B (1991) The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, pp 871-898. Wiley · Zbl 0840.05059
[35] Moser I, Gheorghita M, Aleti A (2017) Identifying features of fitness landscapes and relating them to problem difficulty. Evol Comput 25(3):407-437 MIT · doi:10.1162/evco_a_00177
[36] Pelikan M, Sastry K, Goldberg DE, Butz MV, Hauschild M (2009) Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap. In: Conference on genetic and evolutionary computation GECCO. ACM, pp 851-858
[37] Pitzer E, Beham A, Affenzeller M (2012) Generic hardness estimation using fitness and parameter landscapes applied to robust taboo search and the quadratic assignment problem. In: Conference on genetic and evolutionary computation GECCO. ACM, pp 393-400
[38] Reidys CM, Stadler PF (2002) Combinatorial landscapes. SIAM Rev 44(1):3-54 · Zbl 0996.92026 · doi:10.1137/S0036144501395952
[39] Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput OR 39(5):875-889 · Zbl 1251.90339 · doi:10.1016/j.cor.2011.07.006
[40] Stadler PF (1996) Landscapes and their correlation functions. J Math Chem 20(1):1-45 · Zbl 1002.92547 · doi:10.1007/BF01165154
[41] Sutton AM, Whitley LD, Howe AE (2012) Computing the moments of k-bounded pseudo-boolean functions over hamming spheres of arbitrary radius in polynomial time. Theor Comput Sci 425:58-74 Elsevier · Zbl 1237.68195 · doi:10.1016/j.tcs.2011.02.006
[42] Tayarani-N MH, Prugel-Bennett A (2015) Quadratic assignment problem: a landscape analysis. Evol Intel 8(4):165-184 Springer · doi:10.1007/s12065-015-0132-z
[43] Thierens D (2010) the linkage tree genetic algorithm. Parallel Problem solving from nature—PPSN XI. Springer, pp 264-273
[44] van Remortel P, Ceuppens J, Defaweux A, Lenaerts T, Manderick B (2003) Developmental effects on tuneable fitness landscapes. Evolvable systems: from biology to hardware. Springer, pp 117-128 · Zbl 1034.68710
[45] Verel S, Collard P, Clergue M (2003) Where are bottlenecks in NK fitness landscapes? In: The congress on evolutionary computation, (CEC’03). IEEE, pp 273-280
[46] Verel S, Liefooghe A, Jourdan L, Dhaenens C (2013) On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives. Eur J Oper Res (EJOR) 227(2):331-342 Elsevier · doi:10.1016/j.ejor.2012.12.019
[47] Verel S, Daolio F, Ochoa G, Tomassini M (2018) Sampling local optima networks of large combinatorial search spaces: the QAP case. Parallel problem solving from nature—PPSN XV. Springer, pp 257-268
[48] Weinberger ED (1996) NP completeness of Kauffman?s NK model, a tuneably rugged fitness landscape. Santa Fe Institute Technical Reports
[49] Whitley D, Sutton AM, Ochoa G, Chicano F (2014) The component model for elementary landscapes and partial neighborhoods. Theor Comput Sci 545:59-75 · Zbl 1419.90114 · doi:10.1016/j.tcs.2014.04.036
[50] Wilks SS (1947) Mathematical statistics. Princeton University Press, Princeton · Zbl 0060.29502
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.