分裂性遺傳演算法的研究

Abstract

過去三十多年來，有一個逐漸受到重視的研究領域：演化計算學。這個領 域中有三種成熟的技術：演化策略，演化程式和遺傳演算法。因為它的適 應性佳，遺傳演算法已經被應用在許多問題上例如最佳化問題，設計，控 制，和機器學習。根據新達爾文主義的看法，演化過程可區分為三大類： 平衡性選擇，方向性選擇，和分裂性選擇。過去的所有研究全都是採用方 向性選擇。基於適者生存的原則，傳統的遺傳演算法賦予較多的取樣在看 起來較佳的區域。然而，賦予較多的取樣在看起來較佳的區域並不能保證 能找到最佳解。我們提出一個新的選擇方法：分裂性選擇。這個方法採用 一個與傳統單調適應函數截然不同的非單調適應函數。它賦予較多的機會 給表現優異及差勁的個體而非只偏愛優異的個體。實驗結果顯示分裂性遺 傳演算法採用分裂性選擇的遺傳演算法，可以較快且較可靠的解傳統遺傳 演算法很難解的欺騙性函數。實驗結果亦顯示這個方法可以解傳統遺傳演 算法很難解的一個非欺騙性函數。另外，因為傳統的遺傳演算法會以指數 遞增的方式賦予較多的取樣在看起來較佳的區域，因此很難保持群體的亂 度。分裂性選擇可以有效地減低這個問題。實驗結果顯示分裂性選擇可以 解一個非穩定性問題：最佳解會隨時間而改變。傳統的遺傳演算法因為未 能保持足夠的亂度而無法有效地找到新的目標。另外，我們採用檢驗基因 間影響度的統計量和華西分析法來分析所測試過的問題。同時，建立不同 困難度的問題以測試方向性選擇和分裂性選擇之功效。 During the last thirty years there has been a growing interest in a field called Evolutionary Computation (EC). Three well- defined paradigms are recognized in the field: Evolution Strategies (ES), Evolutionary Programming (EP), and Genetic Algorithm (GA). With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. Applying the survival-of-the-fittest principle, conventional genetic algorithms allocate more trials to observed above-average regions . However, increasing the sampling rate of regions that are observed to be above-average does not gurantee convergence to a global optimum. We propose a novel selection method: disruptive selection. This method adopts a non-monotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional genetic algorithms, this method favors both superior and inferior individuals. Experimental results show that Disruptive Genetic Algorithms (DGA: GA using Disruptive selection) find the optima of deceptive functions more quickly and reliably than GAs using directional selection. Experimental results also show that DGAs easily find the optimal solution of a non-deceptive function that is hard for conventional GAs to optimize. DGAs also can be used to solve a nonstational search problem, where the goal is to track time-varying optima.