Posted by: zyxo | February 19, 2008

Ant Colony Optimisation : Ants or Locusts ?


Locust. This picture was taken at Osaka, Japan.
Image via Wikipedia

With the Antminer+ algoritm David Martens, Manu De Backer, Raf Haesen,
Bart Baesens and Tom Holvoet at the University of Leuven, Belgium try to classify observations by simulating the behaviour of foraging ants. The paths these fake ants follow lead from nowhere to a decision rule. Each step connects two rules, a rule being something like ‘armlength less then 67 cm’ and the total path is the resulting combined if-statement. If the resulting combined rule is an improvement in the solution space feromones are added to the path so that the probability that the same steps are reused rises. Unused steps see their feromones evaporate. Exactly the way ants searchfor food.
Since each possible rule is connected to each other possible rule, and each rule is a possible value of a categorical variable, the connection space increases exponentially with the number of variables. So the principle is nice, but the usability, e.g. for real world datamining purposes, is extremely limited. A dataminer in a financial institution rather uses 1000-odd variables. If you transform 1000 variables in 5 categories per variable, this gives you (5000 times 5000 minus 5000)/2 connections = 12547500 connections or pheromone levels.

More scalable is the solution by Michelle Galea and Qiang Shen in a chapter in Ajith Abraham, Crina Grosan, Vitorino Ramos : Swarm Intelligence in Data Mining . Although they call it “Simultaneous Ant Colony Optimization Algorithms for Learning Linguistic Fuzzy Rules” what they really describe are locusts. They hop from one rule to another, so on their way there are no pheromones but thin air. In stead the places where they land can contain different pheromone levels, influencing their choice either to jump further or to stay (meaning to grasp the rule). Here the number of pheromone levels is exactly the same as the number of rules (5000 in my previous business example).
The drawback of this locust method is that there is no direct interaction between the different rules, because there is no path connecting them. A locust hops trough the sky and can land anywhere.  But the usage of a swarm of locusts should easily cope with this disadvantage.

I like locusts.  For together with this scalability the authors show the possibility of learning multiple rules simultaneously. And there is also the fact that they use fuzzy rules.

Very promising !

add to del.icio.us   Add to Blinkslist    add to furl   Digg it   add to ma.gnolia   Stumble It!   add to simpy   seed the vine         TailRank   post to facebook   


Responses

  1. alslam alikum;
    very good wordpress and thanks for a lot of information;
    i ask if there is open source code for ant miner+ ?
    i hope you can help me by any links or pdf;
    thanks again ;
    best regards;

  2. Leavetarce,
    Thank for visiting my blog.
    As far as I know, Antminer+ was developed for academical purposes as subject of a Ph.d thesis and I suppose you could ask Prof. Baesens for the source code (or a copy of the thesis). You’ll find him at LinkedIn. com
    Zyxo.

  3. alslam alikum;
    thanks for answer ;
    i tried to make connection with prof.baesens in linkedIn but it seems to me by upgrade connection by money;any way i can send email to him;
    i know lot of algorithms in ant colony i want apply in data mining i found antminer source code i work on it now; i ask if you can help me by giving me another links for any source code in classification rule available ;
    and thanks for great helps;
    best regards;

  4. Leavetrace,
    I have to dissapoint you. In data mining I use different techniques but I never code data mining algorithms myself. So I cannot help you with source codes.
    Recently I found a free downloadable book on “Swarm Intelligence, Focus on Ant and Particle Swarm Optimization”, edited by Felix T. S. Chan and Manoj Kumar Tiwari.
    Perhaps this is of interest to you ? Google should be able to find it for you.
    Regards.
    Zyxo

  5. alslam alikum;
    thanks for your support;
    and i already have this book;
    i try to find the way he implement DAG;
    any way;you helped me a lot by your wordpress
    i hope you continue adding posts it is very benefit for students of this feild;
    best regards;


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: