粒子群优化算法

1.4.1　粒子群优化算法

近年来，粒子群优化算法^[2]，又称微粒群优化算法(Particle Swarm Optimization，简称PSO)，已经成为群智能优化算法研究中的一个重要分支，得到了越来越多研究者的重视。特别强调的是，一些机构和组织也开始重视PSO算法，如早在1998年演化计算大会(CEC)第一次将PSO算法列入了专题，2001年在美国专门举办了关于PSO算法的研讨会，遗传与演化计算会议(GECCO)很多专题也涉及了粒子群优化算法，关于群智能专题的国际会议群智能研讨会(SIS)一直将PSO算法列为会议主题之一。此外，还有很多国内外期刊，如在《计算机学报》 、《软件学报》 、《电子学报》 、《计算机研究与发展》等国内权威期刊刊登了大量有关粒子群优化算法方面的研究成果;另外，在IEEE Transactions on Evolutionary Computation;Swarm Intelligence;International Journal of Modelling，Identification and Control等国外权威期刊也出版了关于PSO算法的专刊，关于PSO算法的工具箱以及算法平台也不断被推出。

为了进一步证实粒子群优化算法的流行性和被重视程度，我们搜索了一些常用的英文数据库包括ScienceDirect，IEEE Xplore，ACM Digital Library，SpringerLink以及ProQuest博士论文全文数据库，使用了关键字“particle swarm optimization”，并且以五年左右为一个时间段进行检索，其中2010年的查询记录截止到3月30日，统计结果见表1.1，如果仅按标题是否包含以上关键字进行检索，相关文章的数目可能要比表中列出的数目多。

表1.1　查询结果

1．混合粒子群优化算法

鉴于以上认识，PSO算法已经迅速成为计算智能中非常有潜力、快速发展的研究领域。然而PSO算法发展历史尚短，在研究过程中遇到了和其他计算智能算法类似的难题，针对PSO算法发展过程中存在的问题，Eberhart等人在2004年指出了PSO算法未来研究工作的五个方向和热点，其中之一就是通过与其他演化计算等思想混合来提升和改进标准PSO算法的性能。计算智能领域的期刊在出版PSO算法等SI算法的专辑时，一直将其与其他智能优化算法的融合列为征稿的专题之一。可见，混合粒子群优化算法是当前PSO算法研究当中的一个重要方向。一方面，提出基于独立思想体系的新算法并非易事;另一方面，混合算法在实践中取得了非常大的成功，成为提高算法优化性能的一个重要而有效的途径，并且已经逐渐成为智能优化算法中相对独立的研究领域。如何结合其他技术来克服粒子群优化算法本身存在的不足值得深入探讨，目前这方面的工作主要集中在以下几个方面。

(1)与传统优化算法相结合。单纯形法、共轭梯度法、二次插值法、贪心策略、最速下降法、Levenberg-Marquardt算法等^［23-28］是具有很强局部搜索能力的传统最优化算法，这些方法往往具有较高的计算效率和相对成熟等优点，将粒子群优化算法的全局搜索特性与传统最优化方法的快速收敛和局部搜索能力有机地结合起来，提出了一类改进PSO算法，对复杂高维非线性的优化问题表现出很强的优化效率。

(2)与智能优化算法相混合。各种智能算法具有独立的思想理论体系，有各自的优缺点，通过与其他各种智能优化方法的混合，相互取长补短，实现优势互补，以克服PSO算法自身的局限性。目前，将PSO算法与演化算法、模拟退火算法、差分进化算法、蚁群算法、禁忌搜索、分布估计算法、模糊计算、人工鱼群算法等算法^［29-35］相互结合，形成了各种各样的混合粒子群优化算法。

(3)与自然界中的思想相融合。计算智能中的优化算法大多数是来自于自然界存在的现象和机制的启发，因此将PSO算法与自然界中的思想相融合是一种行之有效的途径。已有学者结合生物界中物种发现生存密度过大时会自动分家迁移的习性、生物学中细菌趋化性、达尔文进化论中的物竞天择与适者生存、小生境、量子特性、控制论等思想^［36-40］提出了大量新颖的改进粒子群优化算法。

以上三类混合粒子群优化算法中融合其他技术的目的是如下几点中的某一点，抑或兼而有之:提高种群的多样性、增强粒子的全局探索能力，或者提高局部开发能力、增强PSO算法的收敛速度与精度。

2．“统计物理·热力学”与计算智能

统计物理与热力学是研究由大量微观粒子组成的宏观物质系统的理论，分别从微观和宏观两个角度来研究热运动规律及热运动对物质宏观性质的影响。在热现象研究中，统计物理和热力学这两种理论各有优缺点，但是两者相辅相成、相得益彰，热力学验证统计物理学，统计物理学揭示热力学本质。计算智能中的大多数智能优化算法是基于种群的随机搜索算法，其核心思想是若干个体组成的种群按照一定的规则进行进化，它的任务主要是研究个体运动的规律及各种算子对种群收敛性质的影响。计算智能的研究人员发现这两者之间在研究对象、任务和方法方面有诸多的相似性，根据统计物理和热力学中的固体退火过程、自由能极小化定律、粒子输运理论、伊藤过程等理论，构造出了大量原创和改进的智能优化算法。

将统计物理与热力学中的思想引入到智能优化算法的设计与改进当中来首推模拟退火算法，它认为组合优化问题的求解过程与固体退火过程存在相似性，随后有很多学者将模拟退火机制引入到诸如演化算法等智能优化算法当中来。近年来，有学者另辟蹊径，从其他思路入手，将统计物理和热力学中的其他思想融入新旧智能优化算法的设计或改进中来，如:基于自由能极小化定律的热力学演化算法^［41］认为种群搜索到最优解的状态对应于热力学系统的自由能最小的基态;基于输运理论的粒子动力学演化算法等^［42］将杂交变异操作看成是粒子在相空间的运动，利用描述粒子输运过程的输运理论构造了一系列求解单目标、约束优化和多目标优化问题的演化算法;伊藤算法^［43］来自于对描述布朗运动的伊藤过程的抽象，伊藤过程中的波动率对应粒子的局部搜索性能，漂移率表示粒子宏观上向最优解移动的趋势。

3．“统计物理·热力学”与粒子群优化算法

有些学者早已经注意到了统计物理和热力学理论对于改进粒子群优化算法的性能有很大的促进作用:借鉴耗散结构理论和自组织临界理论来改善种群的多样性。耗散粒子群优化算法^［44］将PSO模型看成是一个具有耗散结构特征的热力学系统，通过对粒子的速度和位置进行扰动这两种方式引入负熵来改善种群的多样性，使种群尽可能远离平衡态;自组织临界粒子群优化算法^［45］为种群中的每一个粒子增加临界值属性，当某粒子的临界值属性超过阈值时则重新分配该粒子在搜索空间中的位置，从而提高了种群的多样性。

受以上混合技术的启发，将PSO模型看成是一个分子热运动系统，分别从微观、介观和宏观三个层次，借鉴分子热运动中分子力、伊藤过程和扩散现象三个不同机制提出了四种改进粒子群优化算法。

(1)微观层次:在第3章中借鉴分子运动论中分子之间的引力斥力模型，提出了基于分子运动论的粒子群优化算法(MPSO)，参考物理学中的相关概念，MPSO算法中定义了粒子的加速度和种群质心两个概念。

(2)介观层次:在第4章中借鉴描述布朗运动的伊藤过程，把伊藤过程抽象成漂移和波动两个主要过程，首先把漂移过程引入到PSO算法的设计当中，提出了融合漂移过程的粒子群优化算法(IPSO1)，发现IPSO1算法收敛速度较PSO算法有很大的提高，然而收敛效率尚不足，紧接着采用了两种策略来改进IPSO1算法:一种是继续引进漂移过程，提出了融合漂移和波动过程的粒子群优化算法(IPSO2);另一种是引入热力学选择机制，提出了基于热力学选择机制的漂移粒子群优化算法(IPSO3)，IPSO3算法中定义了粒子的熵和自由能等概念。

(3)宏观层次:在第5章中借鉴分子扩散理论提出基于扩散机制的双种群粒子群优化算法(DPSO)，与前几种算法类似，参考物理学中的概念，给出了粒子的扩散能、种群温度和粒子的扩散概率等定义。