DSMGA-II 在具重疊子結構均質環面中的族群大小分析

Abstract

現實世界中的複雜最佳化問題需要適當的問題分解才能克服欺騙性。模型建構基因演算法藉由學習連結資訊來識別底層問題結構。然而，均質環面中的重疊子結構使有效分解單位的邊界在定義上變得不明確。最小穩定最佳解（MSO）用嚴謹的數學定義出問題的通用最小拆解單位，以解決此不明確性。本論文探討最先進的第二代相依結構矩陣基因演算法（DSMGA-II）所需的族群大小。首先，推導 MSO 的大小建立了一個理論上界。然而，DSMGA-II 在演化過程中能藉由模組塊組裝出 MSO，因此可將理論上界進一步下修。其次，分析模組塊的供給係數，建立了一套經實驗驗證的理論族群大小模型。上述分析在定性上可推廣至二維環面，而問題在三維以上則成為 NP-hard。最後，引入神諭框架以建立獨立於演算法的族群大小下界。本論文為評估演化演算法在處理重疊結構問題的複雜度提供堅實的理論基礎。

Complex real-world optimization problems require proper problem decomposition to overcome deception. Model-based genetic algorithms identify underlying problem structures by learning linkage information. However, overlapping substructures within a homogeneous torus obscure the boundaries of effective decomposition units. The minimum stationary optimum (MSO) resolves this ambiguity by mathematically formalizing the atomic units of problem decomposition. This thesis investigates the supply demanded by the state-of-the-art dependency structure matrix genetic algorithm II (DSMGA-II). First, deriving the MSO size establishes a theoretical upper bound. However, assembling the MSO from blocks during evolution tightens this theoretical upper bound. Second, a closed-form supply coefficient establishes a theoretical population sizing model validated empirically. These analyses qualitatively generalize to the two-dimensional torus, whereas the problem becomes NP-hard in three or more dimensions. Finally, an oracle framework is introduced to establish an algorithm-independent supply lower bound. This thesis provides a solid theoretical foundation for evaluating the complexity of evolutionary algorithms on overlapping structures.