Cover-Encodings of Fitness Landscapes

Abstract.  An instance of a discrete optimization problem can be tackled by a local search on a suitably defined cost or fitness landscape. Ruggedness of the landscape arrests the search or slows down its progress due to trapping in local minima. Alternatively, a heuristic approximation may be used for estimating a global cost minimum. Here we present a combination of these two approaches by over-encoding maps from a larger search space to subsets of the original search space. The key idea is to construct the cover-encoding maps with the help of a suitable heuristic that singles out a near-optimal solution and results in a landscape on the larger search space that no longer exhibits trapping local minima. We present cover-encoding maps for the problems of the traveling salesman, number partitioning, maximum matching and maximum clique and demonstrate practical feasibility by simulations of adaptive walks on the encoded landscapes, finding the global minima. In addition, we discuss an analogy between certain types of encodings and coarse-graining and renormalization group of statistical physics.