粒子群算法基本原理

.4.1粒子群算法基来源理粒子群优化算法[45]最原始的工作能够追忆到1987年Reynolds对鸟群社会系统Boids（Reynolds对其仿真鸟群系统的命名）的仿真研究。往常，群体的行为能够由几条简单的规则进行建模，虽然每个个体拥有简单的行为规则，可是却群体的行为却是特别的复杂，所以他们在鸟类仿真中，即Boids系统中采取了下面的三条简单的规则：（1）飞离最近的个体(鸟)，防止与其发生碰撞矛盾；（2）尽量使自己与周围的鸟保持速度一致；（3）尽量试图向自己认为的群体中心凑近。虽然只有三条规则，但Boids系统已经表现出特别逼真的群体齐集行为。但Reynolds只是实现了该仿真，并无实用价值。1995年Kennedy[46-48]和Eberhart在Reynolds等人的研究基础上创建性地提出了粒子群优化算法，应用于连续空间的优化计算中。Kennedy和Eberhart在boids中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来找寻食物。Kennedy和Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域拥有多种意义，于是作者用“粒子（particle）”来称呼每个个体，这样就产生了基本的粒子群优化算法[49]。假定在一个D维搜寻空间中，有m个粒子组成一粒子群，其中第i个粒子的空间地点为Xi(xi1,xi2,xi3,...,xiD)i1,2,...,m，它是优化问题的一个潜在解，...将它带入优化目标函数能够计算出其相应的适应值，根据适应值可权衡xi的优劣；第i个粒子所经历的最好地点称为其个体历史最好地点，记为Pi(pi1,pi2,pi3,...,piD)i1,2,...,m，相应的适应值为个体最好适应值Fi；同时，每个粒子还拥有各自的飞翔速度Vi(vi1,vi2,vi3,...,viD)i1,2,...,m。所有粒子经历过的地点中的最好地点称为全局历史最好地点，记为Pg(Pg1,Pg2,Pg3,...,PgD)，相应的适应值为全局历史最优适应值。在基本PSO算法中，对第n代粒子，其第d维(1≤d≤D)元素速度、地点更新迭代如式(4-1)、(4-2)：vn1vncr(pnxn)cr2(pnxn)(4-1)idid11idid2gdidxidn1xidnvidn(4-2)其中：ω为惯性权值；c1和c2都为正常数，称为加快系数；r1和r2是两个在[0,1]范围内变化的随机数。第d维粒子元素的地点变化范围和速度变化范围分别限制为Xd,min,Xd,max和Vd,min,Vd,max。迭代过程中，若某一维粒子元素的Xid或Vid高出边界值则令其等于边界值。粒子群速度更新公式(4-1)中的第1部分由粒子先前速度的惯性惹起，为“惯性”部分；第2部分为“认知”部分，表示粒子本身的思考，即粒子根据自己历史经验信息对自己下一步行为的影响；第3部分为“社会”部分，表示粒子之间的信息共享和相互合作，即群体信息对粒子下一步行为的影响。基本PSO算法步骤如下：（1）粒子群初始化；（2）根据目标函数计算各粒子适应度值，并初始化个体、全局最优值；（3）判断是否知足终止条件，是则搜寻停止，输出搜寻结果；否则持续下...步；（4）根据速度、地点更新公式更新各粒子的速度和地点；（5）根据目标函数计算各粒子适应度值；（6）更新各粒子历史最优值以及全局最优值；（7）跳转至步骤3。关于终止条件，往常能够设置为适应值误差达到预设要求，或迭代次数超过最大允许迭代次数。基本的连续PSO算法中，其主要参数，即惯性权值、加快系数、种群规模和迭代次数对算法的性能均有不同程度的影响。惯性权值ω的取值对PSO算法的收敛性能至关重要。在最初的基本粒子群算法中没有惯性权值这一参数。最初的PSO算法容易陷入局部最小，于是在后来的研究中引入了惯性权值来改良PSO算法的局部搜寻能力，形成了目前常用的基本PSO算法形式。取较大的ω值使得粒子能更好地保存速度，进而能更快地搜寻解空间，提高算法的收敛速度；但同时由于速度大可能致使算法无法更好地进行局部搜寻，容易错过最优解，特别是过大的ω会使得PSO算法速度过大而无法搜寻到全局最优。取较小的ω值则有利于局部搜寻，能够更好地搜寻到最优值，但因为粒子速度受其影响相应变小进而无法更快地进行全局搜寻，进而影响算法收敛速度；同时过小ω值更是容易致使算法陷入局部极值。因此，一个合适的ω值能有效兼顾搜寻精度和搜寻速度、全局搜寻和局部搜寻，保证算法性能。加快系数c1和c2代表每个粒子向其个体历史最好地点和群体全局历史最好地点的移动加快项的权值。较低的加快系数值能够使得粒子收敛到其最优解的...过程较慢，进而能够更好搜寻目前地点与最优解之间的解空间；但过低的加快系数值则可能致使粒子始终彷徨在最优邻域外而无法有效搜寻目标地区，进而致使算法性能下降。较高的加快系数值则能够使得粒子快速集中于目标地区进行搜索，提高算法效率；但过高的加快系数值则有可能致使粒子搜寻间隔过大，容易越过目标地区无法有效地找到全局最优解。因此加快系数对PSO可否收敛也起重要作用，合适的加快系数有利于算法较快地收敛，同时拥有一定的跳出局部最优的能力。关于速度更新公式(4-1)中，若c1=c2=0，粒子将一直以目前的速度进行惯性飞翔，直到抵达边界。此时粒子只是依靠惯性移动，不能从自己的搜寻经验和其他粒子的搜寻经验中吸取有用的信息，因此无法利用群体智能，PSO算法没有启迪性，粒子只能搜寻有限的地区，很难找到全局最优解，算法优化性能很差。若c=0，则粒子没有认知能力，不能从自己的飞翔经验吸取有效信息，只有社会部分，所以c又称为社会参数；此时收敛速度比基本PSO快，但由于不能有效利用自己的经验知识，所有的粒子都向目前全局最优集中，因此无法很好地对整个解空间进行搜寻，在求解存在多个局部最优的复杂优化问题时比基本PSO容易陷入局部极值，优化性能也变差。若c2=0，则微粒之间没有社会信息共享，不能从同伴的飞翔经验中吸取有效信息，只有认知部分，所以c又称为认知参数；此时个体间没有信息互享，一个规模为m的粒子群等价于m个1单个粒子的运行，搜寻到全局最优解的机率很小。PSO算法中，群体规模对算法的优化性能也影响很大。一般来说，群体规模越大，搜寻到全局最优解的可能性也越大，优化性能相对也越好；但同时算法消耗的计算量也越大，计算性能相对下降。群体规模越小，搜寻到全局最优解的...可能性就越小，但算法消耗的计算量也越小。群体规模对算法性能的影响并不是简单的线性关系，当群体规模抵达一定程度后，再增加群体规模对算法性能的提升有限，反而增加运算量；但群体规模不能过小，过小的群体规模将无法体现出群智能优化算法的智能性，致使算法性能严重受损。关于最大允许迭代次数，较大的迭代次数使得算法能够更好地搜寻解空间，因此找到全局最优解的可能性也大些；相应地，较小的最大允许迭代次数会减小算法找到全局最优解的可能性。关于基本连续PSO来说，由于缺乏有效的跳出局部最优操作，因此粒子一旦陷入局部极值后就难以跳出，地点更新处于阻滞状态，此时迭代次数再增多也无法提高优化效果，只会浪费计算资源。但过小的迭代次数则会致使算法在没有对目标地区实现有效搜寻以前就停止更新，将严重影响算法性能。别的，随机数能够保证粒子群群体的多样性和搜寻的随机性。最大、最小速度能够决定目前地点与最好地点之间地区的分辨率(或精度)。如果最大速度（或最小速度）的绝对值过大，粒子可能会因为累积的惯性速度太大而越过目标地区，进而无法有效搜寻到全局最优解；但如果最大速度（或最小速度）的绝对值过小，则粒子不能快速向目前全局最优解集中，对其邻域进行有效地搜寻，同时还容易陷入局部极值无法跳出。因此，最大、最小速度的限制主假如防备算法计算溢出、改良搜寻效率和提高搜寻精度。基本PSO算法中只波及基本的加、减、乘运算操作，编程简单，易于实现，重点参数较少，设定相对简单，所以惹起了宽泛的关注，目前已有多篇文件对PSO算法进行综述。为了进一步提高基本PSO算法的寻优性能，大量研究工作致力于对基本PSO算法的改良，主要集中于：...（1）对PSO算法更新公式参数、构造的改良主假如对基本PSO算法的速度、地点更新公式中的参数、构造进行调节和增加，以进一步提高算法的优化性能，如引入了惯性权值的PSO算法、自适应惯性权值PSO]算法、模糊自适应惯性权值PSO算法、带收缩因子的PSO算法、Kalman粒子群算法、带邻域算子的PSO算法、拥有社会模式的簇剖析PSO算法、被动会合PSO算法等等。（2）多群、多项PSO算法多群PSO算法即引入多个群体进行优化搜寻；而多相PSO算法中多群体的各个群体对不同的搜寻目标以不同的方式进行搜寻。（3）混淆PSO算法混淆PSO算法的基本思想就是将PSO算法与其余不同算法相联合，实现优势互补，进而进一步提高PSO算法的寻优性能，如模拟退火PSO算法、GA-PSO混淆算法等等。在工程应用中，目前PSO算法在函数优化、神经网络训练、调动问题、故障诊疗、建模剖析、电力系统优化设计、模式辨别、图象办理、数据挖掘等众多领域中均有有关的研究应用报道，取得了优秀的实际应用效果。4.2离散二进制PSO算法离散二进制优化算法拥有好多优势，首先关于纯组合优化问题的表达形式要求优化算法是离散的，其次二进制算法能够表达浮点数，因此也同样合用于连续空间的问题求解。...4.2.1KBPSO算法PSO算法最初是用来对连续空间问题进行优化的，为认识决离散优化问题Kennedy和Eberhart于1997年在基本PSO的基础上提出了一种离散二进制PSO（KBPSO）算法。在KBPSO算法中，粒子定义为一组由0，1组成的二进制向量。KBPSO保存了原始的连续PSO的速度公式(4-1)，但速度丧失了原始的物理意义。在KBPSO中，速度值vid经过预先设计的S形限幅变换函数Sig(vid)变换为粒子元素xid取“1”的概率。速度值vid越大，则粒子元素地点xid取的可能性越大，反之则越小。vn1vncr(pnxn)cr2(pnxn)(4-1)idid11idid2gdidSig(vid)1（4-3）1exp(vid)1ifrand( )Sig(vid)(4-4)xidotherwise0其中Sig(vid)为Sigmoid函数，往常为防备速度过大，令vid[vidmin,vidmax]，以使概率值不会过于凑近0或1，保证算法能以一定的概率从一种状态跃迁到另一种状态，防备算法早熟。虽然Kenndedy和Eberhart将KBPSO应用于函数优化问题，并考证了KBPSO的有效性，但鉴于KBPSO的应用研究有限。...4.2.2SBPSO算法鉴于连续基本PSO算法的信息体制，Shen等人提出一种改良的离散二进制粒子群算法（SBPSO）用于QSAR（QuantitativeStructure－activityrelationship）建模的特点选择中。SBPSO算法中舍弃了基本PSO算法中速度、地点更新公式，从头定义速度vi为一个在0到1之间的随机数，粒子元素的地点xid则根据下列规则由随机产生的vid确定：xidn1xidnif(0vid)（4-5）xidn1Pidnif(vid1(1))（4-6）2xn1Pnif(1(1)v1)idgd2id（4-7）其中α∈(0,1)称为静态概率（staticprobability），是SBPSO算法中唯一可调参数，它能够是一个常数、一个变量或是一个随机数。虽然SBPSO的更新公式在形式上与KBPSO以及基本的PSO算法都有很大的改变但其基本的思想不变，即：每个粒子都只与自己历史最优值和全局最优值进行信息沟通BPSO地点更新公式(4-5)近似于基本连续PSO速度更新公式(4-1)中的第一项，都是一种“惯性”的表现，只可是SBPSO是停留在原来的地点，而PSO中是根据速度惯性持续搜寻。同样，SBPSO地点更新公式(4-6)、(4-7)则分别对应了基本PSO速度更新中的第二、三项，分别代表了粒子的“认知”部分和“社会”部分，表示粒子自己和社会群体对粒子下一步行为的影响。式(4-5)增强了SBPSO算法的全局搜寻能力，使得粒子能够有效地对目标地区进行搜索，找出全局最优解。没有式(4-5)，粒子将完全跟从自己的两个最优解“飞翔”，...进而容易陷入局部最优值。式(4-6)、(4-7)则根据先前的搜寻经验对粒子搜寻进行指导，没有这两项，SBPSO算法例变成了完全的随机搜寻。因此，在SBPSO算法中，静态概率α替代了基本PSO算法中的ω，c1，c2等参数，对算法的性能至关重要。较大的α值能使得算法更好地搜寻解空间，进而能够更好地跳出局部最优搜寻到全局最优；但过大的α值则会致使算法无法充分利用已有的寻优信息，致使算法收敛速度过慢。较小的α值能够使得粒子快速集中于最优邻域，提高收敛速度，但容易致使算法陷入局部最优。4.3离散二进制PSO算法参数性能剖析为了全面地比较、权衡离散二进制PSO算法中重点参数对算法优化性能的影响程度，本文中以标准优化测试函数为对象进行算法优化性能的仿真切验，并按照以下统计指标进行评论。（1）最优率群智能优化算法是一种全局随机性启迪式算法，由于算法的随机性，在对复杂优化问题求解时，并不能保证算法以1的概率收敛到全局最优解。但关于优化算法来说，在一定的运算规模内找到全局最优解最为重要。因此，采用最优率——即优化算法搜寻到全局最优解的概率，作为算法性能评论的第一指标。在本文中，每个算法对标准函数均优化求解100次，其中成功搜寻到全局最优解的比率即为最优率。（2）最优适应值、平均最优适应值最优适应值是优化算法寻优时所找到的最好解，平均最优适应值（简称平均最优值是对优化问题多次求解后搜寻到的最优解适应度值的平均值。最优适应值...能够权衡算法的优化性能，看其可否找到全局最优解，而平均最优适应值则权衡算法性能对随机初值和操作的依靠程度。平均最优适应值越凑近全局最优解适应度值，说明该优化算法对随机初值和操作的依靠程度越低、算法的鲁棒性越高。（3）收敛时间收敛时间是优化算法寻优时所要考虑的另一项重要指标。收敛时间越短，则算法的收敛速度越快，消耗的计算资源就越少；反之，收敛时间越长，则算法的收敛速度越慢，所需的计算资源就越多。在本文中分别以最快收敛步数——即算法搜寻到全局最优解的最少迭代次数，和平均收敛时间——即算法多次寻优找到全局最优解迭代步数的平均值，作为考察指标。最优收敛步数能够表示算法搜寻能力，但考虑到群智能算法的随机性，因此平均收敛步数能更好地表征算法的搜索能力。4.4改良的离散二进制PSO算法离散二进制PSO算法拥有基本PSO算法的简单、易实现等优点，特别是SBPSO算法，其算法中调节参数只有静态概率；但同时也继承了基本PSO算法易陷入局部最优的缺陷。针对这一问题，关于连续空间PSO算法目前已经有大量文件报道对PSO算法的改良研究[50-52]；但关于离散二进制PSO算法的改进工作目前有关的研究报道还很少。本章在基本离散二进制PSO算法的基础上，引入变异操作用以改良离散二进制PSO算法，提高其性能。在遗传算法（GeneticAlgorithm，GA）中，如果种群收敛到早熟集（prematureset）GA算法将基本失去对解空间的搜寻能力。关于怎样防止过早收敛，GA算法中在遗传算子、种群规模、遗传漂浮（geneticdrift）方面均有有关的研究。...其中，在遗传算子方面，献中指出GA的三种基本遗传算子中交错与选择算子只拥有局部搜寻能力，它们的搜寻范围只由目前种群决定，而变异算子是唯一具有全局搜寻能力的遗传算子。根据模式定理，变异算子在遗传算法中的作用主要是使种群保持一定的多样性，防止群体陷入局部最优无法跳出。变异算子虽然具有全局搜寻能力，但在实际应用中变异率不能取值过大，否则将损坏算法固有的搜寻体制，无法有效利用已有信息，使得算法退化为随机搜寻算法。但变异率也并不是越小越好,在GA中变异算子关于遗传算法不单是必需的，而且在变异算子的作用不至于使算法退化为随机搜寻的前提下应尽量加大变异率，否则算法易陷入局部最优。由于变异算法能有效地保持群体的多样性，一定程,度地提高了算法跳出局部最优的概率，且操作简单，因此获得了宽泛的研究与应用，并被成功引入至粒子群算法基本的离散二进制PSO算法，特别是SBPSO算法，易于陷入局部最优。虽然KBPSO算法中最大速度的设定使得粒子每个比特起码拥有一定概率变异，但当算法迭代一定次数后，由于速度较大，变异的概率过小，此时难以有效引入新的模式帮助群体跳出局部最优；而SBPSO算法例完全缺乏跳出局部最优的手段。因此为了提高二进制PSO算法的搜寻能力，在基本的离散二进制PSO算法中引入变异操作，但为了能有效利用群智能保证算法搜寻性能，变异概率不能设置过大，以防备损坏PSO算法的迭代体制影响算法优化性能。与二进制编码的GA同样，在DBPSO算法中变异操作的实施也可采用多种举措，如单点变异、多点变异，其变异概率也能够采用确定值或复杂的自适应参数等等。由于在DBPSO算法中，新的粒子主假如经过DBPSO的地点更新公式实现，变异操作的引入只是为了保持群体的多样性，防备早熟，因此本文采...用简单的变异策略，即设定变异概率pm，新一代粒子群中每一位比特都以概率pm实施变异操作。经过上面的介绍我们来剖析一下对循环流化床床温的PSO算法改良的一般过程为如下