藉由引入條件難度探討二元最佳化之問題難度

Abstract

在基因遺傳演算法研究中，建構模塊常被用來概略性代表一優化問題的基本組成元素，並且在演化過程中需要盡量減少對其的干擾以在使用最少資源的情況下求得最佳解。但是，如此的說法並沒有一個完整且被認可的數學定義來表述，以至我們對建構模塊和優化問題的難度之間的關係一直缺乏更深入的理解。有鑑於此，在這篇論文中我們提出了上位效應建構模塊分析 (EBBA)，為鏈結以及建構模塊等常見的名詞提供正式的數學定義。另外，透過 EBBA，我們導出一個新的度量來表示優化問題的難度，我們稱之為條件難度。條件難度存在於許多現實世界的優化問題中，且強烈的影響著這些問題的整體求解難度。因此，我們在此篇也提出了對既有的首連續一問題的延伸，稱之為首連續陷阱系列。最後，我們以數據說明優化問題的最大建構模塊大小及其求解難度之間存在正相關。藉此來顯示 EBBA 不僅能用於理論推導以及分析，也具備相當的應用價值。

The term building blocks (BBs) has long been used to vaguely describe the basic components of any given problem such that each component requires the least disruption during the effort of obtaining optimal solutions for the problem. However, even with several previous attempts, there is still no universally approved definition of it. The result is a lack of deeper understanding of how BBs affect the difficulty of various problems. In this thesis, we present the epistatic building block analysis (EBBA), which aims at providing a clear definition of BBs and produces a novel fitness-based linkage model. On top of that, we introduce the conditional difficulty, a new aspect of problem difficulty that can be directly derived with the support of EBBA. Conditional difficulty is a pivotal property that dictates the observed difficulty of some pre-existing test problems, and quite possibly an abundance of real-world ones as well. Finally, we complement the practicality of EBBA by highlighting the strong correlation between sizes of largest BB derived from their constructed linkage models and their required numbers of function evaluations to be solved by DSMGA-IIe, which is among the current state-of-the-art model building genetic algorithms.