臺灣博碩士論文加值系統

粒子群演算法（Particle Swarm Optimization, PSO）是一種擁有群體智慧的演算法，以模擬鳥群覓食的行為，讓粒子的每一次移動皆能夠參考其他粒子的移動資訊，以求取全體最佳的解，但由粒子群演算法的編碼方式，並不適用於求解離散型問題。由於傳統的粒子群演算法的維度值是一組連續的實數值，編碼方式不利於求解旅行家問題，故本研究採用權重編碼的方式來代表城市走訪的組合。旅行家問題（Traveling Salesman Problem；TSP）是組合最佳化問題的典型代表，其應用範圍雖廣，解題複雜度卻屬於NP-Complete，因此實務應用上多以啟發式解法(Heuristic)來求得近似解。本研究使用粒子群演算法，搭配權重編碼方式來代表城市走訪的組合，利用粒子群演算法快速收斂的特性，混合貪婪演算法及2-Opt演算法，盼能在求TSP問題的最佳化解答能更精確及穩定。

According Particle Swarm Optimiztion Algorithm, is an swarm intelligence Algorithm. Throught simulate birds behavior,each particle share information each other to reach the best result. But the Particle Swarm Optimiztion Algorithm is good at the continue function,be bad at discrete function. For proofing then Particle Swarm Optimiztion Algorithm can be used at discrete problem, this article combine Particle Swarm Optimiztion Algorithm with 2-Opt algorithm and Greed mtheod to slove Traveling salesman problem. The performance would be superior then the original algorithm.

目錄
論文摘要 I
Abstract II
誌謝辭 III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍與限制 4
第二章 文獻探討 5
2.1 旅行銷售員問題 5
2.1.1 TSP基本定義 5
2.1.2 TSP問題解題法 5
2.2 粒子群演算法(Particle Swarm Optimization) 7
2.2.1 PSO演算法發展背景 7
2.2.2 PSO的運用 9
2.3 粒子權重編碼 10
2.3.1權重編碼操作方式 11
2.3.2權重編碼例題 11
2.4 2-Opt演算法 12
2.4.1 2-Opt演算法操作方式 13
2.5 PSO求解TSP相關文獻 14
第三章 研究方法 15
3.1 貪婪演算法 18
3.1.1貪婪演算法說明 18
3.1.2貪婪演算法虛擬碼 19
3.2 2-Opt演算法 20
3.2.1 2-Opt演算法說明 20
3.2.2 2-Opt演算法虛擬碼 21
3.3 費洛蒙計量表 22
3.3.1 費落蒙計量表說明 22
3.3.2 費落蒙計量虛擬碼 22
第四章 實驗設計 23
4.1 實驗環境 26
4.2 實驗一：採用貪婪演算法進行粒子初始化動作 27
4.2.1測試函數與參數設置 27
4.2.2採用貪婪演算法策略初始化比較實證說明 32
4.3 實驗二：採用粒子權重編碼混合2-Opt演算法 36
4.3.1測試函數與參數設置 36
4.3.2求解能力實證說明 41
4.4 實驗三：採用貪婪演算法進行粒子初始化動作混合2-Opt演算法 45
4.4.1測試函數與參數設置 45
4.4.2求解能力實證說明 50
4.5 實驗四：採用貪婪演算法進行粒子初始化，參照費洛蒙計量表發動2-Opt 54
4.5.1測試函數與參數設置 54
4.5.2求解能力實證說明 59
4.6 實驗結果總結 63
第五章 結論與建議 64
5.1 研究結論 64
5.2 未來研究議題 64
參 考 文 獻 65
圖目錄
圖 2- 1以貪婪演算法選擇路徑 6
圖 2- 2粒子速度與位置搜尋示意圖 9
圖 2- 3 粒子編碼及飛行示意圖 12
圖 2- 4 原始路徑走訪 13
圖 2- 5 發動2-Opt交換後的路徑走訪 13
圖 3- 1 演算法流程圖 17
圖 3- 2 貪婪演算法初始化示意圖 18
圖 3- 3 2-Opt演算法示意圖 20
圖 4- 1 系統畫面 26
圖 4- 2 Burmal14走訪示意圖 28
圖 4- 3 Bays29走訪路徑示意圖 29
圖 4- 4 Berlin52走訪示意圖 30
圖 4- 5 Eil76函數 31
圖 4- 6 Burmal14函數比較分析 33
圖 4- 7 Bays29函數比較分析 33
圖 4- 8 Berlin52函數比較分析 34
圖 4- 9 Eil72函數比較分析 34
圖 4- 10 Burmal14走訪示意圖 37
圖 4- 11 Bays29走訪路徑示意圖 38
圖 4- 12 Berlin52走訪示意圖 39
圖 4- 13 Eil76函數 40
圖 4- 14 Burmal14函數比較測試 42
圖 4- 15 Bays29函數比較測試 42
圖 4- 16 Berlin52函數比較測試 43
圖 4- 17 Eil76函數比較測試 43
圖 4- 18 Burmal14走訪示意圖 46
圖 4- 19 Bays29走訪路徑示意圖 47
圖 4- 20 Berlin52走訪示意圖 48
圖 4- 21 Eil76函數 49
圖 4- 22 Burmal14函數比較測試 51
圖 4- 23 Bays29函數比較測試 52
圖 4- 24 Berlin52函數比較測試 52
圖 4- 25 Eil76函數比較測試 53
圖 4- 26 Burmal14 走訪示意圖 55
圖 4- 27 Bays29走訪路徑示意圖 56
圖 4- 28 Berlin52走訪示意圖 57
圖 4- 29 Eil76函數 58
圖 4- 30 Burmal14函數比較測試 60
圖 4- 31 Bays29函數比較測試 61
圖 4- 32 Berlin52函數比較測試 61
圖 4- 33 Eil76函數比較測試 62
表目錄
表 2- 1 權重編碼示意 7
表 2- 2 PSO解TSP相關文獻 10
表 4- 1 實驗一之測試函數的參數設定 28
表 4- 2 實驗一實證綜合比較 31
表 4- 3 實驗二之測試函數的參數設定 37
表 4- 4 實驗二實證綜合比較 40
表 4- 5 實驗三之測試函數的參數設定 46
表 4- 6 實驗三實證綜合比較 49
表 4- 7 實驗四之測試函數的參數設定 55
表 4- 8 實驗四實證綜合比較 58
表 4- 9 實驗數據總結 63
表 4- 10 實驗數據總結 63

[1]Chia-Feng Juang, “ A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design”,IEEE Transactions on Systems,Man, and Cybernetics,Vol. 34,No 2,2004,pp.997~1006
[2]Eberhart R.C. and Kennedy J. , “A new optimizer using particles swarm theory”, Procceedings of the 1995 IEEE Inernational Conference on Neural Networks,1995,vol. 4,,pp. 1942-48
[3]Farzaneh Afshinmanesh, Alireza Marandi, Ashkan Rahimi-Kian, Member, IEEE” A Novel Binary Particle Swarm Optimization Method Using Artificial Immune System. “, Serbia & Montenegro, Belgrade, November 22-24, 2005, pp. 217~220
[4]Kennedy J. and Eberhart R.C. , “A discrete binary version of the particle swarm algorithm”, Proc.1997 Conf. on Systems,Man, and Cybernetics, Piscataway, 1997,pp. 4104~4109.
[5]Kennedy J. “Stereotyping: improving particle swarm performance with cluster analysis ”,Proceedings of 2000 conference on Evolutionary Computation. Piscatway, N.J.,USA: IEEE,2000,pp. 1507~1512.
[6]Laporte,G., “The Traveling Salesman Problem: A overview of exact of approximate algorithms”,Eupopean Journal of Operational Research,Vol. 59,,1992,ppt. 231~247.
[7]Lin, S. and B. W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,” Oper. Res., Vol.21, No.2, pp. 498-516,1973.
[8]Mohan,C.K. and Al-kazemi , “Discrete particle swarm optimization”,Procedings of the Workshop on Particle Swam Optimizatin 2001,Indianapolis,2001,pp.
[9]Or.I., “Traveling salesman-type Combinatorial Problems and Their Realation on the Logistics of regional Blood Banking”,Ph.D. Dissertation,Northwestern University,1976.
[10]P.LARRANAGA et.al, “Genetic Algorithm for the Travelling Salesman Problem:A Review of Representations and Operators”,Artificial Intelligence Review, Vol. 13,number 2,1999,pp. 129-170.
[11]Shubhra Sankar Ray,Sanghamitra Bandyopadhyay and Sankar K.Pal, “New Operators of Genetic Algorithms for Traveling Salesman Problem”, Proceedings of the 17th International Conference on Pattern Recognition,Vol. 2,,2004,pp.497~500.
[12]Starkweather, T., S. McDaniel, K. Mathias, C. Whitley, and D. Whitley, “A Comparison of Genetic Sequencing Operators”, Proceedings on the Fourth International Conference on Genetic Algorithm,Morgan Kaufmann, publishers, 1991, pp. 69-76.
[13]Takenaka Yoichi and Funabiki Nobuo, “An Improved Genetic Algorithm Using the Convex Hull for Traveling Salesman Problem”, IEEE Transactions on Systems,Man, and Cybernetics,Vol. 3,,1998,pp.2279~2284.
[14]Tillett J, Rao T M, Sahin F, et al. “Darwinian particle swarm optimization”, Proceedings of the 2nd Indian International Conference on Artificial Itelligence. Amsterdam, Holand: Elseriver Publications, 2005, pp. 1474~1487.
[15]Xiaohui Hu,Yuhui Shi and Russ Eberhart, “Recent Advances in Particle Swarm”, IEEE Congress on Evolutionary Computation 2004, Vol. 1,,2004,pp. 90-97.
[16]沈艷、郭兵及古天祥(2005)：粒子群優化算法及與遺傳算法的比較，電子科技大學學報，34卷，5期，pp.696~699。
[17]段曉東、王存睿、劉向東及王楠楠(2002)：基於粒子群信息傳遞模式的混合算法,中國科技論文在線。
[18]高尚、韓斌、吳小俊及楊靜宇(2004)：求解旅行商問題的混合粒子群優化算法，控制與決策期刊，19卷，11期，pp.1286~1289。
[19]郭信川、張健仁及劉清祥(2004)：粒子群演算法於最佳化問題之研究，國立台灣海洋大學。
[20]黃承龍、王良吉及董吉雄(2004)：粒子群最佳化演算法之文獻回顧與研究議題分析，國立第一科技大學資管系。
[21]黃嵐、王康平、周春光、龐巍、董龍江及彭利(2003)：粒子群優化算法求解旅行商問題，吉林大學學報，41卷，4期，pp.477~480
[22]張旭梅(2007)：基於k中心點法的改進粒子群演算法在旅行問題中的應用，計算機集成制造系統，13卷，1期，pp.99~104。
[23]段曉東、王存睿、劉向東及王楠楠(2002)：基於粒子群信息傳遞模式的混合算法，中國科技論文在線。
[24]肖健梅，李軍軍及王錫准(2004)：改進微粒群優化算法求解旅行商問題，計算機工程與用應，40卷，35期，pp.50~52
[25]潭皓，王金兒，何亦征等(2005)：一種基於子群染交機制的粒子群算法求解旅行商問題，系統工程，23卷，4期，pp.83~87
[26]李建億譯(2003)，Richard J. Roiger and Michael W.Geatz著：資料探勘，台北，東華書局發行。
[27]Clerc M. Discrete Particle swarm optimization illustrated by the traveling saleman problem.(2000-01-12). http://ww.mauicelclerc.net.
[28]張祥旺、陳瑞茂、吳忠倫等(2006)：以基因演算法求解多重限制條件之即時排程問題，國立勤益科技大學計中網路組。http://linux2.ncut.edu.tw/wp/?p=10.