請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36432完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 楊烽正 | |
| dc.contributor.author | Chih-Wei YU | en |
| dc.contributor.author | 余致緯 | zh_TW |
| dc.date.accessioned | 2021-06-13T08:00:38Z | - |
| dc.date.available | 2007-07-26 | |
| dc.date.copyright | 2005-07-26 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-07-22 | |
| dc.identifier.citation | 1
羅中育（2001），田口品質工程應用於模擬退火參數組合之研究-以旅行推銷員問題（TSP）為例，雲林科技大學工業工程與管理研究所碩士論文。 2 Rinnoy Kan, A.H.G., Shmoys, D.B., Lawler, E.L., and Lenstra, J.K.（1987）, “The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization,” John Wiley & Sons Ltd. 3 Tóth, A., Juhos, I., Hemert, J.I., Tezuka, M., and Tann, P.（2003）, “A New Permutation Model For Solving The Graph k-coloring Problem,” Kalmàr Workshop on Logic and Computer Science, pages 189-199. 4 Tóth, A., Juhos, I., and Hemert, J.I.（2004）, “Binary Merge Model Representation of the Graph Colouring Problem,” Evolutionary Computation in Combinatorial Optimization, pages 124-134. 5 Tóth, A., Juhos, I., and Hemert, J.I.（2005）, “Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring,” Evolutionary Computation in Combinatorial Optimization, pages 132-143. 6 Melilhov, A.N., Topchy, A.P., Savelev, O.V., Kureichick, V.M., and Miagkikh, V.V. （1996）, “Some New Features in Genetic Solution of The Traveling Salesman Problem,” Proceedings of ACEDC 1996 PEDC, University of Plymouth, UK. 7 TÖRN, A., ALI, M.M., and VIITANEN S.（1999）, “Stochastic Global Optimization: Problem Classes and Solution Techniques,” Journal of Global Optimization, 14, pages 437 – 447. 8 Freisleben, B., and Merz, P.（1996）, “New Genetic Local Search Operators for The Traveling Salesman Problem,” Department of Electrical Engineering and Computer Science University of Siegen, Germany. 9 Tseng, C.C., Tsai, C.F., and Tsai, C.W.（2004）, “A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem,” Information Sciences, 166, pages 67-81. 10 Carrera, C., Lynch, L.A., and Chatterjee, S.（1996）, “Genetic Algorithms and Traveling Salesman Problems,” European Journal of Operational Research, 93, pages 490-510. 11 Johnson, D.S., and McGeoch L.A.（1995）, “The Traveling Salesman Problems: A Case Study in Local Optimization,” Department of Mathematics and Computer Science, Amherst College. 12 Gong, D., and Ruan X.（2004）, “A Hybrid Approach of GA and ACO for TSP,” Proceeding of the 5th World Congress on Intelligent Control and Automation, pages 2068-2072. 13 Debels, D., Reyck, B.D., Katholieke, R. L., Vanhoucke, M.（2004）, “A Hybrid Scatter Search Electromagnetism Meta-Heuristic for Project Scheduling,” Ghent University, London Business School, Leuven University, Ghent University and Vlerick Leuven Gent Management School, WORKING PAPER. 14 Aarts, E., and Lenstra, J.K.（2003）, “Loacl search in combinatorial optimization,” Princeton University Press. 15 Falkenauer, E.（1998）, “Genetic Algorithms and Grouping Problems,” John Wiley & Sons Ltd. 16 Cochrane, E.M., and Beasley, J.E.（2003）, “The Co-adaptive Neural Network Approach to The Euclidean Traveling Salesman Problem,” Neural Networks, 16, pages 1499-1525. 17 Aldous, J.M., and Wilson, R.J.（2001）, “Graphs and Applications: an introductory approach,” Springer. 18 Wang, L., and Zhang, L.（2004）, “Genetic Ordinal Optimization for Stochastic Traveling Salesman Problem,” Proceeding of the 5th World Congress on Intelligent Control and Automation, pages 2086-2090. 19 Wang, K.P., Hung, L., and Zhou, C.G.（2003）, “Particle Swarm Optimization For Traveling Salesman Problem,” Proceeding of 2nd International Conference on Machine Learning and Cybernetics, pages 1583 – 1585. 20 Kennedy, J., Eberhart R.（1995）, “Particle Swarm Optimization,” Proceedings of the 1995 IEEE International Conference on Neural Networks, IEEE Press, pages 1942 –1948. 21 Helsgaun, K.（2000）, “An Effective Implementation of The Lin-Kernighan Traveling Salesman Heuristic,” European Journal of Operational Research, 126, pages 106-130. 22 Wei, P., Xiong, W., and Zhao J.（2004）, “An Improved Ant Colony Algorithm for TSP,” Proceeding of the 5th World Congress on Intelligent Control and Automation, pages 2263-2267 23 Pidgeon, S. et al.（2002）, “Handbook of Applied Optimization,” Oxford University Press 24 Birbil, S.I.（2002）, “Stochastic Global Optimization techniques”, Department of Industrial engineering, A Dissertation Submitted to the Graduate Faculty of North Carolina State University. 25 Birbil, S.I., and Fang, S.C.（2003）, “An Electromagnetism-like Mechanism for Global Optimization”, Journal of Global Optimization, 25, pages 263 – 282. 26 Birbil, S.I., Fang, S.C., and Sheu, R.L.（2002）, “On the Convergence of a Population-based Global Optimization Algorithm,” Kluwer Academic Publisher. 27 Birbil, S.I., and Feyzioglu O.（2003）, “A Global Optimization Method for Solving Fuzzy Relation Equations,” Erasmus Research Institute of Management, Erasmus University, Department of Industrial Engineering, Galatasaray University. 28 Yang, W.H.（2002）, “A Study on the Intelligent Neural Network Training Using the Electromagnetism Algorithm,” Department of Industrial Engineering and Management, Yuan-Ze University. 29 Yang, W.H.（2002）, “Textile Retail Operation using Electromagnetism Algorithm Based Neural network,” Department of Industrial Engineering and Management, Yuan-Ze University. 30 TSPLIB標竿問題網址：http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html 31 ORLIB標竿問題網址：http://mat.gsia.cmu.edu/COLOR/instances.html | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36432 | - |
| dc.description.abstract | 本研究提出仿電磁吸斥離散優化演算法，求解物件排序優化問題及物件分群優化問題。求解問題包括旅行銷售員問題、裝箱重量均等問題、及節點著色問題。本研究針對物件排序優化問題本研究提出「虛擬映射」和「真實映射」兩種粒子移動模式及四種連續座標值映射成離散值的「離散映射作業」法。至於物件分群優化問題，本研究以區間指派法求解裝箱重量均等問題。針對有容量限制的裝箱重量均等問題提出懲罰函數及嘗試修補機制求解。求解節點著色問題是應用群合併法將節線限制問題轉成物件著色群合併作業的排序問題，最後並以求解物件排序優化法求解。本研究成功地擴展仿電磁吸斥優化演算法的應用範圍，使能求解組合優化問題。研究並測試甚多標竿問題的測試顯示效能甚佳。 | zh_TW |
| dc.description.abstract | This thesis proposes a new heuristic based on Electromagnetic-like mechanism （EM）. The method can be used in object sequencing problem and object grouping problem. It still contains an attraction-repulsion mechanism to move the particles towards the global optimality together. The object sequencing problem includes Traveling Salesman Problem（TSP）. The object grouping problem contains Bin Packing Balance Problem and Vertex Coloring Problem（VCP）. In solving object sequencing problem, the thesis proposes two scenario：Keep Continued and Keep Discritied, and also proposes four methods about Discritied Mapping Operation. In solving object grouping problem, the thesis uses Interval Assignment method to solve Bin Packing Balance Problem. The thesis uses Penalty Function and Repair Method to solve Bin Packing Balance Problem with Limited Capacity. In solving Vertex Coloring Problem, the thesis uses Merge Method（Juhos）and solving object sequencing problem methods.
Some test results about Benchmark problem of these problems are included. The method extends successfully to discrete problems. We hope the thesis introduces EM to more researchers. More researches can be attracted to EM, more problem can be solved by EM. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T08:00:38Z (GMT). No. of bitstreams: 1 ntu-94-R92546014-1.pdf: 1218285 bytes, checksum: fb0868cae8c97c453ad761e050c304e0 (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | 誌謝 i
摘要 ii Abstract iii 目錄 iv 圖目錄 vi 表目錄 vii 中英文名詞對照表 viii 中英文名詞對照表 viii 符號說明 ix 第1章 緒論 1 1.1 研究背景 1 1.2 研究動機 2 1.3 研究目的 3 1.4 研究範疇及流程 4 1.5 章節概要 6 第2章 文獻探討 7 2.1 常見的啟發式演算法 7 2.2 仿電磁演吸斥優化演算法 8 2.3 旅行推銷員問題(Traveling Salesman Problem) 15 2.4 裝箱問題(Bin Packing Problem) 18 2.5 節點著色問題(Vertex Coloring Problem) 21 2.6 常見求解旅行銷售員問題的區域搜尋方法 24 2.7 文獻探討結語 27 第3章 仿電磁吸斥離散優化演算法應用於物件排序與分群優化問題 28 3.1 優化問題介紹 28 3.1.1 物件排序優化問題 28 3.1.2 物件分群優化問題 29 3.2 仿電磁吸斥離散優化演算法求解模式 31 3.3 物件排序問題之仿電磁吸斥離散優化演算法 34 3.3.1 物件排序主流程 34 3.3.2 虛擬映射模式與真實映射模式的差異 46 3.4 仿電磁吸斥離散優化演算法的跳動搜尋作業應用於物件排序 47 3.5 物件分群問題之仿電磁吸斥離散優化演算法 48 3.5.1 求解裝箱重量均等問題的主流程 49 3.5.2 求解有容量限制的裝箱重量均等問題的流程 54 3.5.3 求解節點著色問題的流程 59 3.5.4 群合併法 64 3.5.5 範例展示 73 3.6 小結 78 第4章 系統介紹及範例驗證 80 4.1 仿電磁離散優化系統介紹 80 4.2 自動讀檔動態鏈結庫的功能介紹 90 4.3 旅行銷售員問題範例演練 91 4.4 裝箱問題範例演練 95 4.5 節點著色問題範例演練 97 4.6 標竿問題測試 100 4.7 小結 108 第5章 結論與未來研究建議 109 5.1 結論 109 5.2 未來研究方向與建議 110 參考文獻 111 | |
| dc.language.iso | zh-TW | |
| dc.subject | 物件分群優化問題 | zh_TW |
| dc.subject | 裝箱問題 | zh_TW |
| dc.subject | 旅行銷售員問題 | zh_TW |
| dc.subject | 仿電磁吸斥優化演算法 | zh_TW |
| dc.subject | 節點著色問題 | zh_TW |
| dc.subject | 物件排序優化問題 | zh_TW |
| dc.subject | Electromagnetic Attraction and Repulsion Optimization Algorithm. | en |
| dc.subject | Bin Packing Problem | en |
| dc.subject | Vertex Coloring Problem | en |
| dc.subject | Traveling Salesman Problem | en |
| dc.subject | Object Grouping Problems | en |
| dc.subject | Object Sequencing Problems | en |
| dc.title | 物件排序與分群優化問題之仿電磁吸斥優化演算法 | zh_TW |
| dc.title | An Electromagnetic Attraction and Repulsion Simulated Optimization Algorithm for Object Sequencing and Grouping Problems | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 胡黃德,黃遵鉅,陳正剛 | |
| dc.subject.keyword | 仿電磁吸斥優化演算法,物件排序優化問題,物件分群優化問題,旅行銷售員問題,節點著色問題,裝箱問題, | zh_TW |
| dc.subject.keyword | Electromagnetic Attraction and Repulsion Optimization Algorithm.,Object Sequencing Problems,Object Grouping Problems,Traveling Salesman Problem,Vertex Coloring Problem,Bin Packing Problem, | en |
| dc.relation.page | 113 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-07-22 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 工業工程學研究所 | zh_TW |
| 顯示於系所單位： | 工業工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 未授權公開取用 | 1.19 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。