交互式粒子群算法

交互式粒子群算法（精选11篇）

交互式粒子群算法 第1篇

关键词：部队卫生装备,巡修行程规划,交互式粒子群算法

0引言

卫生装备是部队卫生机构遂行卫勤保障任务的物质基础,加强卫生装备的维修保障,保持装备完好率,对于维护官兵健康,提升部队战斗力具有重要意义[1]。在全军联勤保障体系下,部队卫生装备的维修主要依靠总部所—军区所—区域性检修站三级检修机构完成,各级卫生机构定期将需要维修的装备上报,总部所将维修需求汇总,并按照保障范围进行任务分配,各检修机构根据分配的维修任务制订巡修计划,在规定的时间内完成维修并上报维修情况[2,3]。 维修机构在巡修时,由于保障范围广,维修地点多, 常常需要跨省市进行,如何根据维修任务制订最经济合理的巡修行程计划是巡修人员面临的难题[4]。鉴于此,本文首先将巡修行程规划转换为一类拓展的旅行商问题(travelling salesman problem,TSP)问题并利用交互式粒子群算法进行求解,以期为巡修人员制订一条在花费、舒适度等方面均尽可能满意的巡修计划,并在提高卫生装备巡修效率的同时降低巡修成本。

1行程规划分析

巡修行程规划与旅游行程规划问题类似,均属于旅行商问题的一个拓展[5],巡修人员要在规定时间内完成对多个维修需求点的维修保障,制订一条最合理的巡修行程,从巡修机构所在地出发,每个维修需求点访问一次,最后返回出发地点。行程的制订不仅要求交通费用、时间等可量化的指标最优,还要考虑舒适度、个人偏好、情感等主观因素,属于隐性目标决策问题,也是非决定性多项式完成(non-deterministic polynomial complete,NPC)问题[6]。

1.1基本概念定义

对某一检修机构,其保障范围内假设有n个维修需求点,需求点集合表示为DP={vi|i=1,2,…,n}。

(1)行程段。维修需求点vi与vj组成的序偶,可表示为(vi,vj),其中i≠j,表示vi到vj的行程,包括时间、路程等。

(2)行程T。维修需求点的排列,表示对维修需求点的巡修顺序。T=(0,vi1,vi2,…,vin,0),其中,0表示出发点,是集合的一个排列。

(3)单元属性。维修需求点的信息,如维修点的维修任务耗时、到达时间、离开时间等。

(4)双元属性。行程段上的信息,如两维修需求点之间的时间花费、距离等。

(5)行程属性。巡修行程的具体路线所展示的信息,如总的费用、时间花费等。

1.2行程规划模型建立

在某一检修机构的保障范围内,巡修人员需要制订一条经济合理的行程来完成对维修需求点的装备维修任务,即制订一条在费用、时间、舒适度等方面使巡修人员最满意的行程。

式中:T∈NM,NM为所有可能的行程集合;S为行程的满意度;G为行程需满足的限制条件。

满意度不仅包括可量化的指标,如行程的距离、 时间花费、费用花费等,还包括不能或难以量化的值,如巡修人员对到达需求点时间偏好等,因此满意度函数 φ 不能完全表示,无法通过解析方法得到最优行程。对于此类问题,常采用交互式智能算法(IEC) 求解,即借助人的智能信息处理能力给出解方案的适应度,使算法进一步搜索更好的解。采用交互式智能算法,让巡修人员人工地对行程进行评价,促使问题向巡修人员满意的方向收敛,通过智能体的进化, 实现主观情感空间向客观特征空间的映射,最终得到满意的行程。其中,巡修人员的评价值即为问题的适应度F(fitness),可表示为

F(T)=λA

式中:A(attribute)为行程T的属性集;λ 为巡修人员的心理偏好评价函数,是根据个人的知识、经验和偏好等对行程的主观评价。

2算法设计与实现

2.1标准粒子群算法

粒子群算法(particle swarm optimization,PSO) 是一种智能进化算法,从随机解出发,采用“群体”与 “进化”的概念,通过迭代寻找最优解并使用个体的适应值评价解的优劣[7]。该算法将每个鸟儿看作是D维搜索空间中一个没有质量和体积的粒子,在空间中只有一块食物,每只鸟儿(粒子)按一定速度在空间中移动,寻找这块食物,这块食物的位置即为最优解,每个粒子飞行时根据周围粒子和自身的位置调整速度的方向和大小直至寻找到最优解。设粒子的种群规模为m;粒子i的位置为zi=(zi1,zi2,…,zi D),根据要解决的问题设定适应度函数并计算zi当前的适应值;vi=(vi1,vi2,…,vi D)为粒子的飞行速度;pi=(pi1, pi2,…,pi D)为粒子i目前搜索到的最优位置;pg=(pg1, pg2,…,pg D)为整个粒子群目前搜索到的最优位置,粒子的位置和速度更新公式为

式中:i=1,2,…,m;d=1,2,…,D;k为迭代次数;r1和r2为[0,1]之间的随机数;c1为粒子跟踪自己历史最优值的权重系数,表示粒子自身的认识,称为“认知”, 通常设置为2;c2为粒子跟踪群体最优值的权重系数,表示粒子对整个群体知识的认识,称为“社会知识”,一般设置为2;ω 为惯性权重,衡量粒子的全局搜索能力与局部搜索能力。

2.2改进的粒子群算法

行程规划问题的解空间为离散空间,用PSO求解需对标准粒子群算法中粒子的位置、速度以及操作进行重新定义[8]。

2.2.1粒子的位置

行程规划问题的结果是得到具有最优大用户满意度的哈密尔顿圈,其状态空间即为所有行程的集合。粒子的位置可定义为一个包括所有维修需求点与出发点的哈密尔顿圈,即序列x=(n0,n1,…,nN, n0),其中ni∈E,E为状态空间,设所有ni与ni+1之间的路径存在。

2.2.2粒子的速度

2.2.3粒子位置、速度、实数间的操作

粒子位置与速度的加法操作表示将一组置换序列依次作用于某个粒子位置,从而得到一个新位置, 即新的行程排列。例如:位置为{l,5,2,4,3,l}+ {(2,4)}={1,5,4,2,3,1}。

粒子位置与位置相减后结果为一组置换序列, 即速度。粒子速度与速度的加法操作为2个置换序列的合并,结果为一个新的置换序列,即一个新的速度。

实数c为[0,1]的任意实数,设速度v为k个置换序列,则乘法操作为对速度的置换序列进行截取, 使得新的速度的置换序列长度为|c×k|(c×k取整)。

2.2.4公式更新

粒子的速度、位置及其各种操作重新定义后,离散粒子群算法的速度更新公式表示如下:

式中,c1、c2、r1、r2与标准PSO算法中定义相同;茌为两交换序列的合并算子,表示速度与速度的加法操作;“-”表示粒子位置与位置的减法操作;“+”表示粒子位置与速度的加法操作。

2.3算法描述及策略

2.3.1算法流程

图1给出了交互式粒子群算法的流程,其计算过程如下:

(1)设定算法有关参数,包括种群数量、最大迭代次数、惯性权重等;

(2)随机生成指定数量的粒子作为初始种群;

(3)巡修人员标记当代最优粒子,并据此产生适应度;

(4)满意度判断,若巡修人员对当代最优行程满意,则结束,否则,进行下一步;

(5)终止条件判断,若已到达最大迭代次数,则结束,否则,转(6);

(6)粒子群更新,根据速度与位置更新公式产生种群新的位置,转(3)。

2.3.2适应度策略

将行程T的属性A分为可量化与不可量化2个部分,其中可量化部分包括总距离、总花费(油耗、 住宿等)、总时间;不可量化评价部分包括到达时间、 离开时间等。虽然算法中粒子种群规模较小,但对每代个体进行评价易导致用户疲劳,若进一步减少种群规模的话,则会影响算法的收敛速度,为此,采用相对距离给定法[9]与可量化行程属性来计算适应度。 首先用户在每代种群中选出一个最满意的行程个体作为最优个体,并给予固定的适应度值F,则其他粒子的适应度FE按下式计算:

式中:RD为粒子与最优粒子之间路径的相对距离; AT为粒子的可量化属性。

对于行程T1与T2,其路径相对距离计算如下:

式中:L为个体的程度即维修需求点的数量;Ls为T1、T2最长相同子路径的程度;S为最长相同子路径的位移;C为归一化后行程的总花费;WT为总时间; α、β∈R,表示权重。

2.4仿真实验及分析

以某三级维修站某年度维修任务为研究实例,在保障区域内有A1~A15共计15个维修需求点,具体位置见表1。在巡修之前需对各点维修时间进行预判 (见表2)。假设汽车行驶的平均速度为70 km/h,人员住宿标准为100元/(人·d),燃油消耗为15 L/100 km, 汽油价格为7.6元/L,巡修人员每天的工作时间为10 h,巡修行程是从维修站所在地出发,依次完成全部维修需求点的维修任务之后返回驻地,两地间的距离采用公路距离。

注:所有地点均为模拟,不代表实际地点

h

具体行程安排时需满足以下原则:(1)人员的工作时间为8:00—18:00,可适当加班,但不超过1 h; (2)行车时间为8:00—22:00。

将粒子群算法中种群规模设置为20,初始惯性权重为0.96并随迭代次数增加而递减,最大迭代次数设为200,则权重分别为0.5、0.6;个体行程显示总路程、总花费、总时间及各点到达、离开时间等项目; 算法结束方式为达到最大迭代次数或用户手动结束2种。利用Matlab对算法进行实现,邀请巡修人员进行评价,最终计算得到最满意巡修行程如图2所示, 具体安排见表3。

h

最满意行程总路程为2 099 km,总的巡修时间为12 d,总的花费(油耗、住宿、过路费)为4 852元。 通过修改指标权重及行程要求还可制订不同偏好、 不同要求的行程方案,如时间较短、花费较少、加班较少等。

3讨论

基于量子粒子群算法求解整数规划 第2篇

基于量子粒子群算法求解整数规划

通过引入量子行为来增强粒子的全局收敛能力,提出了量子粒子群优化算法(QPSO),并用于求解整数规划问题.测试函数的`仿真结果表明,通过适当的参数设置,并将每次迭代所生成的实数值截至整数值后进行下一次迭代,可以保证QPSO算法求解的精度,提高收敛速度且能有效避免早熟.

作 者：刘静 须文波 孙俊 LIU Jing XU Wen-bo SUN Jun  作者单位：江南大学,信息工程学院,江苏,无锡,214036 刊 名：计算机应用研究  ISTIC PKU英文刊名：APPLICATION RESEARCH OF COMPUTERS 年，卷(期)： 24(3) 分类号：O22 关键词：粒子群算法   量子粒子群算法   整数规划  

改进的自适应多目标粒子群算法 第3篇

关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力

摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.

关键词：多目标优化；粒子群优化；帕累托最优；约束控制；边界处理；全局最优选择；自适应控制； 最大传输能力

摘要：边界处理和全局最优引导者选择操作对多目标粒子群算法的性能有重要影响，在考虑不同操作方法特征的基础上，提出了改进的自适应多目标粒子群（multiobjective particle swarm optimization， MOPSO）算法.当算法陷入局部最优时，启用交叉变异操作；当算法收敛性停滞时，轮换修剪边界处理和指数分布边界处理操作；当算法多样性停滞时，轮换反比于拥挤距离和反比于控制粒子数目的全局最优引导者概率选择操作.标准测试函数以及柔性交流输电系统（flexible AC transmission system， FACTS）装置优化配置问题的仿真结果验证了所提算法的有效性.

蚁群算法与粒子群算法的融合策略 第4篇

对社会性动物的自组织行为进行数学建模并用计算机进行仿真称为群智能算法, 其作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点。目前, 群智能理论研究领域主要有两种算法:蚁群算法 (Ant Colony Algorithm, ACO) 和粒子群算法 (Particle Swarm Algorithm, PSO) 。前者是蚁群觅食过程的模拟, 已成功应用于许多离散优化问题。后者是鸟群觅食过程的模拟, 是一种高效的并行搜索算法, 适应于连续领域的优化。本文在阐述两种算法的原理和模型基础上, 针对这两种算法的不足, 着重分析了两种算法的混合策略以提高算法性能。

1、蚁群算法

Colorni和Dorigo等于20世纪90年代对蚁群觅食行为的研究受启发提出了蚁群算法[1]。它基于对自然界真实蚁群的集体觅食行为的研究, 模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径, 通过在解路径上遗留并交换信息素提高解的质量, 进而达到优化的目的。蚁群算法首先成功应用于旅行商问题 (TSP问题) :设m为蚂蚁数目;n为城市数;dij为城市i和j的距离;τij (t) 为t时刻在路径 (i, j) 上的信息量。 (t) 为t时刻蚂蚁k由城市i转移到j的概率, 蚂蚁根据各路径上的信息量决定其移动方向。

其中, allowedk表示下一步允许选择的城市;tabuk表示已访问的城市。α和β表示启发式因子, ηij表示由城市i转移到j的期望程度。

每只蚂蚁走完一步或走完所有城市后, 信息素按下式更新:

其中, ρ表示信息素挥发系数, △τij (t) 表示信息素增加量, △τkij (t) 表示第k只蚂蚁在本循环中留在 (i, j) 上的信息量。

算法框架如图1中的伪代码所示。

由于蚁群算法本身具有的正反馈性、并行性、强收敛性以及鲁棒性, 已经在组合优化、车间作业调度、网络路由选择等领域已经取得成功的应用。但算法存在着: (1) 算法复杂, 计算量大, 求解时间长。 (2) 收敛速度慢, 易陷入局部最优。 (3) 初始信息素匮乏等等问题, 并且如何合理地设置参数或自适应地调整参数是提升算法性能的关键问题。

2、粒子群算法

Kennedy和Eberhart于1995年对鸟群觅食行为的研究受启发提出了粒子群算法[2]。PSO和遗传算法类似, 是一种基于迭代的优化算法, 算法初始化为一群随机粒子 (随机解) , 然后粒子们追随当前的最优粒子在解空间中探索, 通过迭代找到最优解。在每一次迭代中, 粒子通过跟踪个体极值 (本身所找到的最优解) 和全局极值 (整个种群目前找到的最优解) 来更新自己。

设搜索空间为D维, 粒子数为n, 第i个粒子位置表示为向量Xi= (xi1, xi2, …, xid, …, xiD) , 其历史最优位置为Pi= (pi1, pi2, …, piD) , Pg为所有Pi (i=1, …, n) 中的最优, 粒子i的飞行速度为Vi= (vi1, vi2, …viD) 。每个粒子的位置按公式 (1) 和 (2) 进行变化:

其中, c1和c2为加速因子, rand () 为[0, 1]间的随机数, ω为惯性因子。粒子群初始位置和速度随机产生, 然后按式 (1) 和 (2) 进行迭代, 直至找到最优解。

算法步骤:

(1) 初始化粒子群, 随机产生每个粒子的位置和速度;

(2) 计算每个粒子的适应度;

(3) 对每个粒子, 将其适应度值与pid比较, 如果较好, 则替换pid;

(4) 对每个粒子, 将其适应度值与pgd比较, 如果较好, 则替换pgd;

(5) 更新每个粒子的速度和位置;

(6) 如果满足约束条件 (误差足够好或达到最大循环次数) 退出, 否则返回 (2) 。

与其他进化算法相比, PSO保留了基于种群的全局搜索策略, 其特有的记忆可以动态地跟踪当前的搜索情况来调整下一步的搜索策略, 是一种更高效的并行搜索算法, 而且具有扩展性, 容易与其他算法结合, 适用于处理连续优化问题及多点搜索, 已成功应用于函数优化、多目标优化、动态优化等领域中。但存在着算法容易产生早熟收敛、局部寻优能力差以及反馈信息利用不充分等缺点。

3、两种算法的融合策略

(1) 针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点, 将粒子群算法引入到蚁群算法中, 让蚂蚁也具有粒子的特性。首先通过使用蚁群算法进行搜索, 然后用粒子群算法对蚁群算法得到的有效路径进行调整, 即将每只蚂蚁的当前路径分别与全局最优和个体最优交叉, 产生的路径为新的路径, 并将新路径以一定概率变异, 如果新路径的目标函数较优, 则接受新值;否则拒绝, 该蚂蚁的路径仍为交叉前路径。该融合策略使蚂蚁在每一次遍历中都充分利用局部最优解和全局最优解来调整路径, 以产生性能更优的下一代群体[3]。

(2) 针对蚁群算法初始信息素匮乏的缺点, 利用粒子群算法较强的全局搜索能力, 充分利用其随机性、快速度、全局性, 经过一定的迭代次数得到问题的次优解, 利用问题的次优解调整蚁群算法中的信息素的初始分布;再利用蚁群算法的正反馈机制, 充分利用其并行性、正反馈性、求解精度高等优点求问题的精确解, 从而提高时间效率和求解精度[4][5]。运算过程如下:

Step1:定义目标函数和适应值函数;

Step2:初始化粒子群;

Step3:计算机适应度;

Step4:更新个体最优和全局最优、每个粒子的位置和速度;

Step5:达到迭代次数, 生成若干组次优解, 否则回到Step3;

Step6:初始化蚁群参数, 根据次优解生成信息素初始分布;

Step7:计算每只蚂蚁的转移概率, 根据概率移动蚂蚁;

Step8:更新最优值及其对应位置、信息素;

Step9:达到迭代次数, 输入最优值, 否则转Step7;

(3) 蚁群算法中启发式因子α和β的选取一般都是通过经验来选取的, 选取不当影响算法的性能。可以利用粒子群算法对蚁群算法的α和β进行训:假设有n个粒子组成一个群落, 其中第i个粒子表示为一个二维的向量xi= (xi1, xi2) , i=1, 2, …, n, 即第i个粒子在搜索空间的中的位置是xi。换言之, 每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值, 根据适应值的大小衡量解的优劣。

4、结论

作为群智能算法的两种主要算法, 两者共同点是鲁棒性较强, 对基本算法模型稍加修改便可应用于其它问题, 并且极易与其它算法结合。蚁群算法和粒子群算法的融合不仅可以提高数据搜索的范围而且可以避免早熟, 吸取了两种算法的优点, 克服了各自的缺点。在时间效率上优于蚁群算法, 在求解精度上优于粒子群算法, 取长补短, 有效提高算法的时间性能和优化性能。

参考文献

[1].Kennedy J, Eberhart R., Particle Swarm Optimization[R].In:IEEE Inter-national Conference on Neural Networks, perth, Australia 1995:1942-1948.

[2].A.Colorni, M.Dorigo, V.Maniezzo.Distributed Optimization by AntColonies[C].In:The First European conference on Artificial Lift.France:Elsevier, 1991:134-142.

[3].高尚, 杨静宇.群智能算法及其应用[M], 北京, 中国水利水电出版社.2006:108-111.

[4].张长春, 苏昕, 易克初.粒子群算法和蚁群算法的结合及其在组合优化中的应用[J], 空间电子技术, 2007年第2期.

交互式粒子群算法 第5篇

摘要：针对标准支持向量机训练时间过长与参数选择无指导性问题，给出一种通过粒子群优化双支持向量机模型参数的方法。与标准支持向量机不同，该方法的时间复杂度更小，特别适合不均衡的数据样本分类问题，对求解大规模的数据分类问题有很大优势。将该算法与标准的支持向量机分类器在不同的文本数据集上进行仿真实验对比，以验证算法的有效性。结果表明基于粒子群优化的双子支持向量机分类器的分类结果高于标准支持向量机分类结果。

关键词：双子支持向量机(TWSVM);分类算法;粒子群优化算法(PSO)

DOIDOI：10.11907/rjdk.151455

中图分类号：TP312

基金项目：玉林师范学院校级科研项目(YJYB04)

作者简介作者简介：刘建明(1986-)，男，广西博白人，硕士，玉林师范学院数学与信息科学学院助教，研究方向为数据挖掘与机器学习。

0 引言

粒子群优化算法[1](Particle Swarm Optimization，PSO)是由美国研究学者Kennedy等人在1995年提出的，PSO算法每一代的种群中的解具有向“他人”学习和“自我”学习的优点，该算法能在较少的迭代次数中找到全局最优解，这一特性被广泛应用于神经网络方法、函数优化问题、数据挖掘、模式识别，工程计算等研究领域。

双子支持向量机(Twin Support Vector Machines， TWSVM)是Jayadeva[23] 基于传统支持向量机在提出来的。TWSVM是从SVM演化而来的，是一种新型的基于统计学习理论的机器学习算法。TWSVM具有SVM优点，同时适合处理像文本自动分类、基因表达、空间信息遥感数据、语音识别等这样的大规模数据分类问题。

针对TWSVM对惩罚参数和核函数参数缺乏指导性问题，本文结合PSO算法的优点，给出一种基于PSO的

算法优化改进策略，对TWSVM分类器进行优化。PSO是一种基于群体智能的全局寻优算法，该算法能在较少的迭代次数中找到全局最优解，通过利用粒子群优化算法对双子支持向量机进行优化后，分类器较之标准支持向量机有更好的分类效果。

1 PSO算法

PSO算法步骤：①初始化粒子群，利用随机函数法给每一个粒子的初始位置和速度赋值;②根据第①步的赋值及初始位置与速度更新每一个粒子新的位置;③利用选定的适应度函数计算每一个粒子的适应度值;④对每一个粒子，对比其个体和群体的适应度值，并找出粒子经过的最好位置的适应度值，如果发现更好的位置及适应度值，那么就更新其位置;⑤根据公式更新每个粒子的速度与位置，如果找到最优的位置或者是到了最大的迭代次数，算法终止，否则转入第3步继续迭代求解。

2 双子支持向量机(TWSVM)

与SVM不同，TWSVM求解的`是一对分类超平面，SVM求解一个QP问题而TWSVM解决的是两个QP问题，而这两个QP问题的求解规模比SVM小很多。传统SVM构造两个平行的超平面，并且使两个超平面之间的距离最大即最大间隔化，TWSVM虽然也是构造超平面，但超平面之间不需要平行。TWSVM对每一个样本都构造一个超平面，每个样本的超平面要最大限度地靠近该类的样本数据点，而同时尽可能地远离另一类样本数据点。新数据样本将会分配给离两个超平面中最近的一个平面。事实上，该算法还可以沿着非平行面聚集，而且样本聚集方式是根据完全不同的公式聚合而成的。实际上，在TWSVM中的两个QP问题与标准SVM的QP问题除了求解约束问题不同外，求解公式是相同的。TWSVM的二分类算法通过求解下面的一对QPP(Quadratic Program Problem)问题进行二次规划优化[5]。

3 基于PSO的TWSVM分类算法

在TWSVM中，与SVM相同，都需要对参数进行确定，TWSVM对每个类均有一个惩罚参数和核函数参数。不同的惩罚参数和核函数参数影响分类的准确率，而PSO算法拥有全局的优化能力，因此，本文将PSO算法引入TWSVM中，解决TWSVM参数的选择问题，PSOTWSVM算法不仅能提高TWSVM的准确率同时又能降低SVM的训练时间，提高训练效率。图2展示了应用PSO算法对TWSVM参数选择的优化流程。

传统SVM是基于二分类提出的，其复杂度为O(n3)，其中n为样本数目[2]。然而在TWSVM二分类算法中，设每类样本数据为n/2，因此，求解两个优化问题时间复杂度为：O(2*(n/2)3)，所以在二分类问题中的TWSVM时间复杂度为传统SVM的1/4。推广到多分类问题时，可以发现在时间复杂度方面，TWSVM求解优化问题的时间更少。例如样本类别数为k类，那么该样本的时间复杂度为O(k*(n/k)3)。由于TWSVM分类算法对每类都构造一个超平面，因此该算法在处理不平衡数据时，即一类的样本数目比另一类的样本大得多情况时，TWSVM分别实施不同的惩罚因子，TWSVM克服了传统的SVM处理不均衡样本的局限性，这一点非常适用于大规模的不均衡分类问题。 4 算法仿真实验

为验证基于PSO的TWSVM分类算法的有效性，本文利用该算法构建一个文本分类器，运用不同数据集在该分类器上进行实验并与标准支持向量机构建的分类器进行对比仿真实验。

4.1 分类器性能评价

常用的分类器评价方法包括：准确率和召回率。这两个指标广泛应用于文本分类系统的评价标准。准确率(Precision)是指全部分类文本中划分的类别与实际类别相同的文本数量占全部文本的比率。召回率(Recall)是指分类正确的文本数占应有文档数的比率。文本分类输出结果见表1。

4.2 实验结果分析

由表2可知，PSOTWSVM的分类性能比TWSVM要好。因此，基于PSO的TWSVM是一个有效算法。该算法不但比标准的SVM算法训练时间更短，而且比TWSVM有更好的准确率，PSOTWSVM解决了TWSVM的参数选择问题，提高了TWSVM的泛化性。

5 结语

通过基于PSO的TWSVM分类算法与TWSVM算法的分类对比实验可知，应用PSO算法的全局寻优能力提高了TWSVM分类的能力。PSO优化后TWSVM分类器的性能更为优越。基于PSO的TWSVM分类算法比标准的SVM时间复杂度更小，比TWSVM的准确率更高，基于PSO的TWSVM算法在分类问题上较之传统的SVM算法有更大的优越性。

参考文献：

[2]JAYADEVA，R KHEMCHANDAN， S CHANDRA.Twin support vector machines for pattern Classification[J]. IEEE Trans. Pattern and Machine Intelligence，，29(5)：905910.

[4]谷文成，柴宝仁，腾艳平. 基于粒子群优化算法的支持向量机研究[J].北京理工大学学报，2014， 34(7)：705 709.

[6]王振.基于非平行超平面支持向量机的分类问题研究[D].长春：吉林大学，2014.

粒子群优化算法综述 第6篇

通过对生物群体的观察和研究发现, 生物群体内个体间的合作与竞争等复杂性行为产生的群体智能,往往能为某些特定的问题提供高效的解决方法。

Kennedy等受鸟群觅食行为的启发,于1995年提出粒子群优化算法(Particle Swarm Optimization,PSO)[1]。与进化算法相比,PSO保留了基于种群的全局搜索策略,但其所采用的速度位移搜索模型操作简单,避免了复杂的进化操作。

PSO首先初始化为一群随机粒子(随机解),然后通过迭代搜索最优解。在每一次迭代中,粒子通过个体极值与全局极值更新自身的速度和位置:

vi=wvi+c1rand()(pi-xi)+c2rand()(g-xi) 。 (1)

xi=xi+vi 。 (2)

其中:vi是第i个粒子的速度;xi是第i个粒子的位置;w是惯性权重;pi是第i个粒子经历的最好位置;g是群体所有微粒经历的最好位置;rand()是均匀分布在(0,1)之间的随机数;c1和c2是学因子,通常c1=c2=2。

粒子就在解空间内不断跟踪个体极值与全局极值进行搜索,直到达到规定的最大迭代次数或达到最小的误差标准为止。图1为粒子群优化算法流程图。

2 PSO算法的改进

PSO算法在多维空间函数寻优、动态目标寻优等方面有着收敛速度快、解质量高、鲁棒性好等优点,特别适合于工程应用。而且比较简单,计算量小,实用性好,编程实现较更容易。PSO算法在搜索的初期收敛速度很快,但在后期却易于陷入局部最优。针对这个缺陷,众多学者提出了改进的办法。

2.1 自适应PSO

较大的惯性权值w有利于搜索时跳出局部极值点,而较小的w有利于算法收敛和提高搜索精度。在最初版本中w为常数,后来,文献[2]提出了w的自适应调整策略,刚开始时w较大,随着迭代的进行,w线性减小。文献[3]认为刚开始w=1.4,然后逐步减小到w=0.35比较合适。这种方法的进一步发展是模糊自适应PSO,它用自适应模糊惯性权值控制器来动态优化w。

2.2 带选择机制的PSO

基本的PSO没有选择机制,微粒个体不会被别的微粒个体所取代,迭代时,每个微粒不断地改变自己的位置直到搜索结束。

文献[4]提出一种带选择机制的PSO。这种算法依据某些预定的规则,将每个个体的适应值基于其当前位置,与其他个体进行比较,然后根据定义的规则将所有个体排序,得分最高的出现在群体的前面。一旦群体排序完毕,群体中当前得分低的一半被群体中当前得分高的另一半取代。带选择机制的PSO在解决单峰函数的优化问题时效果明显,但并不一定对所有的优化问题都很有效。这种算法由于有了选择机制,加快了对当前较好区域的开发过程,使得收敛速度较快,但也增加了陷入局部极值解的可能性。

2.3 带空间邻域的PSO

Angeline的研究表明,尽管PSO能比其他进化算法更快地得到较为理想的解,但当迭代次数增加时,并不一定能进行更精确的搜索。为此,可引入一个变化的邻域算子(neighborhood operator)。在迭代的初始阶段,一个微粒的邻域就是它本身;随着迭代的进行,根据候选个体与邻域中心的距离,逐步引入距离近的个体,邻域逐渐变大,包含越来越多的微粒,最后包含所有的微粒。这样,原来的全局历史最好位置搜索就变成了微粒邻域的局部历史最好位置搜索。文献[5]用更为详细的资料和许多测试函数的仿真结果表明这一方法能有效地获得全局最优解。

结合空间邻域和环状拓扑结构,文献[6]进一步提出了具有社会模式(social stereotyping)的聚类分析PSO。该法将微粒群体中的一些微粒作为中心,再将离它最近的N个微粒和中心微粒作为一簇,然后计算每个簇的中心位置,并用这些中心位置替代个体历史最优位置和全局历史最优位置。但文献[6]所示的研究结果并没表明这一方法具有更好的性能,结果难以令人满意,还有许多问题有待于进一步研究。

2.4 带变异算子的PSO

针对PSO算法存在易陷入局部最优点的缺点,文献[7]引入变异算子,与遗传算法类似,在子群的历史最优粒子位置连续无变化或变化极小时,若粒子群出现较严重聚集情况,则保留历史最优粒子位置,将粒子中少部分重新随机初始化,以此来增强全局搜索能力,克服收敛到局部最优点的缺点,同时又不降低收敛速度和搜索精度。

2.5 免疫PSO算法

免疫PSO算法是受生物系统免疫机制的启发,把免疫系统的免疫信息处理机制引入到PSO算法中[8]。此算法结合了PSO算法所具有的全局寻优能力和免疫系统的免疫信息处理机制,改善了PSO算法摆脱局部极值点的能力,提高了算法优化过程中的收敛速度和精度。

3 PSO算法的应用

当前,PSO算法已得到了广泛应用,最直接的应用或许就是多元函数的优化问题,包括带约束的优化问题。如果所讨论的函数受到严重的噪声干扰而呈现非常不规则的形状,同时所求的不一定是精确的最优值,而PSO算法能得到很好的应用。比如在半导体器件综合方面,需要在给定的搜索空间内根据所希望的器件特性来得到符合要求的设计参数,而所能利用的器件模拟器通常得到的特性空间是高度非线形的。有人用PSO替换GA进行了计算,发现PSO能比GA更快地找到较高质量的设计参数。

另外,还有一种更广泛的应用:简单而有效地演化人工神经网络,不仅用于演化网络的权重,而且包括优化神经网络的结构。作为一个演化神经网络的例子,PSO算法已经用于分析人的颤抖,包括帕金森(Parkinson)病和原发性颇抖,是一个非常具有挑战性的领域。PSO已成功地应用于演化一个用来快速和准确地辨别普通个体和有颤抖个体的神经网络。而网络的输入则为从一个活动变化记录系统中获得的归一化的移动振幅。另一个应用例子是使用PSO对一个电气设备的功率反馈和电压进行控制。这里采用一种二进制与实数混合的PSO算法来决定对连续和离散的控制变量的控制策略,以得到稳定的电压。

4 PSO算法研究展望

(1)应用领域的拓展:

虽然已被成功地用于函数优化及神经网络的训练等领域,但在更多领域的应用还处于研究阶段,可见报道不多。开拓新的应用领域,在应用的广度和深度上进行拓展都是很有价值的工作。

(2) 算法参数的确定:

PSO中的一些参数如c1、c2、w、微粒个数以及迭代次数等往往依赖于具体问题,依据应用经验,经多次测试来确定,并不具有通用性。因此,如何方便有效地选择算法参数,也是迫切需要研究的问题。

(3)算法的改进研究:

由于实际问题的多样性和复杂性,尽管已出现了许多改进的算法,但远不能满足需要。研究新的改进以便能更好地用于实际问题的求解也是很有意义的工作。就目前来看,将与其他技术相结合,根据不同的优化问题提出相应的改进算法是PSO当前的研究热点。

(4)算法的基础理论研究:

与相应的相对鲜明的社会特性基础相比,其数学基础显得相对薄弱,缺乏深刻且具有普遍意义的理论分析,不能对PSO的工作机理做出合理的数学解释。虽然PSO的有效性、收敛性等性能在一些实例和函数的仿真研究中得到验证,但没能在理论上进行严谨推敲和严格证明。因此,对PSO的基础理论研究非常重要。

摘要：首先介绍了PSO的原理及具体实现步骤;然后针对PSO算法在搜索的初期收敛速度很快,但在后期却易于陷入局部最优的缺点,提出了各种改进办法;最后介绍了PSO算法的应用领域以及研究展望。

关键词：粒子群算法,综述,优化

参考文献

[1]Kennedy J,Eberhart R C.Particle swarm optimization[G]//Proc of IEEE Int Conf on Neural Networks.NewYork:IEEE,1995:1942-1948.

[2]Shi Y,Eberhart R C.A modified particle swarm[G]//Proceeding of IEEE International Conference onEvolutionary Computaion.New York:IEEE,1998:69-73.

[3]Eberhart R C,Shi Y.Particle swarm optimizationdevelopments,applications and resources[G]//Proceedings of the 2001 Congress on EvolutionaryComputation.Piscataway:IEEE,2001:81-86.

[4]Aneline P J.Using selection to improve particle swarmoptimization[G]//Proceeding of the InternationalConference on Evolutionary Computation.New York:IEEE,1998:84-89.

[5]Suganthan P N.Particle swarm optimizer withneighborhood operator[G]//Proceeding of the 1999Congress on Evolutionary Computation.New York:IEEE,1998:1958-1962.

[6]Kenndy J.Stereotyping improving particle swarmperformance with clusteranlysis[G]//Proceeding of the2000 Conference on Evolutionary Computation.Piscataway:IEEE,2000:1507-1512.

[7]Bergh F van den.An analysis of particle swarmoptimizers[D].South Africa:University of Pretoria,2002:1341-1344.

粒子群优化算法简介 第7篇

由于认识到PSO在函数优化等领域所蕴涵的广阔的应用前景，目前已提出了多种PSO改进算法，并且广泛应用于函数优化，神经网络训练，模式分类等应用领域。本文将介绍基本PSO算法以及几种典型的改进算法。

1 粒子群算法

PSO是群智算法中的一种，PSO中，每个优化问题的解都是搜索空间中一个“粒子”的状态。所有的粒子都有一个适应函数(fitness function)决定的适应值(fitness value)，每个粒子还有一个速度直接影响它们飞翔的距离。粒子根据当前自身情况和粒子群的情况在解空间中搜索。PSO初始化时，将一群粒子的状态赋随机值(随机解)，然后根据公式(1)和(2)来更新自己的速度和新的位置。

其中vid是粒子的速度，c1,c2是学习因子，Rand()是介于(0,1)之间的随机数，xid是粒子当前位置，pid是粒子当前极值，pgd是粒子群当前极值，在公式(1)，等式右边共有三项，第一项是粒子上一次的速度vid与惯性因子w的乘积，惯性因子即是粒子上一次的速度对本次飞行速度的影响因子，Shi[1]研究了惯性因子w对优化性能的影响，发现较大的w值有利于跳出局部极小点，而较小的w值有利于算法收敛;第二项是粒子自身行为差异比较;第三项是粒子群体行为差异比较;后两项合称为粒子的“意识”部分。

图1是PSO迭代曲线示例，其实验参数分别为：粒子个数是20;w=0.9;维度为10;适应函数为;粒子群最佳适应值变化曲线为左下方的红色虚线;平均适应值变化曲线为右边的蓝色实线;迭代次数为400。从图1中可以看出粒子群最佳适应值在不断减小，平均适应值有起有落表明在不断快速跳出局部极小值最终到达全局极小值。

2 邻域粒子群优化算法

粒子群算法中的每个粒子的每一次迭代，速度的更新由三个因素决定即在(1)中等式右边的三项：粒子上一次的速度vid与惯性因子w的乘积，粒子自身的认知部分，粒子群体意识部分。由于视野和视力范围的限制，实际觅食鸟群中的个体并不一定拥有全局“意识”而是观察周围飞鸟的位置和速度情况。在全局模式中，每个粒子的轨迹受例子群中所有粒子的所有的经验和意识的影响。在局部模式中，粒子的轨迹只受自身的认知和最邻近的粒子状况的影响。观察实际的飞鸟觅食过程，往往只是看到相邻的飞鸟的位置和动向，就这一点而言，局部模式更接近粒子群算法的生态本质。

3 混沌粒子群算法

3.1 混沌理论

1972年12月29日，美国麻省理工学院教授、混沌学开创人之一E.N.洛伦兹[1]在美国科学发展学会上提出一个貌似荒谬的论断：在巴西一只蝴蝶翅膀的拍打能在美国得克萨斯州产生一个陆龙卷，并由此提出了天气的不可准确预报性。混沌是一种普遍的非线性现象，其行为复杂且类似随机，但存在精致的内在规律性。混沌具有其独特的性质：随机性、遍历性、规律性。

3.2 混沌粒子群算法

针对粒子群算法中存在粒子的位置和速度初始赋值具有随机性，不宜有遍历性的弱点，产生了混沌粒子群优化算法，该算法利用混沌确定性与随机性的统一、对初始值敏感性和混沌的遍历性特点，引导粒子群中的粒子搜索。混沌PSO基本思想就是用类似载波的方法将混沌状态引入到优化变量(在粒子群算法中用粒子的维度表示)中，并把混沌运动的遍历范围由[0,1]区间“放大”到优化变量的取值范围，然后利用混沌变量进行搜索，具体表现在群体的混沌初始化和最优个体的混沌变尺度载波。

4 结论

本文介绍了基本PSO算法以及两种典型的改进算法，基于这两种方法，可以有效避免粒子搜索过程中容易发生的早熟，甚至是停滞，提高了粒子的搜索效率，改善了粒子群优化的性能。

参考文献

[1]R.C.Eberhart,Y.Shi.Comparison between genetic algorithms and particle swarm optimization[M].Proceedings of7th annual confer-ence on evolutionary computation,1998,611-616.

[2]J.Kennedy,R.Eberhart.Swarm Intelligence.Morgan Kaufmann Publishers[J].Inc,San Francisco,CA,2001.

[3]R.C.Eberhart,Y.Shi.Comparison between genetic algorithms and particle swarm optimization.Proceedings of7th annual conference on evolutionary computation,1998:611-616.

[4]V.Ferrari,T.Tuytelaars,and L.Van Gool.Markerless Augmented Reality with a Real-Time Affine Region Tracker[J]Proc.IEEE and ACM Int'l Symp.Augmented Reality,pp.87-96,2001.

[5]E.S.Peer,F.van den Bergh,A.P.Engelbrecht,Using Neighborhoods with the guaranteed Convergence PSO[J].Proceed of IEEE con-ference on Evolutionary Computation,2003,235-2.

双群替代自适应粒子群优化算法 第8篇

关键词：微粒群优化算法,双群替代的自适应权重粒子群优化算法,适应度值变化率

粒子群算法是一种基于群体迭代，群体在解空间中追随最优粒子进行搜索的算法，该算法简单方便，在运行的初始阶段收敛速度很快，运动轨迹呈正弦波摆动，但是达到一定程度就开始减慢甚至停滞，甚至出现早熟，无法达到最优值，为解决此问题，本文提出一种新的粒子群优化算法(TSAPSO)，在一定程度上增加了种群的多样性，提高了计算的精度，使用matlab软件应用该算法对4种常用函数进行测试证明该算法与基本的粒子群算法(PSO)相比具有一定的优势。

1 基本粒子群算法(PSO)

PSO算法首先初始化一群随机粒子，然后粒子们就追随当前的最优粒子在解空间中搜索，即通过迭代找到最优解。假设d维搜索空间中的第i个粒子的位置和速度分别为Xi(xi,1,xi,2xi,d)和Vi=(vi,1,vi,2vi,d),在每一次迭代中，粒子通过跟踪两个最优解来更新自己，第一个就是粒子本身所找到的最优解，即个体极值Pi=(pi,1pi,2pid);另一种是整个种群目前找到的最优解，即全局最优解Pg=(pg,1pg,2pg,d)。在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置。

vi,j(t+1)=wvi,j(t)+c1r1[pi,j-xi,j(t)]+c2r2[pg,j-xi,j(t)]

xi,j(t+1)=xi,j(t)+vi,j(t+1),j=1,2,,d

其中w为惯性权因子，c1和c2为正的学习因子，r1和r2为0到1之间均匀分布的随机数。

粒子群优化算法的流程如下:

第1步:随机初始化种群中各微粒的位置和速度(粒子数目为N)。

第2步:评价每个粒子的适应度,将当前各微粒的位置和适应度值存储在各微粒的Pi中，将所有Pi中适应值最优个体的位置和适应值存储于Pg中

第3步：根据粒子群速度和位置更新方程来调整粒子的速度和位置;

第4步:对每个微粒，将其适应值与其经历过的最好位置作比较，如果较好，则将其作为当前的最好位置。

第5步：比较当前所有Pi和Pg，更新Pg。

第6步：检查终止条件(通常为达到最大迭代次数或者足够好的适应度值最优解停滞不再变化)。若上述条件满足,终止迭代;否则返回第3步。

2 双群替代的自适应权重粒子群优化算法（TSAPSO)

2.1 自适应权重法

粒子群算法中惯性权重因子w对粒子群算法的收敛性起到很大的作用，w值越大，则速度v就越大，有利于粒子搜索更大的空间，可能发现新的解域，全局寻优能力越强，局部寻优能力越弱，反之，w越小，则速度越小，有利于在当前解空间里挖掘更好的解，局部寻优能力越强，全局寻优能力越弱。因此有必要通过调整w的大小来控制以前速度对当前速度的影响，使其成为兼具当前搜索与局部搜索的一个折中，为了平衡标准PSO算法的全局搜索能力和局部改良能力，可采用非线性的动态惯性权重系数公式取代标准粒子群算法中固定不变的参数值，其表达式如下：

其中wmax,wmin分别表示w的最大值和最小值，f表示粒子当前的目标函数值，favg和fmin分别表示当前所有粒子平均目标值和最小目标值。在上式中，惯性权重随着粒子的目标函数值而自动改变，因此称为自适应权重。当各粒子的目标值趋于一致或者趋于局部最优时，将使惯性权重增加，而各粒子的目标值比较分散时，将使惯性权重减少，同时对于目标函数值优于平均目标值的粒子，其对应的惯性权重因子较小，从而保护了粒子，反之对于目标函数值差于平均目标值的粒子，其对应的惯性权重因子较大，使得该粒子向较好的搜索区靠拢。

2.2 双群替代法

标准PSO算法是根据全体粒子和自身的搜索经验向着最优解飞行，在进化过程中，特别是在进化后期，由于粒子多样性不足而易使粒子收敛速度明显变慢，同时算法搜索到一定精度时，算法无法继续优化，因此算法所能达到的精度差。为解决这个问题，把原有的一个粒子群再分，分为两个粒子群，主群和分群，两个粒子群分别按照基本PSO算法搜索寻优，每完成一次迭代，计算主群粒子适应度值的变化率(K)，计算适应度值的变化率公式如下所示：

其中Pg(n)为整个种群第n次迭代所计算出来的全局最优解。

如果变化率较低，低于给定的值，则说明主群早熟，如果主群早熟，主群和分群中的粒子按照适应度值从低到高的进行排序，将分群中位于前面的若干个适应度值较低的粒子取代主群中位于后面的适应度值较高的粒子，取代粒子的个数随机产生，由0到1之间的随机数乘以分群粒子个数决定。这样在整个搜索过程中优势微粒不断的补充进来而劣势微粒不断的淘汰出去，使得微粒群始终保持在搜索状态，从而保证了最终的搜索精度。

2.3 TSAPSO算法流程

第1步:初始化两个粒子群(主群N个粒子，分群M个粒子)中各微粒的位置和速度。

第2步:分别评价两群中每个粒子的适应度值,将当前各微粒的位置和适应度值存储在各微粒的Pi中，将所有Pi中适应值最优个体的位置和适应度值存储于Pg中

第3步:根据粒子群速度和位置更新方程来调整主群和分群中粒子的速度和位置;

第4步:分别在主群和分群中，对每个微粒，将其适应值与其经历过的最好位置作比较，如果较好，则将其作为当前的最好位置。

第5步：分别在主群和分群中，比较当前所有Pi和Pg，更新Pg。

第6步：计算主群的适应度值变化率，如果低于所设定的值，则进入第7步，否则进入第8步。

第7步：将主群分群粒子按照适应度值由低到高分别进行排序，在分群中选取适应度值较低的前rand*M个粒子取代主群中适应度较高的后rand*M个粒子。

第8步:检查主群是否满足终止条件(通常为达到最大迭代次数或者足够好的适应值最优解停滞不再变化)。若上述条件满足,终止迭代;否则返回第3步。

3 实验

本文使用matlab软件分别采用PSO和TSAPSO算法在4个测试函数(f1,f2,f3,f4)上进行寻优测试实验，其中问题的维数用D表示，迭代的次数用T表示，其他参数表示如前所示。

函数f1:

此函数最小值为0，最佳位置为(0,0,0，0);

微粒群参数设置如表1所示。

函数f2:

此函数最小值为0,

最佳位置为(0,0,0，0);

微粒群参数设置如表2所示。

函数f3:

此函数最小值为0,

最佳位置为(0,0,0，0);

微粒群参数设置如表3所示。

函数f4:

此函数最小值为0,

最佳位置为(0,0,0，0);

微粒群参数设置如表4所示。

4 结果及分析

图1～图4所示曲线图分别为在函数f1～f4上分别采用PSO和TSAPSO算法所得到的迭代曲线图，图中的实线是标准PSO算法适应度值变化图，虚线是TSAPSO算法适应度值变化图，图中横坐标T为迭代次数，纵坐标fitness(pg)为适应度值。

结果分析：

1)从图1～图4可以看出TSAPSO算法对所有的测试函数性能都优于基本的PSO算法，获得更低更好的适应度值。

2)f2为多峰函数，在S={x1[-5.12,5.12]i=1,2,,n}范围内大约有10n个局部机小点，从图2可以看出TSAPSO算法比标准的PSO算法更容易逃脱局部最小值，获得最优的结果。

3)对函数f3,TSAPSO算法虽然比基本的PSO算法精度高，但距离实际最优值还有一定的差距，这是由于TSAPSO算法中，在种群混合替代后，基本PSO算法中的粒子也被拉入局部最优，如果此时粒子在多个局部最优点聚集，很可能适应度变化率不低于已设参数，粒子种群的多样性无法保证，得不到最优解。

4)从图1～图4可以看出TSAPSO算法速度和基本的PSO算法相比针对不同的测试函数有快有慢，这主要是不同的测试函数具有不同的测试极小点和各异的障碍物以及算法不同的寻优结构所造成的。

5 结束语

粒子群优化算法采用实数求解，需要调整的参数较少，易与实现，在神经网络的训练，函数优化和模糊逻辑系统控制等领域有着广泛的应用。本文提出的TSAPSO算法与基本PSO算法相比在精度上有了一定程度的提高，采用此算法训练神经网络，在事故检测方面得到较好的应用，具有一定的实用价值。

参考文献

[1]纪震,廖惠连,吴青华.粒子群算法及应用[M].北京:科学出版社,2009:16-18.

[2]Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proc.Of IEEE International Conference on Neural Networks.Piscataway:IEEEService Center,1995:1942-1948.

[3]吴启迪,江镭.智能微粒群算法研究及应用[M].南京:江苏教育出版社,2005:15-16.

[4]王丽,王晓凯.一种非线性改变惯性权重的粒子群优化算法[J].计算机工程与应用,2007,43(4):47-48.

[5]王启付,王占江,王书亭.一种动态改变惯性权重的粒子群优化算法[J].中国机械工程,2005,16(11):945-948.

[6]段晓东,高红橄,张学东,等.粒子群算法种群结构与种群多样性的关系研究[J].计算机科学,2007,34(11):164-166.

[7]龚纯,王正林.精通MATLAB最优化计算[M].北京:电子工业出版社,2009:270-271

非线性粒子群算法 第9篇

粒子群算法也称为微粒群算法,是一种简单实用的智能计算方法,在许多领域有着广泛的应用。为了提高算法效率本文提出了一种新型的粒子群算法,非线性粒子群算法。该算法在计算粒子速度时采用了非线性计算公式。仿真计算表明,与标准粒子群算法相比,只要选择了适当的非线性项,非线性粒子群算法收敛速度更快。

1标准粒子群算法

粒子群算法(PSO)是一种模拟鸟群飞行的人工智能算法。在粒子群算法中,每个个体被称为粒子。通过粒子之间的集体协作运动来实现群体最优的人工智能算法。虽然每个粒子的行为准则很简单,但是整体的行为却是非常复杂。在一个具体的空间中,每个粒子均按照全局以及个体的最优值调整自己的速度,通过反复调整使得整体向着最优值靠近。每个粒子包含以下参数:当前位置,历史最优位置,粒子当前速度,当前适应值,历史最优适应值。

设有n个粒子,搜索空间为D维空间,则每个粒子按照以下公式调整自己的速度和位置:

v${}_{\text{i}\text{j}}^{\text{k}+1}$= wv${}_{\text{i}\text{j}}^{\text{k}}$+c1r1(pj-x${}_{\text{i}\text{j}}^{\text{k}}$) +c2r2(qj-x${}_{\text{i}\text{j}}^{\text{k}}$) (1)

x${}_{\text{i}\text{j}}^{\text{k}+1}$= x${}_{\text{i}\text{j}}^{\text{k}}$+ v${}_{\text{i}\text{j}}^{\text{k}+1}$ (2)

其中x${}_{\text{i}\text{j}}^{\text{k}}$表示第i个粒子第k次调整后的第j维位置分量,v${}_{\text{i}\text{j}}^{\text{k}}$表示第i个粒子第k次调整后的第j维速度分量,w表示权重,c1、c2分别是粒子的学习因子,r1、r2表示[0,1]之间的随机数,pj、qj分别表示局部的和全局的最优值分量。

粒子群算法的实际计算步骤如下:第一步:初始化速度和位置,对每个粒子的速度和位置初始化;

第二步:计算每个粒子的适应值;

第三步:计算每个粒子自身的最优值;

第四步:计算整个粒子群的最优值;

第五步:更新每个粒子的速度和位置;

第六步:判断是否满足结束条件(例如最大迭代次数或者找到理想的适应值),是则计算结束,否则转向第二步。

粒子的适应值根据事先设定的适应值函数进行计算,用于描述粒子位置的优劣,而适应值函数与要解决的具体问题有关。在计算函数的最值时,适应值就是粒子在具体坐标点的函数值。

2非线性粒子群算法

标准的粒子群算法采用线性函数调整粒子的速度和位置,为了提高算法效能,本文提出了非线性粒子群算法。非线性粒子群算法就是采用非线性计算公式来代替公式(1)。非线性粒子群算法的公式一般形式如下

v${}_{\text{i}\text{j}}^{\text{k}+1}$= wv${}_{\text{i}\text{j}}^{\text{k}}$+c1r1fij(pj-x${}_{\text{i}\text{j}}^{\text{k}}$) +c2r2 gij (qj-x${}_{\text{i}\text{j}}^{\text{k}}$) (3)

x${}_{\text{i}\text{j}}^{\text{k}+1}$= x${}_{\text{i}\text{j}}^{\text{k}}$+ v${}_{\text{i}\text{j}}^{\text{k}+1}$ (4)

如果至少有一个fij(pj-x${}_{\text{i}\text{j}}^{\text{k}}$)或者至少有一个gij(pj-x${}_{\text{i}\text{j}}^{\text{k}}$)是非线性函数,称相应的粒子群算法为非线性粒子群算法。非线性粒子群算法的计算步骤跟标准粒子群算法一致。

非线性粒子群算法具有以下特点:

(1)整个群体至少存在一个非线性计算公式;

(2)对于每个粒子以及粒子的速度分量,公式(3)可以彼此不同,这样每个粒子的速度调整公式也可以彼此不同。

最直观的非线性粒子群算法为

v${}_{\text{i}\text{j}}^{\text{k}+1}$= wv${}_{\text{i}\text{j}}^{\text{k}}$+c1r1(pj-x${}_{\text{i}\text{j}}^{\text{k}}$)a +c2r2(qj-x${}_{\text{i}\text{j}}^{\text{k}}$)b (5)

x${}_{\text{i}\text{j}}^{\text{k}+1}$= x${}_{\text{i}\text{j}}^{\text{k}}$+ v${}_{\text{i}\text{j}}^{\text{k}+1}$ (6)

公式(5)中a、b至少有一个不等于1。显然公式(1)是公式(5)的特殊形式。在公式(5)中每个粒子的速度分量按照同样的非线性函数进行调整。

采用公式(5)进行计算需要注意非线性项的情况,由于a、b至少有一个不等于1,因此在实际编程中需要注意可能出现负数开偶数次方根号的情况,需要根据具体情况采用不同的计算公式。

3数值计算仿真

本文对非线性粒子群算法给出仿真实验。以下按照公式(5)、(6)对应的非线性粒子群算法给出仿真实验。在下面的例子中用N表示粒子数,w表示权重表达式,M表示最大迭代次数,c1、c2表示学习因子,xmin、xmax分别表示求解范围的下限和上限,即xminxixmax。

例1:求解下列线性方程组:

$\{\begin{array}{l}\text{x}{}_1+2\text{x}{}_2-2\text{x}{}_3+\text{x}{}_4=5\\ \text{x}{}_1+\text{x}{}_2+\text{x}{}_3-\text{x}{}_4=1\\ 2\text{x}{}_1+2\text{x}{}_2+\text{x}{}_3-2\text{x}{}_4=3\\ \text{x}{}_1-\text{x}{}_2-\text{x}{}_3+\text{x}{}_4=1\end{array}$

本例的精确解为:x1=1,x2=1,x3=-1,x4=0。采用标准的粒子群算法以及非线性粒子群算法求解方程组其中的参数为

M=500,c1=1.8,c2=1.8 ,xmin=-2,xmax=2,N=100,w=0.5-0.1k/499。计算结果如表1～表3所示。

从上面的计算结果可以看出,非线性粒子群算法的收敛速度快于标准粒子群算法.

例2:求解下列Beale函数

f(x,y)=(1.5-x+xy)2+(2.25-x+xy2)2+(2.625-x+xy3)2

在-4.5x,y4.5上的最小值。

本例存在最小值为minf(x,y)=f(3,0.5)=0。

以下采用标准粒子群算法和非线性粒子群算法求解例2,其中的参数为

M=500,c1=1.8,c2=1.8 xmin=-4.5 xmax=4.5.w=0.5-0.1k/499,N=20。

计算结果见表5-表8。

从上面的计算结果看出,非线性粒子群算法的平均迭代次数小于标准粒子群算法。

采用(5)、(6)给出的非线性粒子群算法进行计算,需要注意a、b的选择,如果a、b选择不当,可能会出现收敛缓慢甚至不收敛的情况发生。按照本文的作者的初步研究,当a=b时,a、b的值不能离1太远,否则便不能做到快速收敛。

4结束语

非线性粒子群算法是一种新的粒子群方法,从仿真实验的情况看只要选择适当的非线性项,就能做到快速收敛。关于非线性粒子群算法需要研究的内容很多,例如如何选择非线性函数,非线性项函数中参数如何选择,参数的选择与粒子群大小的关系等等。关于这方面的内容值得深入研究。

摘要：提出了一种新型的粒子群算法—非线性粒子群算法,给出了计算公式并进行了实验模拟。非线性粒子群算法采用非线性计算公式调整粒子速度。由于非线性计算公式的多样性,因此可以构建种类繁多的具体的非线性粒子群算法。非线性粒子群算法一方面保持了标准粒子群算法的简单性,同时也具有更强的搜索能力。实际计算表明,只要能够选好非线性项中的参数,就可以提高算法的效率。

关键词：标准粒子群算法,非线性粒子群算法,线性方程组,Beale函数

参考文献

[1].纪震,廖惠联,吴清华.粒子群算法及其应用.北京:科学出版社,2009.

[2].段晓东,王存睿,刘向东.粒子群算法及其应用.沈阳:辽宁大学出版社,2007.

交互式粒子群算法 第10篇

关键词：雷达目标跟踪；制导信息估计；粒子滤波；RBPF算法；交互多模型

中图分类号：TP273 文献标识码：A 文章编号：1673-5048（2014）04-0003-05

0 引 言

在雷达信号处理领域，运动目标跟踪问题一直是长期以来的难点所在，实践证明在线性高斯系统中利用最小均方根误差准则进行目标状态估计的Kalman滤波方法[1]是最优的估计方法，但针对非线性非高斯系统，尽管采用基于局部线性化近似的扩展Kalman滤波（ExtendKF，EKF）[2]以及基于确定性采样的Unscented卡尔曼滤波（UnscentedKF，UKF）[3]方法可以解决一定形式的弱非线性、弱高斯条件下的目标跟踪问题，但由于其对系统模型的限制过强，在实际应用中大多无法满足。20世纪90年代出现了以粒子滤波（Particlefilter，PF）[4]为代表的非线性滤波方法，即利用蒙特卡罗采样得到的随机样本（也称为粒子）的加权和来近似状态的整个后验概率密度，其本质是采用蒙特卡罗仿真来获得高维积分的近似数值解，并解决各种估计问题。

粒子滤波面临的两个最大问题：一是粒子退化问题，即经过若干次迭代后，重要性权值可能集中到少数粒子上，这些粒子已经不能有效表达后验概率密度函数，为解决此问题，Gordon[5]等人提出了重采样方法，其思想是减少权值较小的粒子数，增加权值较大的粒子数。另一个问题是采用粒子数目过多导致计算的复杂度增加，当前的解决方法主要是从系统模型出发，利用模型自身的特性来提高滤波器性能。RaoBlackwellized方法[6]即将线性状态从系统中分离出来，利用Kalman滤波器对线性状态进行估计，利用粒子滤波（PF）对剩余的非线性状态进行估计，然后利用贝叶斯定理求取状态的后验概率。由于RBPF降低了粒子滤波状态的维数，与使用相同粒子数的传统PF算法相比，可以获得更优的性能。

当前的RaoBlackwellized粒子滤波（RBPF）中采用单一系统模型作为其中近似线性状态的估计，在跟踪机动目标时与真实飞行轨迹存在偏差。为解决此类问题，本文采用交互多模型的方法来获得状态的重要性分布，从而实现粒子状态的估计，并以仅有角度信息的雷达双目标跟踪问题为例，对改进的算法进行验证。

1 RaoBlackwellized粒子滤波算法

1.1 粒子滤波算法原理

解决目标跟踪问题的最优方法是贝叶斯滤波方法，它通过两个步骤来实现：状态预测和状态更新。贝叶斯滤波的实质是通过获得目标的后验概率密度，根据某些准则（如最大后验估计）近似地计算出目标状态值。定义系统模型如下：

其中：xk为目标在k时刻的状态，如目标的位置、速度、加速度等信息；yk为k时刻的测量值，如目标的位置、弹目距离、目标与传感器的相对角度等；p（xk|xk-1）为目标的动态模型，表征目标状态的动态变化情况；p（yk|xk）为系统的测量模型，表征目标在干扰情况下的测量变化情况。最优滤波的目的就是为了在已知观测信息的前提下获得目标的后验概率。

利用ChapmanKolmogoroff公式可得目标的后验概率密度为

上式从理论意义上提供了最优滤波问题的解决方法，但在非线性系统求解过程中无穷维积分的运算极为困难，无法得到其精确最优解。1.2 RaoBlackwellized粒子滤波算法流程

在RaoBlackwellized粒子滤波算法中，引入任意潜在变量λ，系统的动态模型和测量模型分别变为p（xk|xk-1，λk-1）和p（yk|xk，λk），已知重要性分布为π（λk|λ（i）1∶k-1，y1∶k），对当前粒子群{ω（i）k，λ（i）k，m（i）k，P（i）k：i=1，2，…，N}进行处理，其中m为均值，P为协方差，ω为粒子权重，N为粒子数。在k时刻，Rao-Blackwellized粒子滤波算法的流程如下：

（1）对粒子均值m和协方差P作卡尔曼滤波预测

k，P（i）k） （8）

利用RBPF算法可将多目标跟踪问题分为两个部分：多目标数据关联中后验概率分布的估计和基于数据关联单个目标跟踪的估计。可以分别通过序列重要性采样及Kalman滤波进行最小均方误差估计来解决，将跟踪过程简化为目标判别，即判别当前得到的测量值是目标还是杂波，并在此基础上对目标进行跟踪。

通过设定数据关联指标ck，当ck=j时表示当前测量值对应第j个目标，当ck=0时表示当前测量值经判别为杂波。

为使用RBPF滤波算法，必须首先确定一个重要性分布用以计算不同时刻k各个粒子的权值，即确定分布π（ck|y1∶k，c（i）1∶k-1），利用贝叶斯公式可以方便求取概率密度p（ck|y1∶k，c（i）1∶k-1），因此RBPF算法默认将p（ck|y1∶k，c（i）1∶k-1）作为最优的重要性分布π（ck|y1∶k，c（i）1∶k-1）来计算。 2 采用内部多模型的RBPF算法改进

当前RBPF中对数据关联后线性部分的处理一般采用EKF或UKF算法进行，但EKF或UKF算法多是针对于单一模型进行的，当系统状态在不同模型间发生变化时（如目标在平飞和机动间切换），利用RBPF算法中的线性部分采样单一的模型进行预测和校正往往会带来较大误差，为此对原始的RBPF算法进行改进，采样交互多模型的方法来进行辨识，判断目标当前是处于机动状态还是非机动状态，进而采取不同的模型来代入运算，具体过程如下：

（1）建立采用连续Wiener过程加速度模型（CWPA），系统状态为

Xk=（xk yk x·k y·k x¨k y¨k）T（11）

动力学模型为

（15）

其中：v（t）～N（0，σ2w）。此系统模型虽为非线性，但可采用EKF或UKF求解。

（3）对于每个粒子，分别采用两种模型对RBPF算法的线性部分进行预测及校正，求取其均值和方差，然后利用其每步的信息及误差方差的统计特性求取其对于每个模型的概率密度，即权重。

μik=f（vik，Sik） （16）

其中：μik为粒子权重；vik为测量信息；Sik为误差方差的统计特性。

（4）按照权重比例对计算的粒子均值及方差进行加权，作为下一次计算的初值，以此类推，可求取不同时刻的粒子状态。

mk=∑2

下面针对此问题分别采用线性Kalman滤波及RBPF粒子滤波来仿真，采用粒子数目为10。

图1所示为采用Kalman滤波的估计结果，可以看出，采用Kalman滤波得到的目标运动轨迹输出完全不能够跟踪上目标的真实运动轨迹，这是因为目标的观测模型中不只存在高斯噪声，而且在整个视场内存在均匀散布的杂波测量值，这样导致Kalman滤波算法很快失效。由图2～3可以看出，采用粒子滤波可以将真实目标轨迹与噪声

3.2 双目标跟踪的数字仿真实现

下面对仅有方位角测量信息的雷达双目标跟踪问题进行仿真验证，图5为雷达测量的示意图，此时目标的动态方程与上例中相同，但测量模型不同，此时测量量为角度值，使用两个固定位置的传感器对于两个目标进行测量，测量方程如下：

θik=arctan（yj，k-siy

xj，k-six）+rik（22）

其中：xj，k，yj，k为目标j的位置；six，siy为第i个传感器的位置；rik～N（0，σ2）为测量噪声，此时测量方程为非线性形式，因此需采用EKF或UKF配合使用RBPF算法。

图6为雷达的角度测量值随时间的变化情况，

从图中可以看出，针对两个传感器及两个目标可测量得到4组测量值，同时在视场范围内存在一定数量的杂波测量值。

针对当前双目标雷达跟踪的问题，采用单一Wiener过程加速度模型及机动转弯模型均能完成目标跟踪的过程，即滤波输出能够跟踪目标的运动轨迹，但与真实轨迹均有一定的偏离，按照本文交互多模型算法对RBPF的线性部分进行加权处理，不同时间段内选取不同的模型进行计算，同时按照加权结果生成新的粒子，得到的轨迹及误差如图7所示。图8给出采用交互多模型与采用单一模型的误差对比，从图中可见，采用交互多模型算法可以有效降低单一模型带来的估计误差。

4 结 论

本文首先给出Rao-Blackwellized粒子滤波算法的基本原理及算法流程，然后利用数字仿真验证了其在单目标跟踪问题中的应用效果以及相比Kalman滤波算法的优越性，针对其应用在多目标跟踪问题中存在的滤波局部不收敛的现象，采用交互多模型的方法对粒子的估值进行预测与更新，数字仿真验证可以看出，相比原始的Rao-Black wellized粒子滤波算法，更改后滤波算法的收敛性更好且跟踪精度更高，能够较好地完成杂波干扰下的双目标跟踪任务。

参考文献：

[1]KalmanRE.ANewApproachtoLinearFilteringandPredictionProblems[J].JournalofFluidsEngineering，1960，82（1）：35-45.

[2]SunaharaY.AnApproximateMethodofStateEstimation forNonlinearDynamicalSystems[J].JournalofFluids Engineering，1969，92（2）：385-393.

[3]JulierS，UhlmanJ，DurrantWhyteHF.ANewMethod fortheNonlinearTransformationofMeansandCovariances inFiltersandEstimators[J].IEEETransactionsonAutomaticControl，2000，45（3）：477-482.

[4]CappeO，GodsillSJ，MoulinesE.AnOverviewofExisting MethodsandRecentAdvancesinSequentialMonteCarlo[J].ProceedingsoftheIEEE，2007，95（5）：899-924.

[5]GordonN，SalmondD，SmithAFM.NovelApproachto Nonlinear/NonGaussianBayesianStateEstimation[J]. IEEProceedingsF（RadarandSignalProcessing），1993，140（2）：107-113.

[6]SarkkaS，VehtariA，LampinenJ.RaoBlackwellizedParticleFilterforMultipleTargetTracking[J].Information Fusion，2007，8（1）：2-15.

（1）建立采用连续Wiener过程加速度模型（CWPA），系统状态为

Xk=（xk yk x·k y·k x¨k y¨k）T（11）

动力学模型为

（15）

其中：v（t）～N（0，σ2w）。此系统模型虽为非线性，但可采用EKF或UKF求解。

（3）对于每个粒子，分别采用两种模型对RBPF算法的线性部分进行预测及校正，求取其均值和方差，然后利用其每步的信息及误差方差的统计特性求取其对于每个模型的概率密度，即权重。

μik=f（vik，Sik） （16）

其中：μik为粒子权重；vik为测量信息；Sik为误差方差的统计特性。

（4）按照权重比例对计算的粒子均值及方差进行加权，作为下一次计算的初值，以此类推，可求取不同时刻的粒子状态。

mk=∑2

下面针对此问题分别采用线性Kalman滤波及RBPF粒子滤波来仿真，采用粒子数目为10。

图1所示为采用Kalman滤波的估计结果，可以看出，采用Kalman滤波得到的目标运动轨迹输出完全不能够跟踪上目标的真实运动轨迹，这是因为目标的观测模型中不只存在高斯噪声，而且在整个视场内存在均匀散布的杂波测量值，这样导致Kalman滤波算法很快失效。由图2～3可以看出，采用粒子滤波可以将真实目标轨迹与噪声

3.2 双目标跟踪的数字仿真实现

下面对仅有方位角测量信息的雷达双目标跟踪问题进行仿真验证，图5为雷达测量的示意图，此时目标的动态方程与上例中相同，但测量模型不同，此时测量量为角度值，使用两个固定位置的传感器对于两个目标进行测量，测量方程如下：

θik=arctan（yj，k-siy

xj，k-six）+rik（22）

其中：xj，k，yj，k为目标j的位置；six，siy为第i个传感器的位置；rik～N（0，σ2）为测量噪声，此时测量方程为非线性形式，因此需采用EKF或UKF配合使用RBPF算法。

图6为雷达的角度测量值随时间的变化情况，

从图中可以看出，针对两个传感器及两个目标可测量得到4组测量值，同时在视场范围内存在一定数量的杂波测量值。

针对当前双目标雷达跟踪的问题，采用单一Wiener过程加速度模型及机动转弯模型均能完成目标跟踪的过程，即滤波输出能够跟踪目标的运动轨迹，但与真实轨迹均有一定的偏离，按照本文交互多模型算法对RBPF的线性部分进行加权处理，不同时间段内选取不同的模型进行计算，同时按照加权结果生成新的粒子，得到的轨迹及误差如图7所示。图8给出采用交互多模型与采用单一模型的误差对比，从图中可见，采用交互多模型算法可以有效降低单一模型带来的估计误差。

4 结 论

本文首先给出Rao-Blackwellized粒子滤波算法的基本原理及算法流程，然后利用数字仿真验证了其在单目标跟踪问题中的应用效果以及相比Kalman滤波算法的优越性，针对其应用在多目标跟踪问题中存在的滤波局部不收敛的现象，采用交互多模型的方法对粒子的估值进行预测与更新，数字仿真验证可以看出，相比原始的Rao-Black wellized粒子滤波算法，更改后滤波算法的收敛性更好且跟踪精度更高，能够较好地完成杂波干扰下的双目标跟踪任务。

参考文献：

[1]KalmanRE.ANewApproachtoLinearFilteringandPredictionProblems[J].JournalofFluidsEngineering，1960，82（1）：35-45.

[2]SunaharaY.AnApproximateMethodofStateEstimation forNonlinearDynamicalSystems[J].JournalofFluids Engineering，1969，92（2）：385-393.

[3]JulierS，UhlmanJ，DurrantWhyteHF.ANewMethod fortheNonlinearTransformationofMeansandCovariances inFiltersandEstimators[J].IEEETransactionsonAutomaticControl，2000，45（3）：477-482.

[4]CappeO，GodsillSJ，MoulinesE.AnOverviewofExisting MethodsandRecentAdvancesinSequentialMonteCarlo[J].ProceedingsoftheIEEE，2007，95（5）：899-924.

[5]GordonN，SalmondD，SmithAFM.NovelApproachto Nonlinear/NonGaussianBayesianStateEstimation[J]. IEEProceedingsF（RadarandSignalProcessing），1993，140（2）：107-113.

[6]SarkkaS，VehtariA，LampinenJ.RaoBlackwellizedParticleFilterforMultipleTargetTracking[J].Information Fusion，2007，8（1）：2-15.

（1）建立采用连续Wiener过程加速度模型（CWPA），系统状态为

Xk=（xk yk x·k y·k x¨k y¨k）T（11）

动力学模型为

（15）

其中：v（t）～N（0，σ2w）。此系统模型虽为非线性，但可采用EKF或UKF求解。

（3）对于每个粒子，分别采用两种模型对RBPF算法的线性部分进行预测及校正，求取其均值和方差，然后利用其每步的信息及误差方差的统计特性求取其对于每个模型的概率密度，即权重。

μik=f（vik，Sik） （16）

其中：μik为粒子权重；vik为测量信息；Sik为误差方差的统计特性。

（4）按照权重比例对计算的粒子均值及方差进行加权，作为下一次计算的初值，以此类推，可求取不同时刻的粒子状态。

mk=∑2

下面针对此问题分别采用线性Kalman滤波及RBPF粒子滤波来仿真，采用粒子数目为10。

图1所示为采用Kalman滤波的估计结果，可以看出，采用Kalman滤波得到的目标运动轨迹输出完全不能够跟踪上目标的真实运动轨迹，这是因为目标的观测模型中不只存在高斯噪声，而且在整个视场内存在均匀散布的杂波测量值，这样导致Kalman滤波算法很快失效。由图2～3可以看出，采用粒子滤波可以将真实目标轨迹与噪声

3.2 双目标跟踪的数字仿真实现

下面对仅有方位角测量信息的雷达双目标跟踪问题进行仿真验证，图5为雷达测量的示意图，此时目标的动态方程与上例中相同，但测量模型不同，此时测量量为角度值，使用两个固定位置的传感器对于两个目标进行测量，测量方程如下：

θik=arctan（yj，k-siy

xj，k-six）+rik（22）

其中：xj，k，yj，k为目标j的位置；six，siy为第i个传感器的位置；rik～N（0，σ2）为测量噪声，此时测量方程为非线性形式，因此需采用EKF或UKF配合使用RBPF算法。

图6为雷达的角度测量值随时间的变化情况，

从图中可以看出，针对两个传感器及两个目标可测量得到4组测量值，同时在视场范围内存在一定数量的杂波测量值。

针对当前双目标雷达跟踪的问题，采用单一Wiener过程加速度模型及机动转弯模型均能完成目标跟踪的过程，即滤波输出能够跟踪目标的运动轨迹，但与真实轨迹均有一定的偏离，按照本文交互多模型算法对RBPF的线性部分进行加权处理，不同时间段内选取不同的模型进行计算，同时按照加权结果生成新的粒子，得到的轨迹及误差如图7所示。图8给出采用交互多模型与采用单一模型的误差对比，从图中可见，采用交互多模型算法可以有效降低单一模型带来的估计误差。

4 结 论

本文首先给出Rao-Blackwellized粒子滤波算法的基本原理及算法流程，然后利用数字仿真验证了其在单目标跟踪问题中的应用效果以及相比Kalman滤波算法的优越性，针对其应用在多目标跟踪问题中存在的滤波局部不收敛的现象，采用交互多模型的方法对粒子的估值进行预测与更新，数字仿真验证可以看出，相比原始的Rao-Black wellized粒子滤波算法，更改后滤波算法的收敛性更好且跟踪精度更高，能够较好地完成杂波干扰下的双目标跟踪任务。

参考文献：

[1]KalmanRE.ANewApproachtoLinearFilteringandPredictionProblems[J].JournalofFluidsEngineering，1960，82（1）：35-45.

[2]SunaharaY.AnApproximateMethodofStateEstimation forNonlinearDynamicalSystems[J].JournalofFluids Engineering，1969，92（2）：385-393.

[3]JulierS，UhlmanJ，DurrantWhyteHF.ANewMethod fortheNonlinearTransformationofMeansandCovariances inFiltersandEstimators[J].IEEETransactionsonAutomaticControl，2000，45（3）：477-482.

[4]CappeO，GodsillSJ，MoulinesE.AnOverviewofExisting MethodsandRecentAdvancesinSequentialMonteCarlo[J].ProceedingsoftheIEEE，2007，95（5）：899-924.

[5]GordonN，SalmondD，SmithAFM.NovelApproachto Nonlinear/NonGaussianBayesianStateEstimation[J]. IEEProceedingsF（RadarandSignalProcessing），1993，140（2）：107-113.

交互式粒子群算法 第11篇

云计算概念自2007 年提出后产生了巨大的影响, 全世界都把云计算作为重点新兴战略产业, 为抢占云计算制高点, 很多国家都研制并且出台了云计算的战略规划, 加快部署并推动国家级的云计算相关应用和云计算基础设施, 同时也成为工业界和学术界的研究热点[1,2]。

云计算的关键技术是资源调度技术, 由于虚拟化技术[3]的引入, 云资源调度以虚拟机为单位进行, 将物理资源分配给用户任务对应的虚拟机。由于系统规模增大导致系统具有复杂性、多样性、异构性和动态性等特征, 使得云数据中心基于虚拟机的资源调度充满挑战性, 同时也决定了虚拟机放置问题是一个NP-hard问题[4]。在云环境中, 虚拟机放置时间比调度算法所需的时间长得多, 因此云资源调度需要考虑的主要是虚拟机如何放置的问题。

数据中心服务器的负载是影响系统性能的瓶颈, 由于CPU时间分片和网络等影响, 服务器负载较高时运行任务具有较长的平均完成时间[5], 因此保证数据中心的负载均衡很重要。现有一些算法[6,7,8]往往只关注成本控制和云资源使用率, 忽略了负载均衡对系统性能的影响, 虽然在一定程度上缓解了云资源与用户需求的矛盾, 但云数据中心的资源规模大、资源间差异大、组成复杂等问题直接导致数据中心资源的浪费, 现如今还没有很好的虚拟机放置算法快速实现数据中心的负载均衡, 因此研究先进的虚拟机放置算法具有重要的现实和学术意义。

1 问题描述

1.1 云资源调度模型

根据云计算的特点, 建立云资源调度三层结构二级调度模型如图1 所示。三层结构分别为用户层、虚拟层和物理层。二级调度为任务调度和虚拟机调度, 任务调度为第一级调度, 发生在在用户层和虚拟层之间;虚拟机调度为第二级调度, 发生在虚拟层和物理层之间。虚拟资源的调度和分配策略是云计算的核心问题[9], 本文主要研究云环境下二级调度过程中的虚拟机资源分配, 即将虚拟机放置到满足条件的服务器上。

1.2 基本定义

定义1:云环境中的虚拟机资源调度是将M个虚拟机部署到N个物理机上, 映射模型相当于将M个不同元素放到N个不同元素的集合, 共有NM种解决方案, 该问题属于装箱问题, 即给定集合PM{P1, P2, ……, PN}和集合VM{V1, V2, ……, VM}, 把VM中的M个元素放到PM的N个元素中, 保证使用的PM中元素数量最少。

定义2:N为云数据中心物理机的数量, Nuse为数据中心中已经占用的物理机的数量;Uuse为数据中心物理机CPU的平均利用率, Uiuse为物理机i中CPU的利用率;Muse为数据中心物理机的内存平均利用率, Miuse为物理机i中内存的利用率;Suse为数据中心物理机总存储的平均利用率, Siuse为物理机i中硬盘的利用率。

物理机部署的虚拟机会占用一定数量的CPU、内存和硬盘空间, 因此在定义1中的集合PM中的元素要满足几个约束条件:Nuse≤N, 0≤Uiuse≤1, 0≤Miuse≤1, 0≤Siuse≤1。

定义3:为了衡量云计算数据中心的负载均衡率, 定义E为云计算平台中负载不均衡度, 。可以看出负载不均衡度E的值越小, 表示系统负载越均衡。

定义4:需要定义物理机负载的两个阈值, 本文以物理机的CPU利用率来定义阈值, 即物理机负载最低阈值Tmin和负载最高阈值Tmax, 分别为20%和80%, 物理机负载率在Tmin~Tmax之间的状态称为平衡状态。

1.3 目标函数

为避免数据中心的资源浪费, 达到负载均衡, 根据上小节基本定义, 定义目标函数如下:

(1) f1= Min (Nuse) , f1 表示将虚拟机分配到物理机后, 保证使用的物理机数量最少;

(2) , f2表示将虚拟机分配到物理机后, 保证物理机资源利用率最大化;

(3) f3= Min (E) , f3表示将虚拟机分配到物理机后数据中心的负载不均衡度函数, 其中E即上文1.2 定义的负载不均衡度, 该函数表示E值越小表示系统越平衡。

2 基于改进粒子群算法的虚拟机放置算法

2.1 粒子群优化算法介绍

1995 年由美国博士Kennedy和Eberhart[10]通过研究鸟群觅食行为提出粒子群算法 (Particle Swarm Optimization, PSO) 。设想场景:一群鸟在随机搜寻食物, 区域内仅有一块食物, 所有鸟都不知道食物在哪里, 但它们知道当前位置离食物多远, 那么找到食物最有效的策略就是搜寻目前离食物最近鸟的周围区域。PSO算法是一种基于群体的自适应搜索优化算法。算法中每个优化问题的潜在可能解都称其为“粒子” (Particle) , 每个粒子都有一个被目标函数所决定的适应值 (Fitness Value) , 还有一个速度决定飞翔的方向和距离。每个粒子均受局部最优信息和全局最优信息影响, 以一定速度在整个解空间飞行, 飞行速度和位置由个体飞行经验和群体飞行经验动态调整, 以便用于信息交换。通过大量实验研究, 证实了群体中个体之间的社会协作和信息共享有助于整体进化[11], 用公式表示如下:

其中, 1≤d≤D, 1≤i≤N, D为搜索空间的总维数, N是粒子群内粒子的个数;xi= (xi1, xi2, …, xi D) t表示粒子i的当前位置;vi= (vi1, vi2, …, vi D) t表示粒子i的当前速度;pt id = (pi1, pi2, …, pi D) t是第t时刻粒子i本身的最优位置的第d维变量, 即它经历过的最好位置;pt gd = (Pg1, Pg2, …, Pg D) t是第t时刻粒子群全局最优位置的第d维变量, 即在群体所有微粒经历过的最好位置;ω 是惯性权重;c1、c2是学习因子;r1、r2是均匀分布在[0, 1]区间的随机数。

虽然标准PSO算法优点很多, 但是随机性很大, 多样性比较差, 很容易陷入局部最优现象, 因此需要完善, 下面将介绍本文改进的粒子群算法。

2.2 基于改进粒子群算法的虚拟机放置算法

2.2.1 算法设计

1.粒子群算法编码

首先对n个待部署虚拟机进行编码形成队列, 然后通过虚拟机放置算法得到虚拟机与数据中心m个物理机的映射关系, 最后按照映射关系将虚拟机放置到对应物理机上, 从而实现优化目标。种群中的每个粒子的位置和速度分别用公式 (3) 和公式 (4) 表示, 如下所示:

公式 (3) 中xij表示第i个粒子代表的第j个虚拟机在第t次迭代时放置的物理机节点编号。公式 (4) 中vij代表第i个粒子在第t次迭代的第j维速度。为了避免粒子产生过度偏移现象, 用vmax来限制粒子飞行范围。所有粒子的速度和位置每次迭代通过公式 (1) 、 (2) 更新。

2.分析与设计惯性权重 ω

影响算法搜索结果和收敛速度的关键参数就是ω, 经过先前的大量实验研究, ω 过大有利于全局寻优, ω 过小有利于局部寻优。根据 ω 取值对搜索结果的影响, 可以采用经典的线性递减方式设定 ω 的值如公式 (5) 所示。

其中, ωmax一般取0.9;ωmin一般取0.4;num为最大迭代次数;t为当前迭代次数。ω 随着迭代次数的增加而减小, 且递减速率在变缓, 有利于从全局搜索转变为局部搜索, 并保证算法不会过快收敛。

3.确定算法的适应度函数

根据1.3 提出的算法目标, 通过对目标优化要求的不同设定相应的权值, 实现多目标优化。本算法的目标是在迭代次数范围内找到使适应度函数值最小的资源分配方案, 即最终的虚拟机放置方案。适应度函数可以定义如下公式:

4.种群初始化引入按资源需求和实时负载分配的思想

根据虚拟机对资源的需求情况选择能够满足其要求的物理机, 即所选的物理机一定要满足虚拟机对资源的需求, 同时根据1.2 的定义4 物理机部署虚拟机后不至于过载。

5.引入分组思想

首先将种群随机分成若干份等量的小粒子群, 然后在每一个子群里随机设置参数, 进行粒子群优化算法寻优, 最后再对全部最优解取最小值为最终最分配方案。

2.2.2 算法步骤

Step1:按照初始种群方案生成有M个粒子的种群, 每个粒子编号为1 到M, 将M个粒子随机分成N个独立的子群空间, 每个子群的粒子个数为m =M/N;

Step2:在每一个子群中执行标准PSO, 初始化各参数, 其中xi= (xi1, xi2…xij…xin) 0, n为待放置虚拟机数量, i=1, 2, …, m, vi= (vi1, vi2…vi j…vin) 0;pibest= (xi1, xi2…xij…xin) 0, pqbest=min (p1best, p2best, …, pqbest, …, pmbest) ;

Step3:根据适应度函数公式 (6) 依次计算每个子群中每个粒子的适应值F;

Step4:对于每个粒子, 比较个体当前适应值和历史最优位置pibest, 如果当前适应值较好, 则将此粒子当前的位置作为当前最优的位置并更新pibest, 否则保持pibest不变;

Step5:对于每个粒子, 比较当前最优位置pibest和子群体中整体的最优位置pqgbest, 如果当前最优位置较好, 则将其作为当前群体最优位置并更新pqgbest, 否则pqgbest不变 (q=1, 2...N) ;

Step6:根据公式 (1) 和公式 (2) 更新每个粒子的速度和位置信息;

Step7:判断迭代次数num是否达到最大值, 若达到则结束循环, 再比较所有子群的最优位置的适应度值, 取最小值得到整个粒子群的最优位置, 即pgbest= min (p1gbest, p2gbest, …, pqgbest, …, pNgbest) ;否则转至第三步继续。

3 仿真实验

3.1 实验环境和参数设置

为了验证基于分组的粒子群优化算法GPSO在云环境下虚拟机资源分配问题上的可行性, 本文扩展了Cloud Sim平台进行仿真实验, 并与轮询算法Round Robin和标准的PSO算法进行了比较。参数设置如表1、表2 所示。

3.2 结果与分析

3.2.1 负载不均衡度E的比较

系统的负载不均衡度随着虚拟机数量的增加而减小。图2 表示三种算法分别在不同虚拟机规模时系统的负载不均衡度。由图2 可知GPSO算法的负载不均衡度E小于其他两个算法, 说明GPSO算法在负载平衡方面的性能优于其他两个算法。这是因为PSO算法初始种群是随机生成的, 而GPSO算法的初始种群是根据系统的实时负载随机生成, 并将负载不均衡度作为目标函数进行搜索。轮询算法没有考虑物理机实时负载, 也没有优化目标策略。

3.2.2 资源利用率比较

如图3 所示, GPSO算法比其它两种算法的资源利用率更高, 这是因为目标函数包含了对系统资源利用率的优化策略, 从而一定程度上避免了系统资源的浪费。

4 结论

本文针对现有虚拟机资源放置算法只考虑云资源的能耗和使用率, 忽略负载均衡对系统性能影响的问题, 提出了基于分组的改进粒子群算法 (Grouped Particle Swarm Optimization:GPSO) , 通过最小化云数据中心的负载不均衡度达到系统的负载平衡。与标准粒子群算法中随机生成初始种群的方式不同, 本文根据系统的实时负载来随机生成初始种群, 在算法中引入分组的思想, 将该种群进行随机分组, 通过比较各组的全局最优解得到最终分配方案。通过Cloud Sim平台仿真实验表明, 改进算法生成的资源分配方案较原算法能有更好的负载均衡、更高的资源利用率, 证实了该算法的有效性。

摘要：云计算通过使用虚拟机技术提高了数据中心的资源利用率。虚拟机放置算法作为云计算的关键技术, 具有重要研究意义。现有虚拟机放置算法往往只关注成本控制和云资源使用率, 忽略了负载均衡对系统性能的影响。针对该问题, 本文在标准的粒子群优化算法基础上进行改进, 首先设计多目标函数时引入负载不均衡度概念, 然后通过系统实时负载随机生成初始化种群, 并在算法中引入分组思想, 通过对初始种群进行随机分组, 避免算法陷入早熟现象。通过Cloud Sim模拟平台进行仿真实验, 表明改进后的算法更利于云数据中心进入负载均衡状态, 并有较高的资源利用率。

关键词：云计算,虚拟机放置,负载均衡,多目标优化,粒子优化群算法

参考文献

[1]钱琼芬, 李春林, 张小庆, 等.云数据中心虚拟资源管理研究综述[J].计算机应用研究, 2012, 29 (7) :2411-2415.

[2]王倩, 曹彦.云计算研究[J].软件, 2013, 34 (5) :116-118.

[3]丁养志.浅析虚拟化技术在云计算中的运用[J].软件, 2014, 35 (3) :176-177.

[4]Garey Michael R, Johnson David S.Computers and intractability-a guide to the theory of np-completeness[J].W H Freeman co, 1979, 25-31.

[5]李建锋, 彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用, 2011, 31 (1) :65-69.

[6]米海波, 王怀民, 尹刚, 等.一种面向虚拟化数字中心资源按需重配置方法[J].Journal of Software, 2011, 22 (9) .

[7]林伟伟, 齐德星.一种基于动态重配置虚拟资源的云计算资源调度方法[P].中国201010268105.7, 2001.01.05.

[8]华夏渝, 郑骏, 胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报, 2010, 1 (1) :127.

[9]张栋梁, 谭永杰.云计算中负载均衡优化模型及算法研究[J].软件, 2013, 34 (8) :52-55.

[10]KENNEDY J, EBERHART R C.Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks.New York:IEEE, 1995, 1942–1948.