Evolutionary algorithms and matroid optimization problems
Joachim Reichel, Martin Skutella · 2007
We analyze the performance of evolutionary algorithms on various matroid optimization problems thatencompass a vast number of efficiently solvable as well as NP-hard combinatorial optimizationproblems (including many well-known examples such as minimum spanning tree and maximum bipartitematching). We obtain very promising bounds on the expected running time and quality of the computedsolution. Our results establish a better theoretical understanding of why randomized searchheuristics yield empirically good results for many real-world optimization problems.