Evolutionary algorithms and matroid optimization problems
Loading...
Date
2007-02
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
We analyze teh performance fo evolutionary algorithms on various matroid optimization problems that encompass a vast number of efficiently solvable as well as NP-hard combinatorial optimization problems (including many well-known examples such as minimum spanning tree and maximum bipartite matching). We obtain very promising bounds on the expected running time and quality of the computed solution. Our results establish a better theoretical understanding of why randomized search heuristics yield empirically good results for many real-world problems.
Description
Table of contents
Keywords
combinatorial algorithms, computations on discrete structures, evolutionary algorithms, matroid intersection, matroids, minimum weight basis, nonnumerical algorithms and problems, randomized search heuristics