小生境粒子群算法（精选10篇）
小生境粒子群算法 第1篇
1951年,Nash证明了n人非合作博弈Nash均衡的存在性[1],奠定了非合作博弈的重要基础,但令人遗憾的是,Nash并没有给出Nash均衡的求解算法。围绕Nash均衡的求解,许多学者从纯数学分析的角度提出了大量卓有成效的算法,诸如全局牛顿算法[2]、同伦算法[3]、信赖域优化算法[4]、投影算法[5]等。然而,这些算法大多要求博弈局中人的支付函数具有一定的凸( 凹) 性和连续性,并且算法本身往往依赖初始点的选取,在一定程度上限制了该类算法的应用。Roughgarden[6]指出Nash均衡的求解是一个NP-hard问题,智能算法在解决NP难问题上体现了较强的优越性。因此,人们纷纷尝试利用模拟退火算法、禁忌搜索算法、遗传算法、免疫算法、粒子群优化算法等智能算法求解博弈的Nash均衡,产生了大量的研究成果[6,7,8,9,10,11,12,13],但是这些算法大多仅能求出一个Nash均衡点,对多重Nash均衡求解的研究还是很少。文献[13]对多重Nash平衡的求解进行了很好的探索,其基本思想是利用粒子群算法进行多次计算,直到发现Nash均衡解的个数足够多为止。但在实际计算中,多次计算并不都能保证收敛到多个不同的Nash均衡解,多次计算收敛到同一个Nash均衡解的情况时有发生。因此,针对n人非合作博弈多重Nash均衡求解问题,本文提出了一种自适应小生境粒子群算法。该算法融合了序列小生境技术、粒子群优化算法的思想,并加入了变异算子和自动生成小生境半径机制,使得所有粒子尽可能分布到整个搜索空间的不同局部峰值区域,从而有效地求得N人非合作博弈问题的多重Nash均衡,计算结果表明本文提出的算法具有较好的性能。
1 问题描述
假设一个n人有限非合作博弈,局中人i( 0≤i≤n) 的纯策略集为si= ( s1i,s2i,…,simi) 。定义在si上的混合策略为,即局中人i以xij的概率选择纯策略) 。博弈的一个混合局势可以记为,在此混合局势下,局中人i的期望支付为:
其中,为局中人1选取纯策略,局中人2选取纯策略,…,局中人n选取纯策略snjn时局中人i的收益。
特别地,对2人有限非合作博弈( 双矩阵博弈) : 设局中人1的混合策略为x = ( x1,x2,…,xm) ,局中人2的混合策略为y =( y1,y2,…,yn) ,Am×n,Bm×n分别为局中人1和局中人2的收益矩阵,则局中人1和局中人2的期望支付分别为x AyT和x ByT。
定义1混合策略局势x*是n人有限非合作博弈的一个Nash均衡解,如果x*满足) ,其中x*‖xi表示只有局中人i用xi替换均衡解x*中自己的策略,其他局中人都不改变各自在均衡解中的策略。
性质1混合局势x*是n人有限非合作博弈的一个Nash均衡解的充分必要条件是: 对于任意局中人i的每一个纯策略
特别地,( x*,y*) 是双矩阵博弈的一个Nash均衡的充分必要条件是[16]:
2 自适应小生境粒子群算法的设计
2. 1 算法基本思想和具体步骤
基本粒子群算法最早由Kennedy和Eberhart于1995年通过对鸟群觅食过程的分析和模拟而提出[14],随后由于该算法具有简单易行、收敛速度快和易于并行等特点在许多领域得到了应用和发展。理论上可以通过多次运行基本粒子群算法来求解优化问题的多个最优解,但是实际计算中粒子群在进化过程中易趋向同一化,失去多样性,从而使算法陷入局部最优解,最终多次计算未必能收敛到多个不同的最优解。为此,本文设计了自适应小生境粒子群算法,其基本思想为引入序列生境的技术[17],将粒子群算法和序列生境技术融合,在粒子群进化中将那些与已经找到的最优解相似的粒子进行变异操作,使它们有可能远离最优解区域,即如果粒子群中某个粒子与小生境核集中任何一个小生境核的距离小于小生境半径σ,则用变异操作,将该粒子按照一定的变异概率对其部分维进行变异,使该粒子从这个最优解的区域跳跃到其他最优解的区域,使得所有粒子尽可能分布到整个搜索空间的不同局部峰值区域,从而有效地求得问题的多个最优解。
2. 1. 1 自适应小生境粒子群算法设计步骤
Step1设置初始参数,产生初始粒子群。
Step2执行粒子群算法各个步骤,找到一个最优解,并放入小生境核集中。
Step3重新初始化粒子群。
Step4利用粒子群算法寻求最优解的每代中,执行以下步骤( 1) - 步骤( 3) 。
( 1) 变异条件判断: 判断是否有粒子包含在小生境核集之内,若有,执行第( 2) 步; 否则执行第( 3) 步。
( 2) 变异操作: 对满足条件的粒子执行如下变异操作: 对粒子的所有维分别产生随机数r∈( 0,1) ,如果r < pm,pm为变异概率,则对该粒子该维进行随机初始化,否则该维保持不变。然后对变异后新生成的粒子计算它的函数值,如果优于小生境核集中的任一个值,则重新进行变异操作; 否则转到第 ( 3) 步执行。
( 3) 如果满足粒子群算法的终止条件,则执行Step5; 否则返回Step4继续执行。
Step5将找到的一个最优解放入小生境核集中。
Step6如果小生境核集中找到的最优解数目达到要求或满足算法停止条件,则算法终止,输出小生境核集中的全部最优解; 否则返回Step3继续执行。
2. 1. 2 粒子群算法设计步骤
从上述自适应小生境粒子群算法的设计可以看出,针对n人有限非合作博弈需要设计合适的粒子群算法和确定合适的小生境半径σ,首先设计粒子群算法步骤如下:
Step1确定粒子群算法的参数值。包括学习因子c1、c2、最大迭代次数kmax、最大惯性权重ωmax、最小惯性权重ωmin、精度ε和群体规模N。
Step2随机生成N个粒子xi和初始化速度vi,形成初始化粒子群p0,其中i,并且粒子的初始速度
Step3根据适应度函数计算每个粒子适应度,找到粒子的个体极值pbest( i) ,i = 1,…,N和粒子群的全体极值gbest。
Step4对每个粒子,将其适应度与所经历过的最好位置的适应度进行比较,如果更好,则将其作为粒子的个体历史最优值,用当前位置更新个体历史最好位置。
Step5对每个粒子,将其历史最优适应度与整个粒子群体内所经历的最好位置的适应度进行比较,若更好,则将其作为当前的全局最好位置。
Step6按照公式计算惯性权重ω,其中k为当前迭代次数。按照式( 2) 和式( 3) 更新粒子的速度和位置。
式中,c1和c2为粒子进化学习因子,分别调节全局最好粒子和个体最好粒子方向飞行方向的最大步长,通常情况令c1= c2= 2,r1和r2为在( 0,1) 内变化的随机数,w为惯性权重。
Step7根据精度和最大迭代次数判断是否结束迭代,若是,则输出符合条件的最优粒子( 即近似解) 和迭代次数,算法结束; 否则转Step3。
2. 1. 3 自适应小生境半径的设计
在自适应小生境算法中,小生境半径的确定特别关键,如果σ太大,则不足以发现一些重要个体,从而会遗漏一些极值点,如果σ太小又会形成多余的不必要的局部最优解,从而增加算法的计算量,降低算法的计算效率。实际问题中由于某些极值之间峰值常常随问题而变,同时人们对所求问题解空间的结构事先很难有比较清晰的了解,难于形成较为成熟的先验知识,因此小生境半径σ的值很难预先得到。若在搜索空间中所有的小生境半径简单地使用同一个固定的σ,则会导致计算效果不佳,因此本文在借鉴文献[15]自适应序列生境鱼群算法中小生境半径的设置和调整方法的基础上,设计了一种自适应序列小生境粒子群优化算法,即先给出小生境半径σ的初始预测值,然后再利用粒子群优化算法不断优化调整σ值,具体的小生境半径自动调整方法如下:
假设小生境核集中某一最优解个体为x = ( x*1,x*2,…,x*D)
Step1从个体x的D维变量中选择第j维变量xj。
Step2设置第j维变量xj朝定义域上限方向的小生境半径σ1和下限方向的小生境半径σ2,初始预测值(初始预测值的具体数值可以随机给出,比如也可以设置)j,其中w为第j维变量xj的定义域长度,m为峰的个数。
Step3分别利用粒子群优化算法不断优化调整σ1和σ2的值。
Step3. 1调整σ1的值。
Step3. 1. 1利用粒子群优化算法寻求最小解x'j,使得f( x*1,x*2,…,xj,…,x*D) 在( x*j,x*j+ σ1]区间里达到最小。
Step3. 1. 2若最小解x'j= x*j+σ 1,则调整半径σ1= σ1+ ε( 其中ε > 0) ,并且返回Step3. 1. 1重新执行。否则( x'j< x*j+σ1) ,取σ1= x'1- x*1。
Step3. 2调整σ2的值。
Step3. 2. 1利用粒子群优化算法寻求最小解x″j,使得f( x1*,x2*,…,xj,…,x*D) 在[x*j- σ2,x*j) 区间里达到最小。
Step3. 2. 2若最小解x″j= x*j- σ2,则调整半径σ2= σ2+ ε( 其中ε > 0) ,并且返回Step3. 2. 1重新执行。否则( x″j> x*jσ2) ,取σ2= x*j- x″j。
Step4计算个体x的第j维变量xj的小生境半径为σ( xj)= min( σ1,σ2) 。
Step5重复Step1 - Step4,可以求出x中第j维变量xj的小生境半径σ( xj) ( j = 1,2,…,D) ,则以最优解个体x为核心的小生境半径σ( x) = min{ σ( xj) ,j = 1,2,…,D} 。
2. 2 算法适应度函数的设计
自适应小生境粒子群算法中每一个粒子由所有局中人的混合策略表示,即x = ( x1,x2,…,xn) ,定义粒子的适应度函数如下:
显然,由n人有限非合作博弈Nash均衡的定义和性质易得:
混合局势x*是n人有限非合作博弈的一个Nash均衡解的充分必要条件是:,使得f( x*) = 0,且对任意的x≠x*,有f( x) > 0。
特别地,对作为n人有限非合作博弈特例的双矩阵博弈,算法中每个粒子由两个局中人的混合策略表示,即z = ( x,y) ,定义双矩阵博弈的适应度函数如下:
式中Ai.表示矩阵Am×n的第i行,B. j表示矩阵Bm×n的第j列。同理,由Nash均衡的定义和性质易得:
混合局势z*= ( x*,y*) 是双矩阵博弈的一个Nash均衡解的充分必要条件是,使得f( z*) = 0,且对任意的 z≠z*,有 f( z) > 0。
因此,n人有限非合作博弈的混合策略组合空间内只有Nash均衡点的适应度函数值最小。
3 数值算例
例1 - 例3均来自文献[13],本文给出的自适应小生境粒子群算法的参数设置为: 群体规模N = 10,学习因子c1= c2= 2,最大迭代次数kmax= 500,精度设置为ε = 10- 2,ωmax= 0. 2,ωmin= 0. 1,计算结果分别如表1 - 表3所示。
例1考虑双矩阵对策Γ( X1,Y1,A1,B1) :
例2考虑双矩阵对策Γ( X2,Y2,A2,B2) :
例3考虑双矩阵对策Γ( X3,Y3,A3,B3) :
通过以上3个数值例子的计算结果可以看出,例1 - 例3用本文设计的自适应小生境粒子群算法运行1次就可以分别求出多个Nash均衡解。对于例1,用文献[13]给出的算法每运行1次可以得到1个Nash均衡解,需要反复运行10次才可以求出全部3个Nash均衡解,而本文算法运行1次就可以求出全部3个Nash均衡解。对于例2和例3,用文献[13]中给出的算法需要分别反复运行30次和40次才可以求出全部Nash平衡解,而本文设计的算法运行1次就可以分别求出4个和5个Nash均衡解。与文献[13]中需要随机运行算法40次的结果相比,本文设计的算法运行1次就可以求出多个Nash均衡解,大大提高了单次搜索Nash均衡解的效率。事实上,文献[13]需要反复运行粒子群优化算法获得的多个Nash均衡解带有很大的随机性,并不能保证每一次运行都得到不同的Nash均衡解,很可能运行30次算法得到同一个Nash均衡解而无法求出多个Nash均衡解。而本文的算法则利用自适应小生境技术使所有粒子在搜索过程中尽可能分布到整个搜索空间的不同局部峰值区域,不需要反复运行算法就可以求出多个不同的Nash均衡解,提高了算法的计算效率,并改进了文献[13]中算法计算结果随机性过大的问题。总之,通过例1 - 例3数值算例的计算和分析,可以看出本文提出的自适应小生境粒子群算法在求解n人非合作博弈多重Nash均衡方面具有较好的性能,但是必须注意到本文算法在成功地找到若干个Nash均衡解之后,搜索空间可能会变得更加复杂( 比如峰之间的距离很小或者峰的高度差别较少或者有孤立峰值点等) ,从而求出全部Nash均衡解变得更加困难,有时会遗漏个别Nash均衡解,但也可以通过类似文献[13]中的方法,多运行几次来弥补遗漏。
4 结 语
本文将序列小生境技术引入粒子群算法中,并加入了变异算子和自动生成小生境半径机制,使得所有粒子尽可能分布到整个搜索空间的不同局部峰值区域,从而有效地获得n人非合作博弈问题多重Nash均衡,提高了单纯运用粒子群算法反复计算多重Nash均衡解的效率,是对目前国内外为数不多的有关多重Nash均衡求解算法研究的一种探索和尝试。该算法综合了粒子群算法和小生境算法的优点,较好地克服了粒子群算法收敛到一定精度时,粒子易趋向同一化而陷入局部最优解的特点,而且借助自适应小生境技术,在算法中自动计算小生境半径,最大程度地提高了算法的搜索性能,避免了反复运行粒子算法求解多个不同的Nash均衡时可能收敛到同一个Nash均衡的问题。从当前的应用效果看,这种模拟生物进化思想的自适应小生境粒子群算法具有较好的应用效果,但是由于粒子算法的研究还处于起步阶段,诸如算法的理论分析、收敛性等方面还需要更加深入细致的研究。
摘要：针对n人非合作博弈多重Nash均衡求解问题,提出一种自适应小生境粒子群算法。该算法融合了序列小生境技术、粒子群优化算法的思想,并加入了变异算子和自动生成小生境半径机制,使得所有粒子尽可能分布到整个搜索空间的不同局部峰值区域,从而有效地求得博弈问题的多重Nash均衡。最后给出几个数值算例,计算结果表明所提出的算法具有较好的性能。
基于量子粒子群算法求解整数规划 第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篇
电力系统无功优化是指在满足发电机及电力系统安全运行的条件下,通过对发电机端电压、可调变压器分接头和无功补偿设备的综合调节,使有功损耗最小及母线电压偏移量在合格范围内。由于可投切并联电容器组(或电抗器组)的无功出力和可调变压器的分接头位置是非连续变化的,而发电机的电压是可连续调节的量,因此,无功优化问题同时存在连续变量和离散变量,属于多变量、多约束的混合非线性规划问题[1,2]。
无功优化算法比较多,各有优点,各有不足,传统的梯度法、内点法、线性规划和非线性规划等常规优化算法具有要求目标函数可微、对初值要求高、求解时间较长和容易产生维数灾等缺点[3]。智能算法包括遗传算法(Genetic Algorithm,GA)、专家系统、粒子群算法和蚁群算法[3,4,5,6,7,8,9]等,容易出现早熟现象和陷入局部收敛等,因此,其各种改进形式主要是提高全局寻优能力和加快收敛速度。粒子群算法因对求解信息要求少、建模简单、适用范围广和寻优能力强等优点而被广泛应用。
粒子群算法与其他的进化算法相比,具有存储量少、计算简单、鲁棒性好等优点,但该算法在搜索初期的收敛速度很快,后期却易陷入局部最优,且调节解的速度较慢。本文将一种全新的小生境粒子群优化算法(Iniche PSO)应用于电力系统无功优化问题中,并结合无功优化的特点在粒子群算子、遗传变异算子、终止原则等方面做了改进。小生境粒子群优化算法[1]具有很高的全局寻优能力和收敛速度,在保持解的多样性方面表现良好。
1 电力系统无功优化数学模型
无功优化问题通常是在保证电压质量、电压分布与期望值的差值、控制代价或者它们的任意组合等最小的前提下,适当地采用调整发电机机端电压、变压器分接头、投切无功补偿(并联电容器和电抗器的分组)设备来降低网损,基本数学模型由目标函数、功率方程等式约束和变量不等式约束条件组成。
1.1 目标函数
考虑电力系统运行的经济性,本文以有功损耗最小为主要控制目标,其中又考虑了电力系统各个节点的电压及发电机的无功功率越界的情况,应用罚函数构造出目标函数模型:
式中:Ploss为电力系统有功损耗;该目标函数中包括对负荷节点电压越界的惩罚函数和对发电机无功功率的越界惩罚函数;λq为发电机无功功率越界惩罚系数;λq为电压越界惩罚系数;Ui、QGj为负荷节点的电压和发电机的无功功率;Uimax、Uimin和QGimax、QGimin为对应节点电压及发电机无功功率的变量上下限。
1.2 不等式约束
不等式约束即变量约束,可分为控制变量约束和状态变量约束。分接头可调变压器变比K、无功补偿电纳B和发电机机端电压UG为控制变量;节点电压U和发电机注入无功QG为状态变量。
(1)控制变量的不等式约束为:
式中:UGimax、UGimin为发电机机端电压的上下限;Bimax、Bimin为无功补偿电纳的上下限;Kimax、Kimin为变压器变比的上下限;NG、Nb、Nk为系统发电机节点数、无功补偿数、有载变压器数。
(2)状态变量的不等式约束为:
式中:QGimax、QGimin为节点电压的上下限;QGimax、QGimin为发电机无功输出的上下限;Nd为负荷节点数。
1.3 等式约束
等式约束条件,考虑节点有功和无功功率平衡约束,即潮流约束方程,即:
式中:PGi、QGi为发电机节点的有功功率和无功功率出力;Pli、Qli为负荷节点的有功和无功功率;Gij、Bij和θij为节点ij之间的电导、电纳和电压相角差;N为节点数。第一式为节点有功功率约束,第二式为节点无功功率约束。
2 改进小生境粒子群优化算法
2.1 粒子群算法
无功优化的算法种类繁多,智能进化算法与传统优化算法相比可较好地解决非线性、多变量、复杂系统优化等问题。PSO算法又因其存储量少、计算简单、鲁棒性好等优点在各个领域被广泛应用。粒子通过自己和同伴的经验来决定下一步的运动,通过调整简单的速度一位移来实现搜索最优解。
第t次迭代中,算法中粒子速度与位移寻优基本公式为:
式中:w为惯性系数,控制前一速度对当前速度的影响;cl为加速系数,体现微粒本身记忆的影响;c2为加速系数,体现群体信息的影响;r1和r2为2个在[0,1]间均匀分布的随机数;xij、Vij分别表示粒子i在第j维空间中的位置和速度;Pij,、pgi分别是每个微粒的最优位置和群体发现的最优位置。
2.2 小生境技术
小生境技术的实质是将生物学中的小生境概念应用于进化算法中,将进化计算中的每一代个体划分为若干类,每个类中选出若干最优的个体组成1个群,再在种群中,以及不同种群之间杂交、变异产生新一代个体群。采用某种竞争或排挤或分享等机制优化结果。
2.3 改进小生境粒子群优化算法
按顺序以欧氏距离计算法,首先在当前的种群中找到离初始种群个体距离最近的个体,组成1对,也就是说从初始种群中提取1个个体A,然后再从中找到与其欧式距离相近的对应的1个个体B,构成1对,以后的进化操作主要是对每对个体进行。如果初始种群个体为N(N为偶数)个,那么能够组成N/2对个体群。在规定的变异范围内,对N/2对个体中的每对个体进行变异操作。变异后的子代个体与父代个体根据适应度进行竞争排挤,最终保留2个适应度较高的个体。最后对种群整体进行动态粒子群优化操作,到此算法完成了一代进化。
3 INiche PSO在无功优化中的应用
3.1 算法的改进
考虑电力系统无功优化的实际特点,为改善小生境粒子群算法的计算速度和收敛能力,并针对粒子群的一些缺点做出以下改进,进一步完善算法:
(1)电力系统控制变量多,发电机机端电压可以连续调节,采用浮点编码,有载变压器分接头和无功补偿容量,不能连续调节,采用整数编码。所以,本文采用整数编码和浮点编码相结合的方式。
(2)变异算子中采用自适应的变异率,适应度低的个体采用较高的变异率,使得适应度高的个体采用较小的变异率,从而提高了寻优的速度,即:
式中;fmax为种群中适应度最大值;favg为种群的适应度平均值;f1为要交叉的2个个体中较大的适应度值;Pc1、Pc2为变异率,0
(3)由于小生境过程相对复杂,所以本文对小生境优化过程不采用恒定不变的方式,即只在进化的前期进行小生境的变异运算,这样既能保持种群的多样性,又能改善算法的计算速度和收敛能力。
(4)若连续10代所求解不变则程序运行结束。
(5)粒子群优化算法中,较大的w值有利于跳出局部最优解,而较小的w有利于算法的收敛,因此,惯性权重的取值对算法的性能十分重要,本文采用依据其自身当前的适应值调节粒子的w变化,即:
式中:wmin、wmax为惯性权重系数的最小值和最大值;fi为当前粒子的适应值;favg、fmin分别为当前整个粒子群体适应值的平均值和最小值。可见,个体适应值较好的粒子对当前最优解临近区域做局部细致搜寻,个体适应值差的粒子会以较大步长搜寻以便能找到更好的解,进而保证了整个群体解的多样性及收敛性。
3.2 算法流程
4 算例分析
以IEEE30系统节点为例,该系统包含有6台发电机、41条支路、4台可调压变压器和4个装有容性无功补偿的负荷节点,系统中发电机的节点编号为1、2、5、8、11、13;可调变压器支路为6-9、6-10、4-12、27-28;节点17、18、23、27装有可投切容性无功补偿设备。节点1为平衡节点,余下的发电机节点为PV节点。PV节点和平衡节点电压设置在[0.9,1.1]之间,PQ节点的电压设置在[0.95,1.05]之间,可调变压器变比设置在[0.9,1.1]之间。与Niche PSO及简单遗传算法(SGA)进行比较,图2为各种算法优化后电压的分布情况,各节点的电压较其他算法都有明显改善。表1是各个算法计算的网损情况,在优化后,系统有功网损由原来的0.068 23下降到0.030 52,减小了0.03771,迭代次数由原来的49下降到1 1,由此可知,INiche PSO不仅提高了该系统经济性,而且计算速度明显优于简单遗传算法和小(下转第46页)生境粒子群算法,能以更快的收敛速度获得更优的解。
优化前后系统各个节点电压比较如图2所示。
5 结语
改进小生境粒子群算法在优化过程中,不断淘汰适应度较差的粒子和产生新的粒子,粒子通过自己和同伴的经验来决定下一步的运动,较大程度的避免了局部最优的缺点,通过采用自适应变异算子和考虑是否连续10代解保持不变以提高计算速度和收敛速度,利用迭代前期采用小生境变异操作来提高局部搜索能力,同时对粒子群算法进行改进后,在获得全局最优解、提高计算效率等方面显示了一定的优越性。IEEE30节点系统仿真结果表明该算法对电力系统无功优化问题具有稳定、高效、更好的全局寻优能力和收敛速度等优点,为解决电力系统无功优化问题提供了一种新的可行方法。
参考文献
[1]刘方,颜伟,DAVID C Y.基于遗传算法和内点法的无功优化混合策略[J].中国电机工程学报,2005.25(15):67- 73.
[2]LEE K Y.YANG F F.Optimal Reactive Power Planning Using Evolutionary Algorithms[J].1EEE Transactions on Power Systems,1998.13(1 ):101-108.
[3]王建学,王锡凡,陈皓勇,等.基于协同进化法的电力系统无功优化[J].中国电机工程学报,2004,24(9):124-130.
[4]崔挺,孙元章,徐箭,等.基于改进小生境料子群算法的电力系统无功优化[J].中国电机工程学报,2011,31(19): 43-50.
[5]程浩忠.基于遗传算法的电力系统无功优化[J].上海交通大学学报,1998,32(1):127-130.
[6]朱庆军.基于改进PSO算法的电力系统无功优化研究[D].燕山:燕山大学,2009.
[7]王振树,李林川,李波.基于粒子群与模拟退火相结合的无功优化算法[J].山东大学学报,2008,38(6):15-20.
[8]SERGIO G.Optimal Reactive Dispatch Through Interior Point Method[J].IEEF Transactions on.1994,9(1):136- 142.
[9]石佳川.基于模糊评价的配电网络多目标无功优化研究[D].山东:山东大学,2007.
小生境粒子群算法 第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篇
对社会性动物的自组织行为进行数学建模并用计算机进行仿真称为群智能算法, 其作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点。目前, 群智能理论研究领域主要有两种算法:蚁群算法 (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期.
蚁群粒子群混合算法研究 第7篇
1 蚁群、粒子群算法
1.1 基本蚁群算法
蚁群算法(Ant Colony Algorithms)是一种源于大自然中生物世界的新的仿生类算法，作为与遗传算法同属一类的通用型随机优化方法，它根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索的模型，在一系列困难的组合优化问题求解中取得了卓有成效的结果。与遗传算法类似,蚁群算法不需要任何先验知识,最初随机的选择搜索路径，随着对解空间的了解，搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间
基本的蚁群算法AS可以简单表述如下：在0时刻进行初始化过程，蚂蚁放置在不同的城市，每一条边都有一个初始外激素强度值τij(0).每一只蚂蚁禁忌表的第一个元素置为它的开始城市.然后，每一只蚂蚁从城市i移动到城市j，依据两个变量的概率函数选择移动城市(包括参数α和β)).在n次循环后，所有蚂蚁都完成了一次周游，同时他们的禁忌表将满，这时，计算每一只蚂蚁k的路径长度Lk，ΔτkijΔ依据公式(3)更新.而且，保存由蚂蚁找到的最短路径(即minLk,k=1,…,m)，置空所有禁忌表.重复这一过程直到周游计数器达到最大(用户定义)周游数maxNc，或者所有蚂蚁都走同一路线.后一种情况被称为停滞状态.如果算法在Nc次循环后结束，蚂蚁算法的复杂度为o(Nc·n2·m).信息素更新公式：
其中，ρ是一个参数，1-ρ表示在时刻t和t+n之间外激素的蒸发，
Δτkij是单位长度上在时刻t和t+n之间第k只蚂蚁在边e(i,j)留下的外激素的数量,其中,
如果在时刻t和t+n之间第k只蚂蚁在边e(i,j),其他Q是一个常数，Lk是第k只蚂蚁周游的路程长度.
第k只蚂蚁从城市i到城市的跃迁概率为
其中准，N为一组城市，tabuk表示第k只蚂蚁的禁忌表，α和β都是控制外激素与可见度的相对重要性的参数.跃迁概率是可见度和t时刻外激素强度的权衡。
1.2 粒子群算法
粒子群优化算法(particle swarm optimization PSO)是基于群体智能的一种进化计算，由Eberhart博士和kennedy博士发明。粒子群优化算法也是基于人口的最优化方法，该方法是随机产生一组数据，然后执行最佳收索路径，粒子群优化算法在运算过程通过其中最好的粒子找到最佳的解决方案。粒子群优化算法有较好的后台计算智能，而且运算更加简单，依照它的优势，粒子群优化算法不仅适用于科学研究，而且还适用于工程应用，目前粒子群优化算法在进化计算领域中已经吸引了众多人的注意，近几年来，有很多关于粒子群优化算法的研究成果，粒子群优化算法已经被广泛地应用于最优化、人工神经网络、仿生识别、模糊控制和其它一些领域[2]。
PSO中每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数昕决定的适应值，对于每个粒子，还有一个速度决定它们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪2个“极值”更新自己，一个是粒子本身所找到的最优解，称为个体极值pbest;另一个极值是整个种群目前找到的最优解，该极值是全局极值gbest。另外，也可以不用整个种群而只用其中一部分为粒子的邻居，那么在所有邻居中的极值就是局部极值。在找到这两个最优值时，每个粒子根据如下公式更新白己的速度和新的位置：
其中：vk为第k步粒子的速度向量;xk为第k步粒子的位置;pbestk为第k步粒子本身所找到的最好解的位置：gbestk为第k步整个种群目前找到的最好解的位置：w表示惯性权重：c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长，c1,c2通常在0～2间取值;r1奂(0,1)，r2奂(0,1)为2个相互独立的随机函数;每一个维粒子的速度都被限制于一定范围内，即vk[-vmax,vmax]如果v1>vk时，vk=vmax;如果v1<-vk时，vk=-vmax。
2 混合算法
蚁群粒子群混合算法，在众多的领域中应用价值得到越来越多的体现，其在解决旅行商问题、聚类问题、函数连续优化问题以及实际应用领域如电力系统等的运算效率及与其他算法的仿真实验证实其优越性。
2.1 蚁群粒子群混合算法求解旅行商问题
蚁群算法利用了信息素进行传递信息，而粒子群优化算法利用了本身的信息，个体极值信息和全局极值信息三个信息，来指导粒子下一步迭代位置。混合的特性是让蚂蚁也具有粒子的特性，首先蚂蚁按照蚁群算法，先完成一次遍历，再让蚂蚁根据局部最优解和全局最优解进行调整，思路如下：对于旅行商问题，其当前的位置是基本路径，让当前解与个体极值和全局极值做做交叉操作，产生的解为新的位置，再做变异操作。交叉变异参考：蚁群算法应用及其他算法混合[3]。检验算法有效性,与模拟退火算法、遗传算法分别解决30个城市的Oliver30，结果表明混合算法的效果最好，算法可以显著提高计算效率，具有较大的是使用价值。
2.2 蚁群粒子群混合算法求解聚类问题
周丽娟的改进的粒子群算法和蚁群算法混合[4]在文本聚类问题中取得了很好的效果。该方法主要思想是:
第一步,利用粒子群算法有效的全局搜索特性,对文本进行粗聚类,可以得到聚类原型,这里对精度不做要求,只要得到聚类原型处于最优解的附近邻域即可;
第二步,在第一步得到的聚类原型上的基础上,利用蚁群算法精确求解得到最优聚类
在改善基本粒子群算法的收敛性能方面,引用了Y.Shi和R.C.Eberhart首次在速度进化方程中引入惯性权重[1],即
其中,0<ω<1称为惯性权重,因此,基本粒子群算法是惯性权重ω=1的特殊情况。惯性权重ω使得粒子保持运动惯性,具有扩展空间的趋势,有能力探索新的区域,用来平衡全局搜索能力和局部搜索能力。
2.3 广义蚁群粒子群算法求解电力系统经济负荷分配问题
侯云鹤等人将PSO引入GACO的局部搜索中[5]，采用GACO进行全局搜索，确定最优解存在的邻域，通过PSO实现局部搜索，由于PSO算法充分利用以往的信息，又不依赖于梯度，可实现非凸空间上的高效搜索，在实际计算中比蒙特卡罗法J具有更高的精度和更快的速度。GACO与PSO的结合算法在保证算法全局收敛的前提下，提高了优化的效率和精度。
对于一般的约束优化问题，采用外点法构造辅助函数，将较难计入可行域的l0个等式约束和U0个不等式约束以罚函数形式计入目标函数中，即
式中X=(x1,x2,…,xn)T为待优化矢量;l、u分别为原等式约束和不等式约束的个数。为加速迭代，使罚系数σi与当前迭代次数K有关，开始时较小，这样有助于大范围搜索，再逐步增大，使最终结果成为原问题的解。记式(8)的可行域为S。
式中α为正系数，用于调节σi的变化速度;σi,max为σi(K)的上限值;T为迭代次数上限值。
经试验广义蚁群与粒子群结合算法与粒子群算法及改进进化规划算法相比，收敛精度更高，解的离散度更小。将粒子群算法应用于广义蚁群算法的邻域搜索中，在确保广义蚁群算法的全局收敛性的同时，也提高了算法的优化效率，该方法还可求解常规算法难以解决的非凸、非线性约束优化问题。在提供最优解的同时，还可提供一组次优解以供选择，且容易实现并行运算。
2.4 混合算法解决函数连续优化问题
薛嘉等首先对解空间进行区域划分[6]，进而利用ACO在优化初期具备的快速收敛性能，在整个解空间内搜索最优解的敏感区域。然后利用蚁群的搜索结果初始化PSO粒子，利用PSO快速和全局收敛性进行所在小区域内的搜索。种群更新时根据蚁群的拓扑结构和小区域间的阶跃规则，蚁群不断向最优解敏感区域聚集，使得敏感区域内粒子数增加，则局部的PSO搜索策略可以更细密的搜索最优。实例结果表明，CA-PSO既能保证解的分布性与多样性，又避免了在多峰值函数寻优过程中陷入局部最优解而停止运算，最终将收敛到全局最优解。
2.5 主从递阶结构的蚁群粒子群求解算法
张维存,康凯提出一种主、从递阶结构的蚁群粒子群求解算法[7]。算法中,主级为蚁群算法,完成任务模式选择;从级为粒子群算法,完成主级约束下的任务调度。然后,以工期最小和资源均衡分配为目标设计蚂蚁转移概率、模式优选概率和任务优选概率。最后,针对PSPLIB中的测试集对算法主要参数进行优化,并通过与其他算法比较验证了算法的有效性。仿真和比较表明,该算法具有良好的求解性能和应用前景。
3 结束语
蚁群算法在求解复杂优化问题特别是离散优化问题方面已经显示出了优势，具有较强的鲁棒性和搜索较好解的能力，易与其他算法结合。粒子群优化算法PSO具有并行处理、鲁棒性好和计算效率高等特点,已成功应用于各种复杂的优化问题。而二者结合的蚁群粒子群混合算法在解决旅行商问题的仿真实验表明，混合算法的优化质量和效率都优与模拟退火算法、传统蚁群算法和遗传算法进行比较，接近理论最佳值，混合算法效果较好;在解决连续优化问题、电力系统经济负荷分配、非凸、非线性约束优化问题等方面，都有很好的效果，当然混合算法的研究还处于初级阶段，蚁群算法、粒子群算法在各自的改进算法在优越性方面又有所提升，而针对改进算法的混合算法还有很大的探索空间，其理论依据、收敛性等方面还有待进一步的研究。
参考文献
[1]李炳宇,萧蕴诗.一种基于粒子群算法求解约束优化问题的混合算法[J].控制与决策,2004(7):804-812.
[2]Shi Y,Eberhart R C.A modified particle swarmoptimizer[C].//Proceedings of the IEEE Congress on Evolutionary computation.Piscat-away:IEEE Press,1998:3032-3081.
[3]高尚,韩斌,吴小俊,等.求解旅行商问题的混合粒子群优化算法[J].控制与决策,2004,19(11).
[4]周丽娟.改进粒子群算法和蚁群算法混合应用于文本聚类[J].长春工业大学学报2009,30(3):341-345.
[5]林昭华,侯云鹤,熊信艮,等.广义蚁群算法用于电力系统无功优化[J].华北电力人学学报,2003,30(2):6-9.
[6]薛嘉,蔡金燕,马飒飒,等.基于群智能的连续优化算法研究[J].计算机工程与设计,2009,30(8):1969.
粒子群优化算法简介 第8篇
由于认识到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.
粒子群算法研究概述 第9篇
随着通信技术、计算机技术与人工生命技术的发展和成熟, 使得具有收敛快, 计算应用强, 应用领域广等优点的人工智能算法在各个领域开始扮演重要的角色。人工智能算法通过模拟各种自然界里的生物行为, 通过利用仿生学的各种知识, 进行计算模拟, 来得到各种计算所需的最优解。正是由大量的计算组成的工业生产体系, 使得人工智能算法其价值在于可以实时计算, 处理网络分布区域内的各种环境和监测对象的信息, 并对这些信息进行处理, 获得所要的最佳处理数据, 并将信息传递给用户。在人工智能算法领域里, 粒子群算法因其独特魅力受到广泛关注。
由于粒子群算法具有搜索速度快、效率高, 算法简单等优点, 使其容易被工业生产应用或者应用于人工智能领域, 提高了粒子群算法提供服务的质量。阿尔伯特.爱因斯坦曾说过“当数学原理用于现实时, 是不确定的, 当他们确定时, 又不适用于现实”。近年来, 国内外对于人工智能算法及其应用技术的研究日趋热烈, 也取得了丰富的研究成果。本文从粒子群算法和其发展方向介绍了人工智能算法的研究进展。
1 粒子群算法分析概述
粒子群算法的产生是科学家采用了仿生学的相关概念, 它通过模仿自然界里动物的行为来寻找最优解.
1.1 粒子群算法的产生模型
粒子群算法是由鸟群的捕食行为来得到启发而发展起来的智能算法。整个算法通过模拟这样一个自然场景:一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远, 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。
1.2 粒子群算法的原理
粒子群算法从这种模型中得到启示并用于解决优化问题。粒子群算法中, 每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值 (fitness value) , 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
粒子群算法初始化为一群随机粒子 (随机解) 。然后通过迭代找到最优解。在每一次迭代中, 粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解, 这个解叫做个体极值p Best。另一个极值是整个种群目前找到的最优解, 这个极值是全局极值g Best。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居, 那么在所有邻居中的极值就是局部极值。
粒子群算法通过不断更新适应度值, 对每个d维 (任务的数量) 的粒子进行每一维度的赋值, 对粒子群赋值 (包括position vector and velocity vector) , 粒子在d维 (任务的数量) 空间中所经历过的最好位置, 通过计算更新粒子速度和位置信息, 更新个体粒子的最优解, 进行粒子更新操作, 全局搜索想要的结果, 最后通过比较获取种群中的最优解。
在整个粒子群算法里, 通过化抽象为具体, 将实际生活里的运动转化为代码里的更新, 计算完成时间, 局部最优解, 当然也使用了ETC[i][j], 在算法实现过程中还应计算时间矩阵ETC[][], 为ETC[i][j]=work Load[i]/computing Power[j], 此时通过抽象, i, j被赋予了不同的意义, 更切合粒子群优化算法的意义。并且不断利用提前定义好的数学公式进行粒子更新操作, 更新粒子速度和位置信息。同时在计算里也可以找到最好的迭代次数, 通过比较大小, 最好的迭代次数就是当前最优解的迭代次数, 然后利用该值进行相应操作, 比如更新惯性系数, 最后把每次迭代的最优解进行排序, 得到相应的处理结果。在计算机里, 通过给参数赋予不同意义, 可以抽象出鸟的数目 (粒子群大小) , 离食物的距离, 速度, 鸟的位置 (鸟的任务) 等与实际生活相对应的算法, 体现了计算机世界的奇妙以及与实际生活的联系。
1.3 粒子群算法的计算流程
粒子群优化算法是通过个体之间的协作来寻找最优解, 它利用了生物群体中信息共享会产生进化优势的思想。
通过上文描述, 可以知道粒子群算法的计算流程图为:
2 粒子群算法的发展方向
粒子群算法应该与机器学习和数据挖掘紧密地联系在一起。
机器学习涉及了计算机如何模拟和实现人类的学习行为, 利用已经获取的新的知识和技能, 组织知识结构, 来不断改善自身的性能和工作能力。并且机器学习的目的就是预测性能更好的算法, 它可以自我学习, 提高自身的预测性能, 这一点与粒子群算法不谋而合。粒子群算法通过和机器学习的结合可以使自己的优点得到发挥, 通过粒子群算法的搜索能力可以使机器的自学习能力增强, 通过智能的搜索方法, 可以准确定位所需资源并且可以优化配置资源。机器学习使用了各种算法, 优化了计算模型, 粒子群算法应用于机器学习中, 可以快速地获取当前需要的知识。
在数据挖掘中, 需要综合使用结果, 要综合使用到数据库, 人机交互, 统计分析等技术, 而通过和粒子群算法的结合, 可以用来快速分析数据。而且数据挖掘本身需要用到很多算法, 并且把它们结合起来在广大的数据网里面得到自己所需的信息, 而粒子群算法可以加速这个过程, 通过有效率的计算来保障结果的正确性和搜索的快速性。数据挖掘会从数据本身挖掘信息, 这种发现潜在信息的方式往往会通过算法来实现, 粒子群算法可以给数据挖掘带来一种不同的发现隐藏信息的方式。
3. 结束语
本文主要分析了粒子群算法原理及其流程, 并且提出粒子群算法的发展方向, 粒子群算法应该与机器学习和数据挖掘紧密地联系在一起的思想, 以及粒子群算法在这两个尖端领域里可以起到的作用。由于只是从理论上对这个发展方向进行客观分析, 缺少实践去验证。而粒子群算法在以后的工作研究中会更有利于推动国家高性能的计算发展。随着经济、生产生活和科技研发等方面对高性能的计算越来越多的依赖, 人工智能算法的夏天正慢慢走来。
参考文献
[1]Pinel, F., Pecero, J., Bouvry, P., and Khan, S.U.:“Memory-aware Green Scheduling on Multi-core Processors, ”in 39th IEEE International Conference on Parallel Processing (ICPP) , pp.485╞488, USA, 2010.
[2]Xhafa, F., Abraham, A.:“Computational modelsand heuristic methods for grid scheduling problems”, Future Generation Computer Systems, vol.26, pp.608╞621, 2010.
[3]Zomaya, A.Y.:“Energy-Aware Scheduling and Resource Allocation for Large-Scale Distributed Systems”, in 11th IEEE International Conference on High Performance Computing and Communications (HPCC) , Seoul, Korea, 2009.
[4]Ali, S., Siegel, H.J., Maheswaran, M., and Hensgen, D.:“Task execution time modeling for heterogeneous computing systems”, Proceedings of Heterogeneous Computing Workshop, pp.185╞199, 2000.
非线性粒子群算法 第10篇
粒子群算法也称为微粒群算法,是一种简单实用的智能计算方法,在许多领域有着广泛的应用。为了提高算法效率本文提出了一种新型的粒子群算法,非线性粒子群算法。该算法在计算粒子速度时采用了非线性计算公式。仿真计算表明,与标准粒子群算法相比,只要选择了适当的非线性项,非线性粒子群算法收敛速度更快。
1标准粒子群算法
粒子群算法(PSO)是一种模拟鸟群飞行的人工智能算法。在粒子群算法中,每个个体被称为粒子。通过粒子之间的集体协作运动来实现群体最优的人工智能算法。虽然每个粒子的行为准则很简单,但是整体的行为却是非常复杂。在一个具体的空间中,每个粒子均按照全局以及个体的最优值调整自己的速度,通过反复调整使得整体向着最优值靠近。每个粒子包含以下参数:当前位置,历史最优位置,粒子当前速度,当前适应值,历史最优适应值。
设有n个粒子,搜索空间为D维空间,则每个粒子按照以下公式调整自己的速度和位置:
v
x
其中x
粒子群算法的实际计算步骤如下:第一步:初始化速度和位置,对每个粒子的速度和位置初始化;
第二步:计算每个粒子的适应值;
第三步:计算每个粒子自身的最优值;
第四步:计算整个粒子群的最优值;
第五步:更新每个粒子的速度和位置;
第六步:判断是否满足结束条件(例如最大迭代次数或者找到理想的适应值),是则计算结束,否则转向第二步。
粒子的适应值根据事先设定的适应值函数进行计算,用于描述粒子位置的优劣,而适应值函数与要解决的具体问题有关。在计算函数的最值时,适应值就是粒子在具体坐标点的函数值。
2非线性粒子群算法
标准的粒子群算法采用线性函数调整粒子的速度和位置,为了提高算法效能,本文提出了非线性粒子群算法。非线性粒子群算法就是采用非线性计算公式来代替公式(1)。非线性粒子群算法的公式一般形式如下
v
x
如果至少有一个fij(pj-x
非线性粒子群算法具有以下特点:
(1)整个群体至少存在一个非线性计算公式;
(2)对于每个粒子以及粒子的速度分量,公式(3)可以彼此不同,这样每个粒子的速度调整公式也可以彼此不同。
最直观的非线性粒子群算法为
v
x
公式(5)中a、b至少有一个不等于1。显然公式(1)是公式(5)的特殊形式。在公式(5)中每个粒子的速度分量按照同样的非线性函数进行调整。
采用公式(5)进行计算需要注意非线性项的情况,由于a、b至少有一个不等于1,因此在实际编程中需要注意可能出现负数开偶数次方根号的情况,需要根据具体情况采用不同的计算公式。
3数值计算仿真
本文对非线性粒子群算法给出仿真实验。以下按照公式(5)、(6)对应的非线性粒子群算法给出仿真实验。在下面的例子中用N表示粒子数,w表示权重表达式,M表示最大迭代次数,c1、c2表示学习因子,xmin、xmax分别表示求解范围的下限和上限,即xmin≤xi≤xmax。
例1:求解下列线性方程组:
本例的精确解为: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.1×k/499。计算结果如表1～表3所示。
从上面的计算结果可以看出,非线性粒子群算法的收敛速度快于标准粒子群算法.
例2:求解下列Beale函数
f(x,y)=(1.5-x+xy)2+(2.25-x+xy2)2+(2.625-x+xy3)2
在-4.5≤x,y≤4.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.1×k/499,N=20。
计算结果见表5-表8。
从上面的计算结果看出,非线性粒子群算法的平均迭代次数小于标准粒子群算法。
采用(5)、(6)给出的非线性粒子群算法进行计算,需要注意a、b的选择,如果a、b选择不当,可能会出现收敛缓慢甚至不收敛的情况发生。按照本文的作者的初步研究,当a=b时,a、b的值不能离1太远,否则便不能做到快速收敛。
4结束语
非线性粒子群算法是一种新的粒子群方法,从仿真实验的情况看只要选择适当的非线性项,就能做到快速收敛。关于非线性粒子群算法需要研究的内容很多,例如如何选择非线性函数,非线性项函数中参数如何选择,参数的选择与粒子群大小的关系等等。关于这方面的内容值得深入研究。
摘要：提出了一种新型的粒子群算法—非线性粒子群算法,给出了计算公式并进行了实验模拟。非线性粒子群算法采用非线性计算公式调整粒子速度。由于非线性计算公式的多样性,因此可以构建种类繁多的具体的非线性粒子群算法。非线性粒子群算法一方面保持了标准粒子群算法的简单性,同时也具有更强的搜索能力。实际计算表明,只要能够选好非线性项中的参数,就可以提高算法的效率。
关键词：标准粒子群算法,非线性粒子群算法,线性方程组,Beale函数
参考文献
[1].纪震,廖惠联,吴清华.粒子群算法及其应用.北京:科学出版社,2009.
[2].段晓东,王存睿,刘向东.粒子群算法及其应用.沈阳:辽宁大学出版社,2007.