Campus Event Calendar

Event Entry

What and Who

Evolutionary Algorithms and Sorting

Edda Happ
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
AG Audience

Date, Time and Location

Friday, 23 May 2008
30 Minutes
E1 4


We present a simple framework for dealing with search spaces consisting of permutations. To demonstrate its usefulness, we build upon it a simple (1+1)-evolutionary algorithm for one of the most fundamental problems in computer science, namely the problem of sorting n pairwise comparable items. We give a rigorous proof that the optimization time is at most O(n^2) with high probability. Our experimental evaluation shows that it is much better, namely around O(n log n). This compares favorably with the currently best EAs for sorting, for which an optimization time of O(n^2 log n) was proven (Scharnow, Tinnefeld and Wegener (2004)) and one of similar order is observed experimentally in this work.

Our approach has the particular advantage that it does distinguish between wrong and unexplored information. This allows to retrieve partial, correct information even before the optimal solution has been found.


Edda Happ
--email hidden
passcode not visible
logged in users only

Edda Happ, 05/21/2008 19:54
Edda Happ, 05/21/2008 17:30 -- Created document.