以霍普菲爾類神經網路結合蟻群系統之混合式演算法應用於旅行銷售員問題

簡易檢索 / 詳目顯示

回結果列表

研究生：	李秋緣 Chou-Yuan Lee
論文名稱：	以霍普菲爾類神經網路結合蟻群系統之混合式演算法應用於旅行銷售員問題 Hybrid Search Algorithms of Hopfield Neural Networks and Ant Colony Systems for Traveling Salesman Problem
指導教授：	蘇順豐 Shun-Feng Su
口試委員:	王文俊 none 陶金旺 none
學位類別：	博士 Doctor
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2008
畢業學年度：	96
語文別：	英文
論文頁數：	73
中文關鍵詞：	霍普菲爾類神經網路、蟻群系統、旅行銷售員問題、混合式演算法
外文關鍵詞：	Hopfield Neural Networks, Ant Colony Systems
相關次數：	點閱：226 下載：14
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本文提出以霍普菲爾類神經網路結合蟻群系統之混合式演算法應用於旅行銷售員問題。旅行銷售員問題(Traveling salesman problem)是眾所周知的NP-complete 組合最佳化問題，常做為各種搜尋演算法則在評估搜尋效率時所使用的基準。蟻群系統方法(Ant colony systems algorithm)乃是仿造螞蟻覓食時散發費洛蒙 (Pheromone) 藉以找到最佳路徑的能力。而霍普菲爾類神經網路基本上是一種平行輸入、平行輸出的網路架構可以解決最佳化問題，所以本文提出以霍普菲爾類神經網路結合蟻群系統來解決旅行銷售員問題之各種演算法則的研究。第一個演算法乃針對旅行銷售員問題當霍普菲爾類神經網路在達到收斂解時，應用蟻群系統方法中全域更新法則，先進行費洛蒙(Pheromone)更新，再將此收斂解及費洛蒙引進給蟻群系統搜尋機制,加強其搜尋能力，此種方法雖簡單但很有效率。第二個演算法乃是將霍普菲爾類神經網路視為貪婪式方法引進給蟻群系統做為區域搜尋機制以求解最佳解，此演算法亦具有優秀的搜尋效能，經由實驗結果顯示，霍普菲爾類神經網路雖然收斂速度很快，但在此演算法中計算較繁雜，其搜尋效率沒有比第一個演算法來得好。更進一步地本文加入遺傳基因演算法(Genetic Algorithms)在前面所提出的第一個混合式演算法中，來改良針對霍普菲爾類神經網路本身設計時初始值的問題，提高搜尋能力更有效率地找到問題的最佳解。經由實驗結果顯示，所提出的演算法GAHNNACO能有效地改善HNNACO搜尋效率。最後本文亦提出簡單方法來解決當旅行銷售員問題的城市很多而霍普菲爾類神經網路加權矩陣變得非常大的問題，經由實驗結果顯示使用此方法在尋找問題的最佳解中確實很有效率。

In this dissertation, hybrid search algorithms of combining Hopfield neural networks and ant colony systems for traveling salesman problem are proposed. The Traveling salesman problem (TSP) is a well-known NP-complete combinatorial optimization problem and is often employed as a benchmark for the evaluation of search efficiency for various search algorithms. The algorithm of Ant colony systems (ACS) is a class of algorithms by using artificial ants with the capability of mimicking the behavior of real ants to find the optimal path. Hopfield neural networks (HNN) are a parallel input and output networks structure, which can also be to solve optimization problems. In this study, we intend to study possible combinations of Hopfield neural networks and ant colony systems. Various algorithms are proposed in this dissertation. In the first approach, HNN is used to find a plausibly good solution (locally optimum), which is then used in ACS as the currently best tour for the offline pheromone trail update. The idea is to deposit additional pheromone to ACS to enhance the search efficiency. The idea is very simple, but very effective. The second approach is to employ HNN as a local search mechanism in ACS. The idea is to consider HNN as a greedy algorithm for finding local optimum. The proposed algorithms also demonstrated excellent search performance. It can be found that even though HNN needs only a small fraction of execution time, while using as the local search mechanism in each iteration for ACS, HNN still becomes a computational burden in the hybrid search algorithm. As a result, the search efficiency of the second hybrid search algorithm is worse than that of the first one. Experimental results of solving the traveling salesman problem are reported to justify our claims. Furthermore, an algorithm incorporating genetic algorithms and Hopfield neural networks with ant colony optimization is then proposed to deal with the HNN initial problem. In this approach, Genetic Algorithm (GA) is employed to provide a feasible candidate for HNN so that the search can become efficient. From our experiments, it is clearly evident that the proposed algorithm indeed can significantly improve the search efficiency for the search algorithm without GA. Finally, when the city number increases, the weight matrix of HNN will become extremely large. We also propose a simple way of dealing with this problem. The experiments conducted indeed demonstrate the effectiveness of the proposed approach.

Abstract……………………………………………………….…………………...II
Acknowledgement………………………………………………….……………………V
Table of Contents.………………………………………………………………………VI
List of Tables………………………………………………..….…………………IX
List of Figures……………………………………….……………..……………………XI
Chapter  1  Introduction
1.1	Motivation..………………………………………………………….1
1.2	Major Contributions…………………………..…….……..………2
1.3	Outline of the Dissertation………………………..………..………3
Chapter  2  Various Search Algorithms for TSP
2.1	Introduction………………………….…………………….…4
2.2	Search Algorithms………………………..…………………………5
2.2.1 General Local Search……………………..…………5
2.2.2 Simulated Annealing (SA) Algorithms……………6
2.2.3 Genetic Algorithms (GAs)………….………………….7
2.2.4 Ant Colony Optimization (ACO) and Ant Colony Systems (ACS).................................……………………………………8
2.3	Hopfield neural networks (HNN) for TSP………………………13
2.4 Other Exist Methods…………………..….……………………….15
Chapter  3	Incorporating HNN into GAs and ACS for TSP
3.1	Introduction………………………………………………………17
3.2 GA with HNN as Local Search....…………………………….….18
3.3	HNNGA and HNNACS Algorithms………..……..……………..19
3.3.1 HNNGA…………………………….…………..……..….…..20
            3.3.2 HNNACS…………………………………………..………....21
3.4	Experimental Results…………………………………………23
3.5	Summary……………………………………………..……...……26
Chapter  4  Hybrid Search Algorithms of Hopfield Neural Networks and Ant Colony Systems
4.1	Introduction………………………….……………………………32
        4.2	Incorporating HNN into ACS….. ……………………..…………32
4.2.1 HNNACS I ……………………………..……………………33
4.2..2 HNNACS II …...……………………….……………………33
4.3 Experimental Results .………………………………..……………34
4.4 Summary…………………………………………………………….37
Chapter  5	 Various Initial Mechanism of HNN for HNNACS
5.1	Introduction……………………………………………………..…44
5.2	Competitive HNNACS…………………………………..……44
5.3	GAHNNACO Algorithm……………………………………….46
5.4	Experimental Results……………………...………………………47
5.5	Summary……………….………………………………..…………50
Chapter  6	Segmented HNNACS for Large Traveling Salesman Problem
6.1	Introduction……………………………………………..…………58
6.2 The Segmented HNNACS....………………………………….….58
6.3	Experimental Results………..……..……………………..……...59
6.4	Summary……………………………………………………...……60
Chapter  7	Conclusions
7.1	Conclusions………………………………………………………63
7.2	Suggestions for Further Research.……………………….…..…64
References……………………………………………………………………….…65
作者簡介…………………………………………………………………..……………71
授權書











List of Tables

Table 3.1 Experiment results for TSPLIB instances……………………………………27
Table 3.2: Results of various search algorithms when experiments are stopped after two hours of running……………………………..……………………………...28
Table 3.3: CPU time spent for HNN in HNNACS………………….………………….29
Table 3.4: The length of tour Chnn and offline pheromone updating trail for HNNACS..29
Table 3.5: Comparison results of HNNACS and other algorithms in TSPLIB instances..30
Table 3.6: Comparison CPU time spent of HNNACS and other algorithms in TSPLIB instances…………………...………………………..…………………….….31
Table 4.1: Experiment results for the bays29 TSP. (The best value is 2020)…………… 38
Table 4.2: Experiment results for the swiss42 TSP. (The best value is 273)………..........38
Table 4.3: Experiment results for the att48 TSP. (The best value is 10628)……………. 39
Table 4.4: CPU time spent for various algorithms……………………………………….39
Table 4.5: Comparison of the best solution by various algorithms when experiments are stopped after two hours of running………………………….……..…........... 40
Table 4.6: Experiments using HNNACS I with various initial vectors for kroA100……41
Table 4.7: Experiments using HNNACS I with various initial vectors for Ch130............41
Table 4.8: Experiments using HNNACS I with various initial vectors for kroA200........42
Table5.1: Search performance of various algorithms for the bays29 TSP (The best value is 2020)………………………………………………………………………...…51
Table 5.2: Search performance of various algorithms for the swiss42 TSP (The best value is 1273)……………………………………………………………………....52
Table 5.3: Search performance of various algorithms for the att48 TSP (The best value is 10628)……………………………………………………………………....53
Table 5.4: Comparison CPU time spent of various algorithms……….………..……….54
Table 5.5: Comparison of various search algorithms when experiments are stopped after two hours of running…………………………………………………………54
Table 5.6: Comparison CPU time spent of three algorithms for HNN…………………..55
Table 5.7: Search performance of three algorithms for kroA100………………..……….55
Table 5.8: Search performance of three algorithms for Ch130…………………………..56
Table 5.9: Search performance of three algorithms for kroA200…………………...……57
Table 6.1: Comparing various search algorithms for large scale TSP instances when experiments are stopped after two hours of running …………………..…….61
Table 6.2: Comparison results of large scale TSP instances………………….………….61










List of Figures

Figure 2.1: A conceptual structure of the Hopfield neural network……………………...16
Figure 4.1: The differences A-B and C-D length curves of HNNACS Ⅱ for kroA100….42
Figure 4.2: The differences A-B and C-D length curves of HNNACS Ⅱ for ch130…….43
Figure 4.3: The differences A-B and C-D length curves of HNNACS Ⅱ for kroA200….43
Figure 6.1: The segmented method of large scale TSP.…………………..……………...62

                                

[1] G. Reinelt, “TSPLIB – A Traveling Salesman Problem Library, “ ORSA Journal on Computing, vol. 3, pp. 376-384, 1991.
[2] G. Reinelt, “The Traveling Salesman: Computational Solutions for TSP Application,” LNAC, Springer Verlag, vol. 840, 1994.
[3] M. Dorigo, and G. D. Caro, “Ant colony optimization: A new meta-heuristic,” in Proceedings of the 1999 Congress on Evolutionary Computation, vol. 2, pp. 1470-1477, 1999.
[4] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by a colony of cooperating agents,” IEEE Trans. System, Man, and Cybernetics, Part B, vol. 26, no. 1, pp. 29-41, 1996.
[5] M. Dorigo, L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997
[6] V. Maniezzo, and A. Colorni, “The ant system applied to the quadratic assignment problem,” IEEE Trans. Knowledge and Data Engineering, vol. 11, pp. 769-778, 1999.
[7] L.M. Gambardella and M. Dorigo., “Solving Symmetric and Asymmetric TSPs by Ant Colonies,” Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ECEC’96), IEEE Press, pp. 622-627, 1996.
[8] T. Stűtzle and H. Hoos, “MAX-MIN ant system and local search for the traveling salesman problems,” proceeding of IEEE International Conference on Evolutionary Computation (ICEC’97’), pp. 309 –314, 1997.
[9] L. M. Gambardella and M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” In Proceedings of the eleventh International Conference on Machine learning. Palo Alto, CA: Morgan Kaufmann, pp. 252-260, 1995.
[10] M. Dorigo, V. Maniezzo and A. Colorni, “Positive feedback as a search strategy,” Tech. Rep. Politechnicodi Milano, Italy, pp. 91-106, 1991.
[11] L. M. Gambardella, M. Dorigo, “An ant colony system hybridized with a new local search for the sequential ordering problem,” INFORMS Journal on Computing, vol. 12, no.3, pp.237-255, 2000.
[12] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of European Conference on Artificial Life (ECAL’91), Elsevier, Amsterdam, 1991.
[13] A. Colorni, M. Droigo, and V. Maniezzo, “An investigation of some properties of an ant algorithm,” Proceedings of the Parallel Problem Solving from Nature Conference, Elsevier, Amsterdam, 1992.
[14] M. Dorigo, Optimization, Learning and Natural Algorithms. PhD thesis, Dipartimento di Elettronica, Italy, 1992.
[15] B. Bullnheimer, R. Hartl, and C. Strauss, “A new rank-based version of the Ant System: A computational study,” Central European J Operations Res. vol. 7, no. 1, pp. 25-38, 1999.
[16] T. Stűtzle and H. H. Hoos, “MAX-MIN Ant system,” Future Generat Comput Syst. vol. 16, no. 8, pp. 889-914, 2000.
[17] C. Blum and M. Dorigo, “The hyper-cube framework for ant colony optimization,” IEEE Trans. Systems, Man and Cybernetics, Part B, vol. 34, no.2, pp.1161-72, 2004.
[18] C. Blum, “Ant colony optimization: Introduction and recent trends,” Physics of Life Reviews, vol. 2, pp. 353-373, 2005.
[19] T. Stűtzle and M. Dorigo, Ant Colony Optimization, MIT Press, 2004
[20] . http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
[21] J. J. Hopfield and D. W. Tank, “Neural computation of decisions in optimization problem,” Biological Cybernetics, vol. 52, pp.141-152, 1985.
[22] X. C. Zeng and T. Martinex, “A new relaxatioin procedure in the Hopfield networks for solving Optimization Problems,” neuron processing letter, 10: pp. 211-212, 1999.
[23] R. Durbin and D. Willshaw, “An analog approach to the traveling salesman problem using an elastic net method,” Nature, vol. 326, pp. 689-691, 1987.
[24] Y. Tachibana, G. H. Lee, H. Ichihashi, and T. Miyoshi, “A simple steepest decent method for minimizing Hopfield energy to obtain optimal solution of the TSP with reasonable certainty,” in Proc. of International Conference on Neural Networks, pp. 1871-1875, 1995.
[25] G. V. Wilson and G. S. Pawley, “On the stability of the traveling salesman problems algorithm of Hopfield and Tank,” Biological Cybernetics, vol. 58, pp. 63-70, 1988.
[26] A. H. Gee, S. V. B. Aiyer, and R. Prager, “An analytical framework for optimizing neural networks,” Neural Networks, vol. 6, pp.79-97, 1993.
[27] S.V.B. Aiyer M. Niranjan, and F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Networks, vol. 1, pp. 204-215, 1990.
[28] Van den Bout, D. E. and Miller, T. K., “Improving the Performance of the Hopfield-Tank Network through Normalization and annealing. ” Bio. Cybern., vol. 62, pp. 129-139,1989.
[29] S. Haykin, Neural Networks-a Comprehensive Foundation, Prentice Hall, 1999.
[30] P. M. Talavan and J. Yanez, “Parameter setting of the Hopfield network applied to TSP,” Neural Networks, vol. 15, pp. 363-373, 2002.
[31] L. Wang, “On the dynamics of discrete-time, continuous-state Hopfield neural networks,” IEEE Trans. Circuits Systems 2, Analog Digit. Signal Process, vol. 45, no. 6, pp. 747-749, 1998.
[32] S. Park, “Signal space interpretations for Hopfield neural network for optimization,” in Proc. IEEE Int. Symp. Circuits Systems, pp. 2181-2184, May 1989.
[33] P. W. Protzel, D. L. Palumbo, and M. K. Arras, “Performance and fault-tolerance of neural networks for optimization,” IEEE Trans. Neural Networks, vol. 4, pp. 600-614, 1993.
[34] E. Wacholder, J. Han, and R. C. Mann, “A neural-network algorithm for the multiple traveling salesman problem,” Biological Cybernetics, vol. 61, pp. 11-19, 1989.
[35] S. Matsuda, “Optimal Hopfield network for combinatorial optimization with linear cost function,” IEEE Int. Symp. Circuits Systems, pp. 2181-2184, May 1989.
[36] M. W. Simmen, “Parameter sensitivity of the elastic net approach to the traveling salesman problem,” Neural Computa., vol. 3 pp. 363-374, 1991.
[37] S. Abe, “Global convergence and suppression of spurious states of the Hopfield neural networks,” IEEE Trans. Circuits Systems I: Fundamental. Theory Applications, vol. 40, no. 4, pp. 246-257, 1993.
[38] C. Peterson and B. Soderberg, “A new method for mapping optimization problems onto neural networks,” Int. J. Neural Systems, vol. 1, pp. 3-22, 1989.
[39] R. D. Brandt, Y. Wang, A. J. Laub, and S. K. Mitra, “Alternative networks for solving the traveling salesman problem and list-matching problem,” in Proc. Int. Joint Conf. Neural Networks, vol. 2, pp. 333-340, 1988.
[40] L. Wang and K. Smith, “On chaotic simulated annealing,” IEEE Trans, Neural Networks, vol. 9, no. 4, pp. 716-718, 1998.
[41] P. J. M. Van Laarhoven and E. H. L. Arts, Simulated Annealing: Theory and Applications, Kluwer Academic Publishers, 1992.
[42] S. Kirkpatrick, C. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671-680, 1983.
[43] E. H. L Aarts and J. K. Lenstra, Local Search in Combinatorial Optimization, Wily, New York, 1997.
[44] A. Kolen and E. Pesch, “Genetic local search in combinatorial optimization,” Discrete Applied mathematics and Combinatorial Operations Research and Computer Science . vol. 48, pp. 273-284, 1994.
[45] Z.-J. Lee, S.-F. Su, and C.-Y. Lee, “An Immunity Based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problems,” Applied Soft Computing, vol. 2, pp. 39-47, 2002.
[46] C.-Y. Lee, Z.-J. Lee, and S.-F. Su, “Ant Colonies With Cooperative Process Applied To Resource Allocation Problem,” Journal of the Chinese Institute of Engineers, Vol. 28, No. 5, pp. 879-885, 2005.
[47] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
[48] L. Jian and L. Wang, “Novel genetic algorithm based on immunity,” IEEE Trans. Systems, Man and Cybernetics, Part A, vol. 30, no.5, pp. 552-561, 2000.
[49] Z.-J. Lee, S.-F. Su, and C.-Y. Lee, “Efficiently Solving General Weapon-Target Assignment Problem by Genetic algorithms with Greedy Eugenics,” IEEE Trans. Systems, Man and Cybernetics, Part B, pp. 113-121, 2003.
[50] D. Goldberg, R. Lingle and Alleles, “Loci and traveling salesman problem,” Proceedings of the Second International Conference on Genetic Algorithms, Lawerence Eribaum Associated, Mahwah, NJ, 1985.
[51] Z.-J. Lee, S.-F. Su, and C.-Y. Lee, “ A genetic algorithm with domain knowledge for weapon-target assignment problems,” Journal of the Chinese Institute of Engineers, vol. 25, no. 3, pp287-295, 2002.
[52] K-H Liu, Multiple Sequence Alignment: An Evolutionary Programming Based Algorithm with Local Search, Master Thesis, Department of Electrical Engineering, National Taiwan University of Science and Technology, 2003.
[53] B. Fresleben an P. Merz, “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman problem,” Proceeding of the 1996 IEEE International Conference on Evolution computation, pp. 616-621, 1996.
[54] Y. Zhang, Z.-L. Pei, J.-H. Yang, and Y.-C. Liang, “An improved ant colony optimization algorithm based on route optimization and its applications in traveling salesman problem,” Bioinformatics and Bioengineering, 2007. BIBE 2007. Proceedings of the 7th IEEE International Conference, 14-17 Oct., pp. 693 – 698, 2007.
[55] C. Qi, “An ant colony system hybridized with randomized algorithm for TSP,” Software Engineering, Artificial Intelligence, Networking, and Parallel/ Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference, Vol.3, July 30 2007-Aug. 1, pp. 461 – 465, 2007.
[56] Chou-Yuan Lee, Zne-Jung Lee, and Shun-Feng Su. A hybrid Search Algorithm with Hopfield Neural Network and Ant Colony Optimization for Solving Traveling Salesman Problems. The 10th Conference on Artificial Intelligence and Applications 2005; SS3-2.
[57] Chou-Yuan Lee, Shun-Feng Su, and Zne-Jung Lee, “Incorporation of genetic algorithms and Hopfield neural networks with ant colony optimization”, Engineering Intelligent Systems, Vol. 15, no.4, pp. 187-194, 2007.

簡易檢索 / 詳目顯示

相關論文