Skip to main content
Erschienen in: Journal of Combinatorial Optimization 4/2019

29.08.2019

Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem

verfasst von: Madalina M. Drugan

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Aguirre HE, Tanaka K (2007) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res 181(3):1670–1690MATHCrossRef Aguirre HE, Tanaka K (2007) Working principles, behavior, and performance of MOEAs on MNK-landscapes. Eur J Oper Res 181(3):1670–1690MATHCrossRef
Zurück zum Zitat Aleti A, Moser I, Grunske L (2017) Analysing the fitness landscape of search-based software testing problems. Autom Softw Eng 24(3):603–621CrossRef Aleti A, Moser I, Grunske L (2017) Analysing the fitness landscape of search-based software testing problems. Autom Softw Eng 24(3):603–621CrossRef
Zurück zum Zitat Alyahya K, Rowe JE (2019) Landscape analysis of a class of NP-hard binary packing problems. Evol Comput 27(1):47–73CrossRef Alyahya K, Rowe JE (2019) Landscape analysis of a class of NP-hard binary packing problems. Evol Comput 27(1):47–73CrossRef
Zurück zum Zitat Angel E, Zissimopoulos V (2002) On the hardness of the quadratic assignment problem with metaheuristics. J Heuristics 8(4):399–414CrossRef Angel E, Zissimopoulos V (2002) On the hardness of the quadratic assignment problem with metaheuristics. J Heuristics 8(4):399–414CrossRef
Zurück zum Zitat Basseur M, Goeffon A (2015) Climbing combinatorial fitness landscapes. Appl Soft Comput 30:688–704CrossRef Basseur M, Goeffon A (2015) Climbing combinatorial fitness landscapes. Appl Soft Comput 30:688–704CrossRef
Zurück zum Zitat Biyikoglu T, Leydold J, Stadler PF (2007) Laplacian eigenvectors of graphs: Perron–Frobenius and Faber–Krahn type theorems. Springer, New YorkMATHCrossRef Biyikoglu T, Leydold J, Stadler PF (2007) Laplacian eigenvectors of graphs: Perron–Frobenius and Faber–Krahn type theorems. Springer, New YorkMATHCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Cela E (1997) The quadratic assignment problem. Springer, DordrechtMATH Cela E (1997) The quadratic assignment problem. Springer, DordrechtMATH
Zurück zum Zitat 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 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
Zurück zum Zitat Chicano F, Whitley LD, Alba E (2011) A methodology to find the elementary landscape decomposition of combinatorial optimization problems. Evol Comput 19(4):597–637CrossRef Chicano F, Whitley LD, Alba E (2011) A methodology to find the elementary landscape decomposition of combinatorial optimization problems. Evol Comput 19(4):597–637CrossRef
Zurück zum Zitat Chicano F, Luque G, Alba E (2012) Autocorrelation measures for the quadratic assignment problem. Appl Math Lett 25(4):698–705MathSciNetMATHCrossRef Chicano F, Luque G, Alba E (2012) Autocorrelation measures for the quadratic assignment problem. Appl Math Lett 25(4):698–705MathSciNetMATHCrossRef
Zurück zum Zitat Chung FRK (1994) Spectral graph theory, vol. 92. CBMS Chung FRK (1994) Spectral graph theory, vol. 92. CBMS
Zurück zum Zitat 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 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
Zurück zum Zitat 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). MITCrossRef 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). MITCrossRef
Zurück zum Zitat Draskoczy B (2010) Fitness distance correlation and search space analysis for permutation based problems. Evolutionary Computation in Combinatorial Optimization EvoCOP, pp 47–58. Springer Draskoczy B (2010) Fitness distance correlation and search space analysis for permutation based problems. Evolutionary Computation in Combinatorial Optimization EvoCOP, pp 47–58. Springer
Zurück zum Zitat Ehrgott M (2005) Multicriteria optimization. Springer, BerlinMATH Ehrgott M (2005) Multicriteria optimization. Springer, BerlinMATH
Zurück zum Zitat 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–83CrossRef 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–83CrossRef
Zurück zum Zitat Garrett JD (2008) Multiobjective fitness landscape analysis and the design of effective memetic algorithms. Ph.D. thesis, University of Memphis Garrett JD (2008) Multiobjective fitness landscape analysis and the design of effective memetic algorithms. Ph.D. thesis, University of Memphis
Zurück zum Zitat Happel R, Stadler PF (1996) Canonical approximation of fitness landscapes. Complexity 2(1):53–58CrossRef Happel R, Stadler PF (1996) Canonical approximation of fitness landscapes. Complexity 2(1):53–58CrossRef
Zurück zum Zitat Herrmann S, Ochoa G, Rothlauf F (2016) Coarse-grained barrier trees of fitness landscapes. Parallel problem solving from nature—PPSN XIV, pp 901–910 Herrmann S, Ochoa G, Rothlauf F (2016) Coarse-grained barrier trees of fitness landscapes. Parallel problem solving from nature—PPSN XIV, pp 901–910
Zurück zum Zitat Horn RA, Johnson CR (2013) Matrix analysis. Cambridge University Press, CambridgeMATH Horn RA, Johnson CR (2013) Matrix analysis. Cambridge University Press, CambridgeMATH
Zurück zum Zitat Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, Oxford Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, Oxford
Zurück zum Zitat 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–245CrossRef 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–245CrossRef
Zurück zum Zitat Knowles JD, Corne D (2003) Instance generators and test suites for the multiobjective quadratic assignment problem. Evolutionary multi-criterion optimization (EMO), pp 295–310 Knowles JD, Corne D (2003) Instance generators and test suites for the multiobjective quadratic assignment problem. Evolutionary multi-criterion optimization (EMO), pp 295–310
Zurück zum Zitat 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–56CrossRef 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–56CrossRef
Zurück zum Zitat 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 MITCrossRef 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 MITCrossRef
Zurück zum Zitat Li J, Guo J-M, Shiu WC (2013b) On the second largest Laplacian eigenvalues of graphs. Linear Algebra Appl 438:2438–2446 ElsevierMathSciNetMATHCrossRef Li J, Guo J-M, Shiu WC (2013b) On the second largest Laplacian eigenvalues of graphs. Linear Algebra Appl 438:2438–2446 ElsevierMathSciNetMATHCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3):303–325 MITCrossRef Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3):303–325 MITCrossRef
Zurück zum Zitat Mohar B (1991) The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, pp 871–898. Wiley Mohar B (1991) The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, pp 871–898. Wiley
Zurück zum Zitat Moser I, Gheorghita M, Aleti A (2017) Identifying features of fitness landscapes and relating them to problem difficulty. Evol Comput 25(3):407–437 MITCrossRef Moser I, Gheorghita M, Aleti A (2017) Identifying features of fitness landscapes and relating them to problem difficulty. Evol Comput 25(3):407–437 MITCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput OR 39(5):875–889MathSciNetMATHCrossRef Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput OR 39(5):875–889MathSciNetMATHCrossRef
Zurück zum Zitat 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 ElsevierMathSciNetMATHCrossRef 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 ElsevierMathSciNetMATHCrossRef
Zurück zum Zitat Tayarani-N MH, Prugel-Bennett A (2015) Quadratic assignment problem: a landscape analysis. Evol Intel 8(4):165–184 SpringerCrossRef Tayarani-N MH, Prugel-Bennett A (2015) Quadratic assignment problem: a landscape analysis. Evol Intel 8(4):165–184 SpringerCrossRef
Zurück zum Zitat Thierens D (2010) the linkage tree genetic algorithm. Parallel Problem solving from nature—PPSN XI. Springer, pp 264–273 Thierens D (2010) the linkage tree genetic algorithm. Parallel Problem solving from nature—PPSN XI. Springer, pp 264–273
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat 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 ElsevierMathSciNetCrossRef 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 ElsevierMathSciNetCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Weinberger ED (1996) NP completeness of Kauffman?s NK model, a tuneably rugged fitness landscape. Santa Fe Institute Technical Reports Weinberger ED (1996) NP completeness of Kauffman?s NK model, a tuneably rugged fitness landscape. Santa Fe Institute Technical Reports
Zurück zum Zitat Whitley D, Sutton AM, Ochoa G, Chicano F (2014) The component model for elementary landscapes and partial neighborhoods. Theor Comput Sci 545:59–75MathSciNetMATHCrossRef Whitley D, Sutton AM, Ochoa G, Chicano F (2014) The component model for elementary landscapes and partial neighborhoods. Theor Comput Sci 545:59–75MathSciNetMATHCrossRef
Zurück zum Zitat Wilks SS (1947) Mathematical statistics. Princeton University Press, PrincetonMATH Wilks SS (1947) Mathematical statistics. Princeton University Press, PrincetonMATH
Metadaten
Titel
Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem
verfasst von
Madalina M. Drugan
Publikationsdatum
29.08.2019
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 4/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-019-00445-7

Weitere Artikel der Ausgabe 4/2019

Journal of Combinatorial Optimization 4/2019 Zur Ausgabe