Optimization neighborhood

An optimization neighborhood assigns to each feasible solution $x$ a set $N(x)$ of candidates reachable by the chosen elementary moves. It need not be a neighborhood in a previously chosen geometric metric, nor must reachability be symmetric. For minimization, a solution is locally optimal under these moves whenChanging $N$ can change that conclusion while leaving the objective function unchanged. Specifying the embedded local search is therefore part of specifying an iterated local search method.^[ref]

For a complete binary string example, let the feasible set contain all eight strings of length three. Assign $f(000)=0$, $f(111)=-1$, and $f(x)=1$ for the other six strings. With one-bit flips,so $000$ is a strict local optimum. Allowing flips of one or two bits adds $110,101,011$, but all six neighbors still cost $1$. Allowing three-bit flips finally reaches $111$, so $000$ ceases to be locally optimal. The best value in the entire feasible set is $-1$ throughout; the move rule changes what the local procedure can see.

For length $n$, the one-bit-flip neighborhood has $n$ members, while including all two-bit flips adds $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. A larger neighborhood may expose an improving move but cost more to examine. The corresponding directed graph has feasible solutions as vertices and a directed edge from $x$ to each member of $N(x)$. If this graph cannot reach a region from the initial solution, even repeated local moves cannot explore that region without a different move or a restart.