混沌群体智能及其优化算法的研究和应用
摘要
混沌是指在确定性系统中出现的一种貌似无规则的类似随机的现象。由于这个性质,使它可以被应用于科学的各个领域。近年来生物学家Cloe发现整个蚁群行为是一种周期行为,然而单个蚂蚁的行为却是混沌的,显然混沌现象用Dorigo依据概率理论建立的蚁群优化模型是无法解释的。90年代初,学者Dorigo基于蚂蚁在食物源和蚁巢间可以形成一条最短路径的著名试验提出了蚁群最优化算法理论,并用它成功地解决了大量NP组合优化和路由器选择问题。混沌群体智能的这种复杂的动力学特性使它在信息处理和优化计算等方面有着广泛的应用前景。
本文对混沌群体智能进行了深入的研究。首先系统的介绍了混沌动力学的基本理论,给出了混沌的概念和定性特征、Lyapunov指数、测度熵等,并列举了两种最为典型的混沌系统——Logistic映射和洛伦兹方程,进行了详细的分析。
然后给出了群体智能网络模型,并利用连续型基本蚁群算法(AS)模型求解旅行商问题(TSP)。
接着在此基础上给出了一种基于最大最小型的蚁群(MMAS)算法,并进行了重点研究。它将混沌机制引入网络,利用混沌的遍历性进行随机搜索,再由混沌动态退出和倒分岔出现,使MMAS逐渐趋于一般的AS。这样既避免了陷于局部极小,又加快了收敛速度,使网络能快速收敛到一个全局最优或近似最优的稳定平衡点。仿真结果表明,这是一种能有效解决局部极值问题的全局最优化算法。
最后,本文又进行了仿真,结果表明,它具有更快的收敛速度。
Chaotic system is a kind of determined system and at the same time it appears random phenomenon which looks like to have no rules. Because of this property, it can be used in each realm of science.Recently biologist Cloe find that the acts of a hole ants are regular, but one the act of one ant is chaotic. In the early 90s, based on the fact that ants can find a shortest way from foods to their holes, Dorigo invented ant colony algorithm, with this algorithm, he successfully solves a lot of choose completely NP problem. It comples characteristics make it possiblely for the network to be a technology with extensively application foreground for information processing and optimality calculation.
A in-depth research is done to chaotic swarm intelligence in this pape. Firstly, it introduces the basic theories of the chaotic dynamics completely, gives the concept of chaos, the qualitative attribute, the Lyapunov index, the Kolmogorov entropy, and so on. And then it makes two examples, Logistic and Lorenz Equation, which are the most typical chaotic systems, and analyses them in detail.
Secondly, it introduces the model of swarm intelligence, and uses the model of continuous ant colony algorithm to solve traveling salesman problem(TSP).
Thirdly, it gets a kind of max-min chaotic ant colony algorithm, and Carries on the research carefully. It introduces chaos mechanism into the system, and then applies chaotic ergodicity to stochastic search and controls the chaotic dynamics by annealing strategy to perform inverse bifurcation and disappear. MMAS gradually approaches to AS and converges to a stable point which is globally optimal or near-optimal. Simulation result shows that it is a global optimization algorithm which can effectively avoid local minimal.
Lastly, it simulations the system, the simulation result shows that it has more rapid convergenced speed than AS.
本文对混沌群体智能进行了深入的研究。首先系统的介绍了混沌动力学的基本理论,给出了混沌的概念和定性特征、Lyapunov指数、测度熵等,并列举了两种最为典型的混沌系统——Logistic映射和洛伦兹方程,进行了详细的分析。
然后给出了群体智能网络模型,并利用连续型基本蚁群算法(AS)模型求解旅行商问题(TSP)。
接着在此基础上给出了一种基于最大最小型的蚁群(MMAS)算法,并进行了重点研究。它将混沌机制引入网络,利用混沌的遍历性进行随机搜索,再由混沌动态退出和倒分岔出现,使MMAS逐渐趋于一般的AS。这样既避免了陷于局部极小,又加快了收敛速度,使网络能快速收敛到一个全局最优或近似最优的稳定平衡点。仿真结果表明,这是一种能有效解决局部极值问题的全局最优化算法。
最后,本文又进行了仿真,结果表明,它具有更快的收敛速度。
Chaotic system is a kind of determined system and at the same time it appears random phenomenon which looks like to have no rules. Because of this property, it can be used in each realm of science.Recently biologist Cloe find that the acts of a hole ants are regular, but one the act of one ant is chaotic. In the early 90s, based on the fact that ants can find a shortest way from foods to their holes, Dorigo invented ant colony algorithm, with this algorithm, he successfully solves a lot of choose completely NP problem. It comples characteristics make it possiblely for the network to be a technology with extensively application foreground for information processing and optimality calculation.
A in-depth research is done to chaotic swarm intelligence in this pape. Firstly, it introduces the basic theories of the chaotic dynamics completely, gives the concept of chaos, the qualitative attribute, the Lyapunov index, the Kolmogorov entropy, and so on. And then it makes two examples, Logistic and Lorenz Equation, which are the most typical chaotic systems, and analyses them in detail.
Secondly, it introduces the model of swarm intelligence, and uses the model of continuous ant colony algorithm to solve traveling salesman problem(TSP).
Thirdly, it gets a kind of max-min chaotic ant colony algorithm, and Carries on the research carefully. It introduces chaos mechanism into the system, and then applies chaotic ergodicity to stochastic search and controls the chaotic dynamics by annealing strategy to perform inverse bifurcation and disappear. MMAS gradually approaches to AS and converges to a stable point which is globally optimal or near-optimal. Simulation result shows that it is a global optimization algorithm which can effectively avoid local minimal.
Lastly, it simulations the system, the simulation result shows that it has more rapid convergenced speed than AS.
引文
[1] Gambardella L.M and Dorigo M. HAS-SOP:hybrid ant system for the sequential orderging problem. Technique Report, No.IDSIA 1997
[2] Herskovits E. Computer-based Probabilistic-Network Construction. Doctoral dissertation, Stanford University, 1991
[3] Luis M. de Campos. Ant colony optimization for learning Bayesian networks. International Journal of Approximate Reasoning 31,2002
[4] Colorni A.,Dorigo M.and Maniezzo V..Distributed Optimization by Ant Colonies.Proc of the First European Conf on Artificial Life,Paris,France:Elsevier Publishing,1991
[5] Dorigo M.,Bonabeau E.and Theraulaz G.,Ant algorithms and stigmergy. Future generation Computer Systems,2000,16
[6] Casati G,Ford J(eds.).Stochastic behavior in Classical and Quantum Hamiltonian Systems[J].Lecture Notes in Physics.93,1979.
[7] Lorenz E N.Deterministic nonperiodic flow[J].J.Atoms.Sci.20,1963.
[8] Li T Y,Yorke J A.Period three implies chaos[J].Amer.Math.Monthly.82,1975.
[9] May R.Simple mathematical models with very complicated dynamics[J].Nature,261, 1976.
[10] Feigenbaum M J.Quantitative universality for a class of nonlinear transforma- tions[J].J.Stat.Phys.19(1),1978.
[11] The universal metric properties of nonlinear transformations[J].J.Stat.Phys. 21(6),1979.
[12] Miller W T.Real-time Application of Neural Networks for Sensor-based Control of Robots with Vision[J].IEEE.Trans.Syst.Man.Cybem.19:825-831,1989.
[13] Freeman W J.Simulation of chaotic EEG patterns with a dynamic model of the olfactory system[J].Biological Cybernetics.56(23):139-150,1987.
[14] Nozawa H.A neural network model as a globally coupled map and applications based on chaos[J].Chaos.2:377-386,1992.
[15] Inoue M,Nagayoshi A.A chaos neurocomputer[J].Physics Letter A.158(8):373-376, 1991.
[16] Sttltzle T.and Dorigo M., ACO Algorithms for the Traveling Salesman Problem. Evolutionary Algorithms in Engineering and Computer Science, Wiley,1999
[17] Inoue M,Nagayoshi A.Solving an optimization problem with a chaos neural network[J].Prog.Theor.Phys.66(4):769-773,1992a.
[18] 卢侃,孙建华编著.混沌学传奇[M].上海:上海翻译出版公司.1991.
[19] 吴祥兴,陈忠等编著.混沌学导论[M].上海:上海科学技术文献出版社.1996.
[20] 吕金虎,陆君安等编著.混沌时间序列分析及其应用[M].武汉:武汉大学出版社.2002.
[21] 郝柏林编著.从抛物线谈起——混沌动力学[M].上海:上海教育出版社.1993.
[22] Mandelbrot B B.The fractal geometry of nature[M].Freeman Campany.California. 1982.
[23] 肯尼思等编著.分形几何——数学基础及其应用[J].沈阳:东北工学院出版社.1991.
[24] 汪小帆.Chen's 吸引子——一个新的混沌吸引子[J].控制理论与应用.16(5),1999.
[25] Chen G,Lai D.Feedback anticontrol of discrete-chaos[J].Int.J.of Bifur.Chaos. 8:1585-1590, 1998.
[26] 飞思科技产品研发中心编著.MATLAB 6.5 辅助优化计算与设计[M].北京:电子工业出版社.2003.
[27] Hopfield J J.Neural networks and physical systems with emergent collective computational abilities[J].In:Proc.Natl.Acad.Sci.79:2554-2558,1982.
[28] 吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10)
[29] 陈宝林编著.最优化理论和算法[M].北京:清华大学出版社.2000.
[30] 丁建立,陈增强,袁著祉.遗传算法与蚁群算法的融合.计算机研究与发展.2003,40(9)
[31] Wilson V, Pawlay G S.On the stability of the TSP problem algorithm of Hopfield and Tank[J].Biol.Cybern.58:63-70,1988.
[32] Foster I. Designing and Building Parallel Programs. Addison-Weslley,Reading, MA,1994
[33] Adachi M,Aihara K,Kotani M.An analysis of associative dynamics in a chaotic neural network with external stimulation[J].Proc.IJCNN-93 NAGOYA.1: 409-412, 1993.
[34] Dempster A.P. Laird N.M. and Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm.Journal of the Royal Statistical Society, 1997
[35] 吴斌,史忠植.一种基于蚁群算法的 TSP 问题分段求解算法[J].计算机学报,第 24 卷,第 12 期,2001.12
[36] 周登勇,戴汝为.一个基于改进蚁群算法的多点路由算法[J].系统工程与电子技术.2001,23(8).
[37] 丁亚平,吴庆生.一种新的化学计量学方法----蚁群算法[J].化学通报.2002,65(4).
[38] 李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社.2002.
[39] 段海滨.蚁群算法原理及其应用[M].科学出版社.2002.
[40] 楼顺天,陈生潭.Matlab 5.x 程序设计语言[M].西安电子科技大学出版社.2002
[41] 史忠植.智能主体及其应用[M].科学出版社.2000.
[42] 张纪会,高齐圣.自适应蚁群算法[J].控制理论与应用.2000,17(1)
[43] 覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制.2002,31(3).
[2] Herskovits E. Computer-based Probabilistic-Network Construction. Doctoral dissertation, Stanford University, 1991
[3] Luis M. de Campos. Ant colony optimization for learning Bayesian networks. International Journal of Approximate Reasoning 31,2002
[4] Colorni A.,Dorigo M.and Maniezzo V..Distributed Optimization by Ant Colonies.Proc of the First European Conf on Artificial Life,Paris,France:Elsevier Publishing,1991
[5] Dorigo M.,Bonabeau E.and Theraulaz G.,Ant algorithms and stigmergy. Future generation Computer Systems,2000,16
[6] Casati G,Ford J(eds.).Stochastic behavior in Classical and Quantum Hamiltonian Systems[J].Lecture Notes in Physics.93,1979.
[7] Lorenz E N.Deterministic nonperiodic flow[J].J.Atoms.Sci.20,1963.
[8] Li T Y,Yorke J A.Period three implies chaos[J].Amer.Math.Monthly.82,1975.
[9] May R.Simple mathematical models with very complicated dynamics[J].Nature,261, 1976.
[10] Feigenbaum M J.Quantitative universality for a class of nonlinear transforma- tions[J].J.Stat.Phys.19(1),1978.
[11] The universal metric properties of nonlinear transformations[J].J.Stat.Phys. 21(6),1979.
[12] Miller W T.Real-time Application of Neural Networks for Sensor-based Control of Robots with Vision[J].IEEE.Trans.Syst.Man.Cybem.19:825-831,1989.
[13] Freeman W J.Simulation of chaotic EEG patterns with a dynamic model of the olfactory system[J].Biological Cybernetics.56(23):139-150,1987.
[14] Nozawa H.A neural network model as a globally coupled map and applications based on chaos[J].Chaos.2:377-386,1992.
[15] Inoue M,Nagayoshi A.A chaos neurocomputer[J].Physics Letter A.158(8):373-376, 1991.
[16] Sttltzle T.and Dorigo M., ACO Algorithms for the Traveling Salesman Problem. Evolutionary Algorithms in Engineering and Computer Science, Wiley,1999
[17] Inoue M,Nagayoshi A.Solving an optimization problem with a chaos neural network[J].Prog.Theor.Phys.66(4):769-773,1992a.
[18] 卢侃,孙建华编著.混沌学传奇[M].上海:上海翻译出版公司.1991.
[19] 吴祥兴,陈忠等编著.混沌学导论[M].上海:上海科学技术文献出版社.1996.
[20] 吕金虎,陆君安等编著.混沌时间序列分析及其应用[M].武汉:武汉大学出版社.2002.
[21] 郝柏林编著.从抛物线谈起——混沌动力学[M].上海:上海教育出版社.1993.
[22] Mandelbrot B B.The fractal geometry of nature[M].Freeman Campany.California. 1982.
[23] 肯尼思等编著.分形几何——数学基础及其应用[J].沈阳:东北工学院出版社.1991.
[24] 汪小帆.Chen's 吸引子——一个新的混沌吸引子[J].控制理论与应用.16(5),1999.
[25] Chen G,Lai D.Feedback anticontrol of discrete-chaos[J].Int.J.of Bifur.Chaos. 8:1585-1590, 1998.
[26] 飞思科技产品研发中心编著.MATLAB 6.5 辅助优化计算与设计[M].北京:电子工业出版社.2003.
[27] Hopfield J J.Neural networks and physical systems with emergent collective computational abilities[J].In:Proc.Natl.Acad.Sci.79:2554-2558,1982.
[28] 吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10)
[29] 陈宝林编著.最优化理论和算法[M].北京:清华大学出版社.2000.
[30] 丁建立,陈增强,袁著祉.遗传算法与蚁群算法的融合.计算机研究与发展.2003,40(9)
[31] Wilson V, Pawlay G S.On the stability of the TSP problem algorithm of Hopfield and Tank[J].Biol.Cybern.58:63-70,1988.
[32] Foster I. Designing and Building Parallel Programs. Addison-Weslley,Reading, MA,1994
[33] Adachi M,Aihara K,Kotani M.An analysis of associative dynamics in a chaotic neural network with external stimulation[J].Proc.IJCNN-93 NAGOYA.1: 409-412, 1993.
[34] Dempster A.P. Laird N.M. and Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm.Journal of the Royal Statistical Society, 1997
[35] 吴斌,史忠植.一种基于蚁群算法的 TSP 问题分段求解算法[J].计算机学报,第 24 卷,第 12 期,2001.12
[36] 周登勇,戴汝为.一个基于改进蚁群算法的多点路由算法[J].系统工程与电子技术.2001,23(8).
[37] 丁亚平,吴庆生.一种新的化学计量学方法----蚁群算法[J].化学通报.2002,65(4).
[38] 李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社.2002.
[39] 段海滨.蚁群算法原理及其应用[M].科学出版社.2002.
[40] 楼顺天,陈生潭.Matlab 5.x 程序设计语言[M].西安电子科技大学出版社.2002
[41] 史忠植.智能主体及其应用[M].科学出版社.2000.
[42] 张纪会,高齐圣.自适应蚁群算法[J].控制理论与应用.2000,17(1)
[43] 覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制.2002,31(3).