論分佈估計演算法中之可視鏈結、有效分佈、與模型刪改

Abstract

分佈估測演算法(Estimation of Distribution Algorithms, EDAs)是一種演化式計算的方法，此種演算法利用建立機率模型的方式去自動偵測決策變數之間的關聯，這種自動判斷決策變數之間關聯的能力，能使最佳化程序以較好的方式搜尋解空間。在這篇論文中，我們探討分佈估測演算法的一個弱點：在最佳化問題中，部份子問題有重要程度不同時，演算法會浪費部份的搜尋在不確定的解空間；由此，我們提出一個改善的方法，我們捨棄一般的完整機率建模，改為只使用完整機率模型中利於有效搜尋的部份，而得到一個節省的搜尋策略。發展出的方法利用統計上的性質去辨認出機率模型中可能對於有效搜尋無幫助的部份，進而刪除之，只使用剩餘的部份模型做解空間的搜尋。實驗結果顯示，所提的方式在部份子問題有重要程度不同時，能夠有效的降低搜尋最佳解所需的代價。

Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that replace the traditional variation operators, such as mutation and crossover, by building a probabilistic model on promising solutions and sampling the built model to generate new candidate solutions. Using probabilistic models for exploration enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, complete and accurate identification of all problem structures by probabilistic modeling is not possible because of certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems composed of structures of unequal fitness contributions. Based on the illustrative example, a notion is introduced that the estimated probabilistic models should be inspected to reveal the effective search directions, and we propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented in the extended compact genetic algorithm (ECGA) and experimented on several sets of problems with different scaling difficulties. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire structure of the problem cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.