# «An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»

Case 1: The performed move decremented the level of node v from l + 1 to l.

• If there is an increment move for node v in the priority queue, delete it (it would be no longer valid).

1. Decrement the level of node v.

Node v continues moving one level down, as this move was not possible before.

2. Increment the level of the new predecessor of v, prednew (v), if its level is l − 1 and if this move is already in the priority queue Q. To verify if this move is already in the priority queue Q the inc array is used.

The case that prednew (v) loses v as successor is new. So a new predecessor for v has to be found, this information must be added to the successor ↔ predecessor list and the costs saved by this improvement ∆c have to be updated accordingly.

If the improvement ∆c becomes negative or equal to zero after the update, the corresponding increment move can be removed from the priority queue Q (this holds true for every following increment move, too).

3. Decrement the level of each old successor u of v with lev(u) = l + 2. Note that these nodes will remain successors of v.

This move might not change the represented tree and therefore the objective value, but as already mentioned it should be considered as an improvement move since it may allow further nodes to decrement their level leading to other improvement moves.

Otherwise this move has to be evaluated from scratch with the exception that there is no need to search for a predecessor for u, since it can keep v for sure.

4. Decrement the level of each node u at level l+2 having its predecessor pred(u) = v at level l + 1.

Node u will lose its current predecessor and now v might become its new one.

If such a move can be found in the priority queue Q only the predecessor of u stored in this move has to be checked against v. In case v would be the better choice, the predecessor of u and ∆c have to be updated accordingly.

Otherwise, the decrement move of u has to be evaluated completely new including the search for a new predecessor.

5. Decrement the level of each node u being a new successor of v (note that all these new successors are on level l + 1) if such a decrement move is already in the priority queue Q.

Before moving v to level l node u had another predecessor, assume w. So the calculated ∆c of this move was based on the connection between u and w. Now u has v as its predecessor (c(u, v) has to be less than c(u, w)). In addition, the move can contain the information that u would have become the new predecessor of v at its old level l + 1, but after moving v to level l this is no longer possible.

Furthermore, the move can include new successors of u now connected to v; they have to be checked if still u would be the better predecessor for them.

So there are three possible impacts to ∆c and the successor ↔ predecessor list of the move that have to be updated accordingly.

6. Decrement the level of each node u at level l + 1 not being a new successor of v if there is already a corresponding move in the priority queue Q.

The situation is more or less the same as above with the restriction that the predecessor of u does not change when moving v to level l.

So there are only two possible impacts to ∆c and the successor ↔ predecessor list. In this case the objective value gain can only decrease, making this move worse.

7. Increment the level of each node u being a new successor of v if such a move is already in the priority queue Q.

**There are two cases:**

(a) In the move stored in Q, v would have become the new predecessor of u.

After moving v to level l this is already the case so the move can be deleted without any further investigations.

(b) Otherwise u is now connected cheaper than it was before when the move was evaluated so ∆c of the corresponding move has to be updated accordingly.

8. Decrement the level of each node u at level l, excluding v, if u would be a cheaper predecessor for v than its current predecessor, i.e. c(v, u) c(v, prednew (v)).

If a decrement move for u is already found in Q only the new connection between u and v has to be added. Furthermore, ∆c of the corresponding move has to be updated.

Otherwise, the move has to be calculated from scratch.

9. Increment the level of each node u at level l excluding v.

Now node v could be a new predecessor for u and for all old successors of u at level l + 1, as they lose their predecessor.

If there is already an increment move for u in the priority queue two things have

**to be checked:**

(a) The move contains another new predecessor, assume w, for u. If v would be a cheaper predecessor than w, update the corresponding information and the improvement ∆c.

(b) Old successors of u at level l + 1 will lose their predecessor. For all of these nodes there will be a new predecessor stored in the move.

– In the meantime (after the decrement move of v) it is possible that an old successor, assume w, of u is now successor of v. In this case w will not lose its predecessor, the corresponding information stored in the move record of u must be removed and ∆c has to be updated.

• If there is a decrement move of node v in the priority queue, delete it (it would be no longer valid).

• Reevaluate the following moves:

If this move is not in the priority queue Q it still has not to be considered, as nothing changed to make this move proﬁtable. Nevertheless, if the move is already in Q the costs saved by this move ∆c include the beneﬁt of connecting v to u instead of connecting it to predold (v). Therefore, ∆c and the fact that v is already connected to u have to be updated.

4. Increment the level of each node u at level l − 1 if such a move is already in the priority queue Q.

The move of v to level l has a lot of side eﬀects on already existing increment moves of other nodes from level l − 1 to l. For example v is no longer available as predecessor for u and all old successors of u at level l. In addition, v and some old successors of v at level l could now have u as their new predecessor and so would require to ﬁnd a new node they can connect to. Due to these various special cases an increment move of u already found in Q is evaluated from scratch.

5. Decrement the level of each node u at level l excluding v.

In case such a move is found in the priority queue Q two things have to be checked.

(a) Node v could become a new successor of u if u is a cheaper predecessor for v than its new one, i.e. c(u, v) c(prednew (v), v).

(b) Old successors of v at level l have lost their predecessor. Node u could now be attractive as new predecessor, if this connection is not already saved in the decrement move of u.

In both cases the objective value gain ∆c and the successor ↔ predecessor list of the move object have to be updated accordingly.

If such a move is not found in the priority queue Q it has to be evaluated from scratch. For eﬃciency the computation can be split into two steps. The only things changed are the two points described above, u is a possible new predecessor for v and for old successors of v. If the evaluation of these changes does not lead to a positive ∆c the move cannot be valuable. Therefore, the computation can already be aborted at this point.

6. Increment the level of each old successor u of v at level l.

can get back its old and cheaper predecessor v.

If such a move is already in the priority queue Q then only ∆c has to be updated accordingly, since before v’s increment move u was successor of v and u has now a diﬀerent predecessor. The increment move of u stored in the priority queue Q means that there is another, cheaper predecessor for u at level l so it is not necessary to check the new predecessor of u stored in the move record against v.

If no such move can be found in the priority queue Q the increment move of u has to be evaluated completely new.

7. Decrement the level of each successor u of v at level l + 1 if such a move is already in the priority queue.

If no such move is found in Q it can be ignored since nothing happened that would now make a decrement of node u proﬁtable.

In case there is such a move, u will lose v as predecessor so a new predecessor has to be found leading to a diﬀerent objective value gain ∆c. The rest of the move can be taken without any change.

8. Decrement the level of each node u at level l + 1 with predecessors at level l, excluding successors of v, if such a move is already stored in the priority queue Q and u would have become successor of v.

Node u will lose its best predecessor v after performing its decrement move.

Again, the move itself can keep unchanged, only a new predecessor has to be found and the improvement ∆c must be updated accordingly.

## 5. ANT COLONY OPTIMISATION FOR THE BDMST PROBLEM

In this chapter the concrete design of the ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem, developed within the context of this master thesis, is presented. As already mentioned, ACO algorithms can be extended with extra capabilities to improve overall system eﬃciency, e.g. lookahead, local optimisation or backtracking strategies, to name just a few. The ACO algorithm introduced here is equipped with a local optimisation heuristic, namely a variable neighbourhood descent. So before going into the details of the ACO algorithm for the BDMST problem itself, ﬁrst a VND for the BDMST is introduced, as this VND plays an important role within the ant colony optimisation algorithm.** 5.1 Variable Neighbourhood Descent**

In Chapter 3.1 various strategies to guide a search within a certain neighbourhood have been described. For the ACO the deterministic variable neighbourhood descent (VND) framework is used. The diﬀerent neighbourhood structures for this VND are those four presented in the preceding chapter, namely Edge Exchange, Node Swap, Centre Exchange and Level Change.

The VND algorithm introduced here varies a little from the general VND framework as proposed by Hansen and Mladenovi´ [23]. When following this general VND framework, c the algorithm stops exploring a certain neighbourhood of a solution T, Ni (T ) with i 1, after identifying the best neighbouring solution of T with respect to this neighbourhood structure, T ∈ Ni (T ). It sets T to T and switches back immediately to the ﬁrst neighbourhood structure N1. However, as a best improvement strategy is used to identify an improvement move, the whole neighbourhood has to be enumerated. Depending on the denition of the neighbourhood structure it is sometimes possible to store information while exploring the whole neighbourhood (as shown in the previous chapter). This information allows a faster computation of the successive best move when a move has only local impact on it. Such an incremental enumeration has been introduced for the Node Swap and Level

5. Ant Colony Optimisation for the BDMST Problem 40

Change neighbourhood structures. To beneﬁt from this incremental exploration the VND algorithm presented here does not switch back to the ﬁrst neighbourhood after having identiﬁed the best improvement move. Instead it computes a local optimal solution with respect to the current neighbourhood structure under consideration and only jumps back to the ﬁrst neighbourhood N1, in case the solution could be improved.

After deﬁning the diﬀerent neighbourhood structures the VND is based on, the order these neighbourhoods should by applied to a solution has to be determined. This decision has crucial impact either on the computation time as well as on the quality of solutions obtained.

The neighbourhood order for this VND algorithm has been taken from the VNS for the BDMST proposed by Gruber and Raidl [21], as the neighbourhood structures used in their VNS algorithm are basically the same as those utilised within this VND framework.

Algorithm 8 gives an overview of the VND framework used within the context of this master thesis. Starting from a solution T, ﬁrst the Edge Exchange neighbourhood tries to improve T by moving around whole subtrees. When a local minimum with respect to the Edge Exchange neighbourhood is reached, T is tried to be further improved by optimising the arrangement of every node and its immediate successors (Node Swap). This is again done – as already mentioned and in contrast to the general VND – until a local optimal solution T is found. Afterwards, in case T is better than T, T is saved as new so far best solution T within this VND and the algorithm jumps back to the ﬁrst neighbourhood structure.

If T was already a local minimum due to these two neighbourhoods the Centre Exchange neighbourhood tempts to further improve it by changing the centre node(s). Again, if the Centre Exchange neighbourhood yields an improvement move, the algorithm does not switch back immediately to the Edge Exchange neighbourhood. Instead, it computes a local minimum T due to the Centre Exchange neighbourhood structure and jumps back

5. Ant Colony Optimisation for the BDMST Problem 41 afterwards. And ﬁnally, if T is a local minimum with respect to the Edge Exchange, Node Swap and Centre Exchange neighbourhood, Level Change tries to optimally arrange all non-centre nodes within the level structure. When this VND algorithm terminates it reached a local optimal solution with respect to all four diﬀerent neighbourhood structures.

** 5.2 Ant Colony Optimisation**

As already presented in Chapter 3.2, several diﬀerent ant algorithms have been developed.