research-article

The Permutation in a Haystack Problem and the Calculus of Search Landscapes

Author:

Vincent A. CicirelloAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 20, Issue 3

Pages 434 - 446

https://doi.org/10.1109/TEVC.2015.2477284

Published: 01 June 2016 Publication History

Abstract

The natural encoding for many search and optimization problems is the permutation, such as the traveling salesperson, vehicle routing, scheduling, assignment and mapping problems, among others. The effectiveness of a given mutation or crossover operator depends upon the nature of what the permutation represents. For some problems, it is the absolute locations of the elements that most directly influences solution fitness; while for others, element adjacencies or even element precedences are most important. Different permutation operators respect different properties. We aim to provide the genetic algorithm or metaheuristic practitioner with a framework enabling effective permutation search landscape analysis. To this end, we contribute a new family of optimization problems, the permutation in a haystack, that can be parameterized to the various types of permutation problem (e.g., absolute versus relative positioning). Additionally, we propose a calculus of search landscapes, enabling analysis of search landscapes through examination of local fitness rates of change. We use our approach to analyze the behavior of common permutation mutation operators on a variety of permutation in a haystack landscapes; and empirically validate the prescriptive power of the search landscape calculus via experiments with simulated annealing.

References

[1]

V. Campos, M. Laguna, and R. Martí, “Context-independent scatter and tabu search for permutation problems,” INFORMS J. Comput., vol. 17, no. 1, pp. 111–122, 2005.

Digital Library

[2]

R. Martí, M. Laguna, and V. Campos, “Scatter search vs. genetic algorithms,” in Metaheuristic Optimization via Memory and Evolution. New York, NY, USA: Springer, 2005, pp. 263–282.

[3]

R. Fagin, R. Kumar, and D. Sivakumar, “Comparing top k lists,” SIAM J. Discrete Math., vol. 17, no. 1, pp. 134–160, 2003.

Digital Library

[4]

D. Bollegala, N. Noman, and H. Iba, “RankDE: Learning a ranking function for information retrieval using differential evolution,” in Proc. GECCO, Dublin, Ireland, 2011, pp. 1771–1778.

[5]

F. L. Wauthier, M. I. Jordan, and N. Jojic, “Efficient ranking from pairwise comparisons,” in Proc. ICML, Atlanta, GA, USA, 2013, pp. 109–117.

[6]

I. M. Oliver, D. J. Smith, and J. R. C. Holland, “A study of permutation crossover operators on the traveling salesman problem,” in Proc. ICGA, Cambridge, MA, USA, 1987, pp. 224–230.

[7]

D. E. Goldberg and R. Lingle, Jr., “Alleles, loci, and the traveling salesman problem,” in Proc. ICGA, Pittsburgh, PA, USA, 1985, pp. 154–159.

[8]

V. A. Cicirello and S. F. Smith, “Modeling GA performance for control parameter optimization,” in Proc. GECCO, Las Vegas, NV, USA, Jul. 2000, pp. 235–242.

[9]

L. Davis, “Applying adaptive algorithms to epistatic domains,” in Proc. IJCAI, Los Angeles, CA, USA, 1985, pp. 162–164.

[10]

V. A. Cicirello, “Non-wrapping order crossover: An order preserving crossover operator that respects absolute position,” in Proc. GECCO, vol. 2. Seattle, WA, USA, Jul. 2006, pp. 1125–1131.

[11]

L. Hernando, A. Mendiburu, and J. Lozano, “A tunable generator of instances of permutation-based combinatorial optimization problems,” IEEE Trans. Evol. Comput., to be published.

[12]

M.-H. Tayarani-Najaran and A. Prugel-Bennett, “On the landscape of combinatorial optimization problems,” IEEE Trans. Evol. Comput., vol. 18, no. 3, pp. 420–434, Jun. 2014.

[13]

T. Schiavinotto and T. Stützle, “A review of metrics on permutations for search landscape analysis,” Comput. Oper. Res., vol. 34, no. 10, pp. 3143–3153, Oct. 2007.

Digital Library

[14]

V. A. Cicirello and R. Cernera, “Profiling the distance characteristics of mutation operators for permutation-based genetic algorithms,” in Proc. 26th FLAIRS, St. Pete Beach, FL, USA, May 2013, pp. 46–51.

[15]

K. Sörensen, “Distance measures based on the edit distance for permutation-type representations,” J. Heuristics, vol. 13, no. 1, pp. 35–47, Feb. 2007.

Digital Library

[16]

V. A. Cicirello, “On the effects of window-limits on the distance profiles of permutation neighborhood operators,” in Proc. Int. Conf. Bioinspir. Inf. Commun. Technol., Boston, MA, USA, Dec. 2014, pp. 28–35.

[17]

A. Caprara, “Sorting by reversals is difficult,” in Proc. 1st Int. Conf. Comput. Mol. Biol., Santa Fe, NM, USA, 1997, pp. 75–83.

[18]

M. Mitchell, An Introduction to Genetic Algorithms. Cambridge, MA, USA: MIT Press, 1998.

[19]

S. Wright, “Evolution in Mendelian populations,” Genetics, vol. 16, no. 2, pp. 97–159, Mar. 1931.

[20]

M. Mitchell, S. Forrest, and J. H. Holland, “The royal road for genetic algorithms: Fitness landscapes and GA performance,” in Proc. ECAL, Cambridge, MA, USA, 1992, pp. 245–254.

[21]

M. Mitchell and S. Forrest, “Fitness landscapes: Royal road functions,” in Handbook of Evolutionary Computation. Bristol, U.K.: Inst. Phys., 1997.

[22]

D. Sudholt, “Crossover speeds up building-block assembly,” in Proc. GECCO, Philadelphia, PA, USA, 2012, pp. 689–702.

[23]

G. Reis, F. Fernandéz, and G. Olague, “Cooperative and decomposable approaches on royal road functions: Overcoming the random mutation hill-climber,” in Proc. GECCO, Montreal, QC, Canada, 2009, pp. 1875–1876.

[24]

A. Fialho, M. Schoenauer, and M. Sebag, “Analysis of adaptive operator selection techniques on the royal road and long k-path problems,” in Proc. GECCO, Montreal, QC, Canada, 2009, pp. 779–786.

[25]

E. Lutton and J. Levy Vehel, “Holder functions and deception of genetic algorithms,” IEEE Trans. Evol. Comput., vol. 2, no. 2, pp. 56–71, Jul. 1998.

Digital Library

[26]

A. M. R. Manso and L. M. P. Correia, “A multiset genetic algorithm for the optimization of deceptive problems,” in Proc. GECCO, Amsterdam, The Netherlands, 2013, pp. 813–820.

[27]

M. Li, S. Hill, and C. O’Riordan, “Analysis of a triploid genetic algorithm over deceptive and epistatic landscapes,” ACM SIGAPP Appl. Comput. Rev., vol. 12, no. 3, pp. 51–59, Sep. 2012.

Digital Library

[28]

D. E. Goldberg, “Simple genetic algorithms and the minimal, deceptive problem,” in Genetic Algorithms and Simulated Annealing, L. Davis, Ed. Los Altos, CA, USA: Morgan Kaufmann, 1987, pp. 74–88.

[29]

T. Jones and S. Forrest, “Fitness distance correlation as a measure of problem difficulty for genetic algorithms,” in Proc. ICGA, Pittsburgh, PA, USA, 1995, pp. 184–192.

[30]

C. Höhn and C. R. Reeves, “The crossover landscape for the onemax problem,” in Proc. 2nd Nord. Workshop Genet. Algorithms, Vaasa, Finland, 1996, pp. 27–43.

[31]

R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,” J. ACM, vol. 21, no. 1, pp. 168–173, Jan. 1974.

Digital Library

[32]

S. Ronald, “More distance functions for order-based encodings,” in Proc. IEEE CEC, Anchorage, AK, USA, 1998, pp. 558–563.

[33]

M. Sevaux and K. Sörensen, “Permutation distance measures for memetic algorithms with population management,” in Proc. MIC, Vienna, Austria, Aug. 2005, pp. 832–838.

[34]

S. Ronald, “Distance functions for order-based encodings,” in Proc. IEEE CEC, Indianapolis, IN, USA, 1997, pp. 49–54.

[35]

S. Ronald, “Finding multiple solutions with an evolutionary algorithm,” in Proc. IEEE CEC, Perth, WA, Australia, 1995, pp. 641–646.

[36]

M. G. Kendall, “A new measure of rank correlation,” Biometrika, vol. 30, nos. 1–2, pp. 81–93, Jun. 1938.

[37]

M. Meilă and L. Bao, “An exponential model for infinite rankings,” J. Mach. Learn. Res., vol. 11, pp. 3481–3518, Mar. 2010.

Digital Library

[38]

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. New York, NY, USA: Springer, 2003.

[39]

M. Serpell and J. E. Smith, “Self-adaptation of mutation operator and probability for permutation representations in genetic algorithms,” Evol. Comput., vol. 18, no. 3, pp. 491–514, 2010.

Digital Library

[40]

V. A. Cicirello, “On the design of an adaptive simulated annealing algorithm,” in Proc. CP 1st Workshop Auton. Search, Providence, RI, USA, Sep. 2007.

[41]

C. L. Valenzuela, “A study of permutation operators for minimum span frequency assignment using an order based representation,” J. Heuristics, vol. 7, no. 1, pp. 5–21, Jan. 2001.

Digital Library

[42]

D. E. Knuth, The Art of Computer Programming: Fundamental Algorithms, vol. 1, 3rd ed. Reading, MA, USA: Addison Wesley, 1997.

Digital Library

[43]

W. P. Swartz, “Automatic layout of analog and digital mixed macro/standard cell integrated circuits,” Ph.D. dissertation, Dept. Elect. Eng., Yale University, New Haven, CT, USA, May 1993.

[44]

J. A. Boyan, “Learning evaluation functions for global optimization,” Ph.D. dissertation, School Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA, 1998.

[45]

J. Lam and J.-M. Delosme, “Performance of a new annealing schedule,” in Proc. 25th ACM/IEEE DAC, Anaheim, CA, USA, 1988, pp. 306–311.

[46]

J. Sarma and K. De Jong, “An analysis of the effects of neighborhood size and shape on local selection algorithms,” in Parallel Problem Solving From Nature—PPSN IV. Berlin, Germany: Springer, 1996, pp. 236–244.

[47]

S.-Z. Zhao, P. N. Suganthan, and Q. Zhang, “Decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes,” IEEE Trans. Evol. Comput., vol. 16, no. 3, pp. 442–446, Jun. 2012.

Digital Library

[48]

H. Muhlenbein and J. Zimmermann, “Size of neighborhood more important than temperature for stochastic local search,” in Proc. IEEE CEC, vol. 2. La Jolla, CA, USA, 2000, pp. 1017–1024.

[49]

Y.-K. Wang, K.-C. Fan, and J.-T. Horng, “Genetic-based search for error-correcting graph isomorphism,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 27, no. 4, pp. 588–597, Aug. 1997.

Digital Library

[50]

V. A. Cicirello and W. C. Regli, “An approach to a feature-based comparison of solid models of machined parts,” Artif. Intell. Eng. Design Anal. Manuf., vol. 16, no. 5, pp. 385–399, Nov. 2002.

Digital Library

[51]

T. Mantere and J. Koljonen, “Solving, rating and generating Sudoku puzzles with GA,” in Proc. IEEE CEC, Singapore, 2007, pp. 1382–1389.

[52]

Z. Xu, H. Li, and Y. Wang, “An improved genetic algorithm for vehicle routing problem,” in Proc. ICCIS, Chengdu, China, 2011, pp. 1132–1135.

[53]

D. Romik, The Surprising Mathematics of Longest Increasing Subsequences. New York, NY, USA: Cambridge Univ. Press, 2015.

Cited By

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
Liu HChen LDeb KGoodman E(2017)Investigating the Effect of Imbalance Between Convergence and Diversity in Evolutionary Multiobjective AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2016.260657721:3(408-425)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TEVC.2016.2606577

Index terms have been assigned to the content through auto-classification.

Recommendations

A discrete differential evolution algorithm for the permutation flowshop scheduling problem
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

In this paper, a novel discrete differential evolution (DDE) algorithm is presented to solve the permutation flowhop scheduling problem with the makespan criterion. The DDE algorithm is simple in nature such that it first mutates a target population to ...
Fitness landscapes and problem hardness in genetic programming
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

The performance of searching agents, or metaheuristics, like evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algorithms (simulated annealing, tabu search, etc.) depend on some properties of the search space ...
NM landscapes: beyond NK
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

For the past 25 years, NK landscapes have been the classic benchmarks for modeling combinatorial fitness landscapes with epistatic interactions between up to K+1 of N binary features. However, the ruggedness of NK landscapes grows in large discrete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 20, Issue 3

June 2016

156 pages

ISSN:1089-778X

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 June 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Liu HChen LDeb KGoodman E(2017)Investigating the Effect of Imbalance Between Convergence and Diversity in Evolutionary Multiobjective AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2016.260657721:3(408-425)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TEVC.2016.2606577

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents