×

zbMATH — the first resource for mathematics

Evolutionary algorithms and matroid optimization problems. (English) Zbl 1187.90237
Summary: 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.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bäck, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation. Oxford University Press, London (1997) · Zbl 0883.68001
[2] Balakrishnan, A., Magnanti, T.L., Mirchandani, P.: Designing hierarchical survivable networks. Oper. Res. 46(1), 116–136 (1998) · Zbl 0987.90517
[3] Cunningham, W.H.: Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15(4), 948–957 (1986) · Zbl 0619.68040
[4] 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) · Zbl 1267.68210
[5] Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002) · Zbl 1002.68037
[6] 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)
[7] Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127–136 (1971) · Zbl 0253.90027
[8] Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, 2nd edn. Springer, Berlin (2007) · Zbl 1028.68022
[9] Fischer, S., Wegener, I.: The one-dimensional Ising model: Mutation versus recombination. Theor. Comput. Sci. 344(2–3), 208–225 (2005) · Zbl 1079.68097
[10] 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)
[11] Gabow, H.N., Xu, Y.: Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. Syst. Sci. 53, 129–147 (1996) · Zbl 0859.68041
[12] Gale, D.: Optimal assignments in an ordered set: an application of matroid theory. J. Comb. Theory 4, 176–180 (1968) · Zbl 0197.00803
[13] Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039
[14] 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) · Zbl 1036.68567
[15] 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)
[16] 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)
[17] 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) · Zbl 1297.68022
[18] 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) · Zbl 1112.90068
[19] Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970) · Zbl 0226.90047
[20] 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) · Zbl 0349.05026
[21] 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) · Zbl 0392.90058
[22] Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Applications, 3rd edn. Springer, Berlin (2006) · Zbl 1099.90054
[23] Michail, D.: Minimum cycle basis: algorithms and applications. Ph.D. Thesis, Saarland University (2006) · Zbl 1143.05310
[24] Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006) · Zbl 1173.90535
[25] Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32–40 (2007) · Zbl 1117.68090
[26] Oxley, J.G.: Matroid Theory. Oxford University Press, London (1992) · Zbl 0784.05002
[27] Rado, R.: Note on independence functions. Proc. Lond. Math. Soc. 7(3), 300–320 (1957) · Zbl 0083.02302
[28] Raidl, G.R., Julstrom, B.A.: Edge sets: An effective evolutionary coding of spanning trees. IEEE Trans. Evol. Comput. 7(3), 225–239 (2003) · Zbl 05452072
[29] Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Trans. Evol. Comput. 10(2), 145–156 (2006) · Zbl 05452074
[30] 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) · Zbl 1073.68080
[31] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[32] 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)
[33] Wegener, I.: Towards a theory of randomized search heuristics. In: Proc. of Mathematical Foundations of Computer Science (MFCS’03), pp. 125–141 (2003) · Zbl 1124.68434
[34] Wegener, I.: Randomized search heuristics as an alternative to exact optimization. In: Lenski, W. (ed.) Logic versus Approximation, pp. 138–149 (2004) · Zbl 1099.68743
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.