基於決策樹學習的變數相依性測定法

Abstract

基因演算法及衍生的演算法在過去的研究與應用裡，已展現了其廣泛而有效率、且具備實用性的特性。為了進一步增進基因演算法的能力，各式的方法在演化式計算的研究領域裡被提出；其中一主要的方向在於找出問題中各項變數彼此間的相依性、藉改善其內部預算子的效率以達到增進整體效率的目的，如 Estimation of Distribution Algorithms、Perturbation-based Methods。 本研究嘗試探討Inductive Linkage Identification和各種不同的決策樹學習演算法搭配下的特性、觀察其在不同實驗設定下展現的效能差異；實驗除了包含了4級(order-4)與5級(order-5)的環形問題結構，也包括了高基數(high cardinality)變數的實驗探討。 實驗結果顯示出在二元(binary)變數的問題裡，各種決策樹學習演散法對類似的問題結構，需要著相同時間複雜度來正確鑑定出其結構；而對於高基數的問題，搭配不同的決策數學習演算法會需要不同的運算資源。

Genetic algorithms and their descendant methods have been deemed robust, effective, and practical for the past decades. In order to enhance the features and capabilities of genetic algorithms, tremendous effort has been invested within the research community of evolutionary computation. One of the major development trends to improve genetic algorithms is trying to extract and exploit the relationship among decision variables, such as estimation of distribution algorithms and perturbation-based methods. In this study, we attempt to investigate the integration of perturbation-based method, inductive linkage identifcation (ILI), and decision tree learning algorithms for detecting general problem structures. Experiments on circular problems structures composed of order-4 and order-5 trap functions are conducted, as well as the experiments on the cardinality of variables. Our experiments results indicates that this approach requires a population size growing logarithmically and is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical and those variables are binary. Experiments also shows that different adopted decision tree learning algorithms will demand different requirements when the variables are extended to higher cardinalities.