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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Grid-Based Random Walk Crossover for Genetic Algorithms

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

摘要

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.