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

The Node Swap neighbourhood of a feasible solution T is deﬁned as follows: Neighbours are all feasible solutions T where a node v and one of its immediate successors u ∈ succ(v) have changed their position within the tree. In other words, node v that was predecessor of node u before the move is now an immediate successor of node u. Furthermore, node u inherits all successors of node v and the successor list of node v, succ(v), is cleared.

Reconnecting all immediate successors of v to u ensures that the diameter bound is not violated. Figure 4.2 illustrates this issue.

For this neighbourhood it is possible to implement an incremental exploration after having

**identiﬁed the most proﬁtable move. Therefore we introduce additional data structures:**

and ﬁnally a list l of all nodes that have to be checked once again when the move is performed, since only their situation alters if node u and v change their position.

Members of this list l are pred(v), u, and all nodes n ∈ succ(v)\{u}.

• A priority queue Q containing all proﬁtable moves, including the information saved for each move. The priority queue Q has always the most lucrative move on top.

After having explored the whole neighbourhood and identiﬁed the most proﬁtable move, this priority queue plays the key role for computing the successive best move within the neighbourhood.

Using again a best improvement strategy the full exploration of the Node Swap neighbourhood of a solution T can be described as in Algorithm 5. Already the ﬁrst line points out a major diﬀerence to the Edge Exchange neighbourhood. The Node Swap neighbourhood does not exclude the centre nodes, enabling neighbouring solutions T having a diﬀerent centre. After having selected a node v the algorithm computes in lines 3 to 8 the current costs cv of the connections from v to its immediate successors, succ(v), and, if v ∈ V0, / also the current costs from v to its predecessor. Then each node u ∈ succ(v) is tried to be swapped with node u. Lines 10 to 15 calculate the costs cu of this potential new arrangement. This time the connections from u to each node in succ(v) \ u are essential plus the connection from u to v. And again, if v ∈ V0, also the costs from u to v’s current / predecessor. In case the diameter is odd the costs from u to the second centre node have to be taken into account. In line 16 the costs saved by a node swap of v and u are computed.

If this leads to an improvement greater than the best found so far then node u is marked as best node for a swap with node v. After having tested every node u ∈ succ(v) line 20 checks if a proﬁtable move has been identiﬁed. If so the move and the corresponding data is put into the priority queue Q.

The total size of the Node Swap neighbourhood is O(n). The evaluation of a single neighbouring solution depends on the degree of the node under consideration. Therefore the time required to completely enumerate the whole neighbourhood is O(n · dmax ), where dmax denotes the maximum degree of any node in the current solution.

For reaching a local optimal solution with respect to the Node Swap neighbourhood an incremental enumeration can be applied after having explored the whole neighbourhood once. Since the worst case scenario has to be taken into account the incremental enumeration still requires time in O(n · dmax ), nevertheless, it speeds up computation in practice signiﬁcantly.

4. Neighbourhood Structures 26

After executing the most lucrative move, only certain nodes have to be checked in order to have once again all possible improvement moves stored in the priority queue Q. The nodes aﬀected when executing an improvement move are part of the data stored for it in Q, they can be found in list l. So for an incremental enumeration of the Node Swap neighbourhood only a slight modiﬁcation of Algorithm 5 is required: Instead of executing it for all nodes, as stated in the ﬁrst line, it is only executed for those aﬀected when performing the best move received from Q.

The complete algorithm to reach a local optimal solution is now as follows: First the whole neighbourhood is explored as described in Algorithm 5 to identify the ﬁrst best move.

Afterwards, the priority queue Q contains all proﬁtable moves, having the best one on top.

Then, as long as the priority queue Q is not empty, the ﬁrst element, containing the best improvement move, is received from Q. In the following it has to be checked if this move is still valid. Therefore the current local situation is compared to the situation when the

4. Neighbourhood Structures 27 move was evaluated. This means that it is veriﬁed, if node v, that will be replaced by one of its successors u, still has the same predecessor and the same successors. Only in this case the move is considered to be still valid and will be executed. Otherwise it is ignored and the next move is fetched from the priority queue Q. Therefore the set of immediate successors of node v, succ(v), and its predecessor, pred(v), are saved along with the move.

Assuming a move turns out to be valid it is executed immediately: The successor list of pred(v) has to be updated, by deleting node v and adding node u. Furthermore, each node that was a direct successor of node v before performing the move has to be deleted from the successor list of node v and added, excluding node u, to the successor list of node u. In addition the predecessors of all rearranged nodes have to be set accordingly: Node v gets node u as its new predecessor, u gets the old predecessor of node v, pred(v), and all old successors of node v, succ(v), get node u as their new predecessor. The last step before fetching the next move from the priority queue Q is the update of all aﬀected nodes as described above. A local optimal solution is reached when the priority queue Q is empty.

At this place it has to be mentioned that Gruber and Raidl demonstrated in [21] that the exploration of this Node Swap neighbourhood can be implemented more eﬃciently by directly manipulating the moves stored in the priority queue when updates are required.

As a consequence Q always contains only valid moves and so there is no need for the corresponding validity test and list l.

** 4.2 Level Based Neighbourhoods**

The Centre Exchange and Level Change neighbourhood structures are not based on the predecessor and successor relationships of the nodes but on the levels (0 ≤ lev(v) ≤ D/2, v ∈

V ) the nodes are assigned to. There are always exactly 1 + D mod 2 nodes with a level of 0,

**building the centre. From the level information a local optimal tree can easily be derived:**

Each node v ∈ V \ V0 is connected to the least cost predecessor p with lev(p) lev(v). If there are multiple potential predecessors for a node v with the same minimum edge costs, v always connects to one with minimum level.

Again, for a full and especially eﬃcient exploration of the whole neighbourhood some

**additional data structures are advantageous:**

• For each move the old and the new centre nodes are stored. Furthermore, a list l of new successor ↔ predecessor relations ((u, v): node u will get node v as new predecessor).

Algorithm 6 describes the complete enumeration of the Centre Exchange neighbourhood.

As the name suggests this neighbourhood focuses on ﬁnding a new centre. This is quite an important fact, since beside Centre Exchange there is only the Node Swap neighbourhood that is able to change the centre, but not on this scale. In line 3 the centre node c is assigned to level D/2. Afterwards, a new predecessor has to be found for c. Candidates are all nodes v with 0 ≤ lev(v) D/2. Note that a potential predecessor for the moved centre node c at level 0 exists only in case of an odd diameter. In addition, for all successors u ∈ succ(c) with lev(u) 1 new predecessors have to be found (lines 5, 6). Everything happened so far is only computed once. In lines 8 to 19 each node, excluding those forming the (old) centre, is tried as new centre node. For each node u ∈ V1 it has to be checked in case of an odd diameter if it is cheaper to connect u to the new centre node v or the remaining second centre node. The even diameter case is much simpler since all nodes u ∈ V1 have to be appended to v, because v is their only available predecessor. This happens in lines 11 to 14. For all nodes at the levels 2 to the old level of v it has to be checked if now v is a cheaper predecessor than their current one. In line 16 the attempt installing node v as new centre node is evaluated. If it turns out that moving node v to the centre is the most proﬁtable move found so far it is saved as new best move (lines 17-19).

a complete exploration of the neighbourhood of a given solution T, including identifying the most lucrative move, can only be done in O(n2 ).

An incremental enumeration of the neighbourhood is not presented here, since an implementation is not straightforward and we assume that the solution this neighbourhood structure is applied to is already of some good quality. Therefore it is unlikely to have a longer chain of consecutive improvement moves. A local optimal solution can be reached by calling Algorithm 6 as long as it yields an improvement move. After having identiﬁed the most proﬁtable move of the whole neighbourhood it is executed by deleting the old centre node c from the set V0 and the new centre node v from the set Vlev(v). Then they are appended to their new level sets, c to V and v to V0. Furthermore, the level array lev is D/2

The Level Change neighbourhood is the second one for which an incremental enumeration, after having explored the whole neighbourhood once, is presented. As for the incremental enumeration of the Node Swap neighbourhood again additional data structures are required.

• For every proﬁtable move the following information has to be stored: First the direction of the move, indicating if it is an increment or decrement one. Furthermore, the costs ∆c saved by it, and ﬁnally a list l representing new successor ↔ predecessor relations.

• A priority queue Q always having the most proﬁtable move on top.

• An array dec, saving for each node a pointer to its decrement move within Q, and one array inc, storing a pointer to its increment move. These two arrays are necessary to have immediate access to all moves saved in the priority queue Q.

Algorithm 7 describes the exploration of the whole Level Change neighbourhood. As stated in line one this algorithm is executed for all nodes, excluding those forming the centre. The algorithm is split into two parts. In the ﬁrst one (lines 2 to 11) the algorithm decrements the level of node v and saves this move if proﬁtable. A decrement move is only possible if lev(v) 1, since this neighbourhood does not eﬀect the centre, but decrementing a node u with l(u) = 1 would put this node u into the centre. After decrementing the level of v for each node u at the old level of v it has to be checked if it is now cheaper to reconnect u to become successor of v (lines 4 to 6). If the level of v’s predecessor is less than the new level

4. Neighbourhood Structures 31

of v, v’s predecessor is kept. Otherwise, a new predecessor has to be found (lines 7, 8) in the appropriate levels. In line 9 the costs of this move are evaluated. If it turns out that decrementing v will improve the solution this move is put into the priority queue Q. Even if the move does not change the objective value instantly (∆c = 0) it is put into the priority queue since a node at a lower level can act as potential predecessor for a larger number of other nodes, this could be valuable for subsequent iterations. Such a move, where the level of a node is decremented but the tree derived from the level information does not change, is called a null move in the following.

v can be connected as successor in a cheaper way (lines 15, 16). If no such predecessor can be found an improvement is impossible. Assuming a cheaper predecessor was found, in lines 18 to 20 the algorithm assigns to all old successors u of v (u ∈ succ(v), with lev(u) = levnew (v)) a new predecessor with an appropriate level, since u and v are now on the same level and so cannot be connected any longer. In line 21 the increment move of v is evaluated and if it gains an improvement it is put into the priority queue Q.

As the Level Change neighbourhood is of size O(n) and in the worst-case scenario for each decrement or increment move a node has to be compared with nearly every other node, a complete enumeration of it requires time in O(n2 ).

A local optimal solution has been reached when the priority queue Q is empty. In the following section an incremental enumeration of the Level Change neighbourhood is presented that can be applied after having explored a whole neighbourhood once. In this section it will also be described how to eﬃciently update information stored in Q when executing a move which has local impact on other nodes and their ability to improve the solution with a level increment or decrement. The incremental enumeration cannot reduce the worst-time complexity of O(n2 ), but still speeds up the computation time essential in practice.

** Incremental enumeration of the neighbourhood of solution T**

Assuming the whole neighbourhood has been explored applying Algorithm 7 and all improvement moves are saved in the priority queue Q, now the best move is fetched and performed. Therefore the node to be moved is deleted from its old and added to its new level: According to the direction of the move it is assigned either to the higher level, in case of an increment move, or to the lower level in case of a decrement move. Furthermore, the predecessor array and successor lists are updated based on the list l included in the data stored for a move in Q.

In order to have again all possible improvement moves in a valid state in the priority queue Q, the following rechecks and updates have to be done after executing a move. We have to distinguish between a decrement and increment move.