跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/07/31 23:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:郭東諭
研究生(外文):Tung-YuKuo
論文名稱:平行蟻群演算法中基於費洛蒙矩陣整合之資訊交換策略
論文名稱(外文):Parallel Ant Colony System with Information Exchange Based on Pheromone Matrix Integration
指導教授:朱治平朱治平引用關係
指導教授(外文):Chih-Ping Chu
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:65
中文關鍵詞:蟻群演算法平行蟻群演算法資訊交換策略資訊整合旅行銷售員問題
外文關鍵詞:Ant Colony SystemParallel Ant Colony SystemInformation exchange strategyInformation integrationTraveling Salesman Problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:159
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
在改善平行蟻群演算法的效能中,不同蟻群之間的資訊交換策略是個重要的議題。本研究提出一種以資訊交換策略的概念來提升平行蟻群演算的效能。此資訊交換策略是以費洛蒙矩陣為基礎,並以此基礎提出六種資訊交換策略。更進一步地將六種策略結合最佳解交換策略(PACS和MACS [7])產生出新的交換策略。本研究是利用著名的旅行銷售員資料來進行實驗。實驗結果指出本研究提出的六種策略在解旅行銷售員問題上是有效的。並且,當將六種策略結合最佳解交換策略時,會改善僅使用最佳解交換策略的效能。而此效能改善的效果在資料量大的時候更為顯著。
An important issue on improving the performance of parallel ant colony optimization is to explore useful information exchange strategies for sharing information among ant colonies to improve search behavior. This thesis applies the concept of information exchange to enhance the performance of the parallel ant colony system algorithm. The information exchange is based on the pheromone matrix, and this thesis proposes six information exchange strategies for pheromone matrixes integration. Further, these strategies are also combined with the information exchange based on the best solution (PACS and MACS [7]). The experimental studies based on three well-known traveling salesman data sets demonstrate the six strategies have the effectiveness on search. The studies also indicate that combining with the best solution (PACS and MACS) improves the performance of PACS and MACS, particularly in large problem that accomplishes a significant improvement.
LIST OF TABLE VIII
LIST OF FIGURE IX
LIST OF APPENDIX X
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 BACKGROUND AND RELATED WORK 4
2.1 ACO FOR THE TRAVELLING SALESMAN PROBLEM 4
2.2 ANT COLONY OPTIMIZATION 7
2.2.1 Ant System (AS) 7
2.2.2 Ant Colony System (ACS) 8
2.3 PARALLEL ANT COLONY SYSTEM 11
CHAPTER 3 INFORMATION EXCHANGE WITH PHEROMONE MATRIXES INTEGRATION 14
3.1 PHENOMENON EXPLORATION 14
3.2 CONCEPTIONS DESCRIPTION 15
3.3 NOTATIONS 16
3.4 FRAMEWORK PRESENTATION 17
3.5 PROPOSED STRATEGIES 18
3.6 COMBINATIONS WITH PACS AND MACS 24
3.7 ALGORITHM 26
SECTION 4. EXPERIMENTS AND DISCUSSIONS 28
4.1 PARAMETERS SETTING 29
4.2 DEVIATION BETWEEN INTEGER AND DOUBLE 33
4.3 COMPUTATIONAL RESULTS 35
4.4 INFLUENCE OF EXCHANGE STRATEGIES 43
CHAPTER 5 CONCLUSIONS AND FUTURE WORK 47
REFERENCES 49
APPENDIX 54

[1]E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence: from natural to artificial systems: Oxford University Press, USA, 1999.
[2]A. Colorni, M. Dorigo, and V. Maniezzo, Distributed optimization by ant colonies, in F. Varela, P. Bourgine (Eds.), First Eur. Conference Artificial Life, 1991, pp. 134-142.
[3]A. V. Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli, and L. M. Gambardella, Time dependent vehicle routing problem with a multi ant colony system, European Journal of Operational Research, vol. 185, pp. 1174-1191, 2008.
[4]E. G. Talbi, O. Roux, C. Fonlupt, and D. Robillard, Parallel Ant Colonies for the quadratic assignment problem, Future Generation Computer Systems, vol. 17, pp. 441-449, 2001.
[5]H. Kim and S. Kang, Communication-aware task scheduling and voltage selection for total energy minimization in a multiprocessor system using Ant Colony Optimization, Information Sciences, vol. 181, pp. 3995-4008, 2011.
[6]J.-H. Ho, H.-C. Shih, B.-Y. Liao, and S.-C. Chu, A ladder diffusion algorithm using ant colony optimization for wireless sensor networks, Information Sciences, vol. 192, pp. 204-212, 2012.
[7]I. Ellabib, P. Calamai, and O. Basir, Exchange strategies for multiple Ant Colony System, Information Sciences, vol. 177, pp. 1248-1264, 2007.
[8]M. Pedemonte, S. Nesmachnow, and H. Cancela, A survey on parallel ant colony optimization, Applied Soft Computing, vol. 11, pp. 5181-5197, 2011.
[9]M. Middendorf, F. Reischle, and H. Schmeck, Multi Colony Ant Algorithms, Journal of Heuristics, vol. 8, pp. 305-320, 2002.
[10]A. Sameh, A. Ayman, and N. Hasan, Parallel ant colony optimization, International Journal of Research and Reviews in Computer Science, vol. 1, pp. 77-82, 2010.
[11]S.-C. Chu, J. F. Roddick, and J.-S. Pan, Ant colony system with communication strategies, Information Sciences, vol. 167, pp. 63-76, 2004.
[12]G. Reinelt, TSPLIB library, http://www.iwr.uni-heidelberg.de/groups/comopt/software/tsplib95/.25.
[13]K. Menger, Das botenproblem, Ergebnisse eines mathematischen kolloquiums, vol. 2, pp. 11-12, 1932.
[14]D. Johnson, Local optimization and the Traveling Salesman Problem
Automata, Languages and Programming. vol. 443, M. Paterson, Ed., ed: Springer Berlin / Heidelberg, 1990, pp. 446-461.
[15]S. Goyal, A Survey on Travelling Salesman Problem, 2010, pp. 1-9.
[16]M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Trans Syst Man Cybern B Cybern, vol. 26, pp. 29-41, 1996.
[17]M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press, 2004.
[18]M. Dorigo and G. Di Caro, Ant colony optimization: a new meta-heuristic, in Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, Washington, DC, 1999, p. 1477 Vol. 2.
[19]M. Dorigo and L. M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
[20]T. Stützle and H. Hoos, MAX-MIN ant system, Future Generation Computer Systems, vol. 16, pp. 889-914, 2000.
[21]D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing, vol. 6, pp. 563-581, 1977.
[22]M. Dorigo, Parallel ant system: an experimental study, unpublished manuscript, 1993.
[23]M. Bolondi and M. Bondaza, Parallelizzazione di un algoritmo per la risoluzione del problema del commesso viaggiatore, Master's thesis, Politecnico di Milano, Italy, 1993.
[24]M. Randall and A. Lewis, A parallel implementation of ant colony optimization, Journal of Parallel and Distributed Computing, vol. 62, pp. 1421-1432, Sep 2002.
[25]S. Ibri, H. Drias, and M. Nourelfath, A parallel hybrid ant-tabu algorithm for integrated emergency vehicle dispatching and covering problem, International Journal of Innovative Computing and Applications, vol. 2, pp. 226-236, 2010.
[26]K. F. Doerner, R. F. Hartl, and M. Lucka, A parallel version of the D-ant algorithm for the vehicle routing problem, in Proceedings of the International Workshop on Parallel Numerics, 2005, pp. 109-118.
[27]K. F. DOERNER, R. F. HARTL, S. BENKNER, and M. LUCKA, Parallel cooperative savings based ant colony optimization - multiple search and decomposition approaches, Parallel Processing Letters, vol. 16, pp. 351-370, 2006.
[28]J. Fu, L. Lei, and G. Zhou, A parallel Ant Colony Optimization algorithm with GPU-acceleration based on All-In-Roulette selection, in Advanced Computational Intelligence (IWACI), 2010 Third International Workshop on, Suzhou, Jiangsu, 2010, pp. 260-264.
[29]M. Pedemonte and H. Cancela, A cellular ant colony optimisation for the generalised Steiner problem, International Journal of Innovative Computing and Applications, vol. 2, pp. 188-201, 2010.
[30]E. Alba, G. Leguizamón, and G. Ordo˜nez, Analyzing the behavior of parallel ant colony systems for large instances of the task scheduling problem, in Proceedings of the 19th International Parallel and Distributed Processing Symposium, IEEE Computer Society, 2005, p. 14.
[31]E. Alba, G. Leguizamón, and G. Ordo˜nez, Two models of parallel ACO algorithms for the minimum tardy task problem, International Journal of High Perfomance Systems Architecture, vol. 1, pp. 50-59, 2007.
[32]H. Bai, D. OuYang, X. Li, L. He, and H. Yu, MAX-MIN Ant System on GPU with CUDA, in Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on, Kaohsiung, 2009, pp. 801-804.
[33]C. Twomey, T. Stützle, M. Dorigo, M. Manfrin, and M. Birattari, An analysis of communication policies for homogeneous multi-colony ACO algorithms, Information Sciences, vol. 180, pp. 2390-2404, 2010.
[34]I. Iimura, K. Hamaguchi, T. Ito, and S. Nakayama, A Study of Distributed Parallel Processing for Queen Ant Strategy in Ant Colony Optimization, in Parallel and Distributed Computing, Applications and Technologies, 2005. PDCAT 2005. Sixth International Conference on, 2005, pp. 553-557.
[35]Y. Chen, L. Chen, and L. Tu, Parallel ant colony algorithm for mining classification rules, in Granular Computing, 2006 IEEE International Conference on, 2006, pp. 85-90.
[36]O. Roozmand and K. Zamanifar, Parallel Ant Miner 2, in Lecture Notes in Computer Science. vol. 5097, L. Rutkowski, R. Tadeusiewicz, L. Zadeh, and J. Zurada, Eds., ed: Springer Berlin/Heidelberg, 2008, pp. 681-692.
[37]S. Ramón y Cajal, Advice for a young investigator. Cambridge, Mass: MIT Press, 1999.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊