Two-edge graphical linkage model for DSMGA-II
Ping-Lin Chen, Chun-Jen Peng, Chang-Yi Lu, Tian–Li Yu · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
DSMGA-II, a model-based genetic algorithm, is capable of solving optimization problems via exploiting sub-structures of the problem. In terms of number of function evaluations (NFE), DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA on various benchmark problems as well as real-world problems. This paper proposes a two-edge graphical linkage model, which customizes recombination masks for each receiver according to its alleles, to further improve the performance of DSMGA-II. The new linkage model is more expressive than the original dependency structure matrix (DSM), providing far more possible linkage combinations than the number of solutions in the search space. To reduce unnecessary function evaluations, the two-edge model is used along with the supply bounds from the original DSM. Some new techniques are also proposed to enhance the model selection efficiency. Combining these proposed techniques, the empirical results show an average of 12.2% NFE reduction on eight benchmark problems compared with the original DSMGA-II.