利用前置式區域搜尋技術增強機率模型構建式基因演算法之執行效能研究

Abstract

機率模型構建式基因演算法 (probabilistic model building genetic algorithms) 為當前 所可使用的最好的基因與演化演算法之中的一種。然而，於過去的研究文獻中，我們 可以知道，這一種型式的基因演算法和傳統或是一般的基因演算法比起來，通常會需 要比較大的人口數目 (population size) 方能達到預計的效能。此外，根據基因演算法的 性質，在程式開始後最初的幾代，人口中的個體原則上都和隨機產生出來的個體差別 不大。在這樣的情形下，整體而言，此時基因演算法和隨機搜尋演算法 (random search) 幾近相同。為了要解決這樣的問題，並增強機率模型構建式基因演算法之效能，我們 在本計劃中，將發展一種新的人口初始化的程序，以達成目的。 本計劃將採用前置式區域搜尋技術 (prefix local search techniques) 來初始人口，用 以增進機率模型構建式基因演算法之效能。奠基於機率模型構建過程的特性，前置式 區域搜尋技術應當能夠製造出比完全隨機產生的人口，更適合於進行構建機率模型的 初始人口。藉著適當的初始人口，機率模型構建式基因演算法的效率，應當除了在早 期的執行程序可以有所增進以外，整體的執行和解題效能也應該有一定的加強效果。 在本計劃中，我們將採用由 Harik 於 1999 年提出的延伸型緊緻基因演算法 (extended compact genetic algorithm)，做為研究的標的以及機率模型構建式基因演算法之代表。 而在本計劃中提出之新式人口初始化方法，除了可以使用於延伸型緊緻基因演算法， 亦可以使用於其他的機率模型構建式基因演算法以獲得效能之增進。 本研究計劃的主要執行步驟包括以下四項：一、選用適當的區域搜尋技術以融入演 算法之本體，二、決定區域搜尋技術之使用方式，三、對於隨機產生之個體數目與經 由區域搜尋產生之個體數目的比例之研究，四、瞭解使用前置式區域搜尋技術以產生 初始人口對於機率模型構建過程的效果和影響。我們可將本計劃所提出的人口初始化 技術，視為一種效率增進技術，用以增進配合的演算法本身之效能；同時也可以做為 讓我們更能在理論與實務上瞭解機率模型構建過程的工具和平台。