[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Quadratic assignment problem: a landscape analysis

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

Abstract

The anatomy of the fitness landscape for the quadratic assignment problem is studied in this paper. We study the properties of both random problems, and real-world problems. Using auto-correlation as a measure for the landscape ruggedness, we study the landscape of the problems and show how this property is related to the problem matrices with which the problems are represented. Our main goal in this paper is to study new properties of the fitness landscape, which have not been studied before, and we believe are more capable of reflecting the problem difficulties. Using local search algorithm which exhaustively explore the plateaus and the local optima, we explore the landscape, store all the local optima we find, and study their properties. The properties we study include the time it takes for a local search algorithm to find local optima, the number of local optima, the probability of reaching the global optimum, the expected cost of the local optima around the global optimum and the basin of attraction of the global and local optima. We study the properties for problems of different sizes, and through extrapolations, we show how the properties change with the system size and why the problem becomes harder as the system size grows. In our study we show how the real-world problems are similar to, or different from the random problems. We also try to show what properties of the problem matrices make the landscape of the real problems be different from or similar to one another.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Wright S (1932) The roles of mutation, inbreeding, crossbreeding, and selection in evolution. In: Proceedings of 6th congress of genetics, vol 1. ACM Press, p 365

  2. McCarthy IP (2008) Manufacturing strategy: understanding the fitness landscape. Int J Oper Prod Manag 24(2):124–150

    Article  Google Scholar 

  3. Tavares J, Pereira F, Costa E (2006) The role of representation on the multidimensional knapsack problem by means of fitness landscape analysis. In: IEEE congress on evolutionary computation, 2006. CEC 2006, pp 2307–2314

  4. Tavares J, Pereira FB, Costa E (2008) Multidimensional knapsack problem: a fitness landscape analysis. IEEE Trans Syst Man Cybern B 38(3):604–616

    Article  Google Scholar 

  5. Riley J, Ciesielski V (2010) Fitness landscape analysis for evolutionary non-photorealistic rendering. In: Proceedings of IEEE world congress on computational intelligence, Barcelona

  6. Newth D, Brede M (2006) Fitness landscape analysis and optimisation of coupled oscillators. J Complex Syst 16:317–331

    MathSciNet  Google Scholar 

  7. Slany K, Sekanina L (2007) Fitness landscape analysis and image filter evolution using functional-level cgp. In: Proceedings of the 10th European conference on genetic programming, pp 311–320

  8. Merz P, Freisleben B (1998) Memetic algorithms and the fitness landscape of the graph bi-partitioning problem, ser. Lecture notes in computer science, vol 1498. Springer, Berlin

  9. Czogalla J, Fink A (2009) Fitness landscape analysis for the resource constrained project scheduling problem, ser. Lecture notes in computer science, vol 5851. Springer, Berlin

  10. Moscato P (1989) On evolution, search, optimisation, genetic algorithms and martial arts: toward memetic algorithms. California Institute of Technology, Pasadena. Technical report

  11. Moscato P, Norman MG (1992) A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimisation on message-passing systems. In Proceedings of the international conference on parallel computing and transputer applications, pp 177–186

  12. Qasem M, Prügel-Bennett A (2008) Complexity of max-sat using stochastic algorithms. In: Genetic and evolutionary computation conference, GECCO 2008, proceedings, Atlanta, GA, USA, July 12–16, 2008. ACM, pp 615–616

  13. Shaowei W, Qiuping Z (2007) Fitness landscape analysis for optimum multiuser detection problem. J Nat Sci 12(6):1073–1076

    Google Scholar 

  14. Huanga D, Shenb Z, Miaoa C, Leungc C (2009) Fitness landscape analysis for resource allocation in multiuser OFDM based cognitive radio systems. Mob Comput Commun Rev 13(2):26–36

    Article  Google Scholar 

  15. Mathias K, Whitley D (1992) Genetic operators, the fitness landscape and the traveling salesman problem. In: Parallel problem solving from nature. Elsevier, pp 219–228

  16. Stadler PF, Schnabl W, (1992) The landscape of the traveling salesman problem. Phys Lett A 161(4):337–344. http://www.sciencedirect.com/science/article/pii/0375960192905573

  17. Boese KD (1995) Cost versus distance in the travelling salesman problem. UCLA computer science department, Los Angeles. Technical report

  18. Hertz A, Jaumard B, de Aragão MP (1994) Local optima topology for the k-coloring problem. Discrete Appl Math 49:257–280

    Article  MATH  MathSciNet  Google Scholar 

  19. Hamiez JP, Hao JK (2001) An analysis of solution properties of the graph coloring problem. In 4th Metaheuristics international conference, Porto, Portugal

  20. Culberson J, Gent I (2001) Frozen development in graph coloring. Theor Comput Sci 265:227–264

    Article  MATH  MathSciNet  Google Scholar 

  21. Bouziri H, Mellouli K, Talbi EG (2009) Fitness landscape analysis for optimum multiuser detection problem. J Comb Optim 21(3):306–329

    Article  MathSciNet  Google Scholar 

  22. Yoshizawa H, Hashimoto S (2000) Landscape analyses and global search of knapsack problems. In: 2000 IEEE international conference on systems, man, and cybernetics, vol 3, pp 2311–2315

  23. Weixiong, Zhang (2004) Configuration landscape analysis and backbone guided local search. Part I: satisfiability and maximum satisfiability. Artif Intell 158(1):1–26. http://www.sciencedirect.com/science/article/pii/S0004370204000542

  24. Qasem M, Prügel-Bennett A (2010) Learning the large-scale structure of the MAX-SAT landscape using populations. IEEE Trans Evolut Comput 14(4):518–529

    Article  Google Scholar 

  25. Czogalla J (2008) Fitness landscape analysis for the continuous flow-shop scheduling problem. In: Proceedings of 3rd European workshop, Evo, Naples

  26. Lefticaru R, Ipate F (2008) A comparative landscape analysis of fitness functions for search-based testing. In IEEE 10th international symposium on symbolic and numeric algorithms for scientific computing, USA

  27. Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evolut Comput 4(4):337–352

    Article  Google Scholar 

  28. Weinberger ED (1990) Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol Cybern 63:325–336

    Article  MATH  Google Scholar 

  29. Jones T (1995) Evolutionary algorithms, fitness landscapes and search. Ph.D. dissertation, University of New Mexico, Albuquerque

  30. Manderick B, de Weger M, Spiessens P (1991) The genetic algorithm and the structure of the fitness landscape. In Proceedings of 4th international conference on genetic algorithms, pp 143–150

  31. Altenberg L (1997) Fitness distance correlation analysis: an instructive counterexample. In: Bäck T (ed) Proceedings of the seventh international conference on genetic algorithms. Morgan Kaufmann, San Mateo, CA, pp 57–64

  32. Grover LK (1992) Local search and the local structure of NP-complete problems. Oper Res Lett 12:235–243

    Article  MATH  MathSciNet  Google Scholar 

  33. Stadler P (1995) Towards a theory of landscapes. In: Complex systems and binary networks, pp 78–163

  34. Angel E, Zissimopoulos V (2001) On the landscape ruggedness of the quadratic assignment problem. Theor Comput Sci 263(12):159–172 (combinatorics and computer science). http://www.sciencedirect.com/science/article/pii/S0304397500002395

  35. Knowles J, Corne D (2002) Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem. In: Abraham MKA, Ruiz-del-Solar J (eds) Soft computing systems: design, management and applications. IOS Press, Amsterdam, pp 271–279

    Google Scholar 

  36. Chicano F, Luque G, Alba E (2010) Elementary landscape decomposition of the quadratic assignment problem. In: Proceedings of the 12th annual conference on genetic and evolutionary computation, ser. GECCO ’10. ACM, New York, NY, USA, pp 1425–1432. doi:10.1145/1830483.1830745

  37. Chicano F, Alba E (2011) Elementary landscape decomposition of the 0–1 unconstrained quadratic optimization. J Heuristics 1–18. doi:10.1007/s10732-011-9170-6

  38. Hallam J, Prügel-Bennett A (2005) Large barrier trees for studying search. IEEE Trans Evolut Comput 9(4):385–397

    Article  Google Scholar 

  39. Benfold W, Hallam J, Prügel-Bennett A (2007) Optimal parameters for search using a barrier tree Markov model. Theor Comput Sci 386:94–113

    Article  MATH  Google Scholar 

  40. Stadler P (1996) Landscapes and their correlation functions. J Math Chem 20(1):1–45

    Article  MATH  MathSciNet  Google Scholar 

  41. Prügel-Bennett A, Tayarani-N. M-H (2011) Maximum satisfiability: anatomy of the fitness landscape for a hard combinatorial optimisation problem. IEEE Trans Evolut Comput 15:319–338

    Google Scholar 

  42. Tayarani-N. M-H, Prugel-Bennett A (2014) On the landscape of combinatorial optimization problems. IEEE Trans Evolut Comput 18(3):420–434

    Article  Google Scholar 

  43. Tayarani-N. MH, Prügel Bennett A (2011) Anatomy of the fitness landscape for graph-colouring problem. J Swarm Evolut Comput 10:1

    Google Scholar 

  44. Tayarani-N. MH, Prügel Bennett A (2012) Travelling salesman problem: a landscape analysis. IEEE Trans Evolut Comput 10:1

    Google Scholar 

  45. Boese K, Kahng A, Muddu S (1994) On the big valley and adaptive multi-start for discrete global optimizations. Oper Res Lett 16(2)

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Science, University of Southampton, Southampton, UK

    Mohammad-H. Tayarani-N. & Adam Prügel-Bennett

Authors
  1. Mohammad-H. Tayarani-N.
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adam Prügel-Bennett
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohammad-H. Tayarani-N..

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tayarani-N., MH., Prügel-Bennett, A. Quadratic assignment problem: a landscape analysis. Evol. Intel. 8, 165–184 (2015). https://doi.org/10.1007/s12065-015-0132-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-015-0132-z

Keywords

Search

Navigation