在這篇論文，我們提出一個基於熵(entropy)的啟發式參數動態更新規則，並應用這個規則來改善螞蟻族群最佳化求解旅行銷售員問題的效率，我們的演算法也提出使用一個最低的費洛蒙限制。基本上旅行銷售員問題是一個NP-hard問題，在短時間內很難找到ㄧ個最佳解。螞蟻族群最佳化(ACO)是一個新的萬用啟發式演算法且已經成功地被應用在解答組合最佳化問題，螞蟻族群最佳化演算法是來自真實螞蟻行為的觀察，它是仿造螞蟻搜尋食物的過程，當螞蟻搜尋食物的時候，它們依靠之前在經過的路徑上所留下的費洛蒙藉以找到最佳的路徑。雖然螞蟻族群最佳化演算法在最佳化問題有很好的搜尋能力，它仍然有一些缺點如停滯行為、需要長計算時間及過早收斂等。當問題的複雜度增加時，這些缺點將是更明顯的，在我們的實驗結果裡，我們提出的方法可以避免停滯行為和過早收歛。另外實驗的結果也顯示提出的以熵為基礎的啟發式參數動態更新規則，在初始的搜尋階段將產生高品質的路線，這些好的路線可以導引螞蟻朝向有效的解答空間。

In this thesis, we propose a dynamic updating rule for the heuristic parameters based on entropy to improve the efficiency of ant colony optimization (ACO) in solving the traveling salesman problem (TSP). Our algorithm also proposes to use a lower pheromone trail bound. TSP problems are known as NP-hard problems, which very hard find an optimal solution in a short time. ACO is a new metaheuristic algorithm that has been successfully applied to solve combinatorial optimization problems. ACO algorithm is biologically inspired by one aspect of the behavior of real ants, and it simulates the process of ants searching for food. When ants forage the food, they depend on the amount of pheromone deposited on the traverse path. Although ACO algorithm has very good search capability in optimization problems, it still has some drawbacks such as stagnation behavior, needing longer computing time, and premature convergence. These drawbacks will be more evident when the complexities of the considered problems increase. In our experimental results, the proposed method can avoid stagnation behavior and premature convergence. It can also be found that the proposed dynamic update of the heuristic parameters based on entropy will generate high quality tours and it can guide ants toward the effective solutions space in the initial search stages.

[1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence from natural to artificial systems, Oxford University Press, 1999.
[2] M. Dorigo and L. M. Gambardella, “The colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, April, 1997.
[3] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proc. of ECAL91-European Conference on Artificial Life, pp. 134-142, 1991
[4] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on System, Man, and Cybernetics, Part B, vol. 26, pp. 29-41, 1996
[5] T. Stützle and H. H. Hoos, “Max-min ant system,” Future Generation Computer System, vol. 16, pp. 889-914, 2000.
[6] L. M. Gambardella and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem,” Proceeding of ML-95, Twelfth Intern. Conf. on Machine Learning, Morgan Kaufmann, pp. 252-260, 1995
[7] M Dorigo and L. M. Gambardella, “A study of some properties of ant-Q,” Proceedings of PPSN-IV, Fourth International Conference on Parallel Problem Solving from Nature, vol. 1141, pp. 656-665, Springer-Verlag, 1996.
[8] B. Bullnheimer, R. F. Hartl, and C. Strauss, “A new rank-based version of ant system: A computational study,” Central European Journal for Operations Research and Economics, vol. 7, no. 1, pp. 25-38, 1999
[9] T. Stützle and M. Dorigo, Ant colony optimization, MIT Press, 2004
[10] S. Lin, “Computer solutions of the traveling salesman problem,” Bell Systems Technology Journal, vol. 44, pp. 2245-2269, 1965
[11] B. H. Korte, Applications of combinatorial optimization, Mathematical programming: Recent developments and applications, Kluwer, Dordrecht, pp. 1-55, 1989.
[12] R. G.. Bland and D. F. Shallcross, “Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation,” Operations Research Letters, vol. 8, pp. 125-128, 1989.
[13] G. Reinelt, The traveling salesman: Computational solutions for TSP applications, Lecture Note in Computer Science, vol. 840, Springer-Verlag, Berlin, 1994.
[14] M. Dorigo and G. D. Caro, “Ant colony optimization: A new meta-heuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, vol. 2, pp. 1470-1477, 1999.
[15] R. Beckers, J. L. Deneubourg, and S. Goss, “Trails and U-turn in the selection of the shortest path by the ant Lasius Niger,” Journal of Theoretical Biology, vol. 159, pp.397-415, 1992.
[16] D. J. Rosenkranz, 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, 1997.
[17] N. R. Pal and S. K. Pal, “Entropy: A new definition and its applications,” IEEE Transactions on System, Man, and Cybernetics, vol. 5, no. 21, pp. 1260-1270, 1991.
[18] R. Bose, Information theory, coding, and cryptography, McGraw Hill, 2002
[19] M. Dorigo and G. D. Caro, “Ant algorithm for discrete optimization,” Artificial Life, vol. 5, no. 3, pp. 137-172, 1999
[20] E. T. Jaynes, “On the rationale of the maximum entropy methods,” Proceedings of the IEEE, vol. 70, no. 9, pp. 939-952, 1982
[21] E. L. Lawer, J. K. Lenstra, A .H. R. Kan, and D. B. Shmoys, The traveling salesman problem, Wiley, New Work, 1985..
[22] G. A. Croes, “A method for solving traveling salesman problems,” Operations Research, vol. 6, no. 6, pp. 791-812, 1958.
[23] J. L. Bently, “Fast algorithms for geometric traveling salesman problems,” Journal on Computing, vol. 6, no. 4, pp. 387-411, 1992.
[24] G. E. Robinson, “Regulation of division of labor in insect societies,” Annual Review of Entomology, vol. 37, pp. 637-665, 1992.
[25] L. Nemes and T. Roska, “ A CNN model of oscillation and chaos in ant colonies: A case study,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 42, no. 10, pp. 741-745, 1995.
[26] V. Maniezzo and A. Coorni, “The ant system applied to the quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 11, pp. 769-778, 1999.
[27] S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels, “Self-organized shortcuts in the argentine ant,” Naturwissenchaftn, vol. 76, pp. 579-581, 1989.
[28] S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,” Operations Research, vol. 21, no. 2, pp. 498-516, 1973.
[29] E. Aarts and J. K. Lenstra, Local search in combinatorial optimization, John Wiley & Sons Inc., 1997.
[30] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[31] Zne-Jung Lee, Shun-Feng Su, and Chou-Yuan Lee, “An immunity based ant colony optimization algorithm for solving weapon-target assignment problems,” Applied Soft Computing, vol. 2, pp. 39-47, 2002.
[32] Zne-Jung Lee, Shun-Feng Su, and Chou-Yuan Lee, “A heuristic based ant colony system applied to weapon-target assignment problems,” Journal of Applied Systems Studies, vol. 4, no.2, 2003.