A new crossover mechanism for genetic algorithms with variable-length chromosomes for path optimization problems

A new crossover mechanism containing two operators is proposed.The new mechanism produces more cross point pairs than same point crossover.Our novel genetic algorithm has a desirable performance. Genetic Algorithm (GA) has found wide application in path optimization problem. In many fields such as navigating system, oil transportation, paths between the starting node and the termination node often have distinct number of relay-nodes, which leads to the corresponding chromosomes would have different length. We refer to chromosomes with non-consistent lengths as the variable-length chromosomes. This paper first investigated GAs with variable-length chromosomes widely used and found that Same Point (SP) crossover is the most popular crossover mechanism. Then, a new crossover mechanism called Same Adjacency (SA) is proposed for GA with variable-length chromosomes for path optimization problem, which outperforms GA with SP by a better search capability as the mathematical analysis shows. The simulation study indicates that GAs with our crossover operators could obtain a better solution, as compared to GAs with SP, while still being able to converge fast in different networks with varied sizes.