TSP遗传算法的改进及其并行化研究
|
摘要
遗传算法是一种模拟自然界生物进化的搜索算法，由于它简单易行、鲁棒性强，尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，取得了令人瞩目的成果，引起了广大学者和工程人员的关注。
遗传算法是一种新兴的技术，正处于发展期。虽然在应用领域获得了丰收，但其理论基础还较薄弱，有许多地方需要研究和发展充实。
本文对遗传算法的理论与应用进行了一些研究和分析工作。首先介绍了遗传算法的理论和它在组合优化问题中的应用，然后针对基于遗传算法的TSP问题求解，在原有遗传算法的基础上提出了一种改进的混合遗传算法。该算法在迭代初期引入不适应度函数作为评价标准，结合启发式交叉和边重组交叉算子设计了一种新的交叉算子，采用了模式变异和启发式变异相结合的混合变异算子，并对变异后个体进行免疫操作。数值实验表明，该算法是有效的。最后，为克服遗传算法计算量大的问题，基于遗传算法的并行特性，实现了一种主从式并行混合遗传算法，实验数值结果证明了该算法的可行性和有效性。
The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it doesn't need the special field knowledge, so it has been used in every broad fields. Now the genetic algorithm has got a lot of fruits and more scholars begin to pay attention to it.
The genetic algorithm is still a new developing technology. Despite its success in so many domains, its theoretical fundament is relatively weak. There are still lots of problems to be studied and improved.
This paper has done some work in the research and application of the genetic algorithm. First, The introduction on GA's theory and its applications on combination optimization are given. An improved hybrid genetic algorithm is then presented for TSP problem. In this algorithm, the unfitness function is chosen as a merit at the beginning of iterative and a new cross operation is designed.In addition, we use a hybrid mutation operation, and make immune operation on individual after mutation operation. The simulation numerical results show that this algorithm is efficient. At last, to overcome GA's large computation consumption, a master/slave parallel hybrid genetic algorithm is implemented based on the GA's parallel characteristic. The experiment results demonstrate that the method is valid and efficitive.
遗传算法是一种新兴的技术，正处于发展期。虽然在应用领域获得了丰收，但其理论基础还较薄弱，有许多地方需要研究和发展充实。
本文对遗传算法的理论与应用进行了一些研究和分析工作。首先介绍了遗传算法的理论和它在组合优化问题中的应用，然后针对基于遗传算法的TSP问题求解，在原有遗传算法的基础上提出了一种改进的混合遗传算法。该算法在迭代初期引入不适应度函数作为评价标准，结合启发式交叉和边重组交叉算子设计了一种新的交叉算子，采用了模式变异和启发式变异相结合的混合变异算子，并对变异后个体进行免疫操作。数值实验表明，该算法是有效的。最后，为克服遗传算法计算量大的问题，基于遗传算法的并行特性，实现了一种主从式并行混合遗传算法，实验数值结果证明了该算法的可行性和有效性。
The genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it doesn't need the special field knowledge, so it has been used in every broad fields. Now the genetic algorithm has got a lot of fruits and more scholars begin to pay attention to it.
The genetic algorithm is still a new developing technology. Despite its success in so many domains, its theoretical fundament is relatively weak. There are still lots of problems to be studied and improved.
This paper has done some work in the research and application of the genetic algorithm. First, The introduction on GA's theory and its applications on combination optimization are given. An improved hybrid genetic algorithm is then presented for TSP problem. In this algorithm, the unfitness function is chosen as a merit at the beginning of iterative and a new cross operation is designed.In addition, we use a hybrid mutation operation, and make immune operation on individual after mutation operation. The simulation numerical results show that this algorithm is efficient. At last, to overcome GA's large computation consumption, a master/slave parallel hybrid genetic algorithm is implemented based on the GA's parallel characteristic. The experiment results demonstrate that the method is valid and efficitive.
引文
[1] 罗省贤，何大可 编著．基于MPI的网络并行计算环境及应用．成都：西南交通大学出版社．2001
[2] Bagley J D, The Behavior of Adaptive System which Employ Genetic and Correlation Algorithm, Dissertation Abstracts International, 1967, 28(12)
[3] Holland J H, Adaptation in Natural and Artificial Systems, University of Michigan Press,1975
[4] Goldberg D E, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, 1989
[5] Davis L D, Handbook of Genetic Algorithms, Van Nostrand reinhold, 1991
[6] Michalewicz Z, Genetie Algorithms + Data Structures=Evolution Program, Springer, 1992
[7] Srinivas M. Patnaik L M, Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm, Man and Cybernities, 1994.24(4)
[8] Korte B, Applications of combinational Optimization, T3rd Int mathematical programming symp, 1988
[9] Bland R G and Shallcross D F, Large Traveling Salesman Problem arising from experiments in X-ray crystallography Ops Res Lett, 1989, 8:125-128
[10] Litke J D, An improved solution to the traveling salesman problem with thousands of nodes, ACM commun, 1984,27:1227-1236
[11] Grotschel M and Holland O, Solution of large-scale symmetric traveling salesman problems, Mathe-matical Programming, 1991, 51(2): 141-202
[12] Starkweather, T.et.al,A comparison of Genetic Sequencing Operators, Proceedings of the 4~(th) International Conference on Genetic Algorithms, 1991,69-76
[13] 谢金星 邢文训，现代优化计算方法．北京：清华大学出版社．2000，130-158
[14] 王凌．智能优化算法及其应用．北京：清华大学出版社．2001
[15] 周明 孙树栋．遗传算法原理及应用．北京：国防工业出版社．1996，1-60
[16] 王正志 薄涛．进化计算．北京：国防科技大学出版社．2000，212-244
[17] 玄光男等著，王定伟等译．遗传算法与工程设计．北京：科学出版社．1999
[18] 康立山，谢云等．非数值并行遗传算法——模拟退火算法．北京：科学出版社，1997
[19] 陈国良 王煦法．遗传算法及其应用．北京：人民邮电出版社．1996
[20] 王小平 曹立明．遗传算法理论、应用及软件实现．西安：西安交大出版社，2002
[21] 唐立新．旅行商问题(TSP)的改进遗传算法．东北大学学报，1999．2
[22] 吴志远等．一种新的自适应遗传算法及其在多峰值函数优化中的应用．控制理论和应用，1999，16(1)：127-129
[23] 马均水等．改进遗传算法搜索性能的大变异操作．控制理论和应用，1998，15(3)：404-407
[24] 谢胜利 唐敏等．求解TSP问题的一种改进遗传算法．计算机工程与应用，2002
[25] 王磊 潘进等．免疫算法．电子学报，2000．28(7)：74-78
[26] 徐宗本 聂赞坎 等．父代种群参与竞争遗传算法几乎必然收敛．应用数学学报，2002．1
[27] 梁艳春 冯大鹏等．遗传算法求解旅行商问题时的基因片段保序．系统工程理论与实践，2000．4
[28] 张文修，梁怡．遗传算法的数学基础．西安：西安交通大学出版社．2000
[29] 李敏强 寇纪凇等．遗传算法的基本理论与应用．北京：科学出版社．1999
[30] 尉宇 孙德宝．自适应最优保存的模拟退火遗传算法及应用．华中科技大学学报，2001．9
[31] 孙瑞祥等．遗传算法优化效率的定量评价．控制理论与应用，2001．4
[32] 刘勇 康立山 陈毓屏．非数值并行算法-遗传算法．北京：科学出版社．2000
[33] 史忠植．高级人工智能．北京：科学出版社．1997
[36] 张铃，张钹．问题求解理论及应用．北京：清华大学出版社．1990
[37] 华罗庚，王元．数论在近似分析中的应用．北京：科学出版社．1978
[38] 刘植义等．遗传学．北京：人民教育出版社．1982
[39] 孙树栋，曲彦宾．基于C语言的遗传算法工具箱．西北工业大学学报．1997，15(3)
[40] 谢政，李建平．网络算法与复杂性理论．长沙：国防科技大学出版社，1995
[41] Korte B, Applications of combinational Optimization, T3rd Int mathematical programming symp, 1988
[42] Bland R G and Shallcross D F, Large Traveling Salesman Problem arising from experiments in X-ray crystallography Ops Res Lett, 1989, 8:125-128
[43] Litke J D, An improved solution to the traveling salesman problem with thousands of nodes, ACM commun, 1984,27:1227-1236
[44] Grotschel M and Holland O, Solution of large-scale symmetric traveling salesman problems, Mathematical Programming, 1991, 51(2): 141-202
[45] 都志辉 编著．高性能计算并行编程技术——MPI并行程序设计．北京：清华大学出版社．2001
[46] 李晓梅 等著．并行与分步式可视化技术及应用．北京：国防工业出版社．2001
[47] 刘键 著．并行分布式程序设计．武汉：华中理工大学出版社．1997
[48] 陈国良 著．并行算法的设计与分析．北京：高等教育出版社．1994
[49] 沈志宇，胡子昂 等著．并行编译方法．北京：国防工业出版社．2000
[50] MPICH User Guide
[51] MPE User Guide
[52] http://www-unix.mcs.anl.gov/mpi/mpich/
[53] http://www.ict.ac.cn/lab/ncic/product/
[54] http://www.lighten.com.cn/calculation/programming_stom.asp
[55] http://www.rdcps.ac.cn/shouye/pris2.htm
[56] http://www.huihoo.org/npact/content.htm
[2] Bagley J D, The Behavior of Adaptive System which Employ Genetic and Correlation Algorithm, Dissertation Abstracts International, 1967, 28(12)
[3] Holland J H, Adaptation in Natural and Artificial Systems, University of Michigan Press,1975
[4] Goldberg D E, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, 1989
[5] Davis L D, Handbook of Genetic Algorithms, Van Nostrand reinhold, 1991
[6] Michalewicz Z, Genetie Algorithms + Data Structures=Evolution Program, Springer, 1992
[7] Srinivas M. Patnaik L M, Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm, Man and Cybernities, 1994.24(4)
[8] Korte B, Applications of combinational Optimization, T3rd Int mathematical programming symp, 1988
[9] Bland R G and Shallcross D F, Large Traveling Salesman Problem arising from experiments in X-ray crystallography Ops Res Lett, 1989, 8:125-128
[10] Litke J D, An improved solution to the traveling salesman problem with thousands of nodes, ACM commun, 1984,27:1227-1236
[11] Grotschel M and Holland O, Solution of large-scale symmetric traveling salesman problems, Mathe-matical Programming, 1991, 51(2): 141-202
[12] Starkweather, T.et.al,A comparison of Genetic Sequencing Operators, Proceedings of the 4~(th) International Conference on Genetic Algorithms, 1991,69-76
[13] 谢金星 邢文训，现代优化计算方法．北京：清华大学出版社．2000，130-158
[14] 王凌．智能优化算法及其应用．北京：清华大学出版社．2001
[15] 周明 孙树栋．遗传算法原理及应用．北京：国防工业出版社．1996，1-60
[16] 王正志 薄涛．进化计算．北京：国防科技大学出版社．2000，212-244
[17] 玄光男等著，王定伟等译．遗传算法与工程设计．北京：科学出版社．1999
[18] 康立山，谢云等．非数值并行遗传算法——模拟退火算法．北京：科学出版社，1997
[19] 陈国良 王煦法．遗传算法及其应用．北京：人民邮电出版社．1996
[20] 王小平 曹立明．遗传算法理论、应用及软件实现．西安：西安交大出版社，2002
[21] 唐立新．旅行商问题(TSP)的改进遗传算法．东北大学学报，1999．2
[22] 吴志远等．一种新的自适应遗传算法及其在多峰值函数优化中的应用．控制理论和应用，1999，16(1)：127-129
[23] 马均水等．改进遗传算法搜索性能的大变异操作．控制理论和应用，1998，15(3)：404-407
[24] 谢胜利 唐敏等．求解TSP问题的一种改进遗传算法．计算机工程与应用，2002
[25] 王磊 潘进等．免疫算法．电子学报，2000．28(7)：74-78
[26] 徐宗本 聂赞坎 等．父代种群参与竞争遗传算法几乎必然收敛．应用数学学报，2002．1
[27] 梁艳春 冯大鹏等．遗传算法求解旅行商问题时的基因片段保序．系统工程理论与实践，2000．4
[28] 张文修，梁怡．遗传算法的数学基础．西安：西安交通大学出版社．2000
[29] 李敏强 寇纪凇等．遗传算法的基本理论与应用．北京：科学出版社．1999
[30] 尉宇 孙德宝．自适应最优保存的模拟退火遗传算法及应用．华中科技大学学报，2001．9
[31] 孙瑞祥等．遗传算法优化效率的定量评价．控制理论与应用，2001．4
[32] 刘勇 康立山 陈毓屏．非数值并行算法-遗传算法．北京：科学出版社．2000
[33] 史忠植．高级人工智能．北京：科学出版社．1997
[36] 张铃，张钹．问题求解理论及应用．北京：清华大学出版社．1990
[37] 华罗庚，王元．数论在近似分析中的应用．北京：科学出版社．1978
[38] 刘植义等．遗传学．北京：人民教育出版社．1982
[39] 孙树栋，曲彦宾．基于C语言的遗传算法工具箱．西北工业大学学报．1997，15(3)
[40] 谢政，李建平．网络算法与复杂性理论．长沙：国防科技大学出版社，1995
[41] Korte B, Applications of combinational Optimization, T3rd Int mathematical programming symp, 1988
[42] Bland R G and Shallcross D F, Large Traveling Salesman Problem arising from experiments in X-ray crystallography Ops Res Lett, 1989, 8:125-128
[43] Litke J D, An improved solution to the traveling salesman problem with thousands of nodes, ACM commun, 1984,27:1227-1236
[44] Grotschel M and Holland O, Solution of large-scale symmetric traveling salesman problems, Mathematical Programming, 1991, 51(2): 141-202
[45] 都志辉 编著．高性能计算并行编程技术——MPI并行程序设计．北京：清华大学出版社．2001
[46] 李晓梅 等著．并行与分步式可视化技术及应用．北京：国防工业出版社．2001
[47] 刘键 著．并行分布式程序设计．武汉：华中理工大学出版社．1997
[48] 陈国良 著．并行算法的设计与分析．北京：高等教育出版社．1994
[49] 沈志宇，胡子昂 等著．并行编译方法．北京：国防工业出版社．2000
[50] MPICH User Guide
[51] MPE User Guide
[52] http://www-unix.mcs.anl.gov/mpi/mpich/
[53] http://www.ict.ac.cn/lab/ncic/product/
[54] http://www.lighten.com.cn/calculation/programming_stom.asp
[55] http://www.rdcps.ac.cn/shouye/pris2.htm
[56] http://www.huihoo.org/npact/content.htm