論相依性結構矩陣遺傳演算法二代之鏈接輔助族群再生機制

Investigating Linkage-assisted Reinitialization on DSMGA-II

林奕昀(Yi-Yun Lin)

指導教授 ： 于天立

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

https://doi.org/10.6342/NTU202203685

摘要

相依性結構矩陣遺傳演算法二代與相依性結構矩陣遺傳演算法二代搭配雙邊圖鏈結模型都是模型建構的遺傳演算法中表現十分好的方法，但是，上述提到的兩個演算法因為首連續一問題的特性，都無法解出該問題。在首連續一問題上，除非前面所有基因的數值都為一，否則一個基因不會對適應度有貢獻，我們將該特性稱為條件式特性。條件式特性在混合時造成了強力的漂變影響，並將位於後面的基因導向錯誤的數值。本篇論文基於相依性結構矩陣遺傳演算法二代，提出利用鏈結輔助的族群再生機制，目的是為了解出具有條件式特性的問題。該再生機制利用固定基因數值保留鏈結資訊，並在利用固定之基因數值重新初始化族群。但是，由於再生機制有可能會固定錯誤的基因數值，所以其中會執行逆轉的運算子來補救錯誤。本篇論文也提出改良的基因位翻轉爬山法，稱為預算基因位翻轉爬山法，是為了更適合提出的再生機制，並修正一個基因的固定數值錯誤。為了要驗證提出再生機制的能力，我們延伸首連續一問題至其他兩個問題，問題分別稱作首連續串接陷阱問題與首連續折疊陷阱問題。將相依性結構矩陣遺傳演算法二代搭配雙邊圖鏈結模型與族群再生機制結合後，相依性結構矩陣遺傳演算法二代搭配雙邊圖鏈結模型可以解決首連續一問題與提出之問題，具有適當的可擴展性之外，在大多數測試問題上的表現也只有些微的影響。

關鍵字

演化式演算法 ； 遺傳演算法 ； 鏈結學習 ； 模型建構 ； 首連續一問題

並列摘要

The dependency structure matrix genetic algorithm II (DSMGA-II) and the two-edge DSMGA-II (DSMGA-IIe) are two of the state-of-the-art model-building genetic algorithms. However, due to the property of LeadingOnes, both DSMGA-II and DSMGA-IIe can not address LeadingOnes well. In LeadingOnes, a bit does not contribute to fitness unless all the bits in front of it are ones. We call the property conditional property. The conditional property causes a strong drift effect during mixing and leads the bits in the rear position to converge to incorrect alleles. This thesis introduces a linkage-assisted reinitialization scheme on DSMGA-IIe to solve problems with such property. The scheme preserves the linkage information by fixing the alleles and reinitializes the population. However, since it is possible to fix the incorrect alleles, the reversal operator is performed to remedy the errors. A modified bit-flipping greedy hill climbing (GHC), called budget GHC, is also proposed to fit the scheme and correct the 1-bit error. To examine the ability of the scheme, we extend LeadingOnes to another two test problems, called leading concatenated trap and leading folded trap. Combining with the scheme, DSMGA-IIe can solve the LeadingOnes and the proposed problems with adequate scalability and only slightly affects the performance on the other benchmark problems.

並列關鍵字

Genetic Algorithm ； Estimation-of-Distribution Algorithm ； Linkage Learning ； Model-building ； LeadingOnes

參考文獻

[1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. Proceedings of the Genetic and Evolution- ary Computation Conference (GECCO ’12), page 585–592, 2012.

[2] P.-L. Chen, C.-J. Peng, C.-Y. Lu, and T.-L. Yu. Two-edge graphical linkage model for DSMGA-II. Proceedings of the Genetic and Evolutionary Computa- tion Conference (GECCO ’17), page 745–752, 2017.

[3] W.-M. Chen, C.-Y. Hsu, T.-L. Yu, and W.-C. Chien. Effects of discrete hill climbing on model building forestimation of distribution algorithms. Proceed- ings of the Genetic and Evolutionary Computation Conference (GECCO ’13), page 367–374, 2013.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, second edition, 2001.

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