Abstract
We analyze the performance of 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 optimization problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bäck, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation. Oxford University Press, London (1997)
Balakrishnan, A., Magnanti, T.L., Mirchandani, P.: Designing hierarchical survivable networks. Oper. Res. 46(1), 116–136 (1998)
Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15(4), 948–957 (1986)
Dörr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. In: Proc. of the 10th Genetic and Evolutionary Computation Conference (GECCO’08), Atlanta, USA (2008)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002)
Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schönheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69–87. Gordon and Breach, New York (1970)
Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127–136 (1971)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, 2nd edn. Springer, Berlin (2007)
Fischer, S., Wegener, I.: The one-dimensional Ising model: Mutation versus recombination. Theor. Comput. Sci. 344(2–3), 208–225 (2005)
Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: Proc. of the 23rd Annual ACM Symp. on Theory of Computing (STOC’91), New Orleans, USA, pp. 112–122 (1991)
Gabow, H.N., Xu, Y.: Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. Syst. Sci. 53, 129–147 (1996)
Gale, D.: Optimal assignments in an ordered set: an application of matroid theory. J. Comb. Theory 4, 176–180 (1968)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Proc. of the 20th Symp. on Theoretical Aspects of Computer Science (STACS’03), pp. 415–426 (2003)
Giel, O., Wegener, I.: Maximum cardinality matchings on trees by randomized local search. In: Proc. of the 8th Genetic and Evolutionary Computation Conference (GECCO’06), Seattle, USA, pp. 539–546 (2006)
Goemans, M.X.: Minimum bounded degree spanning trees. In: Proc. of the 47th Annual IEEE Symp. on Foundations of Computer Science (FOCS ’06), pp. 273–282 (2006)
Harvey, N.J.A., Karger, D.R., Murota, K.: Deterministic network coding by matrix completion. In: Proc. of the 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 489–498 (2005)
Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM J. Comput. 33(2), 261–268 (2004)
Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970)
Jenkyns, T.A.: The efficiency of the greedy algorithm. In: Proc. of the 7th S-E Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, pp. 341–350 (1976)
Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. In: Alspach, B., Hell, P., Miller, D.J. (eds.) Aspects of Combinatorics. Annals of Discrete Mathematics, vol. 2, pp. 65–74. North-Holland, Amsterdam (1978)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Applications, 3rd edn. Springer, Berlin (2006)
Michail, D.: Minimum cycle basis: algorithms and applications. Ph.D. Thesis, Saarland University (2006)
Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006)
Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32–40 (2007)
Oxley, J.G.: Matroid Theory. Oxford University Press, London (1992)
Rado, R.: Note on independence functions. Proc. Lond. Math. Soc. 7(3), 300–320 (1957)
Raidl, G.R., Julstrom, B.A.: Edge sets: An effective evolutionary coding of spanning trees. IEEE Trans. Evol. Comput. 7(3), 225–239 (2003)
Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Trans. Evol. Comput. 10(2), 145–156 (2006)
Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest path problems. J. Math. Model. Algorithms 3, 349–366 (2004)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Proc. of the 7th Genetic and Evolutionary Computation Conference (GECCO’05), Washington, DC, pp. 1161–1167 (2005)
Wegener, I.: Towards a theory of randomized search heuristics. In: Proc. of Mathematical Foundations of Computer Science (MFCS’03), pp. 125–141 (2003)
Wegener, I.: Randomized search heuristics as an alternative to exact optimization. In: Lenski, W. (ed.) Logic versus Approximation, pp. 138–149 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Center “Computational Intelligence” (SFB 531).
Rights and permissions
About this article
Cite this article
Reichel, J., Skutella, M. Evolutionary Algorithms and Matroid Optimization Problems. Algorithmica 57, 187–206 (2010). https://doi.org/10.1007/s00453-008-9253-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9253-4