智能优化理论-第10章粒子群优化算法

第10章粒子群优化算法contents目录粒子群优化算法的基本原理基本粒子群优化算法改进的PSO算法离散粒子群优化算法粒子群优化算法应用举例粒子群优化算法的应用优势与存在的主要问题复习思考题粒子群优化算法的基本原理01粒子群优化算法(PSO)是通过观察鸟群捕食行为启发而来。在搜索空间中，每个优化问题的解被视为一只鸟，即“粒子”。初始化一群粒子，每个粒子都是可行解，并由目标函数评价其适应度值。粒子群优化算法的基本原理03设每个优化问题的解是搜索空间的一只鸟，把鸟视为空间中的一个没有重量和体积的理想化的“质点”，称为粒子。01每个粒子都在解空间中运动，并由一个速度决定其飞行方向和距离。02粒子追随当前的最优粒子在解空间中进行搜索，每一次迭代都跟踪两个“极值”来更新自己。粒子群优化算法的基本原理010203每个粒子都有一个由被优化函数所决定的适应度值，还有一个速度决定它们飞行方向和距离。粒子通过追随当前的最优粒子在解空间中搜索最优解，需要性能评价和粒子之间进行全局或局部的信息交流。PSO算法通常具有3种基本的信息拓扑结构：环形拓扑、星形拓扑、分簇拓扑。粒子群优化算法的基本原理粒子群优化算法的基本原理01在环形拓扑结构中，任意一个粒子仅与其邻域中的两个粒子交流信息。02在星形拓扑结构中，中心粒子与其他所有粒子之间具有双向信息交流。其他也有诸如小世界的信息拓扑结构等。03粒子群优化算法的基本原理不同的信息拓扑结构具有不同的邻域定义，体现了不同效率的信息共享能力与社会组织协作机制。它通过邻域规模、邻域算子和邻域中的迄今最优解，影响PSO算法的性能。基本粒子群优化算法02基本粒子群优化算法在n维连续搜索空间中，对粒子群中的第i个粒子或个体进行定义。n维位置向量表示该粒子或个体的当前位置；n维最优位置向量表示该粒子或个体迄今所获得的具有最优适应度值的位置；n维速度向量表示该粒子或个体的搜索方向。PSO算法中的m个粒子一直在并行地进行搜索运动。每个粒子可认为是一个在搜索空间中飞行的智能体。在每次迭代中，该算法记录下每个粒子的迄今最优位置，并相互交流粒子之间的局部信息，进一步获得整个粒子群或邻域的迄今最优位置。问题归结为每个粒子在n维连续解空间中如何从一个位置运动到下一个位置。而这可通过将简单地加上得到。群体中所有粒子所经历过的最优位置称为全局最优位置。基本粒子群优化算法123若令（单位时间），则有以下位置更新公式为这里，对第i个粒子，在计算出后，应对其进行评价，即须计算出相应的适应度值。PSO算法在根据上式计算之前，须先确定出，而这可由PSO算法中的速度更新公式给出。基本粒子群优化算法01基本PSO算法的实现步骤如下02步骤1：初始化。设定PSO算法中涉及的各类参数，包括搜索空间的下限Le和上限He，加速度因子和，算法的最大迭代次数Tmax。或收敛精度，粒子速度范围[vmin，vmax]。03随机初始化搜索点的位置xi和速度vi，设每个粒子的当前位置为pi，从个体找到的最优解中找出种群最优解，记录对应于最优解的粒子的序号g和其位置pg。基本粒子群优化算法评价每一个粒子。计算每个粒子的适应值，如果该适应值优于该粒子当前的个体最优值，则将pi设置为该粒子的位置，同时更新个体最优值。更新粒子状态。根据式对每一个粒子的速度和位置进行更新。如果则将其置为；如果，则将其置为。基本粒子群优化算法步骤3步骤2改进的PSO算法03在PSO算法的迭代过程中，速度值有可能变得非常大，导致性能降低。为了控制速度的增加，通常可采取两个措施：一是通过增加惯性权重，二是加入收缩系数。具有惯性权重的PSO算法通过增加惯性权重可以增强算法的全局搜索能力，并通过减小惯性权重提高局部搜索能力。010203具有速度控制的改进型PSO算法具有速度控制的改进型PSO算法选择一个合适的惯性权重有助于PSO算法均衡它的探索能力和开发能力。在迭代过程中，初始时取较大的值，比如0.9-1.2之间的值，以扩大算法的全局搜索能力。随着迭代的进行呈线性递减，以加强迭代后期的局部搜索性能，能够使算法精确得到全局最优解。引入惯性权重可以消除基本PSO算法对vmax的依赖，并平衡全局和局部搜索能力。随着时间收敛，粒子的振荡轨迹幅度会随时间不断减少。具有速度控制的改进型PSO算法PSO算法的粒子群规模或粒子数m的选择，需要折中求解质量与计算量之间。避免PSO算法的早熟，可增加粒子群的规模，但也会降低搜索速度。将基本PSO算法中的整个粒子群的迄今最优解扩展为考虑粒子邻域的迄今最优解。具有邻域算子的PSO算法邻域大小实际描述了信息共享或社会相互作用的范围，也给出了通信的代价。采用全邻域似乎更好，因其算法性能与基于环形拓扑结构的PSO算法相差不大。PSO算法有全局版本和局部版本。全局版本每个粒子的邻域包含所有个体，而局部版本仅包含与该粒子有直接信息连接的部分个体。具有邻域算子的PSO算法具有邻域算子的PSO算法010203全局版本PSO算法收敛速度较快，但是容易陷入局部最优，而采用不同的邻域拓扑结构的局部版本PSO算法更容易找到全局最优或次优解。如果信息在粒子之间传递得太快，则很容易使整个系统出现早熟，即粒子很快聚集到一个局部极值点上；反之，如果信息传递得太慢，则因为单个粒子很难迅速得到相距较远的粒子的信息，使得算法的收敛速度变慢，从而影响计算效率。常见的邻域结构有星形结构、环形结构、金字塔结构以及冯·诺依曼结构，如图10.2所示。星形结构以其中一个粒子为中心，与邻域中的其他所有粒子相联系，而其他粒子不进行信息交换。星形结构在环形结构中所有粒子排成一个环，该结构中每个粒子与其相邻的两个粒子交换信息，从而有效地保证了种群的多样性。环形结构具有邻域算子的PSO算法离散粒子群优化算法04PSO算法在求解离散变量优化问题上形成了两条完全不同的技术路线。一是以经典的连续型PSO算法为基础，将离散问题空间映射到连续粒子运动空间，并适当修改PSO算法来求解。二是针对离散优化问题，以PSO算法信息更新的本质机理为基础，重新定义特有的粒子群离散表示方式与操作算子来求解。在计算上，以离散空间特有的、对向量的位操作来取代传统向量计算；从信息流动机制上看，仍保留了PSO算法特有的信息交换和流动机制。区别在于前者将实际离散问题映射到粒子连续运动空间后，在连续空间中计算和求解；后者则是将PSO算法映射到离散空间，在离散空间中计算和求解。0102030405PSO算法的离散化方法现有文献对基于连续空间的DPSO算法的研究居多，形成了针对0-1规划问题的二进制PSO算法（BinaryPSO，BPSO），并建立了不同于传统PSO算法的新计算模式。针对排序组合优化问题，在传统PSO算法上增加一些离散化策略是当前研究常采用的方法。在BPSO算法中，粒子位置的每一维被限制为1或者0，而对速度则不作这种限制。使用速度更新位置时，值越大，粒子的位置越有可能选1，值越小则越接近0。基于连续空间的DPSO算法速度更新公式在形式上保持不变，即其中定义在二进制问题空间中的第i个粒子的第j位(bit)以及相应的、取值为1或0。每个粒子均对应一个长度为n的二进制串，如同遗传算法一样，它表示了问题的一个解。粒子的当前速度分量被定义为二进制位取值为1或0的概率，因此必须将概率限制在[0，1]之间。基于连续空间的DPSO算法BPSO算法的粒子状态更新公式为：式中，Sigmoid函数可以保证向量的每个分量都在区间[0，1]内；rand()为满足[0，1]之间均匀分布的随机数。试验结果表明，对于大多数测试函数，BPSO算法都比遗传算法速度快，尤其是在问题的维数增加时。为此，该算法引入了Sigmoid函数进行变换。基于连续空间的DPSO算法用基于连续空间的DPSO算法求解离散问题时，算法生成的连续解与整数规划问题的目标函数评价值之间存在多对一的映射。因此该目标函数不能完全反映PSO算法中连续解的质量。BPSO算法并不直接优化二进制变量本身，而是通过优化连续变化的二进制变量为1的概率，达到间接优化离散变量的目的。基于连续空间的DPSO算法基于连续空间的DPSO算法整数规划问题的连续化导致大量冗余解空间与冗余搜索，从而影响了算法的收敛速度。由于连续空间里的向量计算十分简单，消耗时间短，因此基于连续空间的DPSO算法仍能保持较快的运算速度。目前关于基于离散空间的DPSO算法的研究还比较少。研究者们往往根据具体问题构建相应的粒子表达方式，并通过重新定义粒子优化算法中的加减法和乘法运算规则来求解。Clerc针对旅行商问题提出的TSP-DPSO算法和Farzaneh针对0-1规划问题提出的离散二进制PSO算法（记为B-PSO）。010203基于离散空间的DPSO算法Clerc重新定义了PSO算法中的“加减法”操作和“乘法”操作，实现了PSO算法向离散空间的映射。重新定义后的粒子状态更新公式为：，其中，表示粒子的位置和速度，表示因子和为随机生成的与位置同维度的向量，向量间的“加减法”定义为对二进制位的“异或”操作，记为，向量间“乘法”定义为对二进制位的“与”操作，记为。基于离散空间的DPSO算法基于离散空间的DPSO算法030201B-PSO算法借鉴免疫机制以避免算法陷入局部最优，从其试验结果来看，B-PSO算法的效率高于BPSO算法和遗传算法。B-PSO算法中的粒子速度是与位置同维的二进制向量，粒子的更新计算在离散空间中进行，这与连续空间的BPSO算法完全不同。基于离散空间的DPSO算法采用了位操作，虽可能增加单步计算代价，但不存在冗余搜索问题，且对离散问题表达自然，易与其他进化算法结合。混合PSO算法将PSO算法的基本思想与各种进化计算方法相结合，发展各种混合PSO算法，已成为目前的研究热点之一。PSO算法的最大优点是实现简单，全局搜索能力强，应用广泛。在PSO算法的粒子群中引入遗传算法中的自然选择原理，又如与人工免疫算法结合的免疫PSO算法等。还有与量子计算、混沌方法、耗散结构等相结合的方法，也层出不穷。基于离散空间的DPSO算法粒子群优化算法应用举例05010405060302Schwefel函数的全局最大值为，当n=2时，取得该值。利用PSO算法计算Schwefel函数的近似全局最优解。参数选择：粒子个数n=40，学习率=，惯性权重的初始值为1.0，随迭代次数线性递减。搜索过程如图10.4所示。平均适应度值曲线如图10.5所示。搜索结果如表10.1所示。粒子群优化算法应用举例粒子群优化算法的应用优势与存在的主要问题06010203以社会交互为基础的群体智能具有巨大的价值创造能力，特别是在复杂问题的优化领域。粒子群优化算法应用的优势主要体现在非导数型优化、鲁棒性、协作行为和灵活性方面。该算法不需要依赖于目标函数的导数信息，而是通过个体之间的社会交互机制寻找最优解。粒子群优化算法的应用优势与存在的主要问题粒子群优化算法的应用优势与存在的主要问题搜索过程陷入局部最优值的可能性大大降低，并且基于群体的PSO算法更不容易受到个体失误的影响。02粒子群优化算法最大的优势是它可以工作于动态环境中，并且对于GbestPSO算法，粒子最终收敛于全局最佳与个体最佳位置连线上的一点。03增加惯性的权重，将会增加粒子的速度而导致更多的全局搜索和更少的局部搜索，反之亦然。01调整适当的惯性权值并不是一个简单的任务，它与问题相关。粒子群优化算法还缺少坚实的数学分析基础，尤其缺少算法收敛条件和参数调