Memetic Algorithms in Combinatorial Optimization

For many combinatorial optimization problems, no effective algorithms capable of finding guaranteed optimum solutions in short time are available. Therefore, powerful heuristics have been developed that give no guarantee to find the optimum but have shown to be highly effective in many test cases. In this research project, a special class of heuristics is investigated. The algorithms under consideration are called memetic algorithms, which are -- roughly speaking -- hybrids of evolutionary algorithms and problem-specific search algorithms, such as greedy heuristics and local search.

In order to provide explanations under which circumstances these memetic algorithms are highly effective, a search space analysis relying on the concept of fitness landscapes is considered, consisting of an autocorrelation analysis and a fitness distance correlation analysis of the peaks in the fitness landscape. The former type of analysis enables a comparison and thus a selection of local search algorithms, while the latter type of analysis provides a guideline for the choice of evolutionary variation operators in the evolutionary meta-algorithm. A preliminary search space analysis has been conducted for five combinatorial optimization problems, namely the traveling salesman problem, the graph bipartitioning problem, the quadratic assignment problem, NK landscapes, and the unconstrained binary quadratic programming problem. Based on the results of the analysis, new memetic algorithms have been developed. Experimental results demonstrate that they are among the best heuristics proposed so far for the five problems.

Optimum of a Traveling Salesman Problem Optimum of a Graph-Bipartitioning Problem

Current research focuses on developing new search space analysis techniques and developing algorithms for combinatorial optimization problems in bioinformatics.

Selected Publications

  • P. Merz and B. Freisleben, "Fitness Landscapes, Memetic Algorithms and Greedy Operators for Graph Bi-Partitioning," Evolutionary Computation, vol. 8, no. 1, pp. 61-91, 2000.
  • P. Merz and B. Freisleben, "Fitness Landscape Analysis and Memetic Algorithms for the Quadratic Assignment Problem," IEEE Transactions on Evolutionary Computation, vol. 4, no. 4, pp. 337-352, 2000.
  • P. Merz and B. Freisleben, "Memetic Algorithms for the Traveling Salesman Problem," Complex Systems, vol. 13, no. 4, pp. 297-345, 2001.