利用估計適應度函數的計算次數辨識問題結構: 由實務觀點定義建構模塊

Abstract

加強版基因遺傳演算法(competent genetic algorithms) 透過各式各樣不同的機制來辨識基因之間是否存在鏈結(linkage) 並建立模型以解決問題。它們在真實世界中有著不少的應用，但是它們建立出來的模型是否為基因遺傳演算法真正所想要的卻不得而知。本論文提出以適應度函數的計算次數(number of function evaluation, Nfe) 作為評比模型效能的指標，並定義以最少Nfe 解決問題者為最佳模型。組成該模型的建構模塊(building blocks, BBs) 則定義為正確的建構模塊，且定義每一對屬於同一建構模塊的基因之間存在鏈結。基於以上的定義，我們檢視了一些現存用於偵測鏈結的指標函式，像是非線性(non-linearity)、熵(entropy)、同步性(simultaneity) 以及DMC。我們發現，這些指標函式先天上無法辨識某些問題的正確鏈結。於是本論文設計了一個新的指標函式：eNFE ，以補足它們的缺憾。eNFE 是根據建構模塊的新定義而設計，它藉由現存的基因遺 傳演算法理論來估測鏈結所需要的適應度函數計算次數。實驗證實eNFE 成功地幫助現存的指標函式辨識了之前無法正確辨識的鏈結。這個結果提供了一個探討模型建立與鏈結辨識的全新觀點。

Competent genetic algorithms (competent GAs) identify linkages between genes and build models via various mechanisms to solve problems. They have been applied for real world applications, but whether the models given by them match what are really preferred to solve the problems is yet unknown. This thesis proposes using the number of function evaluation (Nfe) to measure the performance of models and defines the optimal model to be the one that consumes the fewest Nfe for GAs to solve a specific problem. Then the building blocks (BBs) that construct the optimal model are defined as the correct BBs, and correct linkages exist between any two genes which locate in the same BB. The capabilities of existing linkage-identification metrics, including non-linearity, entropy, simultaneity and DMC, are compared based on this definition. We find that all these metrics fail to identify correct linkages for some typical problems intrinsically. This thesis then proposes a new metric, named eNFE, directly based on the idea of Nfe to enhance the existing linkage-identification metrics. Experiment results show that eNFE is able to identify correct linkages for examined problems. The preliminary success suggests another view on learning linkage.