- 期刊
基因演算法成功的一個關鍵因素：何謂“適者”？
A Key Factor in the Success of Genetic Algorithms: What is a Fitter Solution?
摘要
基因演算法是一種基於演化概念的群體式搜尋法。儘管，它已經成功地被應用在解決許多問題上，但仍存在一些問題對基因演算法而言並不容易解。探討究竟是那些問題特性導致基因演算法表現不好，一直是個很重要的研究方向。依循「適者生存，不適者淘汰」之機制，基因演算法會分配較多的取樣給那些比起整個群體平均表現要好的可行解區域，但是如此往往也容易陷入局部最佳解的困境。關鍵在於甚麼樣的可行解才應被視為「適者」？我們猜測待解問題中最佳解與位於最佳解附近的可行解其目標函數值的相對大小在基因演算法搜尋過程中應該是扮演著關鍵的角色。對一個目標函數最大化的問題，傳統的基因演算法是提供越多繁衍後代的機會給那些可使目標函數值越大的可行解；而實際上，對於這類問題的某些例子而言，目前看似表現「平庸」的可行解未來也可能會繁衍出「優秀」的後代。為什麼要捨棄它們呢？為驗證此觀點，本文提出平衡性選擇策略，在目標函數值與適應值之間採取一種非單調式的對映關係，並建構四個函數以測試不同選擇策略下基因演算法的效能。實驗結果支持了我們的猜測也確認了不同的選擇策略適用於不同型態的最佳化問題。最後，本文也採用了著名的Rastrigin函數來測試，以彰顯平衡性選擇之普遍適用性。
並列摘要
Genetic algorithms are a population-based search technique that applies natural selection to mimic evolution. Although, it has been shown to be a promising technique in many applications, there are some problems that genetic algorithms do not perform very well. The study of properties of problems in which genetic algorithms fail is an important topic in genetic algorithms community. Applying the ”survival-of-the-fittest” principle, genetic algorithms allocate more samples to above-average schemata. However, increasing the sampling rate of above-average schemata is apt to trap the search into a local optimal. The key is what kind of solution should be treated as a fitter solution? We conjecture that the function values of solutions in the neighborhood of the optimal solution actually play an important role on the genetic search. In a problem of maximization of an objective function, a traditional GA prefers those solutions that have higher objective function values. Actually, in some instances of this kind of problem, a current moderate solution also may have a greater potential of ”evolving” to a better solution, in the future. Why we discard these moderate solutions rather than exploit them? To verify our conjecture, we implement a genetic algorithm with stabilizing selection that takes a non-monotonic mapping from function values to fitness measures, and construct four functions to evaluate performances of genetic algorithms with different selection strategies. Experiment results corroborate our conjecture and substantiate that different types of selection strategies are suitable for different types of optimization problems. Finally, for demonstrating the wide applicability of stabilizing selection, we also test on a Rastrigin function.