Algorithm

Tree Construct

Everything in this algorithm description is pretty much self explanatory.

Put all edges into a vector

Sort edges by pheromone level

Select the 5n edges with the highest pheromone level and put them into a candidate set, c

Sort the candidate set by cost

Take the lowest cost edge off the list

if( d % 2 == 0)
    
    Set the depth of both vertices connected to the edge to 0.

else
 
    Set the depth of one vertex to 0 and the depth of the other vertex to 1

Mark the edge and both connected vertices in the tree

while(!done)

     if( c is empty)

         Refill c with another n edges

     for each edge in c
         
         if(edgeNodeA.inTree XOR edgeNodeB.inTree)
             
             add the edge to the tree and mark the edge and the vertices in the tree
             
             unconnectedNode.depth = connectedNode.depth + 1
         
         remove the edge from c

         if(tree.size == n)

             done = true
      endFor

endWhile

opt_one_edge_v1

The algorithm for this is fairly simple

Initialize ranges R

Mark all edges in tree

while(i < K)
  
    Generate a random number and remove the edge x that corresponds to the range that number falls in.    

    while(j < t)    

         Pick a random edge r that is not in the tree    

         if Cost(r) < Cost(x) and adding r does not violate the diameter bound    

             then, add r to the tree    
         t++    

    // endwhile    

    if no edge was added    

        replace x    

//endwhile    

opt_one_edge_v2

for 0 ... ONE_EDGE_OPT_BOUND

    randomly select <level> between [1. (d/2) - 1]    

    create ranges for possible edge removals

    use proportional selection based on weight to chose an edge

    remove edge from tree

    update tabu list with the two vertices the edge connects

    of the two vertices, use the one lowest in the tree

    look at this vertex's adjacent list

    get all edges that connect this vertex to some vertex x above it in tree,    
        edges are found in data structure 2 described below.

    store these edges in a vector (could change this code to just keep track of best)

    sort this vector in descending order based on weight

    take the lowest weight edge and see if it is cheaper than the edge being removed

    if cheaper

        then add new edge

    else add old edge, were trying to remove.

end for

data structures

    1.  vector<edge*> list of possible edges to remove
    

    2.  in graph we have a 2d vector. at each level keep a list of vertices at that level.

Algorithm Ideas

These are the future changes and proposals to the algorithm.

The first part of the algorithm modifications is to get rid of the hubs. They seem to be limiting our search space too much. For a simple thing to start with, just run the connectHubs algorithm on the whole graph. Also change the connectHubs algorithm to actually be a proper kruskal's algorithm by selecting the lowest cost edge to find the initial root of the algorithm.

Next, modify the idea of having a root to allow for multiple roots, call it a Hyper-Root. This hyper-root will be a set of k vertices connected into a line. Each of these vertices will have a subtree connected to it.

One way to keep track of the depths off of these subtrees is to keep the depth to the root of the subtree and then make sure that the depths of the vertices do not exceed (d-k)/2.

The other way is to keep track of the depths a little more dynamically so that the depth at the root of each subtree will be the distance to the furthest vertex in the hyper-root. (k)=(k-1)=(k-2)=...=(k/2)=...=(k-2)=(k-1)=(k) Then using this idea, be able to create subtrees with depths greater than (d-k)/2. If one subtree goes beyond (d-k)/2 than the rest of the subtrees must be shorter than that. Vertices in the same subtree could also at the lower depth depending on the lowest common ancestor (an algorithm that will be added on here later).

Finally, we need to modify the way the ants explore to avoid getting stuck in the local star optima. To do this, the idea is to add another field on the edges that combines both cost and pheromone, call it weight(we currently have a weight in the code but it could be changed I suppose). Weight will be calculated in the following way: weight= acost + bpheromone where a and b will change throughout the algorithm based on some pheromone threshold. So that below that threshold a will be negative and above that threshold b will be negative. Not quite sure about how exactly to calculate a and b yet.

---

This is just a brief description of what our algorithm does. This is a work in progress.

Our algorithm started out exactly as the one given in the DCMST ant based algorithm paper by Dr. Bui, and Prof. Zrncic. We then modified it to work for the BDMST problem.

Essentially our algorithm puts an ant on every vertex and then has each one move for several steps to build pheromone levels. The ants are allowed to move for 75 steps and then a tree is constructed based on the pheromone levels. Not only do the ants look at the best edge from their current vertex to the next, but they also take into account the pheromone levels of the edges that contain the potential destination vertex. This ensures that the ant is less likely to travel to a vertex that would be a terrible hub. The algorithm will then save the best tree that has been found so far and then reset the ants and their visited lists and then repeats. Every 100 cycles the base pheromone levels are updated. If the best tree has changed the pheromone levels of the best tree will be enhanced by 1.05, otherwise the pheromone levels of the best tree will be evaporated by a random factor. This process repeats until either a new best tree has not been found for 2500 cycles or the algorithm reaches 10000 cycles total. Then, the best tree is returned.

Each tree is constructed by first sorting the edges based on pheromones. The algorithm takes the top 5(n) edges based on pheromone level and then sorts them in descending order based on cost. The vertices that appear in this list the most will essentially become the base hubs for the tree. The remaining vertices that are not in the tree are then added on as extra hubs. The hubs are then treated as vertices and put into a new graph. These hubs are then connected using the algorithm found in Greedy Heuristics for the Bounded Diameter Minimum Spanning Tree Problem by Bryant A. Julstrom. The algorithm is used to create a tree that conforms to the diameter bound. It does this as follows: It first, picks a vertex to act as the root of the tree or depth zero, right now it is just choosing the first hub. If there is an even number of vertices the algorithm will use one vertex as the root, otherwise it will use two vertices as depth zero. Then, each new vertex connected to the tree is given a depth of k + 1, where k is the depth of the vertex it connects to. The algorithm will not connect a vertex if the depth would be d/2. The vertices are connected using Prim’s algorithm.