31.6 Evaluating a move incrementally¶
Part 4 · Heuristic algorithms · Chapter 31 · Chapter 31: Local search · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Local search · App: TSP: nearest neighbour and 2-opt
-
Every iteration of \(LS\) evaluates many neighbours, and most of the running time is spent there. Computing \(f(y)\) from scratch costs \(O(n)\) for each of the four problems: the profit of a KP solution, the loads of the bins or of the machines, the length of a tour are sums of \(n\) terms.
-
A move changes only a few components of the solution. The incremental evaluation computes the change \(\Delta=f(y)-f(x)\) from the components that change, keeping some information about the current solution (its profit and weight, its loads), without recomputing \(f(y)\).
Proposition 31.3
Let \(\sigma'\) be the tour obtained from \(\sigma\) by the 2-opt move with positions \(i<j\), and let \(u_1=\sigma_i\), \(v_1=\sigma_{i+1}\), \(u_2=\sigma_j\), \(v_2=\sigma_{j+1}\). Then \(L(\sigma')=L(\sigma)+\Delta\), with
Proof
The tours \(\sigma\) and \(\sigma'\) have the same edges, except that \(\sigma\) contains \(\{u_1,v_1\}\) and \(\{u_2,v_2\}\) while \(\sigma'\) contains \(\{u_1,u_2\}\) and \(\{v_1,v_2\}\). The reversed path \(v_1,\dots,u_2\) uses the same edges in the opposite direction, and its length does not change because the distances are symmetric. □
The change of length of a 2-opt move is computed in \(O(1)\) time:
and the move is improving if and only if \(\Delta<0\).
-
For example, on the tour \((1,3,2,4,5)\) of the reference instance, of length \(25\), the move with positions \(i=2\), \(j=4\) removes \(\{3,2\}\) and \(\{4,5\}\) and adds \(\{3,4\}\) and \(\{2,5\}\): \(\Delta=d_{34}+d_{25}-d_{32}-d_{45}=4+4-4-7=-3\). The new tour \((1,3,4,2,5)\) has length \(25-3=22\), as a direct computation confirms: \(2+4+3+4+9=22\).
-
Why it matters. The 2-opt neighbourhood has \(\frac{n(n-3)}{2}\) moves. With the incremental evaluation an iteration of best improvement costs \(O(n^2)\); recomputing every tour from scratch would cost \(O(n^3)\). For \(n=1000\) cities, an iteration evaluates \(498\,500\) moves: about \(5\cdot 10^5\) operations instead of about \(5\cdot 10^8\). The reversal of the path, which costs \(O(n)\), is performed only once per iteration, for the accepted move.
-
The same idea applies to the other neighbourhoods:
| move | change of the solution | time |
|---|---|---|
| KP, flip of \(j\) | profit \(\pm p_j\), weight \(\pm w_j\) | \(O(1)\) |
| KP, swap \(j\) out, \(k\) in | profit \(+p_k-p_j\), weight \(+w_k-w_j\) | \(O(1)\) |
| BPP, move \(j\) from \(a\) to \(b\) | \(L_a-w_j\), \(L_b+w_j\); bin \(a\) is emptied iff \(L_a=w_j\) | \(O(1)\) |
| TSP, 2-opt | \(d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}\) | \(O(1)\) |
| TSP, Or-opt | \(d_{pq}+d_{as_1}+d_{s_\ell b}-d_{ps_1}-d_{s_\ell q}-d_{ab}\) | \(O(1)\) |
| \(P\,||\,C_{\max}\), move \(j\) from \(a\) to \(h\) | \(L_a-t_j\), \(L_h+t_j\); \(C_{\max}=\max\{L_a-t_j,\,L_h+t_j,\,\max_{q\ne a,h}L_q\}\) | \(O(m)\) |
-
The Or-opt formula follows as for 2-opt: the move removes the edges \(\{p,s_1\}\), \(\{s_\ell,q\}\), \(\{a,b\}\) and adds \(\{p,q\}\), \(\{a,s_1\}\), \(\{s_\ell,b\}\), and the segment keeps its orientation.
-
The cost of an iteration of \(LS\) is the size of the neighbourhood times the cost of evaluating a move (plus the cost of applying the accepted move, which is paid once per iteration):
| problem | neighbourhood | evaluation of a move | cost of an iteration |
|---|---|---|---|
| KP | flip | \(O(1)\) | \(O(n)\) |
| KP | swap | \(O(1)\) | \(O(n^2)\) |
| BPP | move | \(O(1)\) | \(O(n\cdot nb)\) |
| BPP | swap | \(O(1)\) | \(O(n^2)\) |
| TSP | 2-opt, Or-opt | \(O(1)\) | \(O(n^2)\) |
| TSP | 3-opt | \(O(1)\) | \(O(n^3)\) |
| \(P\,||\,C_{\max}\) | move | \(O(m)\) | \(O(nm^2)\) |
| \(P\,||\,C_{\max}\) | swap | \(O(m)\) | \(O(n^2m)\) |
- The incremental evaluation does not change the local optima, nor the path followed by the search: it changes only the time needed to follow it. This is why the design of a local search always starts with two questions: which moves? and how fast can a move be evaluated?