The 'Decent' Project: Decentralized Metaheuristics

by Enrique Alba and Martin Middendorf

The project 'Decent' (Decentralized Metaheuristics) is developing new swarm-based metaheuristics in which a decentralized design leads to emergent phenomena. These are not only important for solving complex problems, but are suitable for parallel execution in computing grids and multi-task hardware platforms.

Metaheuristics, such as evolutionary algorithms (EA), ant colony optimization (ACO), simulated annealing (SA) and particle swarm optimization (PSO), are methods that can be applied successfully to almost all optimization problems. For many hard tasks in a huge variety of areas, these algorithms are considered to be the state-of-the-art methods; these areas include engineering applications, bioinformatics, telecommunications, logistics and business.
Due to their practical importance and the need to solve large real-world instances of hard problems, parallel algorithms have been proposed for most metaheuristics. However, most approaches do not utilize the full potential of parallel execution because of their synchronicity and execution on clusters of homogeneous machines. All this makes it difficult to apply them to interesting parallel systems such as dynamically reconfigurable hardware (eg FPGAs) and large heterogeneous networks (computational grids).

In the 'Decent' project, strictly decentralized versions of metaheuristics that do not suffer from the restrictions of standard parallel/distributed metaheuristics are developed. 'Decent' is a two-year joint project between researchers from the University of Málaga (Spain) and the University of Leipzig (Germany). The project is funded by MECD (Ministerio de Educación y Ciencia, Spain) and DAAD (German Academic Exchange Service) within the 'Spain-Germany Integrated Actions' framework (HA2004-0008). The main focus of the project is on decentralized algorithms that are suitable for dynamically changing heterogeneous networks, as mobile ad hoc (and sensor) networks and dynamically reconfigurable computing systems. One main goal is to investigate the emergent properties of such decentralized swarm-based algorithms, not found in the separate behaviour of their components. This is expected to have a significant impact both in the field of advanced algorithms and in applications. This is particularly the case for complex problems arising in telecommunications (routing, coding, broadcasting etc) and bioinformatics (DNA fragment assembly, protein structure etc).

In the first year of the project, a decentralized clustering algorithm that can cluster data packets in networks was designed and applied to Particle Swarm Optimization (PSO). PSO is a metaheuristic inspired by bird flocking behaviour. A PSO algorithm maintains a swarm of particles, which move through the search space in the search for an optimal value. The movement of a particle is influenced by its velocity and the positions where good solutions have already been found, either by the particle itself or by other particles in the swarm. Figure 1 shows a test function that is to be minimized. It can be seen that the clustering helps the PSO to explore different areas containing minimum function values.

Figure 1: Test function (left) and emergent behaviour of the algorithm; swarm particles after 0, 50 and 400 iterations.

Another example of emergent behaviour appears in cellular Genetic Algorithms (cGA). This is a kind of population-based technique in which tentative solutions are evolved on a given topological structure, eg a toroidal 2D mesh (see Figure 2). Each individual in such a population has a fitness (quality of a problem solution) that is iteratively improved by applying operators to the set formed by one individual and its neighbours (much in the manner of traditional GAs, but on overlapped small neighbourhoods defined in the population, eg having five individuals).

Figure 2: Snapshots for a cellular Genetic Algorithm (cGA) every fifty iterations until a problem solution is located (black point in rightmost figure). The brighter an individual is coloured the higher is its fitness (black means a solution has been found); green individuals are within 80% of the optimum value and red ones are within 90%.

Figure 2 illustrates the evolution of a grid of individuals that separately evolve to solve the same problem. Neighbourhoods interact by means of implicit information exchanges achieved by the application of recombination of their shared individuals. Stochastic mutation of the individual contents is also performed, and new individuals are kept at each grid position if they are better than the existing ones. Such decentralized behaviour means that diversity is preserved in the solution space. It also allows a graceful convergence to an optimal solution that would be hard or even impossible to locate with other algorithms. The work in progress includes self-organization of the emergent behaviour and parallelization in clusters and grids.

Most of this work is related to the Spanish TRACER project and to the European EMBIO project.

Links:
http://neo.lcc.uma.es
EMBIO project: http://www-embio.ch.cam.ac.uk
TRACER project: http://tracer.lcc.uma.es

Please contact:
Enrique Alba, University of Málaga / SpaRCIM, Spain
Tel: +34 952 132803
E-mail: eatlcc.uma.es

Martin Middendorf, University of Leipzig, Germany
Tel: +49 341 9732275
E-mail: middendorfinformatik.uni-leipzig.de