Investigation of hungarian mating schemes for genetic algorithms
Chanju Jung, Yong-Hyuk Kim, Yourim Yoon, Byung-Ro Moon · 2014
Mating scheme is the way of selecting two parents to make offspring. It takes effect on the performance of genetic algorithms. In this paper, we investigate mating schemes using the Hungarian method. The schemes include i) minimizing the sum of matching distances, ii) maximizing the sum, and iii) random matching for comparison. We apply the schemes to well-known combinatorial optimization problems, the traveling salesman problem and the graph bisection problem, and analyze how the quality of the best individual changes over generations. Based on the analysis, we finally suggest a new hybrid mating scheme. The suggested scheme showed better performance than the non-hybrid schemes.