Evolutionary algorithms and matroid optimization problems

Loading...
Thumbnail Image

Date

2007-02

Journal Title

Journal ISSN

Volume Title

Publisher

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

Citation