= Optimization neighborhood
An \b[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 when
$$
f(x)\leq f(y)\quad\text{for every }y\in N(x).
$$
Changing $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.<Iterated Local Search by Helena R. Lourenço and others>[§2–3.1, embedded local search and local optima]{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,
$$
N(000)=\{100,010,001\},
$$
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 $\binom n2$ 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.
Back to article page
