以雙邊圖鏈結模型改良相依性結構矩陣遺傳演算法二代

Abstract

相依性結構矩陣遺傳演算法二代是一個模型建構的基因演算法，它能夠利用探索問題的子結構來解出許多的最佳化問題。此演算法在許多指標性問題，其中包含兩個現實問題上，已經顯示了比起兩個具有代表性的演算法表現得更加卓越。在這篇論文之中，我提出了一個客製化的模型稱作雙邊圖鏈結模型，這個模型針對了每一個接收者客製化了相對應的遮罩，使得相依性結構矩陣遺傳演算法二代擁有進一步的性能提升。這個新的模型比起原來的版本，提供了夠多種可能的重組方式。為了減少一些不必要的嘗試，這個模型和供給限制的技術一起搭配使用。此外，這篇論文也提供了一個新的技術稱作提早終止判定，些微地增進了重組的效率。結合以上提出的技術，性能在指標性問題的結果上比起原版的相依性結構矩陣遺傳演算法二代有了平均十二個百分點的提升。

DSMGA-II, a model building genetic algorithm, is able to solve optimization problems via exploiting sub-structures of the problem. DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA on several benchmark problems including two real-world problems, Ising spin-glass and MAX-SAT. In this thesis, I propose a customized model called two-edge graphical linkage model, which customizes the recombination masks for each receiver according to its alleles, to further improve the performance of DSMGA-II. The new linkage model provides far more possible linkage combinations than the original version. To reduce unnecessary trails, the two-edge model is combined with the supply bounds from the original model. A new techniques called early stop criterion is also proposed to slightly enhance the efficiency in mixing. Combining these proposed techniques, the empirical results show an average of 12% NFE reduction on the benchmark problems compared with the original DSMGA-II.