粒子群优化算法的改进

常见粒子群优化算法的改进•1。模糊惯性权重(fuzzyinertiaweight)法•Shi等提出用模糊控制器来动态自适应地改变惯性权重的技术。控制器的输入是当前惯性权重w和当前最好性能评价值(CBPE),CBPE衡量PSO目前找到的最好候选解的性能;输出是w的改变量。由于不同的问题有不同范围的性能评价值,因此需要对CBPE进行如下的规范化NCBPE=（CBPE–CBPEmin）/（CBPEmax–CBPEmin）NCBPE是规范化后的评价值,CBPEmin和CBPEmax依问题而定,且需事先得知或者可估计。模糊w法与线性下降w方法的比较结果显示,后者不知道应该降低w的合适时机,而自适应模糊控制器能预测使用什么样的w更合适,可以动态地平衡全局和局部搜索能力。但是由于需知道CBPEmin和CBPEmax等,使得模糊权重法的实现较为困难,因而无法广泛使用。常见粒子群优化算法的改进•2。压缩因子(constrictionfactor)法•Clerc得出结论:压缩因子有助于确保PSO算法收敛。这种方法的速度更新方程为•其中,为压缩因子，,且φ4。约束因子法控制系统行为最终收敛,且可以有效搜索不同的区域,该法能得到高质量的解。11122[()()]kkkkkkkijijijjijijjgjijvvwvcrpxcrpx1222/2(4)12cc常见粒子群优化算法的改进•3。基于遗传思想改进的PSO算法——选择(selection)法•主要应用PSO的基本机制以及演化计算所采用的自然选择机制。由于PSO搜索过程依赖pbest和gbest,所以搜索区域有可能被他们限制住了。选择PSO算法.在一般粒子群算法中,每个粒子的最优位置的确定相当于隐含的选择机制.为此,Angeline将选择算子引入进了PSO算法中,选择每次迭代后较好的粒子复制到下一代,以保证每次迭代的粒子群都具有较好的性能,实验表明这种算法对某些测试函数具有优越性.自然选择机制的引入将会逐渐减弱其影响。测试结果显示,虽然在大多数测试函数中选择法取得了比基本PSO更好的效果,却在Griewank函数上得到了较差的结果。因此该法提高了PSO的局部搜索能力,但同时削弱了全局搜索能力。常见粒子群优化算法的改进•4。线性减少权系数法•ShiY提出了带有惯性权重的改进PSO算法,进化方程为:•式中w0,称为惯性因子.它随着迭代次数的增加而线性递减,使算法在初期具有较强的全局寻优能力,而晚期具有较强的局部收敛能力,一定程度上提高了算法的性能.如w(t)=(w1-w2)×（itermax–iter）/itermax+w2式中:w1和w2是惯性权重的初始值和最终值,itermax和iter分别为最大迭代次数和当前迭代次数.11122()()kkkkkkijijjijijjgjijvwvcrpxcrpx常见粒子群优化算法的改进•通过经验发现惯性权重为0.7298、加速系数为1.49618时，总能导致收敛的轨迹。•朱小六等人提出的动态自适应惯性权重改变方法：先引入两个变量粒子进化度粒子聚合度然后，定义权重变换公式：w=w0-0.5*e+0.1*a其中，w0为w的初始值，一般取0.9；由e、a的定义可知0e≤1、0a≤1，所以•w0-0.5ww0+0.1。试验证明该方法提高了粒子群收敛的精度，加强了全局搜索的能力。1/kkijijepp1*/Nkkkijgjijkappp常见粒子群优化算法的改进•速度上限选择•粒子的最大速度Vmax控制粒子绝对速度上限，以免粒子的位置坐标越出搜索空间。标准PSO算法中，Vmax取固定值，粒子搜索的区域大小在整个过程中不变，这不符合普遍的搜索规则———在大范围搜索之后，应有细致的局部区域搜索过程。因此，较好的做法应该是，在PSO算法的开始Vmax取较大值，以利于算法的大范围搜索；在算法的后期Vmax取较小值，以利于算法的局部搜索。例如，给Vmax引入一个权重λ=（runmax-run）/runmax，λ从1到0线性递减。应该说明，通常可以设置Vmax为整个搜索空间大小，例如位置矢量分量-5≤xi≤5，则可取Vmax=10。有些研究者认为，已经在速度更新公式中使用了收缩因子或惯性权重，最大速度的限制是多余的，至少没有它也能保证算法收敛。但是，在许多情况下，Vmax对最优值的搜索仍有改善作用。常见粒子群优化算法的改进•加速系数的修正•通常可选择加速系数C1=C2=1.49618，一般取C1=C2∈［０，４］。Ratnaweera等提出自适应公式：•其中，C1i，C1f，C2i，C2f为常数，run为当前迭代次数，runmax为算法迭代总数。这样的修正可以在优化早期促进对整个搜索空间的全局搜索，而在搜索末尾鼓励粒子收敛到全局最优。1111()maxfiirunccccrun2222()maxfiirunccccrun常见粒子群优化算法的改进•繁殖(Breeding)法•L.vbjerg等人将遗传算法中的复制和重组这些称为繁殖的操作加入到全局版PSO中,该方法是对按概率Pi选出的粒子进行如下式•child1(Xi)=pparent1(Xi)+(1.0-pi)parent2(Xi)•child2(Xi)=piparent2(Xi)+(1.0-pi)parent1(Xi)•child1(Vi)=parent1(Vi)+parent2(Vi)|parent1(Vi)+parent2(Vi)|·|parent1(Vi)|•child2(Vi)=parent1(Vi)+parent2(Vi)|parent1(Vi)+parent2(Vi)|·|parent2(Vi)|•的代数杂交操作,产生子代的粒子取代父代。选择父代没有基于适应值,防止了基于适应值的选择对那些多局部极值的函数带来潜在问题。pi是(0,1)间的随机数(经验值约为0.2)。理论上讲繁殖法可以更好地搜索粒子间的空间,2个在不同次优峰处的粒子经繁殖后,可以从局部最优逃离。结果显示,对单峰函数,繁殖法虽略加快了收敛速度,却不如基本PSO和GA找到的解好,而对于多局部极值的函数,繁殖PSO不仅加快了收敛速度,而且找到了同样好或更好的解。1111()maxfiirunccccrun粒子群优化算法的研究方向•算法的数学分析.•目前,大多数研究者主要还是致力于PSO算法的应用研究,很少涉及对算法内部机理的数学分析,表现为:①PSO算法中位置和速度的构造及参数的设计理论不成熟;②对PSO算法中的参数分析,没有实质性的认识,都处在实验分析阶段;③PSO算法的改进算法及其应用也都停留在实验阶段,缺乏理论支持;④还没有给出收敛性、收敛速度估计等方面的数学证明.因此,开展一些对PSO算法机理的研究,不但可以加深对PSO算法机制的认识,而且对于扩展PSO算法的应用领域也具有比较深远的意义.粒子群优化算法的研究方向•参数的选择与优化.•参数w控制了粒子的全局搜索能力与局部搜索能力之间的平衡,为此如何构造一个惯性权重的自适应调整模型,达到控制粒子的全局搜索能力与局部搜索能力之间的平衡是今后研究的一个重要方向.同时,加速因子c1和c2协同控制着算法朝最优解方向的进化,决定了收敛精度和早熟的平衡问题,因此如何构造一个加速因子的协调模型同样十分重要.粒子群优化算法的研究方向•粒子群的拓扑结构.•不同的粒子群邻域拓扑结构是对不同类型社会的模拟,研究不同拓扑结构的适用范围,对PSO算法推广和使用都有重要意义.粒子群优化算法的研究方向•与其他算法的融合.•如何将其它演化的优化和PSO算法的优化相结合.构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向.