Skip to content

30.9 Randomized construction

Part 4 · Heuristic algorithms · Chapter 30 · Chapter 30: Constructive heuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt

  • A greedy heuristic is deterministic: run twice on the same instance, it returns the same solution. The multi-start \(NN\) obtains different solutions by changing the starting city, but the number of starts is limited to \(n\). A more flexible way to obtain many different, and still good, solutions is to randomize the choice: at each step, instead of the best candidate, choose at random one of the good candidates.

  • The good candidates form the restricted candidate list (RCL). For a minimization criterion with values \(g(q)\) of the candidates \(q\), let \(g^{\min}\) and \(g^{\max}\) be the smallest and the largest value; the value-based RCL with parameter \(\alpha\in[0,1]\) is

\[ RCL \;=\; \Big\{\, q \;:\; g(q) \;\le\; g^{\min} + \alpha\,\big(g^{\max}-g^{\min}\big) \Big\} . \]

With \(\alpha=0\) the RCL contains only the best candidates, and the construction is greedy (with random tie-breaking); with \(\alpha=1\) it contains all the candidates, and the construction is purely random.

  • An alternative is the cardinality-based RCL, made of the \(k\) best candidates for a fixed \(k\). Randomized construction is the first ingredient of the metaheuristic GRASP (T.A. Feo, M.G.C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 (1995) 109–133).

  • Random numbers. To make examples and exercises reproducible, the notes on heuristic algorithms use the minimal standard generator of Park and Miller, which produces a sequence of numbers \(u_1,u_2,\dots\) in \((0,1)\) from an integer seed:

\[ seed \;\leftarrow\; (16807\cdot seed) \bmod 2147483647, \qquad\qquad u \;=\; \frac{seed}{2147483647} . \]
  • The modulus is \(2^{31}-1\), a prime number; with \(64\)-bit integers the product never overflows. The same seed gives the same sequence on every computer and in every programming language. A candidate is drawn from an RCL with \(|RCL|\) elements, listed by increasing index, by taking the element in position \(\lfloor u\cdot|RCL|\rfloor+1\); a random number is used only when \(|RCL|\ge 2\).

The randomized nearest neighbour algorithm (denoted by \(RNN_\alpha\)) is a constructive heuristic for the TSP. Starting from city \(s\), at each step it builds the RCL of the unvisited cities whose distance from the last city is at most \(d^{\min}+\alpha\,(d^{\max}-d^{\min})\), and appends a city drawn uniformly at random from the RCL.

Algorithm: Randomized Nearest Neighbour

Input: TSP instance with \(n\) cities, distances \(d[1..n][1..n]\); starting city \(s\); \(\alpha\in[0,1]\); \(seed\)
Output: Tour \(\sigma[1..n]\)
1Function RandomizedNN(\(n, d, s, \alpha, seed\))
2\(\sigma[1] \leftarrow s\), \(visited := \{s\}\)
3for \(len := 2\) to \(n\) do
4\(last := \sigma[len-1]\)
5\(d^{\min} := \min_{j\notin visited} d[last][j]\), \(d^{\max} := \max_{j\notin visited} d[last][j]\)
6\(RCL := \{\, j\notin visited : d[last][j] \le d^{\min}+\alpha\,(d^{\max}-d^{\min})\,\}\) ▹ by index
7if \(|RCL| \ge 2\) then
8\(u :=\) ParkMiller(\(seed\)) \(k :=\) the element in position \(\lfloor u\cdot|RCL|\rfloor+1\) of \(RCL\) ▹ random number in \((0,1)\)
9else
10\(k :=\) the only element of \(RCL\)
11end
12\(\sigma[len] \leftarrow k\), \(visited \leftarrow visited\cup\{k\}\)
13end
14return \(\sigma\)

Run in Colab:PythonC++
  • Repeating the construction with the same generator — the seed is not reset between two runs — gives different tours; the best one is kept. The parameter \(\alpha\) balances quality and variety: a small \(\alpha\) gives tours close to the \(NN\) tour, a large \(\alpha\) gives very different but usually poor tours.

Example 30.15: \(RNN_{0.3}\) on the TSP reference instance

We run \(RNN_\alpha\) four times from city \(1\), with \(\alpha=0.3\) and initial seed \(1\). The generator gives

\[ \begin{array}{ccccccccc} \hline {u_1} & {u_2} & {u_3} & {u_4} & {u_5} & {u_6} & {u_7} & {u_8} & {u_9} \\ \hline {0.0000} & {0.1315} & {0.7556} & {0.4587} & {0.5328} & {0.2190} & {0.0470} & {0.6789} & {0.6793} \\ \hline \end{array} \]

(\(u_1=\frac{16807}{2147483647}\approx 0.0000078\)). From city \(1\) the distances to \(2,3,4,5\) are \(5,2,2,9\), so the threshold is \(2+0.3\cdot(9-2)=4.1\) and \(RCL=\{3,4\}\).

Run 1. \(u_1\): position \(\lfloor 0.0000\cdot 2\rfloor+1=1\), city \(3\). From \(3\) the distances to \(2,4,5\) are \(4,4,7\), threshold \(4+0.3\cdot 3=4.9\), \(RCL=\{2,4\}\); \(u_2\): position \(1\), city \(2\). From \(2\) the distances to \(4,5\) are \(3,4\), threshold \(3.3\), \(RCL=\{4\}\): city \(4\), then city \(5\). Tour \((1,3,2,4,5)\), \(L=25\): the \(NN\) tour.

Run 2. \(u_3\): position \(\lfloor 0.7556\cdot 2\rfloor+1=2\), city \(4\). From \(4\) the distances to \(2,3,5\) are \(3,4,7\), threshold \(3+0.3\cdot 4=4.2\), \(RCL=\{2,3\}\); \(u_4\): position \(1\), city \(2\). From \(2\) the distances to \(3,5\) are \(4,4\): \(d^{\min}=d^{\max}=4\) and \(RCL=\{3,5\}\); \(u_5\): position \(\lfloor 0.5328\cdot 2\rfloor+1=2\), city \(5\); then city \(3\). Tour \((1,4,2,5,3)\), \(L=18=z(I)\).

Run 3. \(u_6\): city \(3\); \(u_7\): city \(2\); then cities \(4\) and \(5\). Tour \((1,3,2,4,5)\), \(L=25\).

Run 4. \(u_8\): city \(4\); \(RCL=\{2,3\}\) and \(u_9\): position \(2\), city \(3\). From \(3\) the distances to \(2,5\) are \(4,7\), threshold \(4.9\), \(RCL=\{2\}\): city \(2\), then city \(5\). Tour \((1,4,3,2,5)\), \(L=2+4+4+4+9=23\).

The four runs give \(25,18,25,23\): the second one finds the optimal tour, which \(NN\) from city \(1\) misses. The randomization has turned a single deterministic answer into a small search.

Next: 30.10 Look-ahead and regret