粒子群算法的一些相关资源

 EAs
 

【转载前辈的好博文】粒子群算法资源合辑[zz]

发信人: logpie (Yuxuan), 信区: Circuit
标 题: 粒子群算法资源合辑
发信站: 紫金飞鸿 (Mon Oct 16 00:22:10 2006)

忙了大半年的big paper昨天终于投掉了。写下这个合集，一方面是对这一年零星资料的总结，另一方面是为方便有兴趣的Echoer们尽早入门，少走弯路，以加快我们合作的速度。下面列出的大部分是领域经典paper以及重要资源汇总。如有遗漏，我会不断增加的。

希望这个collecion能对大家有帮助，更渴望Echoer之间能尽早合作，望各位笑纳。
Any question, plz mailto:logpie@gmail.com.

Books and dissertations:

  • Kennedy, J., Eberhart, R. C., and Shi, Y., Swarm intelligence San Francisco: Morgan Kaufmann Publishers, 2001. (PSO的founders所著)
  • van den Bergh, Frans, “An analysis of particle swarm optimizers.” PhD’s Dissertation Department of Computer Science, University of Pretoria, South Africa, 2002. (Dr.Bergh的博士论文,详尽的给出了他对PSO的分析和改进,建议通读)

Papers

原始论文:

  • Kennedy J,Eberhart R C. Particle Swarm Optimization [C]. Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, 1995.1942-1948.

  • R. C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,”
    in Proc. 6th Int. Symp. Micromachine Human Sci., Nagoya,Japan, 1995

理论基础:

  • Clerc, M. and Kennedy, J., “The particle swarm-explosion, stability, and convergence in a multidimensional complex space,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 58-73, 2002. (较完整的给出了PSO的收敛性,并发现使用压缩因子可以保证收敛,04年IEEE Trans. EVC Best paper award,必读)

  • Ozcan, E. and Mohan, C. K. Particle swarm optimization: surfing the waves. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), Washington, DC, USA. 1999

  • relea, I. C., “The particle swarm optimization algorithm: convergence analysis and parameter selection,” Information Processing Letters, vol. 85, no. 6, pp. 317-325, Mar.2003. (另一个较小的收敛分析)

参数设置:

  • Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization. Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, New York. pp. 591-600, 1998

  • Shi, Y. and Eberhart, R. C. Empirical study of particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ. pp. 1945-1950, 1999 (主要是对惯性权重的试验)

  • Carlisle, A. and Dozier, G. An off-the-shelf PSO. Proceedings of the Workshop on Particle Swarm Optimization 2001, Indianapolis, IN. 2001 (各个参数设置的比较,必读)

综述:

  • Eberhart, R. C. and Shi, Y. Comparison between genetic algorithms and particle swarm optimization. Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, San Diego, CA. 1998 (GA与PSO比较)

  • Eberhart, R. C. and Shi, Y. Particle swarm optimization: developments, applications and resources. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2001), Seoul, Korea. 2001

  • Parsopoulos, K. E. and Vrahatis, M. N., “Recent approaches to global optimization problems through particle swarm optimization,” Natural Computing, vol. 1, no. 2-3, pp. 235-306, 2002. (很长的综述,但是比较偏重作者自己提出的几个改进,呵呵)

应用:

  • Ismail, A. and Engelbrecht, A. P. Training Product Units in Feedforward Neural Networks using Particle Swarm Optimization. Proceedings of the International Conference on Artificial Intelligence, Durban, South Africa. pp. 36-40, 1999

  • van den Bergh, F. and Engelbrecht, A. P., “Cooperative learning in neural networks using particle swarm optimizers,” South African Computer Journal, vol. 26 pp. 84-90, 2000.

  • L. Messerschmidt and A. P. Engelbrecht, “Learning to play games using a PSO-based competitive learning approach,” IEEE Trans. Evol.Comput., vol. 8, pp. 280–288, Jun. 2004.

  • Settles, M. and Rylander, B. Neural network learning using particle swarm optimizers. Advances in Information Science and Soft Computing, pp. 224-226, 2002

  • Tillett, J. C., Rao, R., Sahin, F., and Rao, T. M. Cluster-head identification in ad hoc sensor networks using particle swarm optimization. Proceedings of 2002 IEEE International Conference on Personal Wireless Communications, pp. 201-205, 2002

  • Coello Coello, C. A., Luna, E. H. n., and Aguirre, A. H. n. Use of particle swarm optimization to design combinational logic circuits. Lecture Notes in Computer Science(LNCS) No. 2606, pp. 398-409, 2003

  • Tillett, J. C., Rao, R. M., Sahin, F., and Rao, T. M. Particle swarm optimization for the clustering of wireless sensors. Procedings of SPIE Vol. 5100: Digital Wireless Communications V, pp. 73-83, 2003

改进与分析_离散域拓展及组合优化:

  • Kennedy, J. and Eberhart, R. C. A discrete binary version of the particle swarm algorithm. Proceedings of the World Multiconference on Systemics,Cybernetics and Informatics 1997, Piscataway, NJ. pp. 4104-4109, 1997 (最早的离散PSO,非常聪明的改进,值得一看)

  • Mohan, C. K. and Al-kazemi, B. Discrete particle swarm optimization. Proceedings of the Workshop on Particle Swarm Optimization 2001, Indianapolis, IN. 2001

  • Laskari, E. C., Parsopoulos, K. E., and Vrahatis, M. N. Particle swarm optimization for integer programming. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002 (PSO for 整数规划)

  • Schoofs, L. and Naudts, B. Swarm intelligence on the binary constraint satisfaction problem. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002

  • Wang, K.-P., Huang, L., Zhou, C.-G., and Pang, W. Particle swarm optimization for traveling salesman problem. Proceedings of International Conference on Machine Learning and Cybernetics 2003, pp. 1583-1585, 2003 (引入几个新算子,解决TSP问题)

  • Clerc, M., “Discrete Particle Swarm Optimization,” New Optimization Techniques in Engineering Springer-Verlag, 2004. (Clerc大拿的DPSO,同样引入了新算子)

改进与分析_参数:

  • Shi, Y. and Eberhart, R. C. A modified particle swarm optimizer. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1998), Piscataway, NJ. pp. 69-73, 1998 (惯性权重在此文中提出)

  • Clerc, M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), pp. 1951-1957, 1999 (提出了queen的思想,里面还有个重力场,比较有意思)

  • Eberhart, R. C. and Shi, Y. Comparing inertia weigthts and constriction factors in particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2000), San Diego, CA. pp. 84-88, 2000 (惯性权重与压缩因子)

  • Shi, Y. and Eberhart, R. C. Particle swarm optimization with fuzzy adaptive inerita weight. Proceedings of the Workshop on Particle Swarm Optimization 2001, Indianapolis, IN. 2001 (为适应动态环境,提出模糊惯性权重)

  • A. Ratnaweera, S. Halgamuge, and H. Watson, “Self-organizing hierarchical particle swarm optimizer with time varying accelerating coefficients,”IEEE Trans. Evol. Comput., vol. 8, pp. 240–255, Jun. 2004. (对几个参数做了拓展以及非常详尽的分析)

改进与分析_粒子拓扑方向:

  • Kennedy, J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance. Proceedings of IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ. pp. 1931-1938, 1999 (小世界拓扑对结果的影响)

  • Suganthan, P. N. Particle swarm optimiser with neighbourhood operator. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1999), Piscataway, NJ. pp. 1958-1962, 1999 (引入领域算子)

  • Kennedy, J. Stereotyping: improving particle swarm performance with cluster analysis. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2000), San Diego, CA. pp. 1507-1512, 2000

  • Kennedy, J. and Mendes, R. Population structure and particle swarm performance. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002

  • Krink, T., Vesterstroem, J. S., and Riget, J. Particle swarm optimisation with spatial particle extension. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002

  • Janson, S. and Middendorf, M. A hierarchical particle swarm optimizer. Proceedings of IEEE Congress on Evolutionary Computation 2003 (CEC 2003), Canbella, Australia. pp. 770-776, 2003 (使粒子动态的按照树型排列)

  • Kennedy, J. and Mendes, R. Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms. Proceedings of the 2003 IEEE International Workshop on Soft Computing in Industrial Applications 2003 (SMCia/03), pp. 45-50, 2003

  • R. Mendes, J. Kennedy, and J. Neves, “The fully informed particle swarm: Simpler, maybe better,” IEEE Trans. Evol. Comput., vol. 8, pp. 204–210, Jun. 2004. (重要的FIPs模型,所有粒子的信息用来更新一个粒子的信息)

改进与分析_多样性提升方向:

  • Blackwell, T. M. and Bentley, P. J. Don’t push me! collision-avoiding swarms.Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002

  • Riget, J. and Vesterstroem, J. S. A diversity-guided particle swarm optimizer- the ARPSO. Technical Report No. 2002-02. 2002. Dept. of Computer Science, University of Aarhus, EVALife.

  • Peram, T., Veeramachaneni, K., and Mohan, C. K. Fitness-distance-ratio based particle swarm optimization. Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, Indiana, USA. pp. 174-181, 2003

comments:很多其他类里的paper都可以归类到这儿来。

改进与分析_结合其他算法思想方向:

  • Angeline, P. J. Using selection to improve particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 1998), Anchorage, Alaska, USA. 1998 (借鉴GA里的选择优秀染色体思想)

  • Lvbjerg, M., Rasmussen, T. K., and Krink, T. Hybrid particle swarm optimiser with breeding and subpopulations. Proceedings of the Genetic and Evolutionary Computation Conference 2001 (GECCO 2001), 2001

  • Higashi, N. and Iba, H. Particle swarm optimization with gaussian mutation. Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, Indiana, USA. pp. 72-79, 2003 (同样也是GA里的思想)

  • Y.X.Wang, Z.D.Zhao, R.Ren. Hybrid Particle swarm optimizer with tabu strategy. In submission. (禁忌搜索的思想)

  • Juang, C.-F., “A hybrid of genetic algorithm and particle swarm optimization for recurrent network design,” IEEE Transactions on Systems, Man, and Cubernetics - Part B: Cybernetics, vol. accepted 2003.

  • SHi, X., Lu, Y., Zhou, C., Lee, H., Lin, W., and Liang, Y. Hybrid evolutionary algorithms based on PSO and GA. Proceedings of IEEE Congress on Evolutionary Computation 2003 (CEC 2003), Canbella, Australia. pp. 2393-2399, 2003

  • Stacey, A., Jancic, M., and Grundy, I. Particle swarm optimization with mutation. Proceedings of IEEE Congress on Evolutionary Computation 2003 (CEC 2003), Canbella, Australia. pp. 1425-1430, 2003 (GA also)

改进与分析_其他

  • K. E. Parsopoulos, V. P. Plagianakos, G. D. Magoulas, and M. N. Vrahatis, “Stretching technique for obtaining global minimizers through particle swarm optimization,” in Proc. Particle Swarm Optimization Workshop, Indianapolis, IN, 2001, pp. 22–29.(对目标函数的变换)

  • K.E. Parsopoulos, M.N. Vrahatis, On the computation of all global minimizers through particle swarm optimization. IEEE Trans. on Evolutionary Computation, 2004,8(3):211-224. (上文的拓展,可以检测多全局最优,如Nash均衡点)

  • “UPSO—A unified particle swarm optimization scheme,” in Lecture Serieson Computational Sciences, 2004, pp. 868–873. (将全局拓扑和局部拓扑结合)

  • Al-kazemi, B. and Mohan, C. K. Multi-phase generalization of the particle swarm optimization algorithm. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002 (搜索方向改进)

  • Xie, X., Zhang, W., and Yang, Z. A dissipative particle swarm optimization. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA. 2002 (类比为耗散系统,加入负熵使系统脱离平衡态)

  • Van den Bergh F, Engelbrecht A P. A Cooperative Approach to Particle Swarm Optimization [J]. IEEE Transaction on Evolutionary Computation,2004, 8(3):225-239. (多粒子群协同优化)

  • J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar, “Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions”, IEEE Trans. on Evolutionary Computation, Vol. 10, No. 3, pp. 281-295, June 2006. (新的粒子搜索及合作策略)

comments:PSO的应用以及改进方向并不止我列出的这些,比如多目标优化这里就没有给出。但这些paper已经足够入门了,各位如有兴趣可以自己搜索.04年之前一个比较全的bibliography在 http://www.swarmintelligence.org/bibliography.php 可以找到,大约300多篇。

Websites:

comments:这三个网站关于PSO的资源非常丰富.第3个是clerc大拿的,里面更偏重对算法数学上的分析。

Leading Journals and Confs:

  • Evolutionary Computation (MIT press)
  • IEEE Transactions on Evolutionary Computation
  • IEEE Transactions on Neural Network
  • IEEE Transactions on Systems, Man, and Cubernetics Part:A,B
  • Genetic and Evolutionary Computation Conference (GECCO, ACM SIGEVO)
  • IEEE Congress on Evolutionary Computation(CEC)
  • Parallel Problem Solving from Nature (PPSN)

Homepages

comments:上面是我常去的一些page,主要的PSO学者在 http://www.particleswarm.info/people.html 上可以找到

Benchmarks

Comments:改进或提出一个优化算法需要对其作出性能评测,这里提供一些标准的测试集,包括DeJong系列函数,Rastrigin系列函数等,以及其他有约束,离散,组合优化标准测试问题.

最近Prof.Suganthan等提出了一套Composition functions,具体参见他的homepage,同样CEC05上也提出了大约30个测试函数.对这些函数进行rotate,shift,distortion等操作可以变换为更复杂的函数,具体请参加相关paper。

code、software、projects、implementations

comments:各位如果需要几个重要PSO改进的matlab实现,请联系prof.suganthan或直接发邮件给我.

Future work

2004 年IEEE Transactions on Evolutionary Computation出版了Special issue on PSO,卷首语中指出了当前研究的几个主要方向及热点:

  • 算法分析. PSO在实际应用中被证明是有效的, 但目前还没有给出完整收敛性、收敛速度估计等方面的数学证明,已有的工作还远远不够。
  • 粒子群拓扑结构.不同的粒子群邻居拓扑结构是对不同类型社会的模拟,研究不同拓扑结构的适用范围,对PSO算法推广和使用有重要意义。
  • 参数选择与优化.参数w、φ1、φ2的选择分别关系粒子速度的3个部分:惯性部分、社会部分和感知部分在搜索中的作用.如何选择、优化和调整参数,使得算法既能避免早熟又能比较快速地收敛,对工程实践有着重要意义。
  • 与其他演化计算的融合.如何将其它演化的优点和PSO的优点相结合,构造出新的混合算法是当前算法改进的一个重要方向。
  • 算法应用.算法的有效性必须在应用中才能体现,广泛地开拓PSO的应用领域,也对深化研究PSO算法非常有意义。

我在以前的帖子里曾经提到过,PSO是很适合演化计算方向入门的.特别是其算法实现非常简单,因此建议大家能够先实现基础算法.如果想进一步了解乃至研究,上面列出的除了应用的几十篇paper基本都是需要看的.PSO从提出到现在已经11年了,大小坑挖的也不少了,各位如果想在这个领域出新,出好结果,还是需要有一定功力的.对于我们目前的情况,我认为大家可以主要将精力集中在第(5)点。http://www.particleswarm.info/Problems.html 也列出了一些有意思的open problems。当然,都是有一定难度的 :-)

对于PSO的改进与分析,如何有能力的话,我仍然坚持认为一个突破口是学科交叉,比如粒子搜索的混沌行为,粒子进化以及合作策略中的博弈,统计物理学在群智能中的应用等等.这也是我接下来的研究内容.另外Clerc大拿网站上也有一篇经常更新的paper,”Some ideas about Particle Swarm Optimisation”,里面记录了很多他对PSO的理解,同样非常值得一看。

–
logpie=0.497

※ 来源:·紫金飞鸿 bbs.njupt.edu.cn·

 Previous

Water