請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5874完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 楊烽正 | |
| dc.contributor.author | Chan Lee | en |
| dc.contributor.author | 李湛 | zh_TW |
| dc.date.accessioned | 2021-05-16T16:17:57Z | - |
| dc.date.available | 2015-08-26 | |
| dc.date.available | 2021-05-16T16:17:57Z | - |
| dc.date.copyright | 2013-08-26 | |
| dc.date.issued | 2013 | |
| dc.date.submitted | 2013-08-16 | |
| dc.identifier.citation | Catala, A., Jaen, J., & Modioli, J. A. (2007, 25-28 Sept. 2007). Strategies for accelerating ant colony optimization algorithms on graphical processing units. Paper presented at the Evolutionary Computation, 2007. CEC 2007. IEEE Congress on.
Cecilia, J. M., Garcia, J. M., Ujaldon, M., Nisbet, A., & Amos, M. (2011, 16-20 May 2011). Parallelization strategies for ant colony optimisation on GPUs. Paper presented at the Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on. Crainic, TeodorGabriel, & Toulouse, Michel. (2003). Parallel Strategies for Meta-Heuristics. In F. Glover & G. Kochenberger (Eds.), Handbook of Metaheuristics (Vol. 57, pp. 475-513): Springer US. Delevacq, Audrey, Delisle, Pierre, Gravel, Marc, & Krajecki, Michael. (2013). Parallel Ant Colony Optimization on Graphics Processing Units. Journal of Parallel and Distributed Computing, 73(1), 52-61. doi: http://dx.doi.org/10.1016/j.jpdc.2012.01.003 Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41. doi: 10.1109/3477.484436 Hongtao, Bai, Dantong, Ouyang, Ximing, Li, Lili, He, & HaiHong, Yu. (2009, 7-9 Dec. 2009). MAX-MIN Ant System on GPU with CUDA. Paper presented at the Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on. Pedemonte, Martin, Nesmachnow∗, Sergio, & Cancela, Hector. (2011). A survey on parallel ant colony optimization. Applied Soft Computing, 11(71), 5181–5197. doi: 10.1016/j.asoc.2011.05.042 The, x, Van, Luong, Melab, N., & Talbi, E. (2013). GPU Computing for Parallel Local Search Metaheuristic Algorithms. Computers, IEEE Transactions on, 62(1), 173-185. doi: 10.1109/TC.2011.206 Wang, Jiening, Dong, Jiankang, & Zhang, Chunfeng. (2009, 11-14 Aug. 2009). Implementation of Ant Colony Algorithm Based on GPU. Paper presented at the Computer Graphics, Imaging and Visualization, 2009. CGIV '09. Sixth International Conference on. Weihang, Zhu, & Curry, J. (2009, 11-14 Oct. 2009). Parallel ant colony for nonlinear function optimization with graphics hardware acceleration. Paper presented at the Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on. Yang, Feng-Cheng, & Chou, Yon-Chun. (2009). Superior/Inferior Segment-Discriminated Ant System for combinatorial optimization problems. Computers & Industrial Engineering, 57(2), 475-495. doi: http://dx.doi.org/10.1016/j.cie.2007.12.016 林典翰. (2004). 優加劣減螞蟻擇段系統應用於組合問題. 臺灣大學工業工程學研究所學位論文, 臺灣大學. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5874 | - |
| dc.description.abstract | 啟發式演算法為眾所皆知處理高複雜度問題的技術，但仍在現實中的高維度問題下的運算時間上仍有物理的計算瓶頸存在；而近二十多年來，多執行緒(Multi-Thread)的平行運算的程式開發技術儼然已經成了加速演算速度的重要趨勢。因此本研究使用nVDIA的CUDA平行運算開發平台搭配優加劣減蟻拓優化法(Superior/Inferior Segment-Discriminated Ant System,SDAS)來求解旅行銷售員問題(Travelling Salesman Problem)，並針對平行運算搭配SDAS下的不同演算策略進行進一步的研究分析。 | zh_TW |
| dc.description.abstract | The meta-heuristic algorithm, known as a technique coping with high complexity problems, has still been encountered the physical bottleneck calculating under the high dimension problems in realistic problems. Recent twenty years, moreover, the Multi-Thread parallel calculating program developing techniques has obviously became a vital trend accelerating the speed in calculation speed and effeciency of algorithm.
Therefore, the thesis approaches the Travelling Salesman Problem ( TSP ) , based on the CUDA, a parallel computing platform and programming model created by nVDIA, together with the Superior/Inferior Segment-Discriminated Ant System ( SDAS ). This thesis also looks for further research analysis in connection with different algorithm strategies in collection with the CUDA and the SDAS. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-16T16:17:57Z (GMT). No. of bitstreams: 1 ntu-102-R00546022-1.pdf: 4745551 bytes, checksum: 11c0564b1d584530bc581ae1b28c81ca (MD5) Previous issue date: 2013 | en |
| dc.description.tableofcontents | 中文摘要 i
Abstract ii 目錄 iii 圖目錄 v 表目錄 vi 第一章 緒論 1 1.1. 研究背景 1 1.2. 研究動機與目的 2 1.3. 研究範疇與架構 3 1.4. 章節概要 5 第二章 文獻探討 6 2.1. TSP問題 6 2.2. 蟻拓最佳化技術 7 2.3. 平行化演算技術應用於啟發式演算法 11 2.4. 文獻探討結語 14 第三章 旅行銷售員問題及其平行化SDAS蟻拓求解 15 3.1. 旅行銷售員問題定義 16 3.2. SDAS蟻拓求解法 16 3.2.1 較佳較差界限法 17 3.2.2 優加劣減費洛蒙矩陣更新法則 19 3.3. CUDA及平行化設計概念 21 3.3.1. GPU硬體環境 22 3.3.2. GPU Kernel記憶體管理及設計概念 22 3.4. SDAS求解TSP的序列化演算程序設計 24 3.5. SDAS用於TSP平行化設計－途程解建構 26 3.5.1. 途程解建構kernel－設計概念 27 3.5.2. 途程解建構kernel－程式設計 30 3.6. SDAS用於TSP平行化設計－更新費洛蒙矩陣 36 3.6.1. 更新費洛蒙矩陣kernel 36 3.7. 小結 40 第四章 平行化SDAS及範例驗證 41 4.1. 平行化SDAS求解系統實作 41 4.2. 演算法成效分析 42 4.2.1. 平行化SDAS與SDAS之同質性比較 43 4.2.2. 各演算階段的加速結果比較 45 4.2.3. 整體平行化加速結果比較 55 4.2.4. atomic及partition兩種資料存取模式的結果比較 58 4.3. 小結 60 第五章 結論與未來研究建議 62 5.1. 結論 62 5.2. 未來研究建議 63 參考文獻 64 附錄 66 | |
| dc.language.iso | zh-TW | |
| dc.subject | 優加劣減蟻拓優化法 | zh_TW |
| dc.subject | CUDA | zh_TW |
| dc.subject | 平行運算 | zh_TW |
| dc.subject | 蟻拓最佳化技術 | zh_TW |
| dc.subject | 旅行銷售員問題 | zh_TW |
| dc.subject | TSP | en |
| dc.subject | parallelization | en |
| dc.subject | CUDA | en |
| dc.subject | SDAS | en |
| dc.title | 平行演算之優加劣減蟻拓優化法求解旅行銷售員問題 | zh_TW |
| dc.title | Parallel Superior/Inferior Segment-Discriminated Ant System for Travelling Salesman Problems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 101-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 洪一薰,蔡瑞煌,羅士哲 | |
| dc.subject.keyword | CUDA,平行運算,蟻拓最佳化技術,優加劣減蟻拓優化法,旅行銷售員問題, | zh_TW |
| dc.subject.keyword | CUDA,SDAS,TSP,parallelization, | en |
| dc.relation.page | 73 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2013-08-16 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 工業工程學研究所 | zh_TW |
| 顯示於系所單位： | 工業工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-102-1.pdf | 4.63 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。