臺灣博碩士論文加值系統

優先順序旅行推銷員問題（Sequential Ordering Problem，SOP），是一個非對稱的旅行推銷員問題（Asymmetric Traveling Salesman Problem）加上優先順序的限制。其定義為：有N個城市，城市與城市間來去的距離並不相等，試找出一條路徑能夠拜訪每一個城市一次，使得該路徑之總距離為最小，並符合拜訪各城市間的優先順序條件。基因演算法（Genetic Algorithms，GAs）的應用領域已相當廣泛，但尚未有學者應用基因演算法於限制條件較為嚴格的規劃模式中，而SOP即是屬於此類問題，因此本研究旨在將Gas應用於求解SOP。
本研究首先設計適用於SOP之基因運算元，再透過田口實驗設計方法（Taguchi Method）得到一最佳參數設定組合，最後以此最佳參數組合測試系統績效，採用TSPLIB中SOP題庫做為測試題目。本研究之基因演算法之績效測試得到誤差率平均10％的結果。

Sequential ordering problem is an asymmetric traveling salesman problem with precedence constraints. Given a set of n nodes and the distances between each pair of nodes, find a path from node 1 to node n with minimal distance, taking the given precedence constraints into account. Each precedence constraint requires that some node i have to be visited before some other node j.
Although Genetic Algorithm has already been used widely today, no scholar has applied Genetic Algorithms in a programming model with straitlaced constraints which sequential ordering problem belongs to. Therefore, the main purpose of this research is to apply Genetic Algorithm on sequential ordering problem.
This research first developed the genetic operators applicable to sequential ordering problem, then found the best parameters through the Taguchi method. It then used the best parameters to test my Genetic Algorithm, using the test problems taken from the TSPLIB, which is a library of traveling salesman and related problem instances. The test result of this research''s Genetic Algorithm has an average error ratio of 10%.

目錄
第一章緒論 1
1.1研究動機 1
1.2問題定義 1
1.3研究目的與方法 2
1.4研究流程 2
1.5相關文獻回顧 4
第二章基因演算法概述 5
2.1簡單基因演算法 5
2.1.1 編碼 6
2.1.2 群體數目及初始群體 7
2.1.3 適應函數 7
2.1.4 遺傳運算元 8
2.1.5 結束法則 9
2.2基因演算法的缺點 10
2.3基因演算法之優點 10
第三章基因演算法應用於SOP 11
3.1問題描述 11
3.2編碼、適應函數 13
3.3初始群體產生方法 14
3.4複製運算元 15
3.5交配運算元 15
3.6突變運算元 17
3.7結束法則 19
3.8輔助策略 20
3.8.1 優生政策 20
3.8.2 移民政策 21
第四章參數穩健性設計 22
4.1田口方法 22
4.1.1 品質特性 22
4.1.2 影響產品或製程績效的因子 23
4.1.3 直交表 23
4.1.4 SN比 23
4.2田口參數設計 24
4.2.1 實驗目的與品質特性 24
4.2.2 控制因子及雜音因子 24
4.2.3 水準設定 25
4.2.4 直交表之選用 29
4.2.5 田口實驗結果之分析 30
第五章系統績效測試 35
5.1實驗環境 35
5.2測試題目 35
5.3績效測試指標 35
5.4績效測試結果 35
第六章結論與建議 37
6.1結論 37
6.2後續研究建議 37
參考文獻 39
附錄一、優先順序網圖強度係數 42
附錄二、水準設定數據 44
附錄三、田口實驗直交表 48
附錄四、田口實驗數據 49
附錄五、確認實驗數據 50
表目錄
表 1 基因演算法中適應函數的擴張方式 7
表 2 TSPLIB-SOP題庫 例題:ESC07 11
表 3 基因演算法與ＳＯＰ專有名詞對照表 12
表 4 田口實驗計畫因子列表 25
表 5 內側直交表的因子、因子代號及其水準 30
表 6 外側直交表的因子、因子代號及其水準 30
表 7 各因子水準的平均SN比 31
表 8 SN比之變異數分析表 32
表 9 績效測試結果 36
圖目錄
圖 1 研究流程 3
圖 2 簡單基因演算法之演化流程 6
圖 3 單點交配示意圖 9
圖 4 單點突變示意圖 9
圖 5 ESC07優先順序網圖 12
圖 6 兩點交配 16
圖 7 單點交配Ⅰ 16
圖 8 單點交配Ⅱ 17
圖 9 單點位移突變 18
圖 10 兩點位移突變 19
圖 11 菁英數目對物種數目的影響 20
圖 12 移民數目對物種數目的影響 21
圖 13 產品/製程參數圖 23
圖 14 群體數目水準實驗結果 26
圖 15 交配率水準實驗結果 26
圖 16 突變率水準實驗結果 27
圖 17 最大演化代數水準實驗結果 27
圖 18 兩種初始群體產生方法之比較 28
圖 19 突變運算元之水準實驗 29
圖 20 因子效果圖 31
公式目錄
公式 1 望小特性SN比 24
公式 2 確認實驗之期望平均值的信賴區間 33
公式 3 誤差率 35
公式 4 N節點可能之最多優先順序網枝數 43
公式 5 優先順序網圖強度係數 43

〔1〕 Bui T. N. and Moon B. R., "A New Genetic Approach for the Traveling Salesman Problem," in Proceedings of the First IEEE Conference on Evolutionary Computation, vol.1, pp.7-12, 1994.
〔2〕 Chyu C. C. and Yeh H. P., "A Tabu Search Heuristic for the Traveling Salesman Problem with Precedence Constraints," Automation ''98 and ICPR Asia Meeting, A2-2, pp.1-6, 1998.
〔3〕 Crefenstette J. J., Gopal R., Rosmaita B. J., and Gucht D. Van, "Genetic Algorithms for the Traveling Salesman Problem," In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp.160-168,1985.
〔4〕 Davis L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
〔5〕 Davis L., "Job shop scheduling with genetic algorithms and their applications," In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp.136-140,1985.
〔6〕 Escudero L. F., Guignard M., and Malik K., "A Lagrangean relax-and cut approach for the sequential ordering problem with precedence constraints," Annals of Operations Research, Vol.50, pp.219-237, 1994.
〔7〕 Fox B. R. and McMahon M. B., "Genetic Operators for Sequencing Problems," Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, 1991.
〔8〕 Forrest S., "Genetic Algorithms: Principles of Natural Selection Applied to Computation," Science, Vol.261, pp.872-878, 1993.
〔9〕 Goldberg D. E., Genetic Algorithms In Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
〔10〕 Goldberg D. and Lingle R., "Alleles, Loci, and the Traveling Salesman Problem," In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp.154-159,1985.
〔11〕 Gambardella L. and Dorigo M., "Hybrid Ant System for the Sequential Ordering Problem," Technical Report IDSIA 11-97,1997.
〔12〕 Mingozzi A., Bianco L., and Ricciardelli S., "Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints," Operations Research, Vol. 45, No. 3, 1997.
〔13〕 Oliver I. M., Smith D. J., and Holland J.R.C., "A Study of Permutation Crossover Operations on the Traveling Salesman Problem," In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp.224-230, 1987.
〔14〕 Shang Y. and Li G., "New Crossover Operation In Genetic Algorithms," IEEE International Conference on Tools for AI, pp.150-153, 1991.
〔15〕 Tamaki H. , Kita H. , and Shimizu N. , "A Comparison Study of Genetic Codings for the Traveling Salesman Problem," in Proceedings of the First IEEE Conference on Evolutionary Computation, vol.1, pp.1-6, 1994.
〔16〕 Whitley D., "The Genitor Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive," In Proceedings of the International Conference on Genetic Algorithms and Their Applications, pp.116-121, 1989.
〔17〕 陳建志，「應用遺傳演算法求解最佳機器人路徑及工件位置」，國立中央大學，碩士論文，民國82年。
〔18〕 徐俊能，「以遺傳基因演算法則解決多目標考量的旅行推銷員問題之研究」，私立大葉工學院，碩士論文，民國83年。
〔19〕 楊宗銘，「遺傳演算法在在多途程排程問題之探討」，私立中原大學，碩士論文，民國84年。
〔20〕 施得旭，「淺談田口式品質工程（上）」，工業材料，117期，pp.93-96，民國85年。
〔21〕 施得旭，「淺談田口式品質工程（下）」，工業材料，119期，pp.100-102，民國85年。
〔22〕 陳柏宏，「應用基因演算法於水火力發電排程問題之研究」，國立台灣工業技術學院，碩士論文，民國85年。
〔23〕 蔡世鵬，「應用基因演算法於微波濾波器之最佳化設計」，國立交通大學，碩士論文，民國85年。
〔24〕 楊家豪，「以遺傳演算法應用於電腦輔助裝配程序規劃問題之研究」，國立台灣大學，碩士論文，民國86年。
〔25〕 蘇朝墩，產品穩健設計 田口品質工程方法的介紹和應用，中華民國品質學會，台北，民國86年6月。
〔26〕 蘇木春、張孝德，機器學習 類神經網路、模糊系統以及基因演算法則，全華科技圖書，台北，民國86年12月。
〔27〕 于正之，「優生遺傳演算法應用於解旅行推銷員問題」，國立中興大學，碩士論文，民國86年。
〔28〕 吳育庭，「應用基因演算法於機組最佳維修平排程」，國立台灣大學，碩士論文，民國86年。
〔29〕 王日昌，「基因演算法在多目標組合最佳化問題之研究」， 國立交通大學，博士論文，民國86年。