- 學位論文
基因演算法中的離線模塊辨認
Off-Line Building Block Identification in Genetic Algorithms
摘要
基因演算法(genetic algorithm)中的建構模塊(building block)時常被誤用。在許多的基因演算法研究中,常誤把適應度函數(fitness function)中可被切割出的單元(sub-problem)視為一個建構模塊。但是事實上,即使一個適應度函數可以被分割成若干互不相干的單元,每個單元也未必形成一個建構模塊。本篇論文從數學模型出發,試圖估計:對於任何一個可被分割的適應度函數,把各個單元視為建構模塊、或不視為建構模塊,分別的效能孰優孰劣。若是視為建構模塊時的效能較佳,則這樣的可分割單元才應該被視為一個建構模塊。最後的目的是,對於任何一個給定的可分割適應度函數,經由本篇論文提出的模型計算之後,都可以鑑定出適性函式中的可分割單元是否形成一個建構模塊。為達此一目的,本篇論文提出兩個模型,分別可以預測基因演算法所需的收斂時間(convergence time)和最小群體大小(minimum population size),而其乘積就是適應度函數計算次數的估計值。實驗結果證明兩個模型在預測收斂時間和最小群體大小上都相當準確。
並列摘要
There is a common misunderstanding about building blocks. It is mistakenly believed that in genetic algorithms, if a fitness function can be separated into independent sub-problems, each sub-problem forms a building block. In this thesis we argue that even if a fitness function can be separated into independent sub-problems, each sub-problem does not necessarily form a building block. This thesis aims at examining if sub-problems in a fitness function form building blocks directly from the fitness function without performing genetic algorithms. To do so, this paper extends the convergence time model and the gambler’s ruin model so they can be applied to a larger variety of problems. With proposed models, the number of fitness evaluations can be estimated for both of these two cases: (1) some genes are transferred together in crossover (treated as a building block); (2) the genes are transferred separately. Therefore, we can compare the number of function evaluations and detect the existence of building blocks for a large family of fitness functions without actually performing a genetic algorithm.