族群數可變型基因法則之探討

Abstract

基因法則發展至今已有三十年, 它是一個基於自然界中達爾文的"適者生 存"原則所 發展出的搜尋法則, 能作為解決很多不同問題的最佳化工具, 而且已被證實了在所 知甚少及不規則的解空間中, 能比其他方法更為有 效地搜尋出最佳解。 在很多基因法則的應用中, 族群數目之 決定是很重要的。若是族群數目太少了, 則 族群可能會太快收斂; 若是 族群數目太多了, 等待進步的時間可能得花上許久。在 本篇論文中提出 了族群數可變型基因法則, 在搜尋最佳解的過程中, 族群數目會跟 著變 動。族群數目會根據族群特性而以合理的方式來變動。模擬結果證實了這 種方 法的好處。 Genetic algorithm has been in development for three decades. It is a search algorithm based on the survival-of-the-fittest Darwinian principle in the natural process and could be used as an optimization tool for various problems. It has proved to be particularly effective in searching through poorly understood and irregular spaces. The size of the population can be critical in many applications of genetic algorithm. If the population is too small, the genetic algorithm may converge too quickly; if it is too large, the waiting time for an improvement might be too long. In this thesis, a variant population size genetic algorithm ( VPSGA ) is proposed for maintaining a varying population size in the search process. The population size self- tunes in a reasonable way according to the characteristics of the population. Simulation results are included to demonstrate the advantage of the proposed method.