Searching for a Permutation in a Haystack

In Proceedings of the Tenth International Symposium on Combinatorial Search (SoCS 2017), pages 177. AAAI Press, .

Previously Published Papers Track.



We provide an overview of the Permutation in a Haystack problem, which serves as a tool for fitness landscape analysis, as well as in search algorithm design. The Permutation in a Haystack enables defining a search landscape for permutation optimization problems that abstracts the permutation features, which impact solution fitness, such as absolute element positions, edges, and pairwise element precedences. In this way, it allows the local search algorithm designer to explore a wide variety of landscape characteristics in a problem independent manner. We introduced the Permutation in a Haystack problem in a paper recently published in IEEE Transactions on Evolutionary Computation (Cicirello, 2016). In that paper, we also introduced the Search Landscape Calculus, an analytical framework for analyzing the fitness landscape induced by a local search operator via local rates of change of fitness. We then applied the tools to an analysis of several common permutation mutation operators on a wide variety of permutation search landscapes, and validated the findings empirically using simulated annealing.

Graphical Abstract

Graphical Abstract: Searching for a Permutation in a Haystack