Grid-Based Random Walk Crossover for Genetic Algorithms
摘要
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 Chebyshev 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.