搜索
PSO概述姓名：郭俊杰学号：1511414003日期：2015-10-17目录PSO背景PSO介绍PSO改进PSO应用PSO背景人工智能在经历了繁荣之后，随着人类探索脚步的不断前进，其复杂性，非线性，系统性的问题越来越多，面对系统的复杂性，由于在方法论上始终没有突破经典计算的思想，已经逐步陷入困境。随着生命科学的迅猛发展，人工智能的研究摆脱了经典逻辑计算的束缚。在这种背景下，社会性动物的自组织行为吸引越来越多的学者进入到这个领域，通过模拟生物的简单个体的行为规律，用于解决一些常规方法没有解决的传统问题，这就产生了一种新型智能计算技术，即“群智能”(SI)。目前群智能研究主要包括蚁群优化算法(ACO)和粒子群优化算法(PSO)。PSO介绍PSO背景PSO介绍PSO改进PSO应用PSO介绍算法提出：1995年，Kennedy博士和Eberhart博士受自然界中鸟类运动模型的启发提出了一种新的基于种群的搜索算法——PSO算法。算法简介：如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。算法思想：它把所求解问题空间中可能解的位置看成是鸟群运动模型的栖息地，然后通过个体之间的信息交互，逐步提高在求解过程中发现较好的解的可能性，并指引群体中所有的粒子朝着可能解的位置不断聚集。算法分析：PSO算法相对于其他进化算法最大优势在于实现简单和具有更强的全局优化能力。大量实验表明，PSO算法能够解决GA所能解决的各类优化问题。PSO介绍基本原理：在PSO算法中，可以将种群中的每个个体看成是在寻优空间中的一个没有质量，也没有体积的粒子，个体在搜索空间中以一定的速度飞行，根据个体与群体的飞行经验的综合分析结果动态调整飞行速度，逐渐向问题空间的更好区域移动。每个粒子的位置表示搜索空间中的潜在解，粒子飞翔的方向和距离可以通过粒子的速度来控制，粒子的优劣可以通过一个适应值函数来评价。具体方式：PSO算法初始化为一群随机粒子，然后通过追随当前最优粒子进行不断迭代的搜索直至找到最优解或有效解。在每一次迭代过程中，算法通过跟踪个体极值pbest和全局极值gbest来更新各个粒子。个体极值是目前粒子本身所找到的最优解，全局极值是整个种群目前找到的最优解。PSO介绍算法模型：设粒子群规模为M，决策空间N维，粒子i在时刻t的坐标为𝑥𝑖𝑡=(𝑥𝑖1𝑡,𝑥𝑖2𝑡,…𝑥𝑖𝑛𝑡),粒子i的速度为𝑣𝑖𝑡=(𝑣𝑖1𝑡,𝑣𝑖2𝑡,…𝑣𝑖𝑛𝑡);更新公式：𝑣𝑖𝑗𝑡=𝜔𝑣𝑖𝑗𝑡−1+𝑐1𝑟1𝑝𝑖𝑗−𝑥𝑖𝑗𝑡−1+𝑐2𝑟2𝑔𝑗−𝑥𝑖𝑗𝑡−1;(1)𝑥𝑖𝑗𝑡=𝑥𝑖𝑗𝑡−1+𝑣𝑖𝑗𝑡;x𝑖𝑗𝑡=𝑣𝑚𝑎𝑥,𝑣𝑖𝑗𝑡𝑣𝑚𝑎𝑥−𝑣𝑚𝑎𝑥,𝑣𝑖𝑗𝑡−𝑣𝑚𝑎𝑥(2)其中𝜔为惯性权值，𝑐1和𝑐2为加速因子，𝑟1和𝑟2是在[0,1]范围内的两个独立的随机数。一般使用Vmax来限制粒子的最大速度。𝑝𝑖𝑗表示粒子的个体极值，𝑔𝑗表示全局极值。从速度更新公式中看出，粒子的速度更新模型主要由三个部分组成：①对自身状态的信任：即以前速度的影响。②认知部分：即粒子最优位置和当前位置之间距离③社会部分：即群体最优位置与粒子当前位置之间距离。gbestYO𝑣𝑡𝑥𝑡𝑣𝑝𝑏𝑒𝑠𝑡𝑣𝑔𝑏𝑒𝑠𝑡𝑥𝑡+1Xpbest𝑣t+1PSO介绍基本粒子群优化算法流程Step1：初始化所有粒子Step2：评价每个粒子的适应值Step3：更新每个粒子所经过的最好位置pbestStep4：更新群体经过的最好位置gbestStep5：更新当前粒子的速度和位置Step6：满足迭代终止条件则终止迭代，否则返回Step2继续迭代计算群体历史最优算法开始粒子群初始化粒子适应度评价计算个体历史最优更新速度和位置满足条件？算法结束NYPSO介绍参数分析在基本PSO算法中，需要调节的参数主要有种群规模M、最大速度𝑉max、惯性权值𝜔以及加速因子c1和c2等。1）种群规模：一般情况下，种群规模在20-40区间取值就能保证对解空间进行充分的搜索，对于大部分问题，种群规模取10就足以取得较好的结果，但对于特定问题，种群规模有时需要在100-200区间取值。2）最大速度：最大速度决定当前位置与最好位置之间区域的精度。如果Vmax太大，粒子可能会飞过最优解，如果太小，粒子不能在局部好区域之外进行足够的搜索，导致容易陷入局部最优值。3）加速因子：加速因子c1和c2是一组调整自身经验与群体经验影响粒子运动轨迹的重要参数。如果c1为0，则粒子仅有群体经验作用于粒子的运动，这时它的收敛速度可能较快，但对一些复杂问题可能容易导致局部收敛；如果c2为0，则仅有自身经验对粒子的运动起作用，群体中的粒子之间不具备信息交互能力，失去了群智能算法所具备的特性，从而难以得到最优解。如果c1和c2同时为0，则粒子不包含任何经验信息只能搜索有限区域，从而难以找到较好的解PSO介绍参数分析惯性权值：性质一：惯性权值的设置影响了粒子的全局搜索能力与局部能力之间的平衡。公式的第一部分表示了粒子以前的速度对粒子飞行轨迹的影响，而惯性权值就是一个用来表征粒子以前经历过的速度对当前速度的影响程度的数字量。因此惯性权值的设置影响了粒子的全局搜索能力与局部搜索能力之间的平衡。性质二：使用较大的惯性权值，算法具有较强的全局搜索能力。惯性权值是决定保留多少上一时刻的速度，从而取较大的值可以加强搜索以前所未能达到区域的能力，有利于增强算法的全局搜索能力并跳出局部极小点。而取较小的值则说明算法主要是停留在当前解的附件搜索，从而有利于提高算法的局部搜索能力，并加速算法的收敛。该参数对算法性能影响很大，其大小控制着以前速度对当前速度的影响，体现了全局搜索与局部搜索的一个折衷，对PSO算法的收敛性起着至关重要的作用。目前对惯性权值的调整策略主要有线性变化、模糊自适应和随机变化等。其中应用的最多的是线性递减策略，Shi认为这样可以在开始优化时搜索较大的解空间，得到合适的粒子，然后在后期逐渐收缩到较好的区域进行更精细的搜索，以加快收敛速度。PSO介绍对PSO的评价PSO算法的优点在于不要求优化函数具有可微、可导、连续等性质，收敛速度较快，算法简单，容易编程实现。该算法也存在很明显的缺点：1.对于有多个局部极值点的函数，容易陷到局部极值点中，得不到正确的结果；2.PSO算法并没有很充分地利用计算过程中获得的信息，因此往往不能得到精确的结果；3.PSO算法虽然提供了全局搜索的可能，但是并不能保证收敛到全局最优点上；4.PSO算法是一种启发式的仿生优化算法，目前还没有严格的理论基础。PSO改进PSO背景PSO介绍PSO改进PSO应用PSO改进现实生活中，不同领域的优化问题种类繁多，而且具备各自不同的特点。因此，PSO算法提出至今，引起了学术界的广泛关注并开展了大量的研究工作，有力地推动了该算法的发展。目前对PSO算法的改进研究主要体现在算法的参数选择与设计、领域拓扑结构、群体组织与进化、融合进化计算等概念的混合算法等几个方面。这些改进算法需要更具具体问题的领域知识对算法参数进行相应的设置，从而在提高某种性能的同时也付出其他代价。PSO改进基于惯性权值的改进1.惯性权值线性递减该算法为了保证算法的全局搜索能力，在算法运行初期使用较大的惯性权值，而为了保证算法的局部搜索能力，则在算法运行的后期使用较小的惯性权值。𝜔=(𝜔1−𝜔2)×𝑀𝑎𝑥𝐼𝑡𝑒𝑟−𝐶𝑢𝑟𝐼𝑡𝑒𝑟𝑀𝑎𝑥𝐼𝑡𝑒𝑟+𝜔2为了验证该方法的有效性，使用了4种不同的基准函数进行模拟仿真实验，发现这种参数调整方法确实提高了算法的性能和收敛速度，并且在𝜔1=0.9,𝜔2=0.4时，算法前1500次迭代效果最好但该方法在解决多峰值函数问题时容易陷入局部最优。。PSO改进基于惯性权值的改进2.随机惯性权值𝜔=0.5+rand（）2Rand（）为0~1之间的随机数，实验结果表明，该策略在算法初期确实能够加速粒子的收敛，且对于大部分优化函数都能找到相当好的解。PSO改进基于惯性权值的改进3.惯性权值的自适应调整策略在同一代种群中使用不同的惯性权值进行更新的调整策略：1.较高适应度值的粒子比其他粒子更靠近全局最优解，这时可能需要相应的提高其局部搜索能力以求能够对周围区域进行细致的搜索，而为了增大适应度值低的粒子搜索到最优解的概率，则应尽快将他们加入到相对较优粒子周围区域的搜索行列中，以提高算法的收敛速度。2.算法后期所有粒子逐渐聚集在一起，粒子间的差异性逐渐缩小，从而造成速度逐渐趋于0并有可能陷入局部最优解。这时可以通过对不同粒子使用不同的惯性权值，以增大粒子间的差异性，并可以很好的控制粒子的全局搜索能力和局部搜素能力之间的平衡。实验结果表明，该惯性权值调整策略确实能够在一定程度上很好地控制算法全局收敛能力和局部收敛能力之间的平衡，从而能够加快算法的收敛速度，并能跳出局部最优解。PSO改进基于加速因子的改进Ratnaweera等提出在算法初期使用较大c1和较小c2值而后期逐渐减小c1并增大c2值得加速因子调整策略。保证算法初期的局部范围内的细致搜索以及保证后期算法收敛速度的加快。通过实验结果，作者发现当c1由2.5线性递减至0.5而c2由0.5线性递增至2.5时，算法获得的适应度值是最优的。然而这种方法虽然在单峰值函数的测试中表现突出，但是在多峰值函数的测试中容易导致过早收敛。进一步考虑了c1和c2的非对称变化情况，发现c1由2.75线性递减至1.25,c2由0.5线性增至2.25时，对大多数基准函数都能得到相对较好的适应度值。PSO改进基于邻近群拓扑的改进gbest模型：群体中的所有粒子都使用整个群体中最优值来更新各自的速度和位置，并向这个最优粒子的方向不断靠拢。lbest模型：先根据所选的拓扑结构划分为若干子种群，然后根据每个粒子所在的子种群的局部最优解来不断更新自己的速度和位置。gbest模型虽然加快了算法的收敛速度但是容易陷入局部最优解。lbest模型收敛速度不如前者，但是不容易陷入局部最优解。选择不同的邻近拓扑会在一定程度上影响算法的性能。基于lbest模型产生了多种变形拓扑：轮型和随机环型。实验结果表明：选择合适的邻近群拓扑对于提高算法性能至关重要，但邻近群拓扑与具体问题的关系很大，且无法找到适用于所有基准函数的邻近群拓扑。例如：对于轮型拓扑，虽然能提高算法收敛速度，但只适用于单峰函数。PSO改进基于种群规模的改进动态的调整种群的规模：1.如果种群的改进质量达不到预先所设置的阀值，那么可以通过为邻近群中的最优粒子增加一个自己的“复制”来扩大种群规模。2.如果种群规模的改进质量达到了预先所设置的阀值，那么可以通过删除邻近群中的最差粒子来缩小种群规模。通过观察运行情况，对于一些具体函数，动态调整规模的PSO算法比一种合适的固定种群规模的PSO算法性能要差。但是动态调整种群规模的PSO算法对于那些需要通过多次尝试才能找到合适的种群规模大小的操作则可以大大节省时间。PSO改进协同粒子群优化算法单种群PSO算法的搜索过程中粒子需要在解空间的所有维上同时搜索，优化中可能会出现在某些维上接近目标位置，而在另一些维上却远离其目标位置的情况。故提出一种协同粒子群优化算法CPSO-S，其基本思想是用K个相互独立的粒子群分别在D维的目标搜索空间的不同维度方向上进行搜索。与基本PSO算法相比，其更容易跳出局部极值，达到较高的收敛精度。但算法上存在明显的“启动延迟”现象，在迭代初期，适应值下降缓慢，收敛速度慢。PSO应用PSO背景PSO