igraph-help
[Top][All Lists]

## Re: [igraph] ACO algorithm

 From: Gabor Csardi Subject: Re: [igraph] ACO algorithm Date: Thu, 5 Jul 2007 20:15:33 +0200 User-agent: Mutt/1.5.13 (2006-08-11)

```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