論混合尺度、順序與對象：對第二代相依結構矩陣基因演算法的三個優化

Trimming, Ordering, and Similarity Check: Three Improvements for DSMGA-II

黃靖中(Ching-Chung Huang)

指導教授 ： 于天立

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

https://doi.org/10.6342/NTU202203689

摘要

第二代相依結構矩陣基因演算法(DSMGA-II)乃當代最先進之建模式基因演算法之一，能高效處理二元組合優化問題。算法特點是會按當前族群預判一系列基因模塊，並以各基因模塊為基因交換單元，進行最優混合試驗。此論文針對DSMGA-II的模塊機制提出三點改進：一、動態設定模塊大小上界；二、動態調整模塊試驗順序；三、提出相似性檢驗限制差異過大之子群間交換基因。過大之模塊不但可能導致族群過早收斂，試驗成功機率也非常低，故適時止損試驗過大模塊，將可減少不必要之函數求值成本。另外，在DSMGA-II中模塊測試順序是由小至大的，但吾人應優先試驗高成功機率之模塊，此乃動態調整模塊試驗順序之初衷。最後，若演化過程出現多個差異過大之子群，而子群間的基因交換會打亂基因模塊訊號，則限制此種基因交換，將有助於演化。有鑑於此，提出了相似性檢測。實驗顯示，提出的三個機制都各自能為DSMGA-II帶來進步，且彼此相容。消融實驗亦表明，此三機制缺一不可。最後，規模性實驗說明了此三機制能有效拓展到更多變數的問題上。

關鍵字

演化式算法 ； 建模式基因演算法 ； 最優混合 ； 第二代相依結構矩陣基因演算法

並列摘要

The dependency structure matrix genetic algorithm II (DSMGA-II) is one of the state-of-the-art model-building genetic algorithms capable of solving combinatorial optimization problems by exploiting the underlying structures of the problems. The linkage model generates a series of masks for trial to recombine genes among chromosomes via optimal mixing. This thesis proposes three improvements that adaptively adjust the scope, the order, and the receivers of trials. Specifically, the mean of the mask sizes from previous successful recombinations limits the maximum sizes of later trials. Also, successful recombinations prioritize the corresponding mask sizes of trials. Finally, the proposed similarity check confines recombinations between similar chromosomes. The ablation study indicates that each proposed technique is indispensable. Combined with these three improvements, DSMGA-II empirically consumes fewer function evaluations on most test problems.

並列關鍵字

Evolutional Algorithm ； Model-building Genetic Algorithm ； Optimal Mixing ； Dependency Structure Matrix Genetic Algorithm II

參考文獻

[1] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. In Proceedings of the 14th annual conference on Genetic and evolutionary computation, pages 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. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 745–752, 2017.

[3] 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.

[4] D. E. Goldberg, K. Deb, and J. Horn. Massive multimodality, deception, and genetic algorithms. 1992.

[5] J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, 1992.