在改善平行蟻群演算法的效能中，不同蟻群之間的資訊交換策略是個重要的議題。本研究提出一種以資訊交換策略的概念來提升平行蟻群演算的效能。此資訊交換策略是以費洛蒙矩陣為基礎，並以此基礎提出六種資訊交換策略。更進一步地將六種策略結合最佳解交換策略(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.

[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.