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

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 permutatio...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2016-06, Vol.20 (3), p.434-446
Main Author: Cicirello, Vincent A.
Format: Article
Language:English
Subjects:
Calculus
Correlation
Encoding
Fitness
genetic algorithm
Landscapes
Mathematical analysis
Measurement
Mutation
mutation operators
Mutations
Operators
Optimization
permutation distance metrics
permutation representation
Permutations
search landscape analysis
Search problems
Searching
simulated annealing
Transforms
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2015.2477284