基因演算法結合人造解在生產排程之應用

A Genetic Algorithm with Injecting Artificial Chromosomes for Scheduling Problems

柯瓊惠(Chiung-Hui Ko)

指導教授 ： 張百棧

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

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

摘要

機率模式之演化式演算法（Evolutionary Algorithms Based on Probabilistic Models, EAPM）是GA最新的方法，主要是針對基因演算法演化過程中，將有用之隱含資訊萃取出來應用，以彌補基因演算法之不足。因此，本研究提出一機率模式之啟發式演算法加上基因結構的機制－基因演算法結合人造染色體（AC2GA）來解決組合性問題，主要目的是希望能夠加快基因演算法之收斂速度及進一步找到更好之解，而在此人造染色體產生方式是根據母體中適合度前50%之基因位置資訊轉換而成機率矩陣來產生，其中藉由輪盤法（roulette wheel）來指派工件到位置上，如果機率矩陣中有愈高的機率，則其工件被指派到特別的位置機率也愈高，但是也有可能會被指派到其他位置，因而增加其多樣性；在此產生之人造解集合為母體數個，且用系統方法明確萃取統計資訊產生，故不經過交配及突變，為個別之ㄧ世代。本研究用AC2GA來求解單機（Single Machine）與流程型（Flowshop）之排程問題，其績效準則分別為單機排程問題以總提前及總延遲時間最小化為目標；流程型排程問題以總完工時間最小化為目標，並與一些演算法進行比較，以平均誤差率及Duncan之事後配對檢定（post-hoc）為衡量指標，來討論其求解表現。實驗結果顯示，AC2GA在單機排程問題及流程型排程問題之Reeves測試案例上有顯著差異，皆優於SGA。

關鍵字

基因演算法、排程問題、人造染色體、EAPM

並列摘要

Evolutionary algorithms based on probabilistic models is a lastest method. In order to improve the performance, the main goal of our method is to extract potential significant information in evoluation phase of genetic algorithm. Thus, in this thesis, a genetic algorithm with injecting artificial chromosomes(AC2GA) is developed to solve combinatovial problems. The main purpose of this research is to speed up the convergence of GA and it can improve the solution quality significantly. Artificial chromosomes are generated according to a dominance matrix which is transformed from the gene structure of an elite base. A roulette wheel selection method is applied to generate an artificial chromosome by assigning genes onto each position according to the probability matrix. The higher the probability is, the more possible that the gene will show up in that particular position, which is able to diversify the artificial chromosomes. The number of occurrence of artificial chromosomes is population size and use the gene information to generate artificial chromosomes. This research solved the single machine scheduling problems with the objective of minimizing the total deviation and in solving the flowshop scheduling problems with the objective of minimizing the makespan. The experimental results of AC2GA used in this research will be compared with some algorithms and two kinds of performance metrics: post-hoc and average relative error are utilized as the measurement tools. The resalts shows that overall speaking, AC2GA is better than SGA in single machine scheduling problems and flowshop scheduling problems of reeves’s instances significantly.

並列關鍵字

Genetic Algorithm、Scheduling Problems、Artificial Chromosomes、EAPM

參考文獻

72. 陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學，2006。

74. 湯璟聖，「動態彈性平行機群排程的探討」，碩士論文，中原大學， 2003。

1. Affenzeller, M., “New Variants of Genetic Algorithms Applied to Problems of Combinatorial Optimization,” Proceedings of the EMCSR 2002, 1, pp.75-80, 2002.

2. Aldowaisan, T. and Allahvedi, A. “New heuristics for no-wait flowshops to minimize makespan,” Computers & Operations Research, 30, pp.1219-1231, 2003.

3. Allahverdi, A. and J. Mittenthal, “Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time,” Naval Research Logistics, 41, pp.677-682, 1994.