pso的约束优化

约束优化问题的目标是在满足一组线性或非线性约束的条件下，找到使得适应值函数最优的解。对于约束优化问题，需要对原始PSO算法进行改进来处理约束。

一种简单的方法是，所有的微粒初始化时都从可行解开始，在更新过程中，仅需记住在可行空间中的位置，抛弃那些不可行解即可。该方法的缺点是对于某些问题，初始的可行解集很难找到。或者，当微粒位置超出可行范围时，可将微粒位置重置为之前找到的最好位置，这种简单的修正就能成功找到一系列Benchmark问题的最优解。Paquet让微粒在运动过程中保持线性约束，从而得到一种可以解决线性约束优化问题的PSO算法。Pulido引入扰动算子和约束处理机制来处理约束优化问题。Park提出一种改进的PSO算法来处理等式约束和不等式约束。

另一种简单的方法是使用惩罚函数将约束优化问题转变为无约束优化问题，之后再使用PSO算法来进行求解。Shi将约束优化问题转化为最小—最大问题，并使用两个共同进化的微粒群来对其求解。谭瑛提出一种双微粒群的PSO算法，通过在微粒群间引入目标信息与约束信息项来解决在满足约束条件下求解目标函数的最优化问题。Zavala在PSO算法中引入两个扰动算子，用来解决单目标约束优化问题。

第三种方法是采用修复策略，将微粒发现的违反约束的解修复为满足约束的解。

约束满足

PSO算法设计的初衷是用来求解连续问题，，对微粒的位置和速度计算公式进行了重新定义，使用变量和它的关联变量存在的冲突数作为微粒的适应度函数，并指出该算法在求解约束满足问题上具有一定优势。Lin在Schoofs工作的基础上研究了使用PSO算法来求解通用的n元约束满足问题。杨轻云在Schoofs工作的基础上对适应度函数进行了改进，把最大度静态变量序列引入到适应度函数的计算中。

相对传统多目标优化方法, PSO在求解多目标问题上具有很大优势。首先, PSO的高效搜索能力有利于得到多目标意义下的最优解其次, PSO通过代表整个解集的种群按内在的并行方式同时搜索多个非劣解,因此容易搜索到多个Pareto 最优解再则, PSO的通用性使其适合于处理所有类型的目标函数和约束另外, PSO 很容易与传统方法相结合,进而提出解决特定问题的高效方法。就PSO 本身而言,为了更好地解决多目标优化问题,必须解决全局最优粒子和个体最优粒子的选择问题。对于全局最优粒子的选择,一方面要求算法具有较好的收敛速度,另一方面要求所得解在Pareto边界上具有一定的分散性。对于个体最优粒子的选择,则要求较小的计算复杂性,即仅通过较少的比较次数达到非

劣解的更新。迄今,基于PSO的多目标优化主要有以下几种

思路:

(1)向量法和权重法。文献[ 20 ]利用固定权重法、适应性权重法和向量评价法,首次将PSO 用于解决MO问题。然而对于给定的优化问题,权重法通常很难获得一组合适的权重,而向量评价法往往无法给出MO问题的满意解。

(2)基于Pareto的方法。文献[ 21 ]将Pareto排序机制和PSO相结合来处理多目标优化问题,通过Pareto排序法选择一组精英解,并采用轮盘赌方式从中选择全局最优粒子。尽管轮盘赌选择机制设计的目的是使所有Pareto个体的选择概率相同,但是实际上只有少数个体得到较大的选择概率,因此不利于维持种群的多样性文献[ 22 ]通过在PSO中引入Pareto竞争机制和微粒知识库来选择全局最优粒子。由于非劣解是将候选个体与从种群中随机选出的比较集进行比较来确定的,因此该算法成功与否就取决于比较集规模参数的设定。如果这个参数太小,该过程从种群中选出的非劣个体可能过少如果这个参数太大,则可能发生早熟收敛现象。

(3)距离法。文献[ 23 ]根据个体当前解与Pa2reto解之间的距离来分配其适应值,从而选择全局最优粒子。由于距离法需要初始化潜在解,如果初始潜在值太大,不同解的适应值的差别则不明显。这将导致选择压力过小或个体均匀分布,从而导致PSO算法收敛非常缓慢。

(4)邻域法。文献[ 24 ]提出一种基于动态邻域的选择策略,将一个目标定义为优化目标,而将其它所有目标定义为邻域目标,进而提出了选择全局最优粒子的动态邻域策略,但该方法对优化目标的选择以及邻域目标函数的排序较敏感。

(5)多种群法。文献[ 25 ]将种群分为多个子种群,每个子种群单独进行PSO 运算,各个子种群之间通过信息交换来搜索Pareto最优解。但是由于需要增加微粒数目而增加了计算量。

(6)非优势排序法。文献[ 26 ]利用非优势排序的方法选择全局最优粒子。该方法在整个种群中,比较微粒的个体最优粒子与其后代,有利于提供合适的选择压力,同时使用小生境技术提高种群多样性。然而在整个种群中比较所有微粒的个体最优粒子与其后代,其本质不利于种群多样性,容易形成早熟。另外,文献[ 27 ]将博弈理论中的Maximin策略引入PSO来解决多MO问题。利用Maximin策略确定微粒的适应值可以很好地确定Pareto最优解而不需要聚类和小生境技术。

2 约束优化

近年来, PSO算法在约束优化方面也取得了一定进展。基于PSO的约束优化工作主要分为两类: ①罚函数法②设计特定的进化 *** 作或约束修正因子。文献[ 28 ]采用罚函数法,利用非固定多段映射罚函数对约束优化问题进行转化,再利用PSO求解转化后的问题,仿真结果显示PSO相对进化策略和遗传算法有优越性,但其罚函数的设计过于复杂,不利于求解文献[ 29 ]采用可行解保留策略处理约束,即一方面更新存储区时所有粒子仅保留可行的解,另一方面在初始化阶段所有粒子均从可行解空间取值,然而初始可行解空间对于许多问题是很难确定的文献[ 30 ]提出了具有多层信息共享策略的微粒群原理来处理约束,根据约束矩阵采用多层Pareto排序机制来产生优良粒子,进而用一些优良的粒子来决定其余个体的搜索方向。

3 离散优化对于离散优化而言,解空间是离散点的集合,而非连续区域,因此利用PSO解决离散优化问题就必须修正速度和位置更新公式,或者是对问题进行变形。目前,基于PSO的离散优化工作可分为如下三类:

(1)将速度作为位置变化的概率。文献[ 31 ]首次提出了离散二值PSO。其微粒位置编码采用二进制方式,通过采用Sigmoid函数将速度约束于[ 0, 1 ]区间,来代表微粒位置取1的概率文献[ 32 ]对文献

[ 31 ]中的方法进行改进,用于解决置换排列问题。其中微粒用置换排列表示,而速度则根据两个粒子的相似度来定义,决定微粒位置变化的概率,同时还引入变异 *** 作防止最优粒子陷入局部极小。

(2)重新定义PSO *** 作。文献[ 33 ]通过重新定义微粒的位置、速度、以及它们之间的加减乘 *** 作,提出一种新的离散PSO,并用于求解旅行商问题。尽管该算法的效果较差,但是提供了一种解决组合优化问题的新的思路。

(3)直接将连续PSO用于离散情况。文献[ 34 ]利用连续PSO 解决分布式计算机任务分配问题。为了将实数转化为正整数,把实数的符号和小数部

分去掉。结果表明该方法在解的质量和算法速度方面,要优于遗传算法。

4 动态优化

在许多实际工程问题中,优化的环境是不确定的,或者是动态的。因此,优化算法必须具备随环境动态变化而对最优解作出相应调整的能力,或者是算法具有一定的鲁棒性。文献[ 35 ]首次提出利用PSO跟踪动态系统文献[ 36 ]提出用自适应PSO来自动跟踪动态系统的变化,该方法通过对种群中最好微粒的检测和对微粒重新初始化, 有效增强了PSO对系统变化的跟踪能力文献[ 37 ]为了处理快速变化的动态环境,在微粒速度更新公式中增加了一项变化项,从而无需检测环境的变化就可以跟踪环境。尽管该方面的研究成果至今较少,但不容质疑这是一项重要的研究内容。

微粒群算法的MATLAB程序实现

初始化粒子群

DO

For每个粒子

计算其适应度

If (适应度优于粒子历史最佳值)

用Xi更新历史最佳个体Pi

End

选取当前粒子群中最佳粒子

If (当前最佳粒子优于群历史最佳粒子)

用当前群最佳粒子更新Pg

For每个粒子

按式①更新粒子速度

按式②更新粒子位置

End

While最大迭代数未达到或最小误差未达到。