Main Content

Memetic Algorithms

Artist's impression of a DNA strain.
Photo: Colourbox.de

Some years back, we developed efficient methods for the approximate solution of NP-hard combinatorial optimization problems. Our memetic algorithms combine global, problem-independent and local, problem-dependent search methods. They are among the best performing approaches (in terms of solution quality per computation time) for various combinatorial optimization problems, such as the traveling salesman problem, unconstrained binary quadratic programing, graph bipartioning, and the quadratic assignment problem. We analyzed the fitness landscapes of these problems to understand the characteristics of the problem settings and also the performance of solution approaches.

Recently, we used memetic algorithms to optimize the architecture of a deep neural network to recognize bird species in audio recordings. Our approach won the BirdCLEF 2020 challenge with the best overall result.

Selected Publications

  • Markus Mühling, Jakob Franz, Nikolaus Korfhage, Bernd Freisleben:
    Bird Species Recognition via Neural Architecture Search. CLEF 2020, CEUR Proceedings, Vol. 2696, 2020
    (Winner of BirdCLEF 2020)
  • Peter Merz, Bernd Freisleben:
    Memetic Algorithms for the Traveling Salesman Problem. Complex Systems, 13(4):297-345, 2002
  • Peter Merz, Bernd Freisleben:
    Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming. Journal of Heuristics 8(2): 197-213, 2002
  • Peter Merz, Bernd Freisleben:
    Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning. Evolutionary Computation 8(1): 61-91, 2000
  • Peter Merz, Bernd Freisleben:
    Fitness Landscape Analysis and Memetic Algorithms for the Quadratic Assignment Problem. IEEE Transactions on Evolutionary Computation 4(4): 337-352, 2000
  • Peter Merz, Bernd Freisleben:
    Memetic Algorithms and the Fitness Landscape of the Graph Bi-Partitioning Problem. 5th International Conference on Parallel Problem Solving from Nature, Amsterdam, The Netherlands, LNCS 1498, 765-774, 1998
  • Peter Merz, Bernd Freisleben:
    A Genetic Local Search Approach to the Quadratic Assignment Problem. 7th International Conference on Genetic Algorithms, East Lansing, MI, USA, 465-472, Morgan-Kaufmann, 1997
  • Bernd Freisleben, Peter Merz:
    A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems. International Conference on Evolutionary Computation, Nayoya, Japan, 616-621, 1996
  • Bernd Freisleben, Peter Merz:
    New Genetic Local Search Operators for the Traveling Salesman Problem. 4th International Conference on Parallel Problem Solving from Nature, Berlin, Germany, LNCS 1141, 890-899, Springer, 1996

Further information