Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic Algorithms
Pages 393 - 408
Abstract
Partition Crossover induces lattices over subsets of local optima in the search spaces of classic combinatorial problems such as MAX-SAT and the Traveling Salesman Problem. This paper explores the interaction between Partition Crossover, the lattices that are produced, and various algorithmic decisions. First, we prove that hard selection such as “truncation selection” will make it more difficult to find opportunities to successfully apply Partition Crossover. This suggests that less aggressive forms of selection could be more productive. Second, we consider hybrid genetic algorithms (GAs) that only recombine solutions that are local optima. We prove that hybrid GAs have an inherent bias that makes them more likely to sample other local optima. These two results can inform the design of more effective hybrid evolutionary algorithms.
References
[1]
Canonne, L., Derbel, B.: DRILS revisited: designing perturbation in graybox optimization techniques. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 204-212. Association for Computing Machinery, New York (2022).
[2]
Canonne, L., Derbel, B., Chicano, F., Ochoa, G.: To combine or not to combine graybox crossover and local search? In: GECCO 2023: Genetic and Evolutionary Computation Conference, pp. 257–265. ACM, Lisbon Portugal, Portugal (Jul 2023)., https://inria.hal.science/hal-04379253
[3]
Chen, W., Whitley, D., Tinós, R., Chicano, F.: Tunneling between plateaus: improving on a state-of-the-art MAXSAT solver using partition crossover. In: GECCO Genetic and Evolutionay Computation Conference, pp. 921–928. ACM (2018)
[4]
Chicano, F., Whitley, D., Ochoa, G., Tinos, R.: Optimizing one million variable nk landscapes by hybridizing deterministic recombination and local search. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 753–760. ACM (2017)
[5]
Dunton, P., Whitley, D.: Reducing the cost of partition crossover on large maxsat problems: the px-preprocessor. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 694-702. ACM (2022)
[6]
Goldman BW and Punch WF Chicano F, Hu B, and García-Sánchez P Hyperplane elimination for quickly enumerating local optima Evolutionary Computation in Combinatorial Optimization 2016 Cham Springer 154-169
[7]
Helsgaun K An effective implementation of the lin-kernighan traveling salesman heuristic Eur. J. Oper. Res. 2000 126 1 106-130
[8]
Helsgaun K An effective implementation of the lin-kernighan traveling salesman heuristic Euro. J. Oper. Res. 2000 126 1 106-130
[9]
Helsgaun, K.: DIMACS TSP Challenge Results: Current Best Tours Found by LKH (2013). http://www.akira.ruc.dk/ keld/research/LKH/DIMACS results.html. (24 November 2013)
[10]
Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufman (2004)
[11]
Kauffman, S.: Adaptation on rugged fitness landscapes. In: Stein, D. (ed.) Lectures in the Science of Complexity, pp. 527–618. Addison-Wesley (1989)
[12]
Kauffman S and Levin S Towards a general theory of adaptive walks on rugged landscapes J. Theor. Biol. 1987 128 11-45
[13]
Möbius A, Freisleben B, Merz P, and Schreiber M Combinatorial optimization by iterative partial transcription Phys. Rev. E 1999 59 4 4667-4674
[14]
Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Trick, J. (ed.) Second DIMACS Challenge on Cliques, Coloring and Satisfiability (1993)
[15]
Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: The National Conference on Artificial Intelligence (AAAI), San Jose, CA, pp. 440–446 (1992)
[16]
Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Johnson, D.S., Trick, M.A. (eds.) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. AMS (1996)
[17]
Tinós, R., Whitley, D., Chicano, F.: Partition crossover for pseudo-boolean optimization. In: Foundations of Genetic Algorithms, (FOGA 2015), pp. 137–149 (2015)
[18]
Whitley, D., Chen, W.: Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1357–1364. ACM (2012)
[19]
Whitley, D., Hains, D., Howe, A.: Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 915–922. ACM (2009)
[20]
Whitley D, Hains D, and Howe A Schaefer R, Cotta C, Kołodziej J, and Rudolph G A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover Parallel Problem Solving from Nature, PPSN XI 2010 Heidelberg Springer 566-575
[21]
Whitley, D., Ochoa, G., Chicano, F.: Partition crossover can linearize local optima lattices of k-bounded pseudo-boolean functions. In: Foundations of Genetic Algorithms. ACM (2023)
Index Terms
- Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic Algorithms
Index terms have been assigned to the content through auto-classification.
Recommendations
Partition Crossover for Pseudo-Boolean Optimization
FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIIIA partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be ...
Partition Crossover can Linearize Local Optima Lattices of k-bounded Pseudo-Boolean Functions
FOGA '23: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic AlgorithmsWhen Partition Crossover is used to recombine two parents which are local optima, the offspring are all local optima in the smallest hyperplane subspace that contains the two parents. The offspring can also be organized into a non-planar hypercube "...
Improving artificial neural networks based on hybrid genetic algorithms
WiCOM'09: Proceedings of the 5th International Conference on Wireless communications, networking and mobile computingArtificial neural network (ANN) has outstanding characteristics in machine learning, fault, tolerant, parallel reasoning and processing nonlinear problem abilities. But BP training algorithm is based on the error gradient descent mechanism that the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
442 pages
ISBN:978-3-031-70054-5
DOI:10.1007/978-3-031-70055-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 September 2024
Author Tags
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 13 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in