Ants and Estimation of Distribution Algorithms (ECAL 2009)

Last week I went to Budapest to present the paper “An Ant-Based Rule for UMDA’s Update Strategy” in the 10th European Conference on Artificial Life (ECAL 2009). ECAL is one of the leading congresses in the area and some of the most relevant work in the Artificial Life research field is presented there in first hand. It is held every two years and this time the capital of Hungary was chosen to host the event. The Academy of Sciences, in Roosevelt tér (square), on the banks of the Danube and with a perfect view on the Castle and the hills of Buda was ECAL’s headquarters for 4 days.

Only 30% of the accepted papers were selected for oral presentation. The remaining was scheduled for poster sessions (although all the accepted papers were published in full-length in two LNCS volumes) that lasted…the whole day! I cannot understand why not all the congresses follow a line similar to PPSN (a poster-only congress, with 90 minutes sessions) when it comes to poster sessions, but ECAL’s strategy is, my opinion, particularly ineffective and exhausting.

ECAL 2009, Budapest, Academy of Sciences

As for our paper, it presents a study on an alternative update strategy for the Univariate Marginal Distribution Algorithm based on the ACO computational paradigm and first presented here. The aim is to control the balance between exploration and exploitation in order to avoid diversity loss, reduce the optimal population size and improve the scalability of the algorithm on hard problems. The results confirmed the hypothesis. This is the abstract:

This paper investigates an update strategy for the Univariate Marginal Distribution Algorithm (UMDA) probabilistic model inspired by the equations of the Ant Colony Optimization (ACO) computational paradigm. By adapting ACO’s transition probability equations to the univariate probabilistic model, it is possible to control the balance between exploration and exploitation by tuning a single parameter. It is expected that a proper balance can improve the scalability of the algorithm on hard problems with bounded difficulties and experiments conducted on such problems with increasing difficulty and size confirmed these assumptions. These are important results because the performance is improved without increasing the complexity of the model, which is known to have a considerable computational effort.

Autonomic computing at the Friday paper seminar

Autonomic computing is one of those things that involves a certain amount of hand-waving but that corresponds to a really simple idea: tell a computing system what’s expected of it, instead of a step-by-step account of what we want it to do. We can tell a network we expect 99% uptime, or a database system to improve its performance by 5%, or a webserver to try and serve ten thousand simultaneous connections. Most systems will look back at you slack-jawed, but, well, that’s why the paper we’re dealing with today is called Research challenges of autonomic computing, which is written by Jeffrey O. Kephart, an IBM researcher which has produced lots of fine papers on the topic.
What are, then, the challenges and how does all that relates to our own research? The idea is to achieve what are collectively called self-star properties: self configuration, self-management, self-protection and self-healing. That is, let the system itself handle as a body, with each component being like an organ that performs its own function but is also aware that must work for the collective good and obtain an emergent property like body temperature or oxygen supply. That double function leads to architectural challenges, but also to algorithmic problems like how to be aware of what the system at large is doing and how it is behaving, how to learn new responses to changes in environment, and, eventually, how to optimize the system configuration and behaviour to attain desired targets set by the user.
And that’s where our own research comes in: the evolvable-agent architecture, to a point, configures an overlay network to take advantage of all its resources but it’s not there yet: it would be necessary to include more self-star properties such as self-management and self-configuration, so that the user should have to include just performance targets (obtain solution in a certain amount of time), and the system would set its parameters itself to attain it. A step in the right direction, anyways.