### The idea

A local improvement algorithm can be made faster when we notice that the running time includes the time to needed *perform* the move, but also the time needed to *examine* possible good moves and *find* an improving move (if there is one).

If for a given city `X1`

we previously did not find any improving move and it still has the same neighbors (none of the links between this city and its neighbors has been changed), then chances that we will find an improving move for this city in current iteration are small (although non-zero, see below).

The concept based on this observation is known as *don’t look bits* (DLB). We use special flag for each of the cities. Initially all the flags are turned off, which means that we allow searching for improving moves starting from given city. When a search for improving move starting from city *C* fails, then the bit for this city is turned on. When a move is performed in which this city is involved as one of the endpoints of the exchanged links, then the bit for this city is turned off. When we consider candidates for `X1`

, the first city of an improving move, we skip all cities which have their don’t-look bits set to on.

### Comments

Consider also what happens with DLB when we examine moves “in one direction” only (see 2-opt basic algorithn). In such case we consider *only one of the two links* of `X1`

, that is the link to its successor, the link between `tour[i]`

and `tour[i+1]`

. If we failed to found any improving move, then we turn the don’t-look bit for `X1`

on. If then in some subsequent iteration a move is performed in which `X1`

is one of the endpoints of the exchanged links, then we turn the don’t-look bit off. It works as expected. But what if a move changes *the orientation* of the segment in which `X1`

is *inside*, but is not at one of its ends? The don’t-look bit remains unchanged, although now the previous predecessor of `X1`

is its current successor, and we examined `X1`

only with its succcessor to verify that there are no improvements for `X1`

. So now there could be some improving move for `X1`

in “forward” orientation, but it will not be examined, because the don’t-look bit for this city is still on.

That is why in the code below we consider both tour neighbors of a given city.

For the same reason of not missing improving moves we do not limit searching to the cases where `j>i`

, but cosider *all* possible pairs of `(i, j)`

.

Aside from the above, it may seem impossible that new, improving move for given city could appear when both neighbors of this city remain unchanged, but let us take a closer look:

However we should notice that in this case cities `Y1`

and `Z1`

have their don’t-look bits set to off after making the move. Therefore the new, possibly improving move: from `X0`

and involving the link between `Y1`

and `Z1`

, will be examined in one of the subsequent iterations, that is as a move from `Y1`

or as a move from `Z1`

.

### Using Dont' Looks Bits with a simple 2-opt

```
type
DLB_Array = array[City_Number, bool]
Orientation = enum forward, backward
```

```
proc LS_2_Opt_DLB_General_Idea(tour: var Tour_Array) =
## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
var
locallyOptimal: bool = false
i, j: Tour_Index
pos_2_Limit: Tour_Index
X1, X2, Y1, Y2: City_Number
DontLook: DLB_Array
for city in 0 .. N-1:
DontLook[city] = false
while not locallyOptimal:
locallyOptimal = true
block three_loops:
for counter_1 in 0 .. N-1:
if DontLook[tour[counter_1]]:
continue
for direction in [forward, backward]: # NOTE: both tour neighbors
# consider link between t[i] and t[i+1],
# then between t[i-1] and t[i]
if direction == forward:
i = counter_1
else:
i = (N + counter_1 - 1) mod N
X1 = tour[i]
X2 = tour[(i+1) mod N]
for counter_2 in 0 .. N-1:
j = counter_2 # 2nd cut between t[j] and t[j+1]
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
# the same city or adjacent cities
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
DontLook[X1] = false
DontLook[X2] = false
DontLook[Y1] = false
DontLook[Y2] = false
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break three_loops
# end_for backward loop
DontLook[tour[counter_1]] = true
# end_for counter_1 loop
```

It is expected that the resulting tours will be different from the ones from 2-opt First Take procedure.

### See also an alternative

Instead of don't look bits speedup we can use an array indexed by city numbers, in which each element contains length of tour after improving from given city. This would make implementation simpler, but would require more memory, because of storing numbers (lengths), which are longer than booleans.

### Some simple statistics

Problem # | Method | Time | Best | Avg | Worst |
---|---|---|---|---|---|

1 | NN | 100 | 100.00 | 112.31 | 122.36 |

NN + 2opt | 1146 | 93.09 | 97.73 | 104.89 | |

NN + 2opt-DLB | 313 | 94.42 | 99.86 | 104.98 | |

2 | NN | 100 | 100.00 | 108.83 | 124.17 |

NN + 2opt | 1462 | 86.16 | 90.20 | 97.26 | |

NN + 2opt-DLB | 293 | 87.82 | 91.26 | 96.06 | |

3 | NN | 100 | 100.00 | 106.21 | 115.53 |

NN + 2opt | 1566 | 82.19 | 85.77 | 89.56 | |

NN + 2opt-DLB | 313 | 82.66 | 87.39 | 92.24 | |

4 | NN | 100 | 100.00 | 105.83 | 112.36 |

NN + 2opt | 1146 | 90.02 | 94.78 | 98.19 | |

NN + 2opt-DLB | 213 | 91.64 | 94.91 | 99.78 | |

5 | NN | 100 | 100.00 | 111.19 | 119.81 |

NN + 2opt | 781 | 91.91 | 95.43 | 99.81 | |

NN + 2opt-DLB | 293 | 91.81 | 96.31 | 102.66 | |

6 | NN | 100 | 100.00 | 112.89 | 126.03 |

NN + 2opt | 1360 | 94.35 | 99.05 | 104.02 | |

NN + 2opt-DLB | 206 | 96.02 | 99.56 | 105.29 | |

7 | NN | 100 | 100.00 | 109.35 | 117.75 |

NN + 2opt | 1146 | 90.47 | 93.28 | 99.21 | |

NN + 2opt-DLB | 313 | 90.55 | 93.80 | 99.71 | |

8 | NN | 100 | 100.00 | 109.02 | 120.22 |

NN + 2opt | 1253 | 86.50 | 91.88 | 98.31 | |

NN + 2opt-DLB | 313 | 88.45 | 92.64 | 95.84 | |

9 | NN | 100 | 100.00 | 108.79 | 116.77 |

NN + 2opt | 940 | 95.46 | 97.58 | 101.63 | |

NN + 2opt-DLB | 420 | 95.50 | 98.14 | 102.77 | |

10 | NN | 100 | 100.00 | 105.40 | 113.11 |

NN + 2opt | 1268 | 82.12 | 85.66 | 89.87 | |

NN + 2opt-DLB | 293 | 81.78 | 86.40 | 90.22 |

## No comments:

## Post a Comment