Effectiveness of Selection Mechanisms on the efficiency of Multi Parent Crossover Operator

Abstract

Multi-parent crossover has been proven its ability to address many of combinatorial optimization problems such as the traveling salesman problem and the vehicle routing problem with time windows. The successful use of multi-parent crossover arises from its abilities to enhance the search performance via utilizing information exchanged by more than two parents and inheriting by offspring. These parents are selected according to one of the selection mechanisms. Selecting the most appropriate parents for a crossover process might leads to improving the effectiveness of genetic algorithm. Therefore, this work investigates the effect of selection mechanism on the efficiency of multi-parent crossover. To test this, seven selection mechanisms have been used; random selection mechanism, roulette wheel mechanism, stochastic universal sampling mechanism, tournament selection mechanism, best selection mechanism, single best-couple random selection mechanism and couple best- single random selection mechanism. The performance of the proposed algorithm is tested using Solomon VRPTW benchmark. The experimental results show the superiority of multi-parent crossover that employs the selection mechanism which selects the outstanding individuals to form most of parents over multi-parent crossover that employ other selection mechanisms. This demonstrates the efficiency of employing best parents in a crossover process that can assist the search process to attain a better solution.