max planck institut
informatik
informatik
We consider general purpose algorithms that are often inspired by optimization processes observed in nature. Such algorithms can be easily applied to a wide range of problems without much problem knowledge. The design of such algorithms involves the following steps which makes them easy to apply to a given new problem.
Many general purpose algorithms belong to the field of bio-inspired computation. They follow processes in nature in order to solve optimization or adaptive problems. To imitate the optimization process observed in nature they make use of many random decisions which classifies them as a special class of randomized algorithms. We consider bio-inspired computation methods from a theoretical point of view and give guidelines how to develop good algorithms for applications.
In our work we consider in particular the following topics.
Evolutionary algorithms imitate the evolution process observed in nature. They work with a set of search points called the population and produce in each iteration another set of search points called the population by using mutation and crossover operators. Afterwards a new parent population is constituted by selecting good search points from the parents and children. Evolutionary algorithms make use of many random decisions in the mutation and crossover steps. Also the selection step may be randomized with respect of the quality of the different solutions.
Ant colony optimization algorithms are inspired by the search of an ant colony for a
common source of food. The information about which way
to take to get to the food is distributed between the ants by leaving an information,
called pheromone, on the way an ant has taken. As longer paths to the
source take much more time than shorter paths, shorter paths are more
often visited.
Solutions for a
given problem in an ant colony optimization algorithm are obtained by random walks on a so-called construction graph
that has positive values, the pheromone values, on the edges. These
values influence the random walks in the way that edges with large values
have a larger probability of being traversed.
Bio-inspired computation methods have been applied to a wide range of combinatorial optimization problems. Our goal is to understand which combinatorial structures can be optimized by such general algorithms. We investigate general bio-inspired computation approaches and analyze them on classical combinatorial optimization problem in order increase the understanding how these algorithms work on natural problem. On the other hand, we give guidelines to develop better bio-inspired computation methods for problems from combinatorial optimization.
Problems in multi-objective optimization involve the task of optimizing several objective functions simultaneously. Usually, the objective functions are conflicting which implies that the is no single optimal objective value. Therefore, the task is to compute a set of solutions with objective vectors that represent the different trade-offs with respect to the objective functions. One idea which is very popular is compute such solutions by evolutionary algorithms. In this case, the population of an evolutionary algorithm should be evolved into a set of search points that represents the different trade-offs or that gives a good approximation of them.