Re: [igraph] ACO algorithm

[Gabor Csardi]

George,

i don't know about it, there isn't a big chance anybody did it. I don't know
too much about ACO, but based on what i know i think igraph can help only
moderately in this problem.

If you want a C implementation then you can use igraph's ability to walk 
around in the graph, but this is not trivial since you also need to 
assign "dynamic weights" to the edges and choose where to step based 
on these probabilities. There is an igraph_psumtree_t type which 
implements a partial prefix sum tree which is handy for drawing 
random numbers from a dynamic discrete distribution. It is not documented 
however and also i think it is worth only if the graph has large-degree 
vertices. (I might be wrong.)

This is how i would do ACO in igraph:
1) convert the input graph into an adjacency list (igraph_i_adjlist_t)
2) allocate a list of igraph_psumtree_t's for the pheromones
3) then for each step of an ant choose from the corresponding 
   psumtree and then update it.

A tricky part is to evaporate the pheromones, that would need some 
play with the partial prefix sum trees, obviously you don't want to 
update all edges for evaporation in every time step.

Here is my guess for the running time:
1) adjlist_t, this is O(|V|+|E|)
2) igraph_psumtree_t's, this is O(|V|+|E|) too

A step of an ant is O(log(d)) where d is the possible steps from its 
current position. This is only true if the prefix sum trees can 
be used without the extensive evaporation updates. Interestingly i need
the same kind of extension of psumtree for a project of mine...

So for n ants and N simulation steps the running time is 
O(|V|+|E|+n N log(d)), where d is the maximum vertex degree in the graph.

The space needed is O(|V|+|E|).

I'm not sure this is of any help, i'm not even sure this is the kind of 
thing you want to do,
Gabor

On Thu, Jul 05, 2007 at 06:55:53PM +0200, George Orwell wrote:
> has anybody implemented an ACO (ant colonly optimization)
> algorithm with igraph? if not, are there any suggestions as to
> how to implement with this library?
> 
> thanks
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK