An Efficient Implementation of Local-Search Landscapes

A local search traverses its energy landscape from solution to solution. Solutions and their neighbors are generated and evaluated; most are discarded. This is a common phenomenon of local search heuristics. In this system, we implement an efficient way of solution (more precisely neighbors) generation.

The naive creation of random neighbor of a solution takes order $O(n + f(n))$, where $n$ is the size of the solution, and $f(n)$ is the size of changes of going from the solution to its neighbor defined by the neighborhood structure. The more sophisticated implementation takes order $O(f(n))$. Details are discussed below.

This implementation is accomplished in Operator::gen_mut(), Operator::gen_commit(), and ObjectiveFunction::delta_cost().