摘要
最优化是一个重要的数学分支,也是一门应用相当广泛的年轻学科,最优化的目的是对于给出的一个实际问题,从众多备选方案中选择出最优方案。最优化问题是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问题,其目的是找到使目标函数达到最小或最大的条件。例如,工程设计中怎样选择设计参数,使得设计方案既满足设计要求又能降低成本;资源分配中,怎样有效分配有限的资源,使得分配方案既能满足各方面的基本要求,又能获得好的经济效益。在人类活动的各个领域中都有最优化问题的身影。
优化方法涉及的应用领域很广,问题种类与性质繁多,根据不同的原则可以给出不同的分类。根据决策变量的取值类型,可分为函数优化问题与组合优化问题(又称离散优化问题)。离散优化问题是一类重要的优化问题,随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。很长时间以来,人们试图寻找解决各种组合问题的有效算法。长期的努力在此问题上取得了一定的成效,但NP问题仍然是21世纪一个最具挑战性的科学难题,是在理论信息学中计算复杂度理论领域里至今没有解决的问题。
现代优化方法如人工神经网络、禁忌搜索、模拟退火、遗传算法和蚁群算法等在解决问题时展现出强大潜能,它们可在合理的时间内逼近复杂对象问题的最优解。这些算法涉及神经科学、人工智能、统计力学、生物进化等概念,很多都是以一定的自然、社会现象作为基础构造的算法,其中遗传算法和蚁群算法等称为智能优化算法。
近年来,另外一种新的优化算法-粒子群优化算法(PSO)逐渐成为学者关注的研究方向之一。粒子群优化算法由Dr.Eberhart和Dr.Kenney于1995年提出,它是受到鸟群的社会行为的启发而形成的一种基于种群的随机优化技术。粒子群优化算法属于进化算法,具有进化计算的基本特征。它的主要特点是简单、收敛速度较快,且所需领域知识少。尽管粒子群优化算法发展近十年,但无论是理论还是实践都尚未成熟。
本文在综述了PSO算法及其发展过程的基础上,通过对现有文献的研究和分析提出了粒子间信息交流的策略和具有动态分工策略的改进粒子群算法。
粒子间信息交流的策略通过粒子之间直接的信息共享,能够提高粒子本身的搜索能力,使粒子能够发现一定范围的最优解,从而尽快找到最优解。
在进化算法的研究当中,算法的探测和开发能力单靠一种算法往往无法得到有效利用与平衡,从而影响了算法的求解精度和效率。因此,在PSO算法搜索过程中融合其他优化
Optimization is an important branch of mathematics and a young subject which is extensively used, and it aims at choosing the optimum one from many candidate schemes to solve a practical problem. Many scientific, engineering and economic problems need the optimization of a set of parameters with the aim of minimizing or maximizing the objective function. For example, how to choose the parameter in the engineering design can make the design scheme satisfy the need and decrease the cost, and how to allocate the limit resource can make the design scheme satisfy the need and get better economic benefit. Optimization exits in all kinds of fields of human activities.
The application of optimization methods is very extensive, and it involves a lot of problems and these problems have different characteristics. According to different principles, they can be divided into different classes. For example, according to the value type of the decision-making variable, they can be divided into two classes, function optimization problem and combination optimization problem (namely, discrete optimization problem). The discrete optimization problem is an important optimization problem, and with the development of computer science, the science of the management and the technology of the modernized produce, it is getting more and more attention by the subjects of operational research, applications mathematics, computer science and management science. Since many years, people are trying to look for efficient algorithms to solve the combination problem, and many efficient algorithms have been proposed, but NP problem is still a science difficulty problem in the 21century, and it is not solved in the complexity field of the theory informatics yet.
Modern optimization methods such as artificial neural network, tabu search, genetic algorithm and ant colony algorithm etc., have shown capabilities of finding optimal solutions to many real-word complex problems within a reasonable amount of time. These methods have forged close ties with neural science, artificial intelligence, statistical mechanics, and biology evolution etc., some of them are called intelligent optimization algorithms, such as genetic algorithm and ant colony algorithm.
Recently, particle swarm optimization (PSO) algorithm has been gradually attracted more attention over another intelligent algorithm .PSO was brought forward by Dr. Eberhart and Dr. Kenney in 1995. It was a population based stochastic method motivated by the social behavior of bird flock. PSO shares many similarities with EA&GA. PSO is simple in concept, few in parameters, and easy in implementation.
引文
[1]袁亚湘, 孙文瑜. 最优化理论与方法[M], 北京, 科学技术出版社, 2001
[2]陈宝林, 最优化理论与算法[M], 北京,清华大学出版社, 1989.
[3]Schwefe . H P Numerical Optimization for Computer Model, John Wiley, Chichester,UK, 1981.
[4]Bremermann H J. Optimization through evolution and recombination, Yovits M C, ed. Self-Organizing Systems. Washington , D C, Spartan, 1962.
[5]Friedberg R M. A learning machine: Part 1[J], IBM Journal, 1958,2(1): 2~13.
[6]Friedberg R M, Dunham B, North J H. A learning machine: Part 2[J], IBM Journal, 1958,3(7): 282~287.
[7]Box J E P. Evolutionary operation: a method for increasing industrial productivity[J], Appl Statistics, 1957, 6(2): 81~101.
[8]Holland J H. Outline for a logical theory of adaptive systems[J], J Assoc Compute Mach, 1962(3): 297~314.
[9]Rechenberg I. Cybernetic Solution Path of an Experimental Problem[J], UK: Farnborough, 1965.
[10]Schwefel H.P. Pojekt MHD-Staustrahlrohr: Experimentelle Optimierung einer Zweiphasenduse, TeilI. Berlin, Germany: AEG Forschungsistitut, 1968.
[11]Fogel L J. Autonomous automata. Ind Res,1962 (4): 14~19.
[12]康立山. “演化计算”. 数值计算与计算机应用[M], 1995, 3: 173~179.
[13]Colorni A, Dorigo M and Maniezo V. Distributed optimization by ant colonies[J],Proc. Of 1st European Conf. Artificial Life. Pans, France: Elsevier, 1991, 134-142.
[14]R.C Eberhart, J. Kennedy .A new optimizer using particle swarm theory[J]. Proceedings of the sixth International Symposium on Micro Machine and Human Science . Nagoya Japan, 1995, 39-43.
[15]J.Kennedy, R.C Eberhart. Particle Swarm Optimization[A].In: Proc IEEE International Conference on Neural Networks [C]. IEEE Service Center, Piscataway, NJ, IV: 1995,1942-1948.
[16]姚恩瑜,何勇. 数学规化与组合优化[M].浙江,浙江大学出版社,2002
[17]Hirotaka, Yoshida, Kenichi. A particle Swarm Optimization for Reactive Power and Voltage Control Considering Voltage Stability[A].In: IEEE International Conference on Intelligent System Applications to Power Systems[C], Rio de Janeiro, 1999
[18] M.S Voss, Xin Feng. Arma Model Selection Using Particle Swarm Optimization and Aic Criteria, 15th Triennial World Congress, Barcelona Spain, 2002
[19]K.E Parsopoulos, M N Vrahatis. Particle Swarm Optimization Method in Multi objective Problems[A]. In: Proceedings of the 2002 ACM Symposium on Applied Computing[C] , 2002. 603-607
[20]Van den Bergh, F Engelbrecht A P. Cooperative Learning in Neural Networks using Particle Swarm Optimizers[J], South African Computer Journal, 2000, 26, 84-90.
[21]曹建潮,介靖,崔志华. 微粒群算法[M]. 北京, 科学出版社.
[22]Shi, Y. and Eberhart, R.C. A modified particle swarm optimizer[A]. In: Proceedings of IEEE International Conference on Evolutionary Computation (CEC 1998) [C], Piscataway, NJ, 1998, 69-73.
[23]Shi, Y and Eberhart, R.C. Empirical study of particle swarm optimization[A].In: Proceedings of the World Multi conference on Systemics[C], Cybernetics and Informatics, Orlando, FL, 1999, 1945-1950
[24]Shi Y , Eberhart R C.A Modified Particle Swarm Optimizer[A]. In: Proceeding of the IEEE International Conference on Evolutionary Computation[C]. IEEE Press, Piscataway, NJ, 1998,69-73
[25]Clerc M. The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization. In: Proc [M]. CEC 1999.1999,1951-1957
[26]Corne D, Dorigo M, Glover F. New Ideas in Optimization[J] . McGraw Hill, 1999,379-387
[27]Angeline P j. Using Selection to Improve Particle Swarm Optimization[A]. In: IEEE InternationalConference on Evolutionary Computation[C] , Anchorage, Alaska, USA. 1998, 84-89.
[28]Angeline P j. Evolutionary Optimization Versus Particle Swarm Optimization: Philosophy and Performance[J]. The Seventh Annual Conf. on Evolutionary programming. 1998
[29]Lovbjerg M, Rasmussen T K, Krink T. Hybrid Particle Swarm Optimiser with Breeding and Subpopulations[A]. In: Proceedings of the third Genetic and Evolutionary Computation Conference (GECCO-2001)[C]. 2001.
[30]Suganthan P N. Particle Swarm Optimiser with Neighbourhood Operator[A]. In: Proceedings of the 1999 Congress on Evolutionary Computation[C]. Piscataway, NJ, 1999,1958-1962
[31] Kennedy J, R.C Eberhart, Discrete binary version of the particle swarm algorithm[A].In:Proceedings of the IEEE International Conference on Systems[C], 1997. 4104-4108
[32] Kennedy J, Spears W M. Matching Algorithms to Problems: an Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimode problem Generator.IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA, 1998
[33] Wang Kang-ping, Huang Lan, Zhou Chun-guang et al. Particle Swarm optimization for traveling salesman problem[A].IEEE Service Center, Proceedings of the Second International Conference on Machine Learning and Cybernetics[C], Xi’an: IEEE Press, November 2003,5:1583-1585.
[34] 葛宏伟,梁艳春,周春新.一种新的基于改进粒子群算法的 Job-Shop 调度方法, 2004 年全国博士生学术论坛论文集,2004,9,1-7
[35]Shi XH,Xing XL,Wang QX,Zhang LH,Yang XW,Zhou CG, Liang YC,A discrete PSO method for generalized TSP problem, Proceedings of the Third International Conference on Machine Learning and Cybernetics, Shanghai, 26-29 August 2004,2378-2383
[36]Johnson DS,Mc Geoch L A. The traveling salesman problem: a case study in local optimization [J]. Aarts E H L, Lenstra J K. Local search in combinatorial optimization [C].John Wiley&Sons, 1997:215~310.
[37]D.Applegate, R.Bixby, V Chv 6 tal, and W Cook.On the solution of traveling salesman problems. in Documenta Mathematica: Proc. Int. Cogr. Mathematicians. 1998, vol.3. pp.645-656.
[38]Held, M. and R.M.Karp. A dynamic programming approach to sequencing problems. J.Siam, 1962, 10.1.pp.196-210.
[39]C.N.Fiechter.A parallel tabu search algorithm for large traveling salesman problem Discrete Appl. Math. Combin. Oper. Res. Comput. Sci. 1994, vol. 51.pp.243-f67.
[40] S. Kirkpatrick, C.D.Gelatt Jr., and M.P Vecchi. Optimization by simulated annealing[J]. Science. 1983, vol. 220. no. 4598. pp.671-680.
[41] P van Laarhoven and E.H.L.Aarts. Simulated annealing: theory and applications[J]. Kluwer Academic Publishers, 1987。
[42] J.YPotvin. The traveling salesman problem: a neural network perspective: ORSA J. Comput. 1993, vol. 5. pp.328-348.
[43] E.H.L.Aarts and H.P.Stehouwer .Neural networks and the traveling salesman problem. in Proc. Int. Conf. on Artificial Neural Networks. Springer-Verlag, 1993, 950-955.
[44] L.M.Gambardella and M.Dorigo. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proc. 12th Int. Conf. on Machine Learning. Morgan Kaufmann, 1995, 252-260.
[45] B. Freisleben and P. Merz. New genetic local search operators for the traveling salesman problem[J]. Proc. 4th Conf. Parallel Problem Solving from Nature. 1996,616-621.
[46]Clerc M.Discrete Particle Swarm Optimization,Illustrated by Traveling Salesman Problem[J] [A].Onwubolu G C,Babu B V.New Optimization Techniques in Engineering [M]. Berlin: Springer -Verlag ,2004.
[47]高尚,韩斌,吴小俊等.求解旅行商问题的混合粒子群优化算法[J].控制与决策,2004,19 (11)1286-1289.
[48]庞巍,王康平,周春光等, 模糊离散粒子群优化算法求解旅行商问题[J],小型微型计算机系统,2005.8,pp 1331-1334
[49] 谭 皓,王金岩等 ,一种基于子群杂交机制的粒子群算法求解旅行商问题[J],系 统 工 程,2005.4,83-87
[50] Dorigo M et al. Ant colony system: a cooperative learning approach to the traveling salesman problem[A].IEEE Service Center, IEEE Transactions on Evolutionary Computation [C], Piscataway, NJ: IEEE Press,1997,1(1) 53-66.
[51]Okada M,Taji Kand Fu kushima M. Probabilistic analysis of 2-op for traveling salesman problems [J].Int. J. Systems Science 1998,29(3):297-310
[52]王凌,郑大钟等,一种 GASA 混合优化策略[J],控制理论与应用,2001.8,552-554
[53] Paechter ,B.,et.al.,Two Solutions to the General Timetable Problem Using Evolutionary Methods ,in[95],1994
[54]D Johnson,A Database approach to course timetabling[J].Journal of the Operational Research society,1993.Vo1.44,No.5,425-433,
[55] Burke E.K.,Elliman D.G , Weare R.F.A University timetabling system based on graph colouring and constraint manipulation.[J]The Journal of Research on Computing in F.ducation,Vo1.26,issue 4,1993
[56]王枯民,赵致格.排课表问题中的分组优化决策算法[J].控制与决策,1999,14(2):109-114.
[57]张春梅,行飞.用自适应的遗传算法求解大学课表安排问题[J].内蒙古大学学报(自然科学版),2002,33(4):459-464.
[58] 黄 干 平 , 姚 自 珍 , 张 静 . 使 用 模 拟 退 火 算 法 解 课 表 问 题 [J]. 武 汉 大 学 学 报 ( 自 然 科 学版),2000,46(5):559-563.
[69]胡顺仁,邓毅,王铮.基于高校排课系统中的图论问题研究[J].计算机工程与应用,2002,4:221-222.
[60]吴金荣.求解课程表问题的分支定界算法[J].运筹与管理,2002,11(1):17-22.
[61]熊焱,李大卫等,基于遗传算法的大学课程表问题研究[J],数学的实践与认识[J],2004.6,34(6),82-86