Grid-Based Random Walk Crossover for Genetic Algorithms

Chan, Chi Ho; Sim, Kevin; Chapman, Peter; Paechter, Ben

Abstract

Grid-based random walk crossover (GBRWX) for genetic algorithms (GAs) is proposed. In contrast to traditional crossover operators such as one-point, two-point, and uniform crossover, which exchange genes only at fixed positions in the parent chromosomes, GBRWX allows genes to be copied from one position in a parent and placed in a different position in the offspring. This approach mimics biological transposition, where genes can move within or between chromosomes. More specifically , GBRWX arranges two parent chromosomes into a two-dimensional grid and generates offspring through a random walk guided by Cheby-shev distance, encouraging the inheritance of adjacent genes on the grid while allowing the preservation of gene sequences. As a result, GBRWX can produce offspring that traditional crossover operators are not able to generate. The effectiveness of GBRWX is evaluated against different crossover operators on both binary and real-valued optimization problems. Experimental results show that GBRWX leads to better solutions, faster convergence, and greater population diversity. Notably, it successfully solves the deceptive Trap problem, while traditional crossover operators fail to do so. This opens up opportunities to explore adaptive or alternative traversal heuristics in the random walk crossover process tailored to specific problems.

Citation

Chan, C. H., Sim, K., Chapman, P., & Paechter, B. (2025, September). Grid-Based Random Walk Crossover for Genetic Algorithms. Presented at UK Workshop on Computational Intelligence, Edinburgh, UK

• Presentation Conference Type: Conference Paper (published)
• Conference Name: UK Workshop on Computational Intelligence
• Start Date: Sep 3, 2025
• End Date: Sep 5, 2025
• Acceptance Date: Jun 23, 2025
• Deposit Date: Jul 10, 2025
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Series Title: Lecture Notes in Artificial Intelligence
• Keywords: genetic algorithms; crossover operator; random walk
• Publisher URL: https://link.springer.com/conference/ukci
• External URL: https://ukci2025.napier.ac.uk/index.php