article

A review of metrics on permutations for search landscape analysis

Authors:

Tommaso Schiavinotto,

Thomas StützleAuthors Info & Claims

Computers and Operations Research, Volume 34, Issue 10

Pages 3143 - 3153

https://doi.org/10.1016/j.cor.2005.11.022

Published: 01 October 2007 Publication History

Abstract

Search landscape analysis has become a central tool for analysing the dependency of the performance of stochastic local search algorithms on structural aspects of the spaces being searched. Central to search landscape analysis is the notion of distance between candidate solutions. This distance depends on some underlying basic operator and it is defined as the minimum number of operations that need to be applied to one candidate solution for transforming it into another one. For operations on candidate solutions that are represented by permutations, in almost all researches on search landscape analysis surrogate distance measures are applied, although efficient algorithms exist in many cases for computing the exact distances. This discrepancy is probably due to the fact that these efficient algorithms are not very widely known. In this article, we review algorithms for computing distances on permutations for the most widely applied operators and present simulation results that compare the exact distances to commonly used approximations.

References

[1]

Jones, T. and Forrest, S., Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Eshelman, L.J. (Ed.), Proceedings of the sixth international conference on genetic algorithms, Morgan Kaufmann Publishers, San Mateo, CA, USA. pp. 184-192.]]

Digital Library

[2]

Kallel, L., Naudts, B. and Reeves, C.R., Theoretical aspects of evolutionary computing. In: Kallel, L., Naudts, B., Rogers, A. (Eds.), Properties of fitness functions and search landscapes, Springer, Berlin, Germany. pp. 175-206.]]

Digital Library

[3]

Kauffman, S.A., The Origins of order. Oxford University Press, NY, USA.]]

[4]

Merz, P. and Freisleben, B., Fitness landscapes and memetic algorithm design. In: Corne, D., Dorigo, M., Glover, F. (Eds.), New ideas in optimization, McGraw Hill, London, UK. pp. 244-260.]]

Digital Library

[5]

Mühlenbein, H., Evolution in time and space-the parallel genetic algorithm. In: Rawlins, G.J. (Ed.), Foundations of genetic algorithms, Morgan Kaufmann Publishers, San Mateo, CA, USA. pp. 316-337.]]

[6]

Hoos, H.H. and Stützle, T., Stochastic local search-foundations and applications. Morgan Kaufmann Publishers, San Francisco, CA, USA.]]

Digital Library

[7]

Reeves, C.R., Landscapes operators and heuristic search. Annals of Operations Research. v86. 473-490.]]

[8]

Reidys, C.M. and Stadler, P.F., Combinatorial landscapes. SIAM Review. v44 i2. 3-54.]]

Digital Library

[9]

Stadler PF. Towards a theory of landscapes. In: Lopéz-Peña R, Capovilla R, Garcí¿a-Pelayo R, Waelbroeck H, Zertuche F. editors. Complex systems and binary networks. Lecture notes in physics, vol. 461, Berlin, Germany: Springer, 1995. p. 77-163.]]

[10]

Stadler, P.F., Fitness landscapes. In: Lässig, M., Valleriani, A. (Eds.), Biological evolution and statistical physics, Springer, Berlin, Germany. pp. 187-207.]]

[11]

Weinberger, E.D., Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics. v63 i5. 325-336.]]

[12]

Merz, P. and Freisleben, B., Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Transactions on Evolutionary Computation. v4 i4. 337-352.]]

[13]

Stützle, T. and Hoos, H.H., MAX-MIN Ant System. Future Generation Computer Systems. v16 i8. 889-914.]]

Digital Library

[14]

Watson, J.P., Barbulescu, L., Whitley, L.D. and Howe, A.E., Contrasting structured and random permutation flow-shop scheduling problems: search space topology and algorithm performance. INFORMS Journal on Computing. v14 i2. 98-123.]]

[15]

Cayley, A., Note on the theory of permutations. Philosophical Magazine. v34. 527-529.]]

[16]

Christie DA, Genome rearrangement problems. Ph.D. thesis, University of Glasgow, 1998.]]

[17]

Vergara J-PC. Sorting by bounded permutations, Ph.D. thesis, Virginia Tech, 1997.]]

Digital Library

[18]

Wright, S., The roles of mutation, inbreeding, crossbreeding and selection in evolution. In: Proceedings of the sixth congress on genetics, pp. 365]]

[19]

Jerrum, M.R., The complexity of finding minimum-length generator sequences. Theoretical Computer Science. v36. 265-289.]]

Digital Library

[20]

Watson, J.-P., Beck, J.C., Howe, A.E. and Withley, L.D., Problem difficulty for tabu search in job-shop scheduling. Artificial Intelligence. v143. 189-217.]]

Digital Library

[21]

Bachelet V. Métaheuristiques parallèles hybrides: application au problème d'affectation quadratique. Ph.D. thesis, Université des Sciences et Technologies de Lille, 1999.]]

[22]

Beyer WA, Stein ML, Ulam SM. Metric in biology, an introduction. Preprint LA-4937, University of California, Los Alamos, 1972.]]

[23]

Critchlow, D., Ulam's metric. In: Encyclopedia of statistical sciences, vol. 9. Wiley, New York. pp. 379-380.]]

[24]

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C., Introduction to algorithms. 2nd ed. MIT Press, Cambridge, MA, USA.]]

Digital Library

[25]

van Emde Boas, P., Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters. v6. 80-82.]]

[26]

Bespamyatnikh, S. and Segal, M., Enumerating longest increasing subsequences and patience sorting. Information Processing Letters. v76 i1-2. 7-11.]]

Digital Library

[27]

Orlowski, M. and Pachter, M., An algorithm for the determination of a longest increasing subsequence in a sequence. Computers & Mathematics with Applications. v17 i7. 1073-1075.]]

[28]

Scharnow, J., Tinnefeld, K. and Wegener, I., The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms. v3 i4. 349-366.]]

[29]

Caprara, A., Sorting by reversals is difficult. In: Waterman, M., Istrail, S., Pevzner, P. (Eds.), Proceedings of the first annual international conference on computational molecular biology (RECOMB'97), ACM Press, NY, USA. pp. 75-83.]]

Digital Library

[30]

Solomon, A., Sutcliffe, P. and Lister, R., Sorting circular permutations by reversal. In: Dehne, F.K.H.A., Sack, J.-R., Smid, M.H.M. (Eds.), Proceedings of the eighth international workshop on algorithms and data structures, vol. 2748. Springer, Berlin, Germany. pp. 75-83.]]

[31]

Berman, P. and Karpinski, M., On some tighter inapproximability results (extended abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (Eds.), Proceedings of the 26th international colloquium on automata, languages and programming, vol. 1644. Springer, Berlin, Germany. pp. 200-209.]]

Digital Library

[32]

Berman P, Hannenhalli S, Karpinski M. 1.375-approximation algorithm for sorting by reversals. In: 10th European symposium on algorithms (ESA). Lecture notes in computer science. Berlin, Germany: Springer, 2002, p. 200-10.]]

Digital Library

[33]

Boese, K.D., Kahng, A.B. and Muddu, S., A new adaptive multi-start technique for combinatorial global optimization. Operations Research Letters. v16 i2. 101-113.]]

[34]

Merz P. Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of Siegen, Germany, 2000.]]

[35]

Caprara, A., Lancia, G. and Ng, S.-K., Sorting permutations by reversals through branch-and-price. INFORMS Journal on Computing. v13 i3. 224-244.]]

[36]

Berman P, Hannenhalli S. Fast sorting by reversal. In: Hirschberg DS, Myers EW, editors. Proceedings of the seventh annual symposium on combinatorial pattern matching. Lecture notes in computer science, vol. 1075, Berlin, Germany: Springer; 1996, pp. 168-85.]]

Digital Library

[37]

Kaplan, H., Shamir, R. and Tarjan, R.E., Faster and simpler algorithm for sorting signed permutations by reversals. In: RECOMB '97: Proceedings of the first annual international conference on computational molecular biology, ACM Press, NY, USA. pp. 163]]

Digital Library

[38]

Hartman T, Shamir R. A simpler 1.5-approximation algorithm for sorting by transpositions, In: Baeza-Yates RA, Chávez E, Crochemore M, editors. Proceedings of the 14th annual symposium on combinatorial pattern matching. Lecture notes in computer science, vol. 2676, Berlin, Germany: Springer; 2003. p: 156-69.]]

[39]

Heath, L.S. and Vergara, J.-P.C., Sorting by bounded block-moves. Discrete Applied Mathematics. v88. 181-206.]]

Digital Library

[40]

Heath, L.S. and Vergara, J.-P.C., Sorting by short block-moves. Algorithmica. v28 i3. 323-354.]]

[41]

Or I. Traveling salesman-type problems and their relation to the logistics of regional blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL, USA, 1976.]]

[42]

Glover F. A template for scatter search and path relinking. In: Hao J, Lutton E, Ronald E, Shoenauer M, Snyers D, editors. Artificial evolution 1997. Lecture notes in computer science, vol. 1363, Berlin, Germany: Springer, 1997. p. 13-54.]]

Digital Library

Cited By

Kammerdiner ASemenov APasiliao E(2024)Landscape properties of the very large-scale and the variable neighborhood search metaheuristics for the multidimensional assignment problemJournal of Global Optimization10.1007/s10898-023-01285-w88:3(653-683)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10898-023-01285-w
Branson LSutton AYan X(2023)Finding Antimagic Labelings of Trees by Evolutionary SearchProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607133(27-37)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607133
Chu XLi SGao FCui CPfeiffer FCui J(2023)A data-driven meta-learning recommendation model for multi-mode resource constrained project scheduling problemComputers and Operations Research10.1016/j.cor.2023.106290157:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.cor.2023.106290
Show More Cited By

Index Terms

A review of metrics on permutations for search landscape analysis
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Permutations and combinations
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization

Recommendations

Sorting permutations with transpositions in O(n ³) amortized time
Abstract
The problem of sorting a permutation π over alphabet ∑ = { 1 , 2 , 3 … n } with the minimum number of transpositions is known to be intractable. That is, the computation of transposition distance i.e. d t ( π ), is hard. Such sorting ...
Highlights
- Amortized time complexity is O ( n 3 ) for transposition operation.
- With ...
The minimum Manhattan distance and minimum jump of permutations
Abstract
Let π be a permutation of { 1 , 2 , … , n }. If we identify a permutation with its graph, namely the set of n dots at positions ( i , π ( i ) ), it is natural to consider the minimum L 1 (Manhattan) distance, d ( π ), between any pair ...
Tighter upper bound for sorting permutations with prefix transpositions

Permutations are sequences where each symbol in the given alphabet Σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier Ltd © 2005.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 October 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kammerdiner ASemenov APasiliao E(2024)Landscape properties of the very large-scale and the variable neighborhood search metaheuristics for the multidimensional assignment problemJournal of Global Optimization10.1007/s10898-023-01285-w88:3(653-683)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10898-023-01285-w
Branson LSutton AYan X(2023)Finding Antimagic Labelings of Trees by Evolutionary SearchProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607133(27-37)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607133
Chu XLi SGao FCui CPfeiffer FCui J(2023)A data-driven meta-learning recommendation model for multi-mode resource constrained project scheduling problemComputers and Operations Research10.1016/j.cor.2023.106290157:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.cor.2023.106290
Hu RWu XQian BMao JJin H(2022)Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling ProblemComplexity10.1155/2022/99241632022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/9924163
Zhang ZQian BHu RJin HWang LYang J(2022)A matrix-cube-based estimation of distribution algorithm for blocking flow-shop scheduling problem with sequence-dependent setup timesExpert Systems with Applications: An International Journal10.1016/j.eswa.2022.117602205:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.eswa.2022.117602
Cicirello V(2022)On Fitness Landscape Analysis of Permutation Problems: From Distance Metrics to Mutation Operator SelectionMobile Networks and Applications10.1007/s11036-022-02060-z28:2(507-517)Online publication date: 8-Nov-2022
https://dl.acm.org/doi/10.1007/s11036-022-02060-z
Shao WShao ZPi D(2022)A multi-neighborhood-based multi-objective memetic algorithm for the energy-efficient distributed flexible flow shop scheduling problemNeural Computing and Applications10.1007/s00521-022-07714-334:24(22303-22330)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00521-022-07714-3
Bulteau LShahaf GShapiro ETalmon N(2021)Aggregation over Metric SpacesJournal of Artificial Intelligence Research10.1613/jair.1.1238870(1413-1439)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12388
Hu RWu XQian BMao JJin H(2020)An Enhanced Differential Evolution Algorithm with Fast Evaluating Strategies for TWT-NFSP with SSTs and RTsComplexity10.1155/2020/88353592020Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1155/2020/8835359
Kaufmann THorn MRaidl G(2020)A Variable Neighborhood Search for the Job Sequencing with One Common and Multiple Secondary Resources ProblemParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58115-2_27(385-398)Online publication date: 5-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-58115-2_27
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents