臺灣博碩士論文加值系統

雖然基因演算法（Genetic Algorithm, GA）為一著名的求解組合性問題的工具，但面臨過早收斂而陷入了局部最佳化的缺點。類免疫演算法（Artificial Immune System, AIS）與基因演算法一樣具有多點同步搜尋的特性，不同於基因演算法的是，其使用了記憶訓練方式與不同抗體對抗入侵的抗原變化，除了針對抗體與抗原的匹配性，也考慮抗體與抗體之間的關係，能彌補過去基因演算法的系統機制只能針對染色體單純特徵組合求解的缺陷，有鑑於此，本研究混合基因加免疫的演算法(HGIA)，輔以共演化策略改善，並將生命力賦予染色體，作為生存策略，期望在搜尋空間尋找更多樣化的解，另外，為兼顧收斂速度與探索空間，本篇加入了株落選擇機制，以人造複製的T細胞及突變的B細胞共同演化出辨識率更高之抗體，透過此機制之優良探究與探索特性，可求得近似最佳解。本研究求解單目標流程型（Flowshop）排程問題，其績效準則為以總完工時間最小化為目標，因GA之快速收歛特性，故在第一階段以GA進行演化，並於第二階段以HGIA進一步搜尋更寬廣之解空間。研究顯示，本研究所提之TPGIA，在特定問題上可提升原有SGA之求解品質。

In this paper, a Hybrid Genetic-Immune algorithm (HGIA) is developed to solve the flow-shop scheduling problems. The regular genetic algorithm (GA) is applied in the first-stage to rapidly evolve and when the processes are converged up to a pre-defined iteration then the Artificial Immune System (AIS) is introduced to hybridize Genetic Algorithm in the second stage is named HGIA. In the process of co-evolution, GA and AIS cooperates with each other to search optimal solution by searching different objective functions. One is named fitness in GA section and another one is antigen which will evoke the withstanding of antibodies. In the process of fighting, the antibodies evolve till they can resist the antigen. Moreover, an survival strategy is proposed to extend the lifespan of the antibodies to stay in system longer. Finally, Clonal selection is adopted into the infrastructure of AIS which contains certain types of B and T lymphocytes are selected for destruction of specific antigens invading the body. Due to the hybrid of GA and AIS contains two objectives, larger searching space and escaping from local optimal solution will be the superiority for hybridization. In the research, a set of flow-shop scheduling problems are applied for validating the efficiency. The intensive experimental results show the effectiveness of the proposed approach for Flow-shop problems in Production Scheduling.

目錄
摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究方法 3
1.4 研究架構與流程 4
第二章 文獻探討 7
2.1 排程問題 7
2.1.1 排程類型 7
2.1.2 排程的績效目標 9
2.1.3 排程問題的求解方法 11
2.1.4 排程問題之相關研究 13
2.2 基因演算法 15
2.2.1 基因演算法的流程 15
2.2.2 基因演算法的特性及優缺點 17
2.2.3 基因演算法之相關研究 19
2.3 類免疫演算法 21
2.3.1 類免疫演算法的流程 22
2.3.2 類免疫演算法的特性及優缺點 24
2.3.3 類免疫演算法之相關研究 26
2.4 基因演算法與類免疫演算法之異同點 27
2.5 共演化之相關研究 28
第三章 問題定義與介紹 30
3.1 流程型排程介紹 30
3.2 流程型排程之績效衡量準則 31
3.3 流程型排程測試案例 32
3.3.1 Taillard流程型排程測試資料 32
3.3.2 Reeves流程型排程測試資料 33
3.4 流程型排程問題之範圍限制與假設 33
第四章 研究方法 35
4.1 免疫系統親和力計算方式 38
4.2 TPGIA演算流程 40
4.3 欲比較之演算法介紹 49
第五章 實驗結果與分析 51
5.1 於Taillard測試案例之流程型排程問題 51
5.1.1 Taillard測試案例之參數設計 51
5.1.2 求解於Taillard測試案例之實驗結果與效益評估 52
5.2 於Reeves測試案例之流程型排程問題 57
5.2.1 Reeves測試案例之參數設計 57
5.2.2 求解於Reeves測試案例之實驗結果與效益評估 58
5.3 綜合討論與分析 62
第六章 結論與未來展望 64
6.1 結論 64
6.2 未來展望 66
參考文獻 68
附錄A. Taillard測試案例之實驗設計 73
A.1 SGA於Taillard測試案例之參數設計與實驗結果 73
A.1.1 SGA於Taillard測試案例(同Ruiz等人[37]執行次數)之實驗設計 73
A.1.2 SGA於Taillard測試案例(同Lian等人[27]執行次數)之實驗設計 75
A.2 TPGIA於Taillard測試案例之參數設計與實驗結果 77
A.2.1 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)之實驗設計 78
A.2.2 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)之實驗設計 80
附錄B. Reeves測試案例之實驗設計 83
B.1 SGA於Reeves測試案例之參數設計與實驗結果 83
B.2 TPGIA於Reeves測試案例之參數設計與實驗結果 85
附錄C. 於Taillard測試案例在流程型排程問題上之實驗結果 89
C.1 各方法於Taillard測試案例(同Ruiz等人[37]執行次數)之實驗結果 89

表目錄
表2-1 生產排程類型說明 8
表2-2 排程績效目標 10
表2-3 排程績效目標分類 11
表2-4 求解排程問題法則 12
表2-5 排程之相關研究 14
表2-6 基因演算法與類免疫演算法之比較 27
表3-1 工件加工時間表 32
表4-1 四個工件於兩部機台之加工時間 39
表4-2 抗體基因資訊之優勢矩陣 45
表4-3 位置2之每個工件的機率及累加機率 46
表4-4 基因位置之投票結果 49
表4-5 位置3之每個工件的機率及累加機率 50
表5-1 於Taillard測試案例之建議參數 52
表5-2 於Taillard測試案例之最大搜尋次數 52
表5-3 於Taillard測試案例(同Ruiz等人[37]執行次數)之實驗結果 53
表5-4 於Taillard測試案例(同Ruiz等人[37]執行次數)之平均誤差率（%） 54
表5-5 於Taillard測試案例(同Ruiz等人[37]執行次數)ANOVA分析 54
表5-6 於Taillard測試案例(同Lian等人[27]執行次數)之實驗結果 56
表5-7 於Taillard測試案例(同Lian等人[27]執行次數)之平均誤差率（%） 56
表5-8 於Taillard測試案例(同Lian等人[27]執行次數)ANOVA分析 57
表5-9 於Reeves測試案例之建議參數 57
表5-10 於Reeves測試案例之最大搜尋次數 57
表5-11 於Reeves測試案例之實驗結果 58
表5-12 於Reeves測試案例之平均誤差率（%） 59
表5-13 於Reeves測試案例ANOVA分析 59
表6-1 各方法之特色及優缺點 65
表A-1 SGA於Taillard測試案例之因子設計 73
表A-2 SGA於Taillard測試案例(同Ruiz等人[37]執行次數)ANOVA分析 74
表A-3 SGA於Taillard測試案例(同Ruiz等人[37]執行次數)之參數設定 75
表A-4 SGA於Taillard測試案例(同Lian等人[27]執行次數)ANOVA分析 76
表A-5 SGA於Taillard測試案例(同Lian等人[27]執行次數)之參數設定 77
表A-6 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)之因子設計 78
表A-7 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)ANOVA分析 78
表A-8 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)之參數設定 80
表A-9 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)之因子設計 80
表A-10 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)ANOVA分析 81
表A-11 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)之參數設定 82
表B-1 SGA於Reeves測試案例之因子設計 83
表B-2 SGA於Reeves測試案例ANOVA分析 83
表B-3 SGA於Reeves測試案例之參數設定 85
表B-4 TPGIA於Reeves測試案例之因子設計 86
表B-5 TPGIA於Reeves測試案例ANOVA分析 86
表B-6 TPGIA於Reeves測試案例之參數設定 88

圖目錄
圖1-1 研究架構圖 6
圖2-1 基因演算法基本流程圖 16
圖2-2 類免疫演算法示意圖 22
圖2-3 抗原與抗體結合示意圖 23
圖3-1 排列式流程型排程示意圖 31
圖3-2 排列式流程示意圖 32
圖4-1 TPGIA演算流程圖 36
圖4-2 抗原（ ）與抗體（ ）間親和力計算解說圖 38
圖4-3 親和力計算 39
圖4-4 順序編碼模式 40
圖4-5 順序編碼之雙點交配 42
圖4-6 順序編碼之移動式突變 42
圖4-7 參與投票的六條抗體資訊 45
圖4-8 株落選擇示意圖 47
圖4-9 AC2GA演算流程圖 50
圖5-1 SGA、AC2GA及TPGIA在案例ta021之收斂圖 55
圖5-2 SGA、AC2GA及TPGIA在案例ta081之收斂圖 55
圖5-3 SGA、AC2GA及TPGIA在案例rec27之收斂圖 60
圖5-4 (a)~(f) SGA、AC2GA及TPGIA於Reeves各問題上之收斂圖 61
圖A-1 SGA於Taillard測試案例(同Ruiz等人[37]執行次數)之主效應圖 74
圖A-2 SGA於Taillard測試案例(同Ruiz等人[37]執行次數)之交互作用圖 75
圖A-3 SGA於Taillard測試案例(同Lian等人[27]執行次數)之主效應圖 76
圖A-4 SGA於Taillard測試案例(同Lian等人[27]執行次數)之交互作用圖 77
圖A-5 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)之主效應圖 79
圖A-6 TPGIA於Taillard測試案例(同Ruiz等人[37]執行次數)之交互作用圖 79
圖A-7 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)之主效應圖 81
圖A-8 TPGIA於Taillard測試案例(同Lian等人[27]執行次數)之交互作用圖 82
圖B-1 SGA於Reeves測試案例之主效應圖 84
圖B-2 SGA於Reeves測試案例之交互作用圖 85
圖B-3 TPGIA於Reeves測試案例之主效應圖 87
圖B-4 TPGIA於Reeves測試案例之交互作用圖 87

1.Aldowaisan, T. and Allahvedi, A. “New heuristics for no-wait flowshops to minimize makespan,” Computers & Operations Research, 30, pp.1219-1231, 2003.
2.Alisantoso, D., Khoo, L.P., Jiang, P.Y., “An immune algorithm approach to the scheduling of a flexible PCB flow shop,” International Journal of Advanced Manufacturing Technology, 22 (11-12), pp. 819-827, 2003.
3.Baker, K. R., Introduction to Sequencing and scheduling, John Wiley & Sons, New York, 1974.
4.Brucker, P., Sceduling algorithms, Springer, Berlin, 1998.
5.Chan, F. T. S., S. H. Chung and P. L. Y. Chan, “Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems,” International Journal of Production Research, 44, pp.523-543, 2006.
6.Chandrasekaran, M., Asokan, P., Kumanan, S., Balamurugan, T., Nickolas, S., “Solving job shop scheduling problems using artificial immune system,” International Journal of Advanced Manufacturing Technology 31 (5-6), pp. 580-593, 2006.
7.Chang, P. C., Chen, S. H., & Lin, K. L., “Two phase subpopulation genetic algorithm for parallel machine scheduling problem,” Expert Systems with Applications, 29(3), 705–712, 2005b.
8.Chang, P. C., Chen, S. H. and Hsieh, J. C., “A Global Archive Sub-Population Genetic Algorithm with Adaptive Strategy in Multi-Objective Parallel-Machine Scheduling Problem,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4221 LNCS - I, pp.730-739, 2006.
9.Chang, P. C., Chen, S. H. and Liu, C. H., “Sub-Population Genetic Algorithm with Mining Gene Structures for Production Scheduling Problems,” Expert Systems with Application, 33(3), 2007.
10.Chang, P. C., Chen, S. H., & Fan, C. Y., “Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems, ” Applied Soft Computing, 8, 767–777, 2007.
11.Chen, C. L., V. S. Vempati and N. Aljaber, “An Application of Genetic Algorithms for Flow Shop Problems,” European Journal of Operational Research, 80(2), pp.389-396, 1995.
12.Cochran, j. k., S. M. Horng and J. W. Fowler, “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines,” Computers & Operations Research, 30, 1087-1102, 2003.
13.Coello Coello, C.A., Rivera, D.C., Cortés, N.C., “Use of an artificial immune system for job shop scheduling,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2787, pp. 1-10, 2003.
14.Endoh, S., Toma, N., Yamada, K., “Immune algorithm for n-TSP,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics 4, pp. 3844-3849, 1998.
15.Engin, O., Döyen, A., “A new approach to solve hybrid flow shop scheduling problems by artificial immune system,” Future Generation Computer Systems 20 (6 SPEC. ISS.), pp. 1083-1095, 2004.
16.Farmer, J. D., Packard, N. H., and Perelson, A.S., “The immune system, adaptation, and machine learning,” Physica, 22D, pp.187-204, 1986.
17.Gangadharan, R. and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp.437-476, 1994.
18.Glass, C. A. and C. N. Potts, “A Comparison of Local Search Methods for Flow Shop Scheduling,” Annals of Operation Research, 63, pp.489-509, 1996.
19.Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
20.Gonzalez F. and Dasgupta D., “Artificial Immune Systems Research in the Last Five Years,” Proceedings of the Congress on Evolutionary Computation Conference, Canberra, 8-12, 2003.
21.Hajela, P., Yoo, J., and Lee, J., “GA based simulation of immune networks applications in structural optimization,” Engineering Optimization, 22, 131-149, 1997.
22.Jerne N. K., “Towards a network theory of the immune system”, COLLECT.ANN.INST.PASTEUR, 125 C (1-2), pp. 373-389, 1974.
23.Jiao, L., Wang, L.,” A Novel Genetic Algorithm Based on Immunity,” IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans. 30 (5), pp. 552-561, 2000.
24.Jinlan, L., Jian, N., ” A hybrid Immune Genetic Algorithm approach to optimize the integrated forward/reverse logistics network for 3PLs,” Proceedings - Third International Conference on Natural Computation, ICNC 2007 3, part. no. 4304787, pp. 609-613, 2007.
25.Kubiak, M., “Distance Metrics and Fitness –Distance Analysis for the Capacitated Vehicle Routing Problem,” Presented at The 6th Metaheuristics International Conference, Vienna, Austria, 2005.
26.Kubota, N., K. Shimojima and T. Fukuda, “The Role of Virus Infection in Virus-Evolutionary Genetic Algorithm,” Evolutionary Computation, Proceedings of IEEE International Conference, pp.182-187, 1996.
27.Lian, Z., “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan,” Applied Mathematics and Computation, 175, pp.773-785, 2006.
28.Mark N., “Meta-Stable Memory in an Artificial Immune Network”, Department of Computer Science, University of Wales, Aberystwyth. UK, 2003.
29.Mellor, P., “A Review of Job Shop Scheduling,” Operation Research Quarterly, 17, pp.294-301, 1992.
30.Muruta, T. and H. Ishibuchi, “Performance Evolution of Genetic Algorithms for Flowshop Scheduling Problems,” Proceedings of 1st IEEE International Conference on Evolutionary Computation, pp.812-817, 1994.
31.Muruta, T. and H. Ishibuchi, “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems,” Proceedings of IEEE International Conference on Evolutionary Computation, pp170-175, 1996
32.Nagar, A., S. S. Heragu, and J. Haddock, “A Branch and Bound Approach for a Two-Machine Flowshop Scheduling Problem,” Journal of the Operational Research Society, 46, pp.721-734, 1995.
33.Neppali, V. R., C. L. Chen and J. N. D. Gupta, “Genetic Algorithms for the Two-stage Bicriteria Flowshop Problem,” European Journal of Operational Research, 95, pp.356-373, 1996.
34.Osman, I. and Potts, C., “Simulated annealing for permutation flow-shop scheduling, ”OMEGA, The International Journal of Management Science, 17(6), pp.551-557, 1989.
35.Parunak, H. V. D., “Characterizing the Manufacturing Scheduling Problem,” Journal of Manufacturing Systems, Vol. 10, pp.241-259, 1991.
36.Reeves, C. R., “Genetic Algorithm for Flowshop Sequencing,” Computers & Operations Research, 22, pp.5-13, 1994.
37.Ruiz, R. and Stützle, T., “A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem,” European Journal of Operational, Research 177(3), pp.2033-2049, 2007.
38.Ruiz, R. et al, “Two new robust genetic algorithms for the flowshop scheduling problem,” OMEGA, the International Journal of Management Science, Accepted for publication, 2004.
39.Sankar, S. S., S. G. Ponnanbalam. and C. Rajendran, “A Multiobjective Genetic Algorithm for Scheduling A Flexible Manufacturing System,” International Journal of Advanced Manufacturing Technology, 22(3-4), pp.229-236, 2003.
40.Shao, X., Chen Z., and Lin X., “Resolution of Multicomponent Overlapping Chromatogram Using An Immune Algorithm and Genetic Algorithm,” Chemometrics and Intelligent Laboratory Systems, 51, 91-99, 2000.
41.Sung, C. S., Y. H. Kim and S. H. Yoon, “A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines,” European Journal of Operational Research, 121, pp.179-192, 2000.
42.Tavakkoli-Moghaddam, R., Rahimi-Vahed, A.R., Mirzaei, A.H. “Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm,” International Journal of Advanced Manufacturing Technology 36 (9-10), pp. 969-981, 2008.
43.Taillard, E., “Benchmarks for basic scheduling problems,” European Journal of Operational Research, 64(2), pp.278-285, 1993.
44.Taillard, E., “Some efficient heuristic methods for the flow shop sequencing problem,” European Journal of Operational Research, 47(1), pp.67-74, 1990.
45.Tazawa, I., Koakutsu, S., and Hirata, H., “An immunity based genetic algorithm and its application to the VLSI floorplan design problem,” IEEE, 417-421, 1996.
46.Timmis J. and Mark N., “A resource limited artificial immune system for data analysis,” knowledge-based system, 14, pp. 121-130, 2001.
47.Valls, V., Ballestín, F., Quintanilla, S., “A hybrid genetic algorithm for the resource-constrained project scheduling problem,” European Journal of Operational Research 185 (2), pp. 495-508, 2008.
48.Wang, C. X. et al, “A novel genetic algorithm based on gene therapy theory,” Transactions of the Institute of Measurement and Control, 28, pp.253-262, 2006.
49.Whitely, D., T. Starkweather and D. Fuquay, “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator,” in Schafer(ed), Proceedings of the Third International Conference for Genetic Algorithms, Morgan Kaufmann PubIishers, Inc., pp.133-140, 1989.
50.Widmer, M. and A. Hertz, “A new heuristic method for the flow shop sequencing problem,” European Journal of Operational Research, 41, pp.186-193, 1989.
51.Xu, X. d. and C. x. Li, “Research on immune genetic algorithm for solving the job-shop scheduling problem,” The International Journal of Advanced Manufacturing Technology, Int J Adv Manuf Technol, 2006.
52.Yong, Z. and N. Sannomiya, “An Improvement of Genetic Algorithms by Search Space Reductions in Solving Large-scale Flowshop Problems,” The Transactions of The Institute of Electrical Engineers of Japan, pp.1010-1015, 2001.
53.Yu, H. et al, “Genetic Algorithm for Single Machine Scheduling with General Early-Tardy Penalty Weights,” American Control Conference, San Diego, USA, 2, pp.885-889, 1999.
54.Zhang, H. f., X. p. Li and P. Zhou, “A Job shop oriented Virus Genetic Algorithm,” Proceedings of the 5th World Congress on Intelligent Control and Automation, pp.15-19, 2004.
55.王培珍，「應用遺傳演算法與模擬在動態排程問題之探討」，碩士論文，中原大學，1995。
56.林我聰，現場排程專家系統-應用個體導向技術建立之研究，資訊與電腦公司出版，1994。
57.林昆霖，「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例」，碩士論文，元智大學，2005。
58.柯惠雯，「結合模擬退火法與禁忌搜尋法在流程式生產排程之應用」，碩士論文，大葉大學，2001。
59.柯瓊惠，「基因演算法結合人造解在生產排程之應用」，碩士論文，元智大學，2007。
60.陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學，2006。
61.黃維，「以類免疫系統法建構垃圾郵件過慮系統之研究」，碩士論文，中原大學，2005。
62.湯璟聖，「動態彈性平行機群排程的探討」，碩士論文，中原大學， 2003。
63.廖子銘，「類免疫演算法於多目標最佳化問題之研究與應用」，碩士論文，大同大學，2001。
64.廖海崴，「機率性類免疫分類演算法之設計與應用」，碩士論文，元智大學， 2007。
65.廖國清，「最佳演算法應用於負載預測及機組排程問題」，博士論文，國立中山大學，2005。
66.蘇建龍，「應用蟻族尋優法進行非相關平行機台排程探討」，碩士論文，屏東科技大學，2005。