求解旅行商问题的进化算法
|
摘要
进化算法是人们从大自然的生物进化过程所得到的灵感中发展起来的一种现代优化方法,它作为一种新型的、模拟生物进化过程的随机化搜索、优化方法,具有全局优化,隐并行性,鲁棒性强,操作简单等特点,近十几年来在组合优化领域得到了相当广泛的应用,并已在解决诸多典型的组合优化问题(如旅行商问题)中显示了良好的性能和效果。
首先,针对一类特殊的大规模旅行商问题,比如说城市可以分为若干组、而且各组内城市之间的距离较小的问题,本文提出了一种基于聚类以及局部搜索技术的新进化策略来进行求解,并且证明了该算法的全局收敛性。
其次,针对对称型的旅行商问题,本文设计了一个新的进化算法进行求解,该算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解的质量,同时被证明是全局收敛的。
最后,数值模拟实验结果表明,本文所提出的这两个算法都是有效的。
Evolutionary algorithms are new kinds of modern optimization algorithms which are inspired by the principle of nature evolution. As new kinds of random search algorithms, they have some advantages such as global search ability, implicit parallelism, robustness, simple operation and so on. In the recent decades, evolutionary algorithms have a wide range of applications in the area of combinatorial optimization. They have been used to solve many classical combinatorial optimization problems (e.g. Traveling Salesman Problem) and show their good performance and effectiveness.
Firstly, a new evolution strategy based on clustering and local search scheme is proposed for some kind of large-scale traveling salesman problems in which the cities can be classified into several groups and in each group the cities crowd together. This algorithm is then proved to converge to the global optimal solution with probability 1.
Secondly, a new evolutionary algorithm is proposed to deal with the symmetric traveling salesman problems. In this new algorithm, a new crossover operator and a new mutation operator are designed to generate offspring. Then a local search scheme is used to improve the solutions. Also, the global convergence with probability 1 of the proposed algorithm is proved.
Finally, the simulation results show the effectiveness of the two proposed algorithms.
首先,针对一类特殊的大规模旅行商问题,比如说城市可以分为若干组、而且各组内城市之间的距离较小的问题,本文提出了一种基于聚类以及局部搜索技术的新进化策略来进行求解,并且证明了该算法的全局收敛性。
其次,针对对称型的旅行商问题,本文设计了一个新的进化算法进行求解,该算法设计了新的交叉算子和变异算子来产生后代以及一种局部搜索方法来改善解的质量,同时被证明是全局收敛的。
最后,数值模拟实验结果表明,本文所提出的这两个算法都是有效的。
Evolutionary algorithms are new kinds of modern optimization algorithms which are inspired by the principle of nature evolution. As new kinds of random search algorithms, they have some advantages such as global search ability, implicit parallelism, robustness, simple operation and so on. In the recent decades, evolutionary algorithms have a wide range of applications in the area of combinatorial optimization. They have been used to solve many classical combinatorial optimization problems (e.g. Traveling Salesman Problem) and show their good performance and effectiveness.
Firstly, a new evolution strategy based on clustering and local search scheme is proposed for some kind of large-scale traveling salesman problems in which the cities can be classified into several groups and in each group the cities crowd together. This algorithm is then proved to converge to the global optimal solution with probability 1.
Secondly, a new evolutionary algorithm is proposed to deal with the symmetric traveling salesman problems. In this new algorithm, a new crossover operator and a new mutation operator are designed to generate offspring. Then a local search scheme is used to improve the solutions. Also, the global convergence with probability 1 of the proposed algorithm is proved.
Finally, the simulation results show the effectiveness of the two proposed algorithms.
引文
[1] E.L.Lawler, J.K.Lenstra, A.H.G.Rinnooy Kan and D.B.Shmoys(eds.). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, NewYork, 1985.
[2] M.R.Garey, R.L.Graham, and D.S.Johnson. Some NP-complete geometric problems, in Proc. 8th Annu. ACM Symp. Theory of Computing, 1976, 10-22.
[3] R.Baraglia, J.I.Hidalgo, and R.Perego. A hybrid heuristic for the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 2001, vol.5, no.6, 613-622.
[4] Huai-Kuang Tsai, Jinn-Moon Yang, Yuan-Fang Tsai, and Cheng-Yan Kao. An evolutionary algorithm for large traveling salesman problems, IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics, 2004, vol.34, no.4, 1718-1729.
[5] Hung Dinh Nguyen, Kunihito Yamamori, and Moritoshi Yasunaga. Implementation of an e?ective hybrid GA for large-scale traveling salesman problems, IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics, 2007, vol.37, no.1, 92-99.
[6] J. H. Holland. Adaption in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.
[7] L.J. Fogel, A.J. Owens, and M.J. Walsh. Artificial Intelligence through Simulation Evolution. New York: John Wiley, 1966.
[8] I. Rechenberg. Evolutionsstrategie-Optimierung Technischer Systeme nach Prinzipfen der Biologischen Evolution. Frommann-Holzboog, Stuttgart,1973.
[9] J. Koza. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. PhD Thesis, Stanford University, 1990.
[10] D. E. Goldberg. Genetic Algorithm in Search, Optimization and Machine Learning New York: Addiso-Wesley Publishing Company, INC, 1989.
[11] L. Daris. Handbook of Genetic Algorithms. Van Nostrand Rainhold, New York, 1991.
[12]云庆夏,黄光球,王战权。遗传算法和遗传规划。冶金工业出版社,1997。
[13]张文修,梁怡。遗传算法数学基础。西安交通大学出版社,2000。
[14]刘勇,康立山,陈毓屏。非数值并行算法(第二册):遗传算法。科学出版社,1995。
[15] Z. Mchelewich. Genetic Algorithms + Data Structure = Evolutionary Programming(3rd edition). New York: Springer-Verlag, 1996.
[16]王小平,曹立明。遗传算法—理论、应用与软件实现。西安交通大学出版社,2002。
[17] W.M. Jenkins. Structural optimization with the genetic algorithm. Structural Engineer, 1991, 69(24):408-422.
[18] D. E. Goldberg. Computer-aided gas pipeline operation using genetic algorithm and rule learning. Doctoral dissertation, No. 8402282, Department of Civil Engineering, University of Michigan, 1983.
[19] R. Chandrasekharam. Genetic algorithm for embedding a complete graph in a hypercube with a VLSI application. Micro-processing and Micro-programming, 1994, 40: 537-552.
[20] Xin Yao. A review of evolutionary artificial neural network. International Journal of Intelligent Systems, 1993, 8(3): 539-565.
[21] Yoon Byungjoo. Efficient genetic algorithm for training layered feed-forword neural network. Information Science, 1994, 76(1-2): 67-85.
[22] J. J. Davis. Trainning product unit neural networks with genetic algorithms. IEEE Expert, 1993, 8(5): 26-33.
[23] D. J. Montana and L. Davis. Trainning feed-forward neural networks using genetic algorithms. In Proceeding of the International Joint Conference on Artificial Intelligence, Los Altos, CA: Morgan Kaufmann Publishers, 1989: 762-767.
[24] K. A. De Jong. Learning with genetic algorithms: an overview. Machine Learning, 1988, 3: 121-138.
[25] M. Dorigo and U. Schneph. Genetic-gased machine learning and behavior-based robotics: a new synthesis. IEEE Transaction on Systems, Man and Cybernetics, 1993, 23(1): 141-154.
[26] L.B. Booker. Classifier systems and genetic algorithms. Artificial Intelligence, 1989, 40(1-3): 235-282.
[27] G. E. Liepins and L. A. Wang. Classifier system learning of Boolean concepts. In Proceedings of Fourth International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers, 1991: 318-322.
[28] A. D. McAulay and J. C. Oh. Improving learning of genetic rule-based classifier systems. IEEE Trans. on System, Man, and Cybernetics, 1994, 24(1): 152-159.
[29] A. Barodi and P. Bonelli. A new approach to fuzzy classifiers. In Proceedings of Fifth International Conference on Genetic Algorithms, Los Altos, CA, 1993.
[30] S. Matwin. Genetic algorithms approach to negotiation support system. IEEE Tans.on Systems, Man and Cybernetics, 1991, 21(1): 102-114.
[31] C. Nikolopoulos and P. Fellrath. Hybrid expert system for investment advising. Expert System, 1994, 11(4): 245-248.
[32] P. Van Bommel. Genetic algorithm for optimal logical database design. Internetional Software Technology, 1994, 36(2): 725-732.
[33] S. Forrest. Genetic algorithm: principles of natural selection application to computation. Science, Aug. , 1993, 261: 872-878.
[34] C. L. Karr. Design of an adaptive fuzzy logic controller using genetic algorithm. In Proceedings of Fourth International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers, 1991: 450-457.
[35] L. M. Freeman. Turning fuzzy logic controller using genetic algorithms in aerospace applications. In Proceeding of the AAAIC’90 Conference, Dayton, Oct. , 1990: 351-358.
[36] F. Glover. Genetic algorithms and tabu search: hybrids for optimization. Computer and Operation Research(UK), 1995, 122(1): 111-134.
[37] Z. Michalewicz, C. Janikow, and J. Kjrawczyk. A modified genetic algorithm for optimal control problems. Computers and Mathematical Applications, 1992, 23(12): 83-94.
[38] R. J. Bauer. Genetic algorithms and investment strategies. New York: John Wiley & Sons, Inc. , 1994.
[39] D. B. Fogel. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems, 1993, 24: 27-36.
[40] J. J. Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the First International Conference on Genetic Algorithms(ICGA 1), J. J. Grefenstette(ed.), Hillsdale, NJ: Lawrence Erlbaum Associates, 1985: 160-168.
[41] Mitchell Melanie. An introduction to genetic algorithms. Cambridge, MA: The MIT Press, 1996.
[42] N. Kadaba, K. E. Nygard, and P. J. Juell. Integration of adaptive machine learning and knowledge-cased systems for routing and scheduling applications. Expert Systems with Applications, Vol. 2, No. 1, 1991: 15-27.
[43] S. H. Lin, E. D. Goodman, and W. F. Punch. Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problem. In the Sixth International Conference on Evolutionary Programming, P. Angeline, R. J. M. Reynolds, and R. Eberhart(eds.), Berlin: Springer-Verlag, April 1997: 383-393.
[44] D. Maclay, and R. Dorey. Applying genetic search techniques to drivertrain modeling. IEEE Control Systems, Special Issue on Intelligent Control, Vol. 13, No. 3, June, 1993:50-55.
[45] J. Zhang and P. D. Robert. Use of genetic algorithms in training dagnostic rules for process fault dagnosis. Knowledge-Based Systems, Vol. 5, No. 4, Dec. , 1992: 277-288.
[46] Binglin Zhong. Genetic algorithm for diagnosis problem solving. In Proceeding of the IEEE International Conference on Systems, Man and Cybernetics. IEEE Service Center, Piscataway, NJ, USA, 1992: 404-408.
[47] Y. Davidor. Genetic algorithm and robotics, a heuristic strategy for optimization. World Scientific Series in Robotics and Automated System, 1991, 1.
[48] M. A. C. Gill and A. Y. Zomaya. Obstacle avoidance in multi-robot systems: experiments. In Parallel Genetic Algorithms. Singapore: World Scientific Press, 1998.
[49] R. A. McCallum and K. A. Spackman. Using genetic algorithm to learn disjunctive rules from examples. In Proceeding of the International Conference on Machine Learning, San Mateo, CA: Morgan Kaufmann, 1990: 149-152.
[50] J. Bala, K. A. De Jong, J. Huang, H. Vafaie, and H. Wechsler. Hybrid learning using genetic algorithms and decision trees for pattern classification. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada, August 19-25, 1995.
[51] B. K. Lavine. Pattern recognition analysis via genetic algorithms & multivariate statistical methods. Boca Raton, Fla: CRC Press, 2000.
[52] K. Bennett. A genetic algorithm for database query optimization. IEEE Conference on Evolutionary Computation, 1994: 400-407.
[53] J. D. Schaffer, L. D. Whitley, and L. J. Eshelman. Combinations of genetic algorithms and neural networks: a survey of the state of the art. In Proceedings of the International Workshop on Combinations of Genetic Algorithms and Neural Networks, Baltimore, June, 1992: 1-37.
[54] A. J. F. von Rooij, L. C. Jain, and R. P. Johnson. Neural network training using genetic algorithms. Singapore: World Scientific Press, 1996.
[55] H. Adeli. Machine learning: neural networks, genetic algorithms, and fuzzy systems. New York: John Wiley & Sons, 1995.
[56] E. Vonk, L. C. Jain, and R. P. Johnson. Automatic generation of neural network architecture using evolutionary computation. Singapore: World Scientific Press, 1997.
[57] J. R. Koza. Recognizing patterns in protein sequences using iteration-performing calculations in genetic programming. In Proceedings of the 1st IEEE ConferenceEvolutionary Computation, Piscataway, NJ, 1994, Part 1: 244-249.
[58] S. K. Pal. Genetic algorithms for pattern recognition. Boca Raton, Fla: CRC Press, 1996.
[59] S.Arora, C.Lund, R.Motwani, M.Sudan, and M.Szegedy, Proof verification and intractability of approximation problems, in Proc. 33rd IEEE Symp. Foundations of Computer Science, 1992, 13-22.
[60] G. Gutin and A. P. Punnen(Eds.). The Traveling Salesman Problem and Its Variations. London: Kluwer, 2002.
[61] http://iris.gmu.edu/~khoffman/papers/trav_salesman.html.
[62] S. A. Cook. The complexity of theorem-proving procedures. Proceedings of 3rd Annual ACM Symposium on the Theory of Computing, 1971, 151-158.
[63]王晓东编著。计算机算法设计与分析。电子工业出版社,北京,2001。
[64] S. Lin. Computer solutions of the traveling salesman problem. Bell System Computer Journal, 1965, 44, 2245-2269.
[65] S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 1973, 11, 972-989.
[66]周明。传算法原理及应用。国防工业出版社,2000。
[67] D. B. Fogel. Evolutionary Computation: toward a new philosophy of machine intelligence. IEEE Neural Networks Council. New York: IEEE Press, 1995.
[68] K. Miettinen, P. Neittaanmaki, and J. Periaux(eds). Evolutionary algorithms in engineering and computer science: recent advances in genetic algorithms, evolution strategies, evolutionary programming. New York: John Wiley & Sons, June, 1999.
[69] T. B?ck, D. B. Fogel, and Z. Michalewicz. HandBook of Evolutionary Computation. University Oxford Press, New York, 1997.
[70] N. Srinivas and Deb. Kalyanmoy. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithm, Evolutionary Computation. 1994, 2(3): 221-248.
[71] H. P. Schwefel. Numerical Optimization of Computer Models. John Wiley, Chichester, UK, 1981.
[72]李敏强等。遗传算法的基本理论与应用。科学出版社,2002。
[73] D. B. Fogel. Evolutionary Programming for Training Neural Networks. International Joint Conf. on Neural Networks'90. Washington.D.C., 1990, 1601-1605.
[74] D. B. Fogel. Evolving Neural Networks. Biol. Cybern. 1990, 487-493.
[75] N. Saravanan, D. B. Fogel. Evolving Neurocontrollers Using Evolutionary Programming. In ICEC'94, Orlando, Florida. USA, IEEE Press. 1994, 63-66.
[76] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natual Selection. MIT Press. Cambridge. 1992.
[77] J. R. Koza. Genetic Programming II: Automatic Discovery of reusable programs. MIT Press. Cambridge. 1994.
[78]徐宗本,高勇。遗传算法过早收敛现象的特征分析及其预防。中国科学(E辑)。1996, 4:364-375。
[79]张讲社,徐宗本,梁怡。遗传算法的整体退火选择及其收敛主要条件。中国科学(E辑)。1997, 2:154-164。
[80] X. F. Qi and F. Palmieri. Theoretical analysis of evolution algorithms with an infinite population size in continuous space, Part 1, 2: basic properties of selection and mutation. IEEE Transactions on Neural Network, 1994, 5(1): 102-129.
[81]梁艳春,王在申,周春光。选择和变异操作下遗传算法的收敛性研究。仅算机研究与进展,1998,35(7):657-662。
[82] T. B?ck and H. P. Schwefel. Evolutionary computation: an overview. In Proceedings of the Third IEEE Conference on Evolutionary Computation. Piscataway: IEEE Press, 1996, 20-29。
[83] G. Rudolph. Self-Adaptation and global convergence: A Counter-Example. In Proceedings of the Congress on Evolutionary Computation, Piscataway: IEEE Press, 1999, 1: 646-651.
[84] G. Rudolph. Convergence of non-elitist strategies. In Proceedings of the First IEEE Conference on Evolutionary Computation, Piscataway: IEEE Services Center, 1994, 1: 63-66.
[85] G. Rudolph. Convergence of evolutionary algorithms in general search spaces. In Proceedings of the Third IEEE Conference on Evolutionary Computation, Piscataway, NJ: IEEE Services Center, 1996, 1: 50-54.
[86] J. Grefenstete, et. al. Genetic algorithms for the traveling salesman problem. in Proc. of 1st Int. Conf. in Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates,1985, 154-168.
[87] Yuping Wang, Yinghua Li, and Chuangyin Dang. A novel globally convergent hybrid evolutionary algorithm for traveling salesman problems. In Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, August 2004, 26-29.
[88] Yuping Wang, Lixia Han, Yinghua Li, and Shuguang Zhao. A new encoding based genetic algorithm for the traveling salesman problem. Engineering Optimization. January 2006, Vol. 38, No. 1, 1-13.
[89] L. Davis. Applying adaptive algorithms to epistatic domains. in Proc. of 9th Int. Joint Conf. on Artificial Intelligence. 1985.
[90] I. Oliver, D.Smith and J. Holland. A study of permutation crossover operators on the traveling salesman problem. in Proc. 2nd Int. Conf. Genetic Algorithms. 1987, 224 - 230.
[91] A.Homaifar, S .Guan, and G. Liepins. A new approach on the traveling salesman problem by genetic algorithms. North Carolina A & T State Univ. ,Greensboro, NC. 1991 .
[92] D. Whitley, et. al. Scheduling problems and traveling salesman: the genetic edge recombination operator. in P roc. of 3rd Int. Conf. on Genetic Algorithms. Morgan Kaufmann, 1989, 133-140.
[93] T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, and C. Whitley. A comparison of genetic sequencing operators. in Proc. 4th Int. Conf. Genetic Algorithms. 1991, 69-76.
[94]B. Freisleben and P. Merz. New genetic local search operators for the traveling salesman problem. in Proc. 4th Conf. Parallel Problem Solving from Nature. 1996, 616 - 621.
[95] Soonchul Jung and Byung-Ro Moon. Toward minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean TSP. IEEE Trans. on Evolutionary Computation. 2002, Vol. 6, No. 6, 557-565.
[96] Y. Nagata and S. Kobayashi. Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In T.B?ck, editor, Proc. of the 7th Int. Conf. on GAs, Morgan Kaufumann, 1997.
[97] H. K. Tsai, J. M. Yang, and C. Y. Kao. Solving traveling salesman problems by combining global and local search mechanisms. in Proc. Congr. Evolutionary Computation, 2002, 1290-1295.
[98] D. B. Fogel. A parallel processing approach to a multiple traveling salesman problem using evolutionary programming. in L .Canter( ed.) Proceedings on the Fourth Annual Parallel Processing Symposium. Fullerton, CA, 1990, 318-326.
[99] D. B. Fogel. An evolutionary approach to the traveling salesman problem. Biol. Cybern. , 1988, 60, 139-144.
[100] W. Banzhaf. The "Molecular" traveling salesman problem. Biological Cybernetics. 1990, 64, 7-14.
[101] A.K. Jain, M.N. Murty, P.J. Flyn.: Data clustering: A review. ACM Computing Survey. 1999, 31(3) , 264-323.
[102] T. B?ck. Evolutionay algorithms in theory and practice. New York, Oxford Univ. Press. 1996.
[103] G. Reinelt. TSPLIB-A traveling salesman library. ORSA J. Comput. , 1991, Vol.3, No.4, 376-384.
[104] D. S. Johnson. Local optimization and the traveling salesman problem, in Proceedings of 17th Automata, Languages, and Programming, Warwick University, England, Springer-Verlag, 1990, 446–461.
[105] P. Merz and B. Freisleben. Genetic local search for the TSP. New results, in Proceedings of the 1997 International Conferenece on Evolutionary Computation, Piscataway, NJ, IEEE Press, 1997, 159–163.
[106] Katayama, K. and Narihisa, H., Iterated local search approach using genetic transformation to the traveling salesman problem, in Proceedings of Genetic and Evolutionary Computation Conference, New York, USA, Morgan Kaufmann, 1999, 321–328.
[107]卢开澄,卢华明。组合数学。清华大学出版社,第3版。2002。
[2] M.R.Garey, R.L.Graham, and D.S.Johnson. Some NP-complete geometric problems, in Proc. 8th Annu. ACM Symp. Theory of Computing, 1976, 10-22.
[3] R.Baraglia, J.I.Hidalgo, and R.Perego. A hybrid heuristic for the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 2001, vol.5, no.6, 613-622.
[4] Huai-Kuang Tsai, Jinn-Moon Yang, Yuan-Fang Tsai, and Cheng-Yan Kao. An evolutionary algorithm for large traveling salesman problems, IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics, 2004, vol.34, no.4, 1718-1729.
[5] Hung Dinh Nguyen, Kunihito Yamamori, and Moritoshi Yasunaga. Implementation of an e?ective hybrid GA for large-scale traveling salesman problems, IEEE Transactions on Systems, Man, and Cybernetics–Part B: Cybernetics, 2007, vol.37, no.1, 92-99.
[6] J. H. Holland. Adaption in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.
[7] L.J. Fogel, A.J. Owens, and M.J. Walsh. Artificial Intelligence through Simulation Evolution. New York: John Wiley, 1966.
[8] I. Rechenberg. Evolutionsstrategie-Optimierung Technischer Systeme nach Prinzipfen der Biologischen Evolution. Frommann-Holzboog, Stuttgart,1973.
[9] J. Koza. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. PhD Thesis, Stanford University, 1990.
[10] D. E. Goldberg. Genetic Algorithm in Search, Optimization and Machine Learning New York: Addiso-Wesley Publishing Company, INC, 1989.
[11] L. Daris. Handbook of Genetic Algorithms. Van Nostrand Rainhold, New York, 1991.
[12]云庆夏,黄光球,王战权。遗传算法和遗传规划。冶金工业出版社,1997。
[13]张文修,梁怡。遗传算法数学基础。西安交通大学出版社,2000。
[14]刘勇,康立山,陈毓屏。非数值并行算法(第二册):遗传算法。科学出版社,1995。
[15] Z. Mchelewich. Genetic Algorithms + Data Structure = Evolutionary Programming(3rd edition). New York: Springer-Verlag, 1996.
[16]王小平,曹立明。遗传算法—理论、应用与软件实现。西安交通大学出版社,2002。
[17] W.M. Jenkins. Structural optimization with the genetic algorithm. Structural Engineer, 1991, 69(24):408-422.
[18] D. E. Goldberg. Computer-aided gas pipeline operation using genetic algorithm and rule learning. Doctoral dissertation, No. 8402282, Department of Civil Engineering, University of Michigan, 1983.
[19] R. Chandrasekharam. Genetic algorithm for embedding a complete graph in a hypercube with a VLSI application. Micro-processing and Micro-programming, 1994, 40: 537-552.
[20] Xin Yao. A review of evolutionary artificial neural network. International Journal of Intelligent Systems, 1993, 8(3): 539-565.
[21] Yoon Byungjoo. Efficient genetic algorithm for training layered feed-forword neural network. Information Science, 1994, 76(1-2): 67-85.
[22] J. J. Davis. Trainning product unit neural networks with genetic algorithms. IEEE Expert, 1993, 8(5): 26-33.
[23] D. J. Montana and L. Davis. Trainning feed-forward neural networks using genetic algorithms. In Proceeding of the International Joint Conference on Artificial Intelligence, Los Altos, CA: Morgan Kaufmann Publishers, 1989: 762-767.
[24] K. A. De Jong. Learning with genetic algorithms: an overview. Machine Learning, 1988, 3: 121-138.
[25] M. Dorigo and U. Schneph. Genetic-gased machine learning and behavior-based robotics: a new synthesis. IEEE Transaction on Systems, Man and Cybernetics, 1993, 23(1): 141-154.
[26] L.B. Booker. Classifier systems and genetic algorithms. Artificial Intelligence, 1989, 40(1-3): 235-282.
[27] G. E. Liepins and L. A. Wang. Classifier system learning of Boolean concepts. In Proceedings of Fourth International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers, 1991: 318-322.
[28] A. D. McAulay and J. C. Oh. Improving learning of genetic rule-based classifier systems. IEEE Trans. on System, Man, and Cybernetics, 1994, 24(1): 152-159.
[29] A. Barodi and P. Bonelli. A new approach to fuzzy classifiers. In Proceedings of Fifth International Conference on Genetic Algorithms, Los Altos, CA, 1993.
[30] S. Matwin. Genetic algorithms approach to negotiation support system. IEEE Tans.on Systems, Man and Cybernetics, 1991, 21(1): 102-114.
[31] C. Nikolopoulos and P. Fellrath. Hybrid expert system for investment advising. Expert System, 1994, 11(4): 245-248.
[32] P. Van Bommel. Genetic algorithm for optimal logical database design. Internetional Software Technology, 1994, 36(2): 725-732.
[33] S. Forrest. Genetic algorithm: principles of natural selection application to computation. Science, Aug. , 1993, 261: 872-878.
[34] C. L. Karr. Design of an adaptive fuzzy logic controller using genetic algorithm. In Proceedings of Fourth International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers, 1991: 450-457.
[35] L. M. Freeman. Turning fuzzy logic controller using genetic algorithms in aerospace applications. In Proceeding of the AAAIC’90 Conference, Dayton, Oct. , 1990: 351-358.
[36] F. Glover. Genetic algorithms and tabu search: hybrids for optimization. Computer and Operation Research(UK), 1995, 122(1): 111-134.
[37] Z. Michalewicz, C. Janikow, and J. Kjrawczyk. A modified genetic algorithm for optimal control problems. Computers and Mathematical Applications, 1992, 23(12): 83-94.
[38] R. J. Bauer. Genetic algorithms and investment strategies. New York: John Wiley & Sons, Inc. , 1994.
[39] D. B. Fogel. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems, 1993, 24: 27-36.
[40] J. J. Grefenstette, R. Gopal, B. Rosmaita, and D. Van Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the First International Conference on Genetic Algorithms(ICGA 1), J. J. Grefenstette(ed.), Hillsdale, NJ: Lawrence Erlbaum Associates, 1985: 160-168.
[41] Mitchell Melanie. An introduction to genetic algorithms. Cambridge, MA: The MIT Press, 1996.
[42] N. Kadaba, K. E. Nygard, and P. J. Juell. Integration of adaptive machine learning and knowledge-cased systems for routing and scheduling applications. Expert Systems with Applications, Vol. 2, No. 1, 1991: 15-27.
[43] S. H. Lin, E. D. Goodman, and W. F. Punch. Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problem. In the Sixth International Conference on Evolutionary Programming, P. Angeline, R. J. M. Reynolds, and R. Eberhart(eds.), Berlin: Springer-Verlag, April 1997: 383-393.
[44] D. Maclay, and R. Dorey. Applying genetic search techniques to drivertrain modeling. IEEE Control Systems, Special Issue on Intelligent Control, Vol. 13, No. 3, June, 1993:50-55.
[45] J. Zhang and P. D. Robert. Use of genetic algorithms in training dagnostic rules for process fault dagnosis. Knowledge-Based Systems, Vol. 5, No. 4, Dec. , 1992: 277-288.
[46] Binglin Zhong. Genetic algorithm for diagnosis problem solving. In Proceeding of the IEEE International Conference on Systems, Man and Cybernetics. IEEE Service Center, Piscataway, NJ, USA, 1992: 404-408.
[47] Y. Davidor. Genetic algorithm and robotics, a heuristic strategy for optimization. World Scientific Series in Robotics and Automated System, 1991, 1.
[48] M. A. C. Gill and A. Y. Zomaya. Obstacle avoidance in multi-robot systems: experiments. In Parallel Genetic Algorithms. Singapore: World Scientific Press, 1998.
[49] R. A. McCallum and K. A. Spackman. Using genetic algorithm to learn disjunctive rules from examples. In Proceeding of the International Conference on Machine Learning, San Mateo, CA: Morgan Kaufmann, 1990: 149-152.
[50] J. Bala, K. A. De Jong, J. Huang, H. Vafaie, and H. Wechsler. Hybrid learning using genetic algorithms and decision trees for pattern classification. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada, August 19-25, 1995.
[51] B. K. Lavine. Pattern recognition analysis via genetic algorithms & multivariate statistical methods. Boca Raton, Fla: CRC Press, 2000.
[52] K. Bennett. A genetic algorithm for database query optimization. IEEE Conference on Evolutionary Computation, 1994: 400-407.
[53] J. D. Schaffer, L. D. Whitley, and L. J. Eshelman. Combinations of genetic algorithms and neural networks: a survey of the state of the art. In Proceedings of the International Workshop on Combinations of Genetic Algorithms and Neural Networks, Baltimore, June, 1992: 1-37.
[54] A. J. F. von Rooij, L. C. Jain, and R. P. Johnson. Neural network training using genetic algorithms. Singapore: World Scientific Press, 1996.
[55] H. Adeli. Machine learning: neural networks, genetic algorithms, and fuzzy systems. New York: John Wiley & Sons, 1995.
[56] E. Vonk, L. C. Jain, and R. P. Johnson. Automatic generation of neural network architecture using evolutionary computation. Singapore: World Scientific Press, 1997.
[57] J. R. Koza. Recognizing patterns in protein sequences using iteration-performing calculations in genetic programming. In Proceedings of the 1st IEEE ConferenceEvolutionary Computation, Piscataway, NJ, 1994, Part 1: 244-249.
[58] S. K. Pal. Genetic algorithms for pattern recognition. Boca Raton, Fla: CRC Press, 1996.
[59] S.Arora, C.Lund, R.Motwani, M.Sudan, and M.Szegedy, Proof verification and intractability of approximation problems, in Proc. 33rd IEEE Symp. Foundations of Computer Science, 1992, 13-22.
[60] G. Gutin and A. P. Punnen(Eds.). The Traveling Salesman Problem and Its Variations. London: Kluwer, 2002.
[61] http://iris.gmu.edu/~khoffman/papers/trav_salesman.html.
[62] S. A. Cook. The complexity of theorem-proving procedures. Proceedings of 3rd Annual ACM Symposium on the Theory of Computing, 1971, 151-158.
[63]王晓东编著。计算机算法设计与分析。电子工业出版社,北京,2001。
[64] S. Lin. Computer solutions of the traveling salesman problem. Bell System Computer Journal, 1965, 44, 2245-2269.
[65] S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 1973, 11, 972-989.
[66]周明。传算法原理及应用。国防工业出版社,2000。
[67] D. B. Fogel. Evolutionary Computation: toward a new philosophy of machine intelligence. IEEE Neural Networks Council. New York: IEEE Press, 1995.
[68] K. Miettinen, P. Neittaanmaki, and J. Periaux(eds). Evolutionary algorithms in engineering and computer science: recent advances in genetic algorithms, evolution strategies, evolutionary programming. New York: John Wiley & Sons, June, 1999.
[69] T. B?ck, D. B. Fogel, and Z. Michalewicz. HandBook of Evolutionary Computation. University Oxford Press, New York, 1997.
[70] N. Srinivas and Deb. Kalyanmoy. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithm, Evolutionary Computation. 1994, 2(3): 221-248.
[71] H. P. Schwefel. Numerical Optimization of Computer Models. John Wiley, Chichester, UK, 1981.
[72]李敏强等。遗传算法的基本理论与应用。科学出版社,2002。
[73] D. B. Fogel. Evolutionary Programming for Training Neural Networks. International Joint Conf. on Neural Networks'90. Washington.D.C., 1990, 1601-1605.
[74] D. B. Fogel. Evolving Neural Networks. Biol. Cybern. 1990, 487-493.
[75] N. Saravanan, D. B. Fogel. Evolving Neurocontrollers Using Evolutionary Programming. In ICEC'94, Orlando, Florida. USA, IEEE Press. 1994, 63-66.
[76] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natual Selection. MIT Press. Cambridge. 1992.
[77] J. R. Koza. Genetic Programming II: Automatic Discovery of reusable programs. MIT Press. Cambridge. 1994.
[78]徐宗本,高勇。遗传算法过早收敛现象的特征分析及其预防。中国科学(E辑)。1996, 4:364-375。
[79]张讲社,徐宗本,梁怡。遗传算法的整体退火选择及其收敛主要条件。中国科学(E辑)。1997, 2:154-164。
[80] X. F. Qi and F. Palmieri. Theoretical analysis of evolution algorithms with an infinite population size in continuous space, Part 1, 2: basic properties of selection and mutation. IEEE Transactions on Neural Network, 1994, 5(1): 102-129.
[81]梁艳春,王在申,周春光。选择和变异操作下遗传算法的收敛性研究。仅算机研究与进展,1998,35(7):657-662。
[82] T. B?ck and H. P. Schwefel. Evolutionary computation: an overview. In Proceedings of the Third IEEE Conference on Evolutionary Computation. Piscataway: IEEE Press, 1996, 20-29。
[83] G. Rudolph. Self-Adaptation and global convergence: A Counter-Example. In Proceedings of the Congress on Evolutionary Computation, Piscataway: IEEE Press, 1999, 1: 646-651.
[84] G. Rudolph. Convergence of non-elitist strategies. In Proceedings of the First IEEE Conference on Evolutionary Computation, Piscataway: IEEE Services Center, 1994, 1: 63-66.
[85] G. Rudolph. Convergence of evolutionary algorithms in general search spaces. In Proceedings of the Third IEEE Conference on Evolutionary Computation, Piscataway, NJ: IEEE Services Center, 1996, 1: 50-54.
[86] J. Grefenstete, et. al. Genetic algorithms for the traveling salesman problem. in Proc. of 1st Int. Conf. in Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates,1985, 154-168.
[87] Yuping Wang, Yinghua Li, and Chuangyin Dang. A novel globally convergent hybrid evolutionary algorithm for traveling salesman problems. In Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, August 2004, 26-29.
[88] Yuping Wang, Lixia Han, Yinghua Li, and Shuguang Zhao. A new encoding based genetic algorithm for the traveling salesman problem. Engineering Optimization. January 2006, Vol. 38, No. 1, 1-13.
[89] L. Davis. Applying adaptive algorithms to epistatic domains. in Proc. of 9th Int. Joint Conf. on Artificial Intelligence. 1985.
[90] I. Oliver, D.Smith and J. Holland. A study of permutation crossover operators on the traveling salesman problem. in Proc. 2nd Int. Conf. Genetic Algorithms. 1987, 224 - 230.
[91] A.Homaifar, S .Guan, and G. Liepins. A new approach on the traveling salesman problem by genetic algorithms. North Carolina A & T State Univ. ,Greensboro, NC. 1991 .
[92] D. Whitley, et. al. Scheduling problems and traveling salesman: the genetic edge recombination operator. in P roc. of 3rd Int. Conf. on Genetic Algorithms. Morgan Kaufmann, 1989, 133-140.
[93] T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, and C. Whitley. A comparison of genetic sequencing operators. in Proc. 4th Int. Conf. Genetic Algorithms. 1991, 69-76.
[94]B. Freisleben and P. Merz. New genetic local search operators for the traveling salesman problem. in Proc. 4th Conf. Parallel Problem Solving from Nature. 1996, 616 - 621.
[95] Soonchul Jung and Byung-Ro Moon. Toward minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean TSP. IEEE Trans. on Evolutionary Computation. 2002, Vol. 6, No. 6, 557-565.
[96] Y. Nagata and S. Kobayashi. Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In T.B?ck, editor, Proc. of the 7th Int. Conf. on GAs, Morgan Kaufumann, 1997.
[97] H. K. Tsai, J. M. Yang, and C. Y. Kao. Solving traveling salesman problems by combining global and local search mechanisms. in Proc. Congr. Evolutionary Computation, 2002, 1290-1295.
[98] D. B. Fogel. A parallel processing approach to a multiple traveling salesman problem using evolutionary programming. in L .Canter( ed.) Proceedings on the Fourth Annual Parallel Processing Symposium. Fullerton, CA, 1990, 318-326.
[99] D. B. Fogel. An evolutionary approach to the traveling salesman problem. Biol. Cybern. , 1988, 60, 139-144.
[100] W. Banzhaf. The "Molecular" traveling salesman problem. Biological Cybernetics. 1990, 64, 7-14.
[101] A.K. Jain, M.N. Murty, P.J. Flyn.: Data clustering: A review. ACM Computing Survey. 1999, 31(3) , 264-323.
[102] T. B?ck. Evolutionay algorithms in theory and practice. New York, Oxford Univ. Press. 1996.
[103] G. Reinelt. TSPLIB-A traveling salesman library. ORSA J. Comput. , 1991, Vol.3, No.4, 376-384.
[104] D. S. Johnson. Local optimization and the traveling salesman problem, in Proceedings of 17th Automata, Languages, and Programming, Warwick University, England, Springer-Verlag, 1990, 446–461.
[105] P. Merz and B. Freisleben. Genetic local search for the TSP. New results, in Proceedings of the 1997 International Conferenece on Evolutionary Computation, Piscataway, NJ, IEEE Press, 1997, 159–163.
[106] Katayama, K. and Narihisa, H., Iterated local search approach using genetic transformation to the traveling salesman problem, in Proceedings of Genetic and Evolutionary Computation Conference, New York, USA, Morgan Kaufmann, 1999, 321–328.
[107]卢开澄,卢华明。组合数学。清华大学出版社,第3版。2002。