Evolving Populations of Solved Subgraphs with Crossover and Constraint Repair
Pages 133 - 148
Abstract
We introduce a population-based approach to solving parameterized graph problems for which the goal is to identify a small set of vertices subject to a feasibility criterion. The idea is to evolve a population of individuals where each individual corresponds to an optimal solution to a subgraph of the original problem. The crossover operation then combines both solutions and subgraphs with the hope to generate an optimal solution for a slightly larger graph. In order to correctly combine solutions and subgraphs, we propose a new crossover operator called generalized allelic crossover which generalizes uniform crossover by associating a probability at each locus depending on the combined alleles of the parents. We prove for graphs with n vertices and m edges, the approach solves the k-vertex cover problem in expected time using a simple RLS-style mutation. This bound can be improved to by using standard mutation constrained to the vertices of the graph.
References
[1]
Branson, L., Sutton, A.M.: Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems. In: Proceedings of the Sixteenth ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery, New York, NY, USA (2021).
[2]
Coello Coello CA Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art Comput. Methods Appl. Mech. Eng. 2002 191 11–12 1245-1287
[3]
Downey, R.G., Fellows, M.R.: Parameterized Complexiy. Springer, New York (1999).
[4]
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Cham (2006).
[5]
Friedrich, T., Hebbinghaus, N., Neumann, F., He, J., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. In: Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO), London, UK, pp. 797–804. ACM (2007).
[6]
Friedrich, T., et al.: Crossover for cardinality constrained optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). ACM, July 2022.
[7]
Goldberg Jr., D.E., Lingle, R.: Alleles, loci, and the traveling salesman problem. In: Grefenstette, J.J. (ed.) Proceedings of the First International Conference on Genetic Algorithms and their Applications (ICGA), Pittsburgh, PA, USA, vol. 154, pp. 154–159. Lawrence Erlbaum, Hillsdale, NJ (1985)
[8]
Jansen, T., Oliveto, P.S., Zarges, C.: Approximating vertex cover using edge-based representations. In: Neumann, F., Jong, K.A.D. (eds.) Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms (FOGA XII), Adelaide, SA, Australia, 16–20 January 2013, pp. 87–96. ACM (2013).
[9]
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, Held 20–22 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85–103. The IBM Research Symposia Series, Plenum Press, New York (1972).
[10]
Khuri, S., Bäck, T.: An evolutionary heuristic for the minimum vertex cover problem. In: Kunze, J., Stoyan, H. (eds.) Workshops of the Eighteenth Annual German Conference on Artificial Intelligence (KI-1994), pp. 86–90, Saarbrücken, Germany (1994)
[11]
Kratsch S and Neumann F Fixed-parameter evolutionary algorithms and the vertex cover problem Algorithmica 2012 65 4 754-771
[12]
Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, pp. 89–131. Natural Computing Series, Springer, Cham (2020).
[13]
Mitchell, G.G., O’Donoghue, D., Barnes, D., McCarville, M.: GeneRepair - a repair operator for genetic algorithms. In: Late-Breaking Papers at the Genetic and Evolutionary Computation Conference (GECCO), Chicago, IL, USA, pp. 235–239 (2003). http://mural.maynoothuniversity.ie/10351/
[14]
Moraglio, A.: Abstract convex evolutionary search. In: Proceedings of the Eleventh Workshop on Foundations of Genetic Algorithms (FOGA XI). ACM, January 2011.
[15]
Mühlenbein, H.: Parallel genetic algorithms in combinatorial optimization. In: Balci, O., Sharda, R., Zenios, S.A. (eds.) Computer Science and Operations Research: New Developments in their Interfaces, pp. 441–453. Pergamon Press, Amsterdam (1992).
[16]
Neumann, F., Sutton, A.M.: Parameterized complexity analysis of randomized search heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 213–248. Natural Computing Series. Springer, Cham (2020).
[17]
Oliveto PS, He J, and Yao X Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems IEEE Trans. Evol. Comput. 2009 13 5 1006-1029
[18]
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Upper Saddle River (1982)
[19]
Pelikan, M., Kalapala, R., Hartmann, A.K.: Hybrid evolutionary algorithms on minimum vertex cover for random graphs. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), London, UK, pp. 547–554. ACM (2007).
[20]
Radcliffe, N.J.: Forma analysis and random respectful recombination. In: Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA) (1991)
[21]
Spears, W.M., Jong, K.A.D.: On the virtues of parameterized crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA), pp. 230–236 (1991)
[22]
Sutton AM Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem Algorithmica 2021 83 4 1138-1163
[23]
Syswerda, G.: Uniform crossover in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms (ICGA), vol. 3, pp. 2–9 (1989)
Index Terms
- Evolving Populations of Solved Subgraphs with Crossover and Constraint Repair
Index terms have been assigned to the content through auto-classification.
Recommendations
Forbidden Subgraphs and Weak Locally Connected Graphs
A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called $$N^i$$Ni-locally connected if $$G[\{ x\in V(G): 1\le d_G(w, x)\le i\}]$$G[{x?V(G):1≤dG(w,x)≤i}] is connected and $$N_2$$N2-locally connected if $$G[\{uv: \{uw, vw\...
Bipartite subgraphs of triangle-free subcubic graphs
Suppose G is a graph with n vertices and m edges. Let n^' be the maximum number of vertices in an induced bipartite subgraph of G and let m^' be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G)=m^'/m is called the bipartite ...
Factors and vertex-deleted subgraphs
A relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271-277] proved that for even ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
435 pages
ISBN:978-3-031-70070-5
DOI:10.1007/978-3-031-70071-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 September 2024
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024