基于光学原理的最优搜索方法研究
|
摘要
随着应用领域的拓展,最优化问题的时空复杂性使其求解非常困难,传统的优化算法已很难满足问题需要。智能优化算法的诞生给最优化技术提供了新的思路和手段,并在科学研究、经济及工程技术问题中得到广泛应用和发展。
光线寻优算法是2008年提出的一种通过对自然界光线折射现象的模拟而进行寻优的优化算法。本文详细地介绍了它的基本原理和算法流程。通过数值实验对固定网格的光线寻优算法进行了参数分析,并且做了相应的算法改进,提出变网格的光线寻优算法,改进原有算法的不足。本文主要研究内容可归纳为：
1.详细分析光线寻优算法中蕴含的最优化理论的数学思想以及光线寻优算法的基本原理、计算步骤。数值实验表明,光线寻优算法简单易行,并可在大范围内较快地搜索到极值点。阐明了算法中重要参数对算法性能的影响。
2.通过系列的数值实验,给出了光线寻优算法参数选择的合理建议。为研究本文算法性能,在4个具有代表性的基准测试函数上,进行了算法的数值实验。并且针对参数网格步长的大小提出变网格的光线寻优算法,通过系列数值实验表明,网格的等比递减和等差递减这两种改进算法能有效地提高算法局部搜索能力,从而很大程度地改善算法性能。
3.针对目标函数值域只能恒正的局限,提出了大M参数法,来解决这一问题,从而研究改进算法性能。在3个具有代表性的测试函数上,进行了算法的数值实验。实验结果显示,大M参数法使得光线寻优算法突破目标函数值域只能恒正的局限。
With the development of applied fields, optimization of the problem is very difficult to solve in temporal and spatial complexity, the traditional optimization algorithm has been difficult to meet the requirement. But Intelligent Optimization Algorithm is a new way, it provides new means to be used.Economic and technical aspects of the project is widely applied and developed.
Professor proposes a new optimization algorithm-Light Ray Optimization, which stimulates the natural phenomenon of light refraction.There are the basic theory and algorithm steps of the Light Ray Optimization in this paper. Parameters of LRO are analysed by numerical experiments on the fixed grid Light Ray Optimization,and the algorithm is improved. Variable grid light ray optimization is proposed, it is overcomed for disadvantage of the fixed grid Light Ray Optimization. The main works given in the dissertation are as follows.
1.The Light Ray Optimizion is detailedly analysed, and the mathematical idea in the algorithm is introduced. The basic principles of algorithm calculation steps are also introduced. The feasibility of algorithm is verified by numerical experiment. Numerical experiments show that Light Ray Optimization is simple, and in the large scope of the search quickly to the extreme points. We expound the influence of important parameters to the algorithm performance of algorithms presented in the dissertation.
2.We give reasonable suggestion to the choosing of the parameters in the algorithm by series of numerical experiments. In order to study the performance of the algorithms, we did series of numerical experiments on five representative benchmark functions. Grid size of Light Ray Optimization is variable, the variable grid Light Ray Optimization is proposed. The decending grid is classified into a linear trend of decending and non-linear of decending, the decending trends of the two math iterative formulas are given. Through comparing two methods in are given. Through comparing two methods in numerical experiments, algorithm of grid of geometric descending and arithmetic descending generate better numerical results. Algorithms can effectively enhance local search capability, thus improve algorithm performance greatly
3.The objective function value can only be a positive number. A large M parameter method is proposed to solve this problem. We did series of numerical experiments with the improved algorithm on three benchmark functions. The experimental results show that, the problem of constant for the positive is solved by this improved algorithm.
光线寻优算法是2008年提出的一种通过对自然界光线折射现象的模拟而进行寻优的优化算法。本文详细地介绍了它的基本原理和算法流程。通过数值实验对固定网格的光线寻优算法进行了参数分析,并且做了相应的算法改进,提出变网格的光线寻优算法,改进原有算法的不足。本文主要研究内容可归纳为：
1.详细分析光线寻优算法中蕴含的最优化理论的数学思想以及光线寻优算法的基本原理、计算步骤。数值实验表明,光线寻优算法简单易行,并可在大范围内较快地搜索到极值点。阐明了算法中重要参数对算法性能的影响。
2.通过系列的数值实验,给出了光线寻优算法参数选择的合理建议。为研究本文算法性能,在4个具有代表性的基准测试函数上,进行了算法的数值实验。并且针对参数网格步长的大小提出变网格的光线寻优算法,通过系列数值实验表明,网格的等比递减和等差递减这两种改进算法能有效地提高算法局部搜索能力,从而很大程度地改善算法性能。
3.针对目标函数值域只能恒正的局限,提出了大M参数法,来解决这一问题,从而研究改进算法性能。在3个具有代表性的测试函数上,进行了算法的数值实验。实验结果显示,大M参数法使得光线寻优算法突破目标函数值域只能恒正的局限。
With the development of applied fields, optimization of the problem is very difficult to solve in temporal and spatial complexity, the traditional optimization algorithm has been difficult to meet the requirement. But Intelligent Optimization Algorithm is a new way, it provides new means to be used.Economic and technical aspects of the project is widely applied and developed.
Professor proposes a new optimization algorithm-Light Ray Optimization, which stimulates the natural phenomenon of light refraction.There are the basic theory and algorithm steps of the Light Ray Optimization in this paper. Parameters of LRO are analysed by numerical experiments on the fixed grid Light Ray Optimization,and the algorithm is improved. Variable grid light ray optimization is proposed, it is overcomed for disadvantage of the fixed grid Light Ray Optimization. The main works given in the dissertation are as follows.
1.The Light Ray Optimizion is detailedly analysed, and the mathematical idea in the algorithm is introduced. The basic principles of algorithm calculation steps are also introduced. The feasibility of algorithm is verified by numerical experiment. Numerical experiments show that Light Ray Optimization is simple, and in the large scope of the search quickly to the extreme points. We expound the influence of important parameters to the algorithm performance of algorithms presented in the dissertation.
2.We give reasonable suggestion to the choosing of the parameters in the algorithm by series of numerical experiments. In order to study the performance of the algorithms, we did series of numerical experiments on five representative benchmark functions. Grid size of Light Ray Optimization is variable, the variable grid Light Ray Optimization is proposed. The decending grid is classified into a linear trend of decending and non-linear of decending, the decending trends of the two math iterative formulas are given. Through comparing two methods in are given. Through comparing two methods in numerical experiments, algorithm of grid of geometric descending and arithmetic descending generate better numerical results. Algorithms can effectively enhance local search capability, thus improve algorithm performance greatly
3.The objective function value can only be a positive number. A large M parameter method is proposed to solve this problem. We did series of numerical experiments with the improved algorithm on three benchmark functions. The experimental results show that, the problem of constant for the positive is solved by this improved algorithm.
引文
[1]沈继红.基于光学折射原理的最优化搜索方法.哈尔滨工程大学理学院学术交流年会.中国哈尔滨.2007：72-77页
[2]徐宗本.计算智能(第一册)——模拟进化计算.北京：高等教育出版社,2004,1：114-116页
[3]J.Kennedy, Eberhart R. C. Particle Swarm Optimization. In Proc. IEEE Int'1. Conf. on Neural Networks, IV. Piscataway, NJ:IEEE Service Center,1995:1942-1948P
[4]王凌.智能优化算法及其应用.北京：清华大学出版社,2001：1-12页
[5]王玫,朱云龙,何小贤.群体智能研究综述.计算机工程.2005,31(22)：194-196页
[6]张丽平.粒子群优化算法的理论及实践.浙江大学博士论文.2005：26-27页
[7]M. Dorigo, V. Maniezzo, A. Colorni Ant System:Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part,1996, B:29-41P
[8]Powell, M. J. D.. An efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Darivatives, The Computer Journal, Vol.7,1964:155-62P
[9]徐成贤,陈志平,李乃成.近代最优化方法.北京：科学出版社,2005：271-304页
[10]李博.粒子群优化算法及其在神经网络中的应用.大连理工大学硕士论文.2005：47页
[11]张卓奎,陈慧婵.随机过程.西安：西安电子科技大学出版社,2004：301-320页
[12]匡继昌.常用不等式(第三版).济南山东科学技术出版社,2004
[13]何坚勇.最优化方法.北京：清华大学出版社,2007：384-395页
[14]M. Dorigo, L. M. Gambardella Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation,1997:53-66P
[15]M. Clerc, J. Kennedy, The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Transactions on Evolutionary Computation,2002:58-73P
[16]V. Cerny A Thermodynamical Approach to the Travelling Salesman Problem:an Efficient Simulation Algorithm. Journal of Optimization Theory and Applications,1985,45:41-51P
[17]S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi Optimization by Simulated Annealing. Science,1983,220:671-680P
[18]Wolpert D. H., Macready W. G. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1997,1:67-82P
[19]Moody J., C. Darken Fast Learning in Networks of Locally-Tuned Processing Units. Neural Computation,1989,1:281-289P
[20]唐焕文,秦学志.实用最优化方法.大连：大连理工大学出版社,2004：94-149页
[21]高尚,杨静宇,吴小俊等.基于模拟退火算法思想的粒子群优化算法.计算机应用与软件.2005,22(1)：103-105页
[22]董长虹.神经网络与应用.北京：国防工业出版,2005：67-90页
[23]毕晓君,文頔俐.基于协同神经网络的经济比对问题研究.中国人工智能学会第十一届全国学术年会.中国人工智能进展,2005.北京：北京邮电大学出版社
[24]Winston P. H.. ArtificialIntelligence,3rd edition. Addison-Welley, Reading MA,1992
[25]Test problems for global optimization. Available: http://www2. imm. dtu. dk/-km/GlobOpt/testex/
[26]Hu XH, Eberhart RC. Adaptive particle swarm optimization: Detection and response to dynamic system. In:Proc. of the IEEE Int'1 Conf. on Evolutionary Computation. Honolulu:IEEE Inc., 2002:1666-1670P
[27]吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报.2004,32(3)：416-420页
[28]SdfKazemi BAL, Mohan CK. Multi-Phase generalization of the particle swarm optimization algorithm. In:Proc. of the IEEE Intl Conf. on Evolutionary Computation. Honolulu:IEEE Inc.2002: 489-494P
[29]曾建潮,介婧,崔志华.微粒群算法.北京：科学出版社,2004：10-11页,104-120页
[30]loan Cristian Trelea. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters,2003,85(6):317-325P
[31]杨维,李歧强.粒子群优化算法综述.中国工程科学.2004,5：87-94页
[32]马振华.现代应用数学手册-运筹学与最优化理论卷.北京：清华大学出版社,1998：103-148页
[33]Habib M K, Asama H. Efficient Method to Generate Collision Free Paths for Autonomous Mobile Robot Based on New Free Space Structuring Approach. in:IEEE/RSJ International Workshop on Intelligent Robots and Systems IROS'91. Osaka.1991. Japan:IEEE Cat,1991:563-567P
[34]Bonabeau E, Dorigo M, Theraulaz G. Swarm Intelligence:From Natural to Artificial Systems. Massachosetts:Oxford Press, 1999:65-68P
[35]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用.北京：科学出版社,2002
[36]Gang Feng. A Compensating Scheme for Robot Tracking Based on Neural Networks. Robotics and Autonomous Systems,1995:199-206P
[37]El Gallad A, El Hawary M, Sallam A, Kalas A, Enhancing the particle swarm optimizer bia proper parameters selection. IEEE CCECE02 Proceedings. Piscataway, NJ, Canadian:IEEE service center, 2002:792-797P
[2]徐宗本.计算智能(第一册)——模拟进化计算.北京：高等教育出版社,2004,1：114-116页
[3]J.Kennedy, Eberhart R. C. Particle Swarm Optimization. In Proc. IEEE Int'1. Conf. on Neural Networks, IV. Piscataway, NJ:IEEE Service Center,1995:1942-1948P
[4]王凌.智能优化算法及其应用.北京：清华大学出版社,2001：1-12页
[5]王玫,朱云龙,何小贤.群体智能研究综述.计算机工程.2005,31(22)：194-196页
[6]张丽平.粒子群优化算法的理论及实践.浙江大学博士论文.2005：26-27页
[7]M. Dorigo, V. Maniezzo, A. Colorni Ant System:Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part,1996, B:29-41P
[8]Powell, M. J. D.. An efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Darivatives, The Computer Journal, Vol.7,1964:155-62P
[9]徐成贤,陈志平,李乃成.近代最优化方法.北京：科学出版社,2005：271-304页
[10]李博.粒子群优化算法及其在神经网络中的应用.大连理工大学硕士论文.2005：47页
[11]张卓奎,陈慧婵.随机过程.西安：西安电子科技大学出版社,2004：301-320页
[12]匡继昌.常用不等式(第三版).济南山东科学技术出版社,2004
[13]何坚勇.最优化方法.北京：清华大学出版社,2007：384-395页
[14]M. Dorigo, L. M. Gambardella Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation,1997:53-66P
[15]M. Clerc, J. Kennedy, The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Transactions on Evolutionary Computation,2002:58-73P
[16]V. Cerny A Thermodynamical Approach to the Travelling Salesman Problem:an Efficient Simulation Algorithm. Journal of Optimization Theory and Applications,1985,45:41-51P
[17]S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi Optimization by Simulated Annealing. Science,1983,220:671-680P
[18]Wolpert D. H., Macready W. G. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1997,1:67-82P
[19]Moody J., C. Darken Fast Learning in Networks of Locally-Tuned Processing Units. Neural Computation,1989,1:281-289P
[20]唐焕文,秦学志.实用最优化方法.大连：大连理工大学出版社,2004：94-149页
[21]高尚,杨静宇,吴小俊等.基于模拟退火算法思想的粒子群优化算法.计算机应用与软件.2005,22(1)：103-105页
[22]董长虹.神经网络与应用.北京：国防工业出版,2005：67-90页
[23]毕晓君,文頔俐.基于协同神经网络的经济比对问题研究.中国人工智能学会第十一届全国学术年会.中国人工智能进展,2005.北京：北京邮电大学出版社
[24]Winston P. H.. ArtificialIntelligence,3rd edition. Addison-Welley, Reading MA,1992
[25]Test problems for global optimization. Available: http://www2. imm. dtu. dk/-km/GlobOpt/testex/
[26]Hu XH, Eberhart RC. Adaptive particle swarm optimization: Detection and response to dynamic system. In:Proc. of the IEEE Int'1 Conf. on Evolutionary Computation. Honolulu:IEEE Inc., 2002:1666-1670P
[27]吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报.2004,32(3)：416-420页
[28]SdfKazemi BAL, Mohan CK. Multi-Phase generalization of the particle swarm optimization algorithm. In:Proc. of the IEEE Intl Conf. on Evolutionary Computation. Honolulu:IEEE Inc.2002: 489-494P
[29]曾建潮,介婧,崔志华.微粒群算法.北京：科学出版社,2004：10-11页,104-120页
[30]loan Cristian Trelea. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters,2003,85(6):317-325P
[31]杨维,李歧强.粒子群优化算法综述.中国工程科学.2004,5：87-94页
[32]马振华.现代应用数学手册-运筹学与最优化理论卷.北京：清华大学出版社,1998：103-148页
[33]Habib M K, Asama H. Efficient Method to Generate Collision Free Paths for Autonomous Mobile Robot Based on New Free Space Structuring Approach. in:IEEE/RSJ International Workshop on Intelligent Robots and Systems IROS'91. Osaka.1991. Japan:IEEE Cat,1991:563-567P
[34]Bonabeau E, Dorigo M, Theraulaz G. Swarm Intelligence:From Natural to Artificial Systems. Massachosetts:Oxford Press, 1999:65-68P
[35]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用.北京：科学出版社,2002
[36]Gang Feng. A Compensating Scheme for Robot Tracking Based on Neural Networks. Robotics and Autonomous Systems,1995:199-206P
[37]El Gallad A, El Hawary M, Sallam A, Kalas A, Enhancing the particle swarm optimizer bia proper parameters selection. IEEE CCECE02 Proceedings. Piscataway, NJ, Canadian:IEEE service center, 2002:792-797P