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.