自指引遺傳演算法

The Self-Guided Genetic Algorithm

陳世興(Shih-Hsin Chen)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/博士(2008年)

https://doi.org/10.6838/YZU.2008.00241

摘要

過去的具機率模式的演化式演算法 (Evolutionary Algorithm Based on Probabilistic Models, EAPM)先從群體中萃取出基因分佈的資料並建立起機率模型後，然後藉由機率模式產生新解，雖然EAPM在求解不同類型的問題能得到不錯的求解品質，但EAPM在求解順序性問題時間複雜度較高，因此本論文提出自指引遺傳演算法(Self-Guided Genetic Algorithm)，並非透過機率模式產生新解，主要目的是將所建立起的機率模型當作一個評估新解好壞的方法，因為在此機率模式中的聯合機率函數可以計算出此基因順序所帶來的機率值，若機率值高則代表較好的求解品質。因此，此機率模型嵌入在交配與突變運算子，當有新解產生時便透夠此方法新解先行評估其優劣，藉此引導演化的方向。此外，該方法也可以應用在區域搜尋法 (Local Search Method)，當區域搜尋法使用完整搜尋時所需要驗證的鄰近解相當龐大，因此可使用該方法先評估是否值得進行實際的運算，可以避免浪費過多的運算時間於不必要的鄰近解組合。本論文使用的測試例題包含單機與流線型機台排程問題，分別為最小化提早與延遲時間與最小化完工時間，此實驗結果指出自指引遺傳演算法無論在求解品質與運算時間上，都與其他演算法比較有顯著之差異，而當機率模式與區域搜尋法結合時也成為最有效率之演算法，因此將機率模型當作一個評估新解好壞的方法，無論對於演化式演算法或是具機率模式的演算法都將有所助益。

關鍵字

具機率模式演化式演算法 ； 排程

並列摘要

This thesis proposed a Self-Guided genetic algorithm which is one of the algorithms in the category of evolutionary algorithm based on probabilistic models (EAPM). Previous EAPM research explicitly used the probabilistic model from the parental distribution, and then generated solutions by sampling from the probabilistic model without using genetic operators whereas GA employs crossover and mutation operators. Although EAPM is promising in solving different kinds of problems, Self-Guided GA doesn't intend to generate solution by the probabilistic model directly because the time-complexity is high when we solve difficult combinatorial problems, particularly the sequencing ones. In this research, the probabilistic model serves as a fitness surrogate which estimates the fitness of the new solution beforehand. So the probabilistic model is used to guide the evolutionary process of crossover and mutation. When it comes to local search, the fitness surrogate also can be applied in local search and it prunes some bad moves in advance. The hybridization of local search and probabilistic model is named Self-Guided Genetic Local Search. This research studied the single-objective scheduling problems, including the single machine and flowshop scheduling problems. From the experiment results, it shows that the Self-Guided GA outperform other algorithms significantly in terms of solution quality and computational time. Self-Guided Genetic Local Search evens works more efficiently than Genetic Algorithms. As a result, it could be a significant contribution in the branch of EAPM and is of interest for researchers in the field of evolutionary computation.

並列關鍵字

Evolutionary Algorithm with Probabilistic Models ； Scheduling

參考文獻

[44] Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local

[10] Baluja S, Davies S (1997) Using Optimal Dependency-Trees for Combinational Optimization.

[91] Tsutsui S, Pelikan M, Ghosh A (2006) Edge histogram based sampling with local

[22] Chang P, Chen S, Fan C (2008) Mining gene structures to inject arti cial chromosomes

[67] Ono I, Satoh H, Kobayashi S (1998) A real-coded genetic algorithm for function