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

Improving DSMGA-II with Two-edge Graphical Linkage Model

陳品霖(Ping-Lin Chen)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704045

摘要

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

關鍵字

演化式演算法 ； 基因演算法 ； 鏈結學習 ； 模型建構

並列摘要

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.

並列關鍵字

Evolutionary Algorithm ； Genetic Algorithm ； Linkage Learning ； Model Building

參考文獻

[1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 585–592, 2012.

[2] F. Chicano, D. Whitley, G. Ochoa, and R. Tinós. Optimizing one million variable nk landscapes by hybridizing deterministic recombination and local search. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 753–760, 2017.

[3] L. Davis. Applying adaptive algorithms to epistatic domains. In Proceedings of the International Joint Conference on Artificial Intelligence, volume 1, pages 162–164, 1985.

[4] K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of mathematics and Artificial Intelligence, 10(4):385–408, 1994.

[5] K.-C. Fan, T.-L. Yu, and J.-T. Lee. Linkage learning by number of function evaluations estimation: Practical view of building blocks. Information Sciences, 230:162–182, 2013.