Lab: Genetic Algorithms & Bioinspired Computation

A Laboratory of the Research Group
"Soft Computing and Intelligent Information Systems"


Research Summary

GABIC is a laboratory focused on the study of evolutionary algorithms. Concretely, GABIC is interested in Genetic Algorithms, Memetic Algorithms and Ant Colony Optimization.

Genetic Algorithms are general purpose search algorithms that use principles inspired by natural genetic populations to evolve solutions to problems. The basic idea is to maintain a population of chromosomes that represent candidate solutions to the concrete problem.

The Genetic Algorithm evolves the population through a process of competition and controlled variation. Each chromosome in the population has an associated fitness to determine which ones are used to form new chromosomes in the competition process, which is called parent selection. The new ones are created using genetic operators such as crossover and mutation.

Genetic Algorithms have had a great measure of success in search and optimisation problems. The reason for a great part of their success is their ability to exploit the information accumulated about an initially unknown search space in order to bias subsequent searchers into useful subspaces. This is their key feature, particularly in large, complex, and poorly understood search spaces, where classical search tools (enumerative, heuristic, ...) are inappropriate, offering a valid approach to problems requiring efficient and effective search techniques.

We are mainly interested in developing Genetic Algorithms for Real-Parameter Optimisation Problems.

Memetic Algorithms are Genetic Algorithms that apply a separate local search process to refine the individuals of the population. An important aspect concerning Memetic Algorithms is the trade-off between the exploration abilities of the Genetic Algorithm, and the exploitation abilities of the local search process used.

A common way to use the local search process is to refine the solutions obtained by crossover and mutation with a low probability. Most Memetic Algorithms use efficient local search process, such as Quasi-Newton, conjugate gradient, SQP, random linkage, and Solis and Wet, to refine the solutions. However, a more recent idea is to use recombination operators as the move operator for the local search process.

We are developing models that adapt the balance between the Genetic Search and the Local Search to the tackled problem.

Ant Colony Optimization is a metaheuristic inspired by the shortest path searching behavior of several ant species. Ants are social insects that live in colonies and that, thanks to their collaborative interaction, are capable of showing complex behaviors and to perform difficult tasks from an ant's local perspective. A very interesting aspect of the behavior of several ant species is their ability to find shortest paths between the ants' nest and the food sources. This fact is specially noticeable having in mind that, in many ant species, ants are almost blind, which avoids the exploitation of visual clues.

While walking between their nest and food sources, some ant species deposit a chemical called pheromone (an odorous substance). If no pheromone trails are available, ants move essentially at random, but in the presence of pheromone they have a tendency to follow the trail. In practice, choices between different paths occur when several paths intersect. Then, ants choose the path to follow by a probabilistic decision biased by the amount of pheromone: the stronger the pheromone trail, the higher its desirability. Because ants in turn deposit pheromone on the path they are following, this behaviour results in a self-reinforcing process leading to the formation of paths marked by high pheromone concentration. This behavior also allows ants to identify shortest paths between their nest and the food source.

We are currently interested in models for order based problems. Particularly, we study the application of Ant Colony Optimization Process to Multi-objective order based problems.

© 2007 GABIC - Genetic Algorithms & BIoinspired Computation Webmaster: Carlos García Martínez