31.5 First improvement and best improvement

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

• The function \(\textit{Improve}\) of \(LS\) can stop at the first improving neighbour it finds, or examine the whole neighbourhood and return the best neighbour. The pseudo-codes are written for a minimization problem; for a maximization problem, “\(<\)” becomes “\(>\)”.

31.5.1 First improvement

The first improvement rule examines the neighbours of the current solution in a fixed order and returns the first neighbour that is better than the current solution. If no neighbour is better, it returns \(\textit{NULL}\).

Algorithm: First improvement

Input: a feasible solution \(x\), a neighbourhood \(N\), an objective function \(f\) (to be minimized)

Output: the first neighbour \(y\in N(x)\) with \(f(y)<f(x)\), or \(\textit{NULL}\)

1Function FirstImprovement(\(x, N, f\))

2for \(y \in N(x)\), in the order of the neighbourhood do

3if \(f(y) < f(x)\) then

4return \(y\) ▹ improving neighbour: accept it at once

5end

6end

7return \(\textit{NULL}\) ▹ \(x\) is a local optimum

Run in Colab:PythonC++

31.5.2 Best improvement

The best improvement rule examines all the neighbours of the current solution and returns the best one, if it is better than the current solution; ties are broken in favour of the neighbour examined first. If no neighbour is better, it returns \(\textit{NULL}\).

Algorithm: Best improvement

Input: a feasible solution \(x\), a neighbourhood \(N\), an objective function \(f\) (to be minimized)

Output: a best neighbour \(y\in N(x)\) if \(f(y)<f(x)\), otherwise \(\textit{NULL}\)

1Function BestImprovement(\(x, N, f\))

2\(\bar y := \textit{NULL}\) \(\bar f := f(x)\) ▹ best improving neighbour found so far its value

3for \(y \in N(x)\), in the order of the neighbourhood do

4if \(f(y) < \bar f\) then

5\(\bar y \leftarrow y\) \(\bar f \leftarrow f(y)\) ▹ better than all the neighbours seen so far

6end

7end

8return \(\bar y\) ▹ NULL if \(x\) is a local optimum

Run in Colab:PythonC++

31.5.3 Comparison

• In a local optimum both rules examine the whole neighbourhood: the last iteration costs the same.

• Before reaching it, first improvement makes cheaper iterations, since it stops at the first improving neighbour, but each move usually improves less, so it tends to make more moves. Best improvement makes the steepest descent: each iteration costs a full exploration of the neighbourhood, and each move improves as much as possible.

• The two rules follow different paths, so they may stop in different local optima. Neither rule is better than the other on all instances: the steepest move now can lead into a worse valley later.

• With first improvement the result depends on the order in which the neighbours are examined; randomizing that order is a simple way to obtain different local optima from the same starting solution.

Example 31.1: First and best improvement on the KP

We start from the solution of the greedy by weight \(GR_w\) on the KP reference instance (\(c=9\)), i.e., \(x=(0,0,1,1)\), of weight \(6\) and profit \(10\), with the neighbourhood flip+swap. The neighbours are examined in the order of Section 31.4:

move	neighbour	weight	profit
flip \(1\)	\((1,0,1,1)\)	\(11\)	—	infeasible
flip \(2\)	\((0,1,1,1)\)	\(10\)	—	infeasible
flip \(3\)	\((0,0,0,1)\)	\(3\)	\(4\)
flip \(4\)	\((0,0,1,0)\)	\(3\)	\(6\)
swap \(3\) out, \(1\) in	\((1,0,0,1)\)	\(8\)	\(14\)	\(\leftarrow\) first improvement
swap \(3\) out, \(2\) in	\((0,1,0,1)\)	\(7\)	\(11\)
swap \(4\) out, \(1\) in	\((1,0,1,0)\)	\(8\)	\(16\)	\(\leftarrow\) best improvement
swap \(4\) out, \(2\) in	\((0,1,1,0)\)	\(7\)	\(13\)

First improvement accepts \((1,0,0,1)\), of profit \(14\), after examining \(3\) feasible neighbours. From \((1,0,0,1)\) (weight \(8\)) the neighbours are examined again from the beginning:

move	neighbour	weight	profit
flip \(1\)	\((0,0,0,1)\)	\(3\)	\(4\)
flip \(2\)	\((1,1,0,1)\)	\(12\)	—	infeasible
flip \(3\)	\((1,0,1,1)\)	\(11\)	—	infeasible
flip \(4\)	\((1,0,0,0)\)	\(5\)	\(10\)
swap \(1\) out, \(2\) in	\((0,1,0,1)\)	\(7\)	\(11\)
swap \(1\) out, \(3\) in	\((0,0,1,1)\)	\(6\)	\(10\)
swap \(4\) out, \(2\) in	\((1,1,0,0)\)	\(9\)	\(17\)	\(\leftarrow\) first improvement

and \((1,1,0,0)\), of profit \(17\), is accepted after \(5\) feasible neighbours. It is the optimal solution, so no neighbour is better: the \(6\) feasible neighbours are examined and the search stops. In total: \(2\) moves, \(3+5+6=14\) feasible neighbours examined.

Best improvement examines all the \(6\) feasible neighbours of \((0,0,1,1)\) and moves to \((1,0,1,0)\), of profit \(16\). This is the solution of \(GR\), whose neighbourhood is in the chapter «Heuristic algorithms: definitions»: the best neighbour is \((1,1,0,0)\), of profit \(17\), reached with the swap “\(3\) out, \(2\) in”. The search stops there after examining its \(6\) feasible neighbours. In total: \(2\) moves, \(6+6+6=18\) feasible neighbours examined.

The two rules reach the optimum along different paths, \(10\to14\to17\) and \(10\to16\to17\), and first improvement examines fewer neighbours. The flip neighbourhood alone would not have moved at all: from \((0,0,1,1)\) every feasible flip removes an item, so \((0,0,1,1)\), of profit \(10\), is a local optimum for flip.

---

Next: 31.6 Evaluating a move incrementally