## Search Landscape Analysis

Recently, I have been exploring the fitness landscapes of permutation optimization problems, problems where one must find an optimal ordering of some discrete set (e.g., scheduling problems, mapping problems, among others). Such permutation problems fall into one of three broad categories, depending upon the structural characteristics of greatest influence on solution fitness (absolute positioning of elements, relative positioning of elements, or element precedences), although some problems may span more than one of these categories. For example, the fitness of solutions to the traveling salesperson problem (TSP) is completely dependent upon the costs of the edges between cities, and not at all dependent upon where in the tour the edge appears. Thus, the TSP is an example of an R-Permutation problem, one where fitness depends upon the relative positions of elements. Mapping problems where one must find an optimal mapping between the elements of two sets, such as the largest common subgraph problem, are A-Permutation problems as fitness depends strictly upon the absolute locations of elements within the permutation. Many scheduling problems are P-Permutation problems with element precedences playing a substantial role in the fitness of solutions (e.g., perhaps it is important to fitness that task A occurs sometime prior to tasks B, C, and D, but that it otherwise doesn't matter what task immediately follows A). Among other things, my research on permutation fitness landscapes has introduced a theoretical framework enabling exploring the effects of these structural properties on search performance. This includes the "Permutation in a Haystack" problem which enables specifying permutation fitness landscapes; as well as the "Calculus of Search Landscapes", a new tool for search landscape analysis that focuses on rates of change of fitness landscape topology, complementing other search landscape analysis tools such as fitness-distance correlation.

### Selected Publications

- Searching for a Permutation in a Haystack.

Vincent A. Cicirello.

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

Previously Published Papers Track.

[PDF] [BIB] - The Permutation in a Haystack Problem and the Calculus of Search Landscapes.

Vincent A. Cicirello.

*IEEE Transactions on Evolutionary Computation*, 20(3):434-446, June 2016.

[PDF] [BIB] [DOI] - On the Effects of Window-Limits on the Distance Profiles of Permutation Neighborhood Operators.

Vincent A. Cicirello.

In*Proceedings of the 8th International Conference on Bio-inspired Information and Communications Technologies*, pages 28-35. ICST, December 2014.

[PDF] [BIB] [PUB] - Profiling the Distance Characteristics of Mutation Operators for Permutation-Based Genetic Algorithms.

Vincent A. Cicirello and Robert Cernera.

In*Proceedings of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference*, pages 46-51. AAAI Press, May 2013.

[PDF] [BIB] [PUB]