利用實數模型增進分布估計演算法之效能

Improving EDAs’ Performance by Using Real-valued Models

李瑞庭(Jui-Ting Lee)

指導教授 ： 于天立

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

https://doi.org/10.6342/NTU.2011.00023

摘要

現有的估計分布演算法從變數的對偶相互作用中學習相依性，並藉此建構模型。模型中用來描述變數的關係之特徵函數是為二元函數。 意即，此特徵函數描述了變數之間存在相互作用與否。 然而實驗中可能會發生變數間並非是絕對的有相互作用或無。 本論文提出使用實數特徵函數來描述這樣的模糊性。 在測試問題上，我們檢視了所有可能的二元模型以及實數模型，發現到估計分布演算法使用最佳的實數模型，在效率上會勝過使用最佳的二元模型。 本論文也提出了兩個可以利用實數模型資訊的基因重組演算法，實驗結果說明使用提出的演算法可以減少四分之三的函數估算次數。 此外，本論文也提出了有效找到基於平均信息量之交互作用偵測度量的臨界點的方法以及產生實數模型的方法。 實驗中得知我們提出的基因重組演算法使用了產生的實數模型可以良好運作。

關鍵字

基因遺傳演算法 ； 鏈結辨識 ； 建構模塊 ； 模型建立

並列摘要

Existing estimation of distribution algorithms (EDAs) learn linkages starting from pairwise interactions of variables and construct models from the linkages. The characteristic function of models which indicates the relations among variables are binary. In other words, the characteristic function indicates that there exist or not interactions among variables. Empirically, it can occur that two variables should be sometimes related but sometimes not. This thesis introduces a real-valued characteristic function to illustrate this property of fuzziness. We examine all the possible binary models and real-valued models on test problems. The results show that EDAs using optimal real-valued models outperforms the one using optimal binary models. This thesis also proposes two recombination algorithms which are able to utilize the information provided by real-valued models. Experiments show that the proposed pairwise crossover could reduce function evaluations by three quarters. Moreover, this thesis proposes an effective method to find a threshold for entropy based linkage-learning metric and a method to generate real-valued models. Experiments show that the proposed crossover with generated real-valued models works well.

並列關鍵字

Estimation of Distribution Algorithm ； Linkage Learning ； Building Block ； Model Building

參考文獻

[1] R. Etxeberria and P. Larra˜naga. Global optimization using bayesian networks.

Proceedings of the Second Symposium on Artificial Intelligence Adaptive Sys-

[2] D. E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem.

Genetic Algorithms and Simulated Annealing, pages 74–88, 1987.

[3] D. E. Goldberg. Genetic algorithms in search, optimization and machine learn-