Question

微粒群算法的改进方法

Answer 1

1 多目标优化
相对传统多目标优化方法, 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最大迭代数未达到或最小误差未达到。

Answer 2

本人是搞NOIP的，至今还没听说过什么“微粒算法”