PROJECT TITLE :

Maximum Satisfiability: Anatomy of the Fitness Landscape for a Hard Combinatorial Optimization Problem

ABSTRACT :

The fitness landscape of MAX-three-SAT is investigated for random instances higher than the satisfiability phase transition. This paper includes a scaling analysis of the time to achieve a local optimum, the quantity of native optima, the expected likelihood of reaching a local optimum as a operate of its fitness, the expected fitness found by local search and the simplest fitness, the probability of reaching a world optimum, the dimensions and relative positions of the worldwide optima, the mean distance between the native and international optima, the expected fitness as a perform of the Hamming distance from an optimum and their basins of attraction. These analyses show why the matter becomes hard for local search algorithms because the system size will increase. The paper conjointly shows how a recently proposed algorithm will exploit long-vary correlations in the fitness landscape to boost on the state-of-the-art heuristic algorithms.