自适应权重粒子群算法

2024-08-17

自适应权重粒子群算法（精选7篇）

自适应权重粒子群算法篇1

0 引言

粒子群优化PSO是由Kennedy和Eberhart等人提出的一类模拟群体智能行为的优化算法。其思想来源于对鸟群捕食行为的研究,与遗传算法和蚁群算法相比,PSO容易实现并且可调整参数较少,因此被广泛应用。

文献[1,2,3]指出,目前PSO的研究主要集中在三个方面:一是算法的改进研究;二是算法的性能分析;三是算法的应用研究。而算法的性能分析主要针对参数不同取值组合对算法性能的影响。惯性权值是粒子群算法最重要的可调整参数之一。文献[4]指出较大的权值有利于提高算法的全局搜索能力,而较小的权值会增强算法的局部搜索能力。为了找到一种能在全局搜索和局部搜索之间取得最佳平衡的惯性权值选取方法,研究人员进行了大量的研究工作,先后提出了线性递减权值(LDIW)策略、模糊惯性权值(FIW)策略和随机惯性权值(RIW) 策略。而已有的搜索策略都是将粒子群看作一个整体来调整惯性权重,没有考虑到不同适应度的粒子需要不同的惯性权重,忽视了问题复杂度和群体规模等重要因素。本文分析了PSO算法中的惯性权重与种群规模、粒子适应度以及搜索空间维度的关系,把粒子惯性权重定义为这三者的函数,并结合动态管理种群的策略提出了改进的粒子群算法。新算法在每次迭代后根据当算法搜索状态更新每个粒子的惯性权重,实现了自适应调整全局搜索与局部搜索能力。通过与LDIW、 FIW 、RIW等调整算法在常用多峰测试函数上的实验结果证明,新算法具有较强的全局寻优能力与较高的搜索效率。

1 经典粒子群算法

PSO算法是一种进化计算技术,源于对鸟群捕食的行为的模拟。搜索空间中每个粒子代表一个可能解,粒子在解空间中移动的过程就是搜寻最优值的过程。所有的粒子都有一个表示当前在解空间中位置的属性Xi=(xi1xi2,… ,xin),根据粒子当前位置会产生一个粒子适应度以反映粒子位置即解的优劣。每个粒子还有一个速度向量Vi=(vi1,vi2,…,vin)决定其运动的方向和运动的快慢。首先粒子群初始化为一群随机粒子(随机解),然后通过迭代来寻找最优解。在每一轮的迭代中,粒子通过速度更新当前位置,并通过适应值函数计算出其适应度,然后根据式(1)更新其当前速度:

Vi=ωVi+c1×rand()×(Pbesti-xi)+

c2×rand()×(Gbest-xi) (1)

接着用式(2)更新粒子位置Xi:

Xi=Xi+Vi (2)

其中Pbesti表示粒子i的个体最优值,即粒子i目前为止在搜索空间中到过的最佳点,Gbest表示整个粒子群的全局最优值,即整个粒子群到目前为止在搜索空间中到过的最佳点。C1 和C2是两个正常数,称为学习因子。 rand() 表示0 到1之间的随机数。另外,ω称为惯性因子,ω值较大,全局寻优能力强,收敛较慢;反之局部寻优能力较强,收敛较快。

2 惯性权重调整策略

惯性权重ω是PSO算法中调整全局搜索与局部搜索的最重要参数。文献[4]指出,较大的惯性权重有利于全局探索,但效率较低;较小的惯性权重能够加速算法的收敛,但是容易陷入局部最优。如何设置合理的惯性权重,是避免陷入局部最优并高效搜索的关键。在实际问题背景下,惯性权重如何设置,要同时分析众多因素和当前搜索状态。其中,粒子适应度、种群规模以及搜索空间维度是表征当前搜索状态的重要参数。下面分别定性分析这三者与惯性权重的关系。

粒子适应度是反应粒子当前位置优劣的一个参数。对于某个具有较高适应度的粒子Pi,在Pi所在局部区域可能存在能够更新全局最优的点Px,即Px所表示的解优于全局最优。为使全局最优能够迅速更新,迅速找到Px,应当应减小粒子Pi惯性权重以增强其局部寻优能力;而对于适应度较低的粒子,当前位置较差,所在区域存在优于全局较优解的概率较低,为了跳出当前的区域,应当增大惯性权重,增强全局搜索能力。

种群规模是决定粒子对搜索空间覆盖程度关键因素。种群规模较大时,种群多样性较高,粒子所在区域覆盖全局最优解的概率较大,则应该减小惯性权重,提高局部搜索能力,实现快速收敛于全局较优;种群规模较小时,尤其对于多峰函数,粒子通常不能有效覆盖整个搜索空间,则应该增大惯性权重,提高全局搜索能力,避免陷入局部最优。

由文献[5]可知,当搜索空间维度较大并且问题较复杂时,PSO常常收敛过早,很容易陷入局部最优。如何根据不同复杂程度的问题背景,在搜索效率和寻优能力之间寻求较好平衡极为重要。对于具有高维度搜索空间的复杂问题,应该减小惯性权值以提高全局搜索能力,避免过早收敛陷入局部最优。相反,当搜索空间维度较少时,应该增大惯性权值实现快速收敛以提高搜索效率。

由以上分析可知,粒子适应度、种群规模以及搜索空间维度与惯性权重有密切关系,可根据这些参数的值实现自适应调整惯性权重。式(3)将惯性权重定义为粒子适应度、种群规模以及搜索空间维度三者的函数:

$ω_{i} = \frac{1}{a F_{i} / (D \times \sum_{i = 1}^{i = n} F_{i}) - \exp (- n / b) + 1} (3)$

其中ωi表示第i个粒子惯性权重,Fi表示第i个粒子适应度,D表示搜索空间维度,n表示粒子数目,a、b为经验参数。算法在每次迭代后通过式(3)更新所有粒子的惯性权重,从而实现了对局部搜索和全局搜索的能力自适应调整。

3 动态管理种群策略

在PSO算法的某一次迭代中,如果有部分粒子位置不佳,致使其Pbesti连续多次没有更新,这些粒子当前所在位置较差,并不能为Gbest的更新作出贡献,为提高算法搜索效率,可以把这些粒子删除。相反,如果Gbest连续多次没有被更新,此时粒子群体可能陷入局部最优,需要增加粒子来增加启发信息,加快Gbest的更新。因此,提出动态种群管理策略,具体描述如下:

1) 当Gbest连续s次没有改变,说明现有种群需要新的粒子来提供启发信息,则动态添加一个粒子,并用个体最优Pbesti更新最频繁的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度;

2) 当Gbest连续s次改变,说明现有种群启发信息已经充足,为提高算法运行效率,则动态删除Pbesti更新最不频繁的粒子。

4动态管理种群的自适应惯性权重粒子群算法描述

根据上述分析,提出动态管理种群的自适应惯性权重粒子群算法—DSAPSO,算法描述如下:

DSAPSO (D, MAX,MIN,K, Pn,s)

输入:求解空间维度D,粒子数目上限MAX,粒子数目下限MIN,初始粒子数目Pn,粒子动态管理敏感指数s。

输出:问题的解。

步骤:

(1) 随机生成Pn个粒子的初始位置及初始速度;

(2) 计算粒子适应度Fi,更新个体最优Pi及全局最优Pg;根据式(3)计算粒子惯性权重ωi;

(3) 根据粒子适应度更新个体最优Pi及全局最优Pg;

(4) 根据式(1)更新粒子速度,根据式(2)更新粒子位置;

(5) 动态管理种群:

① 当Gbest连续s次改变,且Pn>MIN,则动态删除Pbesti更新最不频繁的粒子。

② 当Gbest连续s次没有改变,且Pn<MAX,则增加一个粒子,用Pbesti更新最频繁的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度。

③ 当Gbest连续s次没有改变,且Pn=MAX,则删除Pbesti更新最不频繁非全局最优粒子,然后动态添加一个新的粒子,并用Pbesti频繁被更新的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度。

(6) 若达到结束条件则结束,否则返回(2)。

算法整体采用动态管理种群策略,并在每一次迭代中计算式(3),分别更新每个粒子的惯性权重。

5 实验结果以及分析

5.1 实验环境以及实验参数设置

在实验中,取粒子群规模MAX为30,MIN为5,其他算法粒子数目固定为30;设置c1=c2=2 。实验选取了六个不同特点的常用测试函数,如表1所示。其中,Sphere为简单的单峰函数, 在原点达到极小值;Rosenbrock为非凸的病态函数,在xi=1时达到极小值;Griewank在xi=0时达到全局极小值,当xi=±kπ i(i=1,2,…,n,k=1,2,…,n)时,达到局部极小值;Schaffer’f6的全局极大值在(0,0),它的全局最优点被次优点所包围;Rast rigrin为多峰函数, 当xi=0时达到全局极小值,在其周围存在多个局部极小点;其中,维数是各个函数求值的空间维度D,目标值是算法结束条件,即算法搜索到的解所必须达到的值。

5.2 实验方案

采用本文提出的DSAPSO算法与下面三种惯性权重调整算法进行比较:惯性权重线性下降的标准粒子群算法LWPSO (文献[5]) 、随机惯性权重粒子群算法RWPSO(文献[6])以及带压缩因子的粒子群算法CFPSO(文献[7])。对于四种不同算法,采用两种方案进行试验:方案一是固定迭代次数为1000次,计算每种算法运行结果的平均值;方案二是确定每个函数的优化目标值,计算每种算法的评价迭代次数,超过5000次记为无穷大。每种方案独立运行10次计算结果平均值。

5.3 实验结果汇总

表2统计了固定迭代次数为1000次时,四种算法求解的平均值和最差的一次求解结果。表3统计了四种算法搜索到表1中对每个函数预订的目标值时,迭代的次数和所用的时间(单位:秒),如果迭代次数超过5000,则将次数和时间都计为无穷大。图1记录DASPSO算法在Sphere函数上求解时,PSO粒子数目随迭代次数的变化。

5.4 实验结果分析

从表2中可以看出,本文提出的DASPSO算法,由于惯性权重选择较为恰当,全局寻优能力较强,在五个函数上求解普遍优于其他算法,而且最差解与平均解相差不大,较为稳定。RWPSO 算法采用随机策略,增加种群多样性,在对多峰函数优化上算法取得不错的结果;但对单峰Sphere函数效果较差,其主要原因算法在后期仍然采用随机惯性赋值策略,没有增强局部搜索能力,很难收敛到较优解。表2比较了四种算法的全局寻优能力与收敛速度。可以看出,DASPSO算法迭代次数与所用时间远少于其他算法。这是由于在迭代过程中,动态删除部分无效粒子并不断补充新粒子,粒子数目一直少于其他算法,但每个粒子都非常活跃,全局最优更新非常快。图1记录了在Sphere函数上搜索时粒子数目的变化折线图,可以看出,在搜索过程中粒子数目很少达到30,较少的粒子减少了计算粒子适应度以及粒子移动等时间开销,极大地提高了搜索效率。

6 结语

惯性权重是决定PSO算法全局寻优与局部寻优的重要参数。本文提出了根据搜索状态在一种每次迭代后自适应调整惯性权重,进而更好地平衡全局搜索和局部开发的改进PSO算法。改进的算法采用了动态管理种群策略,极大地提高了搜索效率。新算法与LDIW、 FIW 、RIW等调整算法在常用多峰测试函数上的实验结果证明,新算法具有较强的全局寻优能力与较高的搜索效率。

摘要：为较好平衡粒子群算法中全局搜索能力与局部搜索能力,分析了PSO(Particle Swarm Optimization)算法中的惯性权重与种群规模、粒子适应度以及搜索空间维度的关系,并把粒子惯性权重定义为这三者的函数。通过在每次迭代后更新每个粒子的惯性权重,实现了自适应调整全局搜索能力与局部搜索能力,并结合动态管理种群的策略提出了改进的粒子群算法。通过在多个常用测试函数上与已有惯性权重调整算法测试比较,证明新算法具有较强的全局寻优能力与较高的搜索效率。

关键词：粒子群算法,自适应惯性权重,种群规模,搜索空间维度,粒子适应度,动态管理种群

参考文献

[1]Angeline P J.Using selection to improve particle swarm optimization[C]//IEEE International Conference on Evolutionary Computation.Anchorage,Alaska,USA,2007:84-89.

[2]Jacques Roget,Jacob SVesterstr.A Diversity guided Particle Swarm Op-timizer,the ARPSO[R].Technical Report No.2002202,2008:65-69.

[3]Shi Y,Eberhart R.A modified particle swarm optimizer[C]//IEEEWorld Conf on Computational Intelligence.Piscataway:IEEE,2005:69-73.

[4]Zhang L P,Yu H J,Hu S X.A new approach to improve particle swarmoptimization[C]//Lecture Notes in Computer Science.Chicago:Springer2Verlag,2006:134-139.

[5]盛跃宾,陈定昌,等.有等式约束优化问题的粒子群优化算法[J].计算机工程与设计,2006,27(13):25-29.

[6]刘洪波,王秀坤,谭国真.粒子群优化算法的收敛性分析及其混沌改进算法[J].控制与决策,2006,21(6):636-640.

[7]韩江洪,李正荣,魏振春.一种自适应粒子群优化算法及其仿真研究[J].系统仿真学报,2006,18(10):2969-2971.

[8]Salomon R.Reevaluating genetic algorithm performance under coordi-nate rotation of benchmark functions[J].BioSystems,1996,39:263-278.

自适应权重粒子群算法篇2

基于群体智能理论的计算技术的研究成为了近几年研究的热点, 蚁群算法、粒子群优化算法、混合蛙跳算法等等都是基于群体协作的搜索算法。粒子群优化算法[1,2] (particle swarm optimization, PSO) 是由Kennedy和Eberhart于1995年提出的一种全局优化算法。相对于其他算法而言, PSO算法原理比较简单, 需要调节的参数较少, 容易实现, 而且PSO算法中的粒子具有记忆功能, 可以保留局部最优和全局最优信息, 协同搜索最优解。不过PSO算法也存在着缺点, 由于它收敛速度快, 容易陷入局部最优, 在进化后期, 由于种群多样性的减少, 搜索精度逐渐降低。

针对以上PSO算法的缺点, 研究人员提出了各种改进的方法。Shi等[3]将惯性权重引入了速度的更新公式中;Van den Bergh等[4]提出了合作粒子群算法, 引入多种群等等。在本文中, 通过借鉴遗传算法[5]的特点及合理平衡算法的搜索能力, 提出了一种新的改进的混合粒子群算法, 即基于交叉和自适应权重的混合粒子群优化算法。

1 基本粒子群优化算法

PSO算法是源于鸟的捕食行为, 将每个待优化问题的解都看成是空间中的一只鸟, 并抽象成一个粒子, 每个粒子有一个初始的位置和速度, 并有一个由被优化的函数 (即适应度函数) 决定的适应值, 粒子的优劣由此适应值决定。

PSO算法是通过迭代找到最优解, 但它具有自己独特的搜索方式。首先, 随机初始化一群粒子, 粒子们知道自己目前所处的位置以及目前自己发现的最好位置, 此外粒子还知道此时整个粒子群体中的最好位置。假设在d维搜索空间中的第i个粒子的位置和速度分别是Xi=[xi, 1, xi, 2, …, xi, d]和Vi=[vi, 1, vi, 2, …vi, d], 每一次的迭代过程中, , 粒子是通过两个最优解来更新自己, 一个是粒子本身找到的最优解, 称为个体极值pbest, Pi= (pi, 1, pi, 2, …, pi, d) ;另一个是整个种群目前的最优解, 称为全局最优解gbest, Pg= (pg, 1, pg, 2, …, pg, d) 。粒子根据下面两个公式[3]更新自己的速度和新的位置。

其中, w为惯性权重因子, c1和c2为学习因子, 一般c1等于c2, 通常取值为2。

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

步骤一:随机初始化所有粒子, 粒子的种群规模设为N, 初始化粒子的位置和速度。

步骤二:对种群中的所有粒子进行评价, 将当前各个粒子的位置和适应值存在各粒子的pbest中, 将整个pbest中适应值最优个体的位置和适应值存于gbest中。

步骤三:利用上面的公式 (1) 和公式 (2) 更新粒子的速度和位置。

步骤四:根据适应度函数评价种群中的所有粒子。

步骤五:对于每个粒子, 将其适应值与经历过的最好位置pbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为当前的最好位置pbest保存。

步骤六:将每个粒子的适应值和全局经历的最好位置gbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为全局的最好位置gbest保存。

步骤七:如果达到终止条件, 则停止算法, 输出结果, 否则返回步骤三继续进行搜索。

2 改进的粒子群优化算法

2.1 交叉因子

在粒子群优化算法中, 整个搜索的过程是跟随当前的最优解的过程, 所以算法可以更快的收敛于最优解, 然而过快的收敛却使算法容易陷入“局部极值”。再者, 由于粒子群优化算法不同于遗传算法、差分进化算法[6]等群体进化算法有交叉和变异操作来作用于个体, 以产生一个新的种群, 从而维持种群的多样性。粒子群优化算法在种群多样性降低的情况下搜索精度也会降低。为了解决上述问题, 借鉴遗传算法中的交叉的思想, 在算法的每一次迭代过程中, 按照一定的交叉概率选取指定数量的粒子, 将选取的粒子随机两两进行交叉, 产生相同数目的子代粒子, 用新产生的子代粒子替换其父代粒子, 从而产生新一的种群。

子代粒子的位置可以由下面公式得出:

child (x) =p*parent1 (x) + (1-p) *parent2 (x)

或child (x) = (1-p) *parent1 (x) +p*parent2 (x)

p为0～1之间的随机数。

子代粒子的速度由下面公式计算得出:

undefined

或childundefined

2.2 自适应权重

粒子群算法的全局探索和局部改良能力的平衡决定了算法的搜索性能, 对于群体智能算法, 其迭代搜索过程可以归纳为社会协作、自我适应和竞争三个基本环节[7]。“自我适应”是指个体主动或者被动的调节自身的状态以便于更好的适应环境。对于粒子群算法而言, 其惯性权重部分即属于粒子的自我适应。如果惯性权重w较大, 有利于跳出局部最小点, 便于进行全局搜索;如果惯性权重w较小, 则有利于算法在当前的范围内进行局部精确搜索。Shi 和Eberhart提出了线性递减的权重[8], 但是这种方法需要反复的试验确定最佳的值, 而且如果在最初搜索阶段找不到最优值, 随着w的减小, 收敛能力增强, 易陷入局部最优。黄轩等[9]提出了随机惯量取值策略, 然而这种方法随机性太强。本文中我们运用非线性的动态权重策略, 即自适应惯性权重。当所有粒子的适应值差异较大时将惯性权重减小, 当所有粒子的适应值趋于一致或趋于局部最优时, 将惯性权重增加。惯性权重w如下表示:

undefined

上述中wmin、wmax分别表示w设为最小值和最大值, f表示粒子当前的适应值, favg和fmin分别表示当前所有粒子的平均适应值和最小适应值。运用上述的方法来设置权重, 当粒子适应值优于平均适应值时其惯性权重较小, 对粒子起到了保护作用, 相反当适应值差于平均适应值时其惯性权重较大, 可以使粒子向较好的区域移动, 有利于向最优解靠近。

2.3 新的混合算法

经过上述方法将基本的粒子群优化算法进行改进, 称改进后的为基于交叉自适应权重混合粒子群优化算法。流程图如图1所示。

改进后的混合PSO的基本步骤如下:

步骤一:随即初始化种群, 初始化所有粒子的初始速度和位置。

步骤二:对种群中的所有粒子进行评价, 将当前各个粒子的位置和适应值存在各粒子的pbest中, 将整个pbest中适应值最优个体的位置和适应值存于gbest中。

步骤三:更新粒子的速度和位置。

步骤四:更新惯性权重w。

步骤七:根据交叉概率将指定数量的粒子进行两两交叉, 产生相同数目的子代粒子, 按照上述的子代粒子的速度和位置公式计算其相应的速度和位置。

步骤八:如果达到终止条件, 则停止算法, 输出结果, 否则返回步骤三继续进行搜索。

3 实验

用Shuber函数来测试改进后的粒子群算法的寻优能力, 并与基本的粒子群算法进行比较。

undefined

该函数存在760个局部极小点, 函数的最小值为-186.7309。

在基本PSO和混合PSO算法中, 将种群大小设为30, c1和c2设为2, 在混合PSO算法中, 杂交概率设为0.9, wmax=1.0, wmin=0.4。将两种算法的迭代次数设为2000, 分别独立运行50次, 得出如表1所示的结果。

4 结束语

本文针对粒子群算法易陷入局部最优及由于种群多样性减少搜索精度不高的特点, 提出了基于交叉机制的自适应权重的混合粒子群算法。通过实验可以看出新的混合的粒子群算法较基本的粒子群算法而言具有更好的寻优能力, 未来的研究工作是深入研究新算法的机理并将其应用到实际的未曾运用到的领域。

参考文献

[1]Kennedy J, Eberhart R C.Particle swarm optimization[C]//Pro-ceedings of the IEEE International Conference on Neural Networks, 1995:1942-1948.

[2]Eberhart R, Kennedy J.Anewoptimizer using particle swarm theo-ry.Proc of the Sixth[C].International Symposium on Micro Ma-chine and Human Science, Nagoya, Japan, 1995:39-43.

[3]Shi Y, Eberhart R C.Amodified particle swarm optimizer.[C]//Proceedings of the IEEE CEC.1998:303-308.

[4]Van den Bergh F, Engelbrecht A P.A cooperative approach to par-ticle swarm optimization[J].IEEE Trans.on Evolut.Comput.2004, 8:225-239.

[5]Holland J H.Adaptation in Natural and Artificial Systems[J].AnnArbor:University of Michigan Press, 1975.

[6]Price K, Storn R, Lampinen J.Differential Evolution-A PracticalApproach to Global Optimization[J].Berlin:Springer, 2005.

[7]王凌, 刘波.微粒群优化与调度算法[M].北京:清华大学出版社, 2008:17-19.

[8]Shi Y, Eberhart R C.Empirical study of particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computa-tion, 1999:1945-1950.

自适应权重粒子群算法篇3

关键词：双层规划,自适应粒子群优化算法,分层迭代

1 引言

双层规划研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者,并不直接干涉下层的决策;而下层决策者只需要把上层的决策作为参数,他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时,必须考虑到下层决策者可能采取的策略对自己的不利影响。因此,双层规划是一种NP hard问题,具有一定的复杂性与现实意义。

目前对于双层规划模型通常采用数值仿真计算,以期在合理的时间内获得模型的近似最优解。但是,当前国内外一些学者提出的求解算法或求解方法,都是针对特定的双层规划模型提出的,并且算法的运行效率和收敛精度都不高。本文在分析和借鉴现有的一些较优秀的算法思想的基础上,提出采用自适应粒子群优化算法求解双层规划模型。实验研究表明,本文提出的算法不仅能有效求解双层规划模型,可以获得高质量的全局最优解,而且该算法具有通用性和普遍性,不依赖于具体的双层规划模型。

2 双层规划模型

双层规划模型的基本思想可以用下面的数学模型来描述:

设上层决策者控制的变量为

下层决策者控制的变量为

上层规划的数学模型为:

其中y=y(x)由下层规划求解。

下层规划数学的模型为:

双层规划模型是由以上两个相互关联的子模型(U)和(L)组成,F是上层规划所确定的目标函数,x为上层规划的决策变量,G是对变量的约束;f为下层规划所确定的目标函数,y为下层规划的决策变量,g是对变量y的约束。上层决策者通过设置x的值影响下层决策者,因此限制了下层决策者的可行约束集,而下层决策者的行为反过来又会通过y影响上层的决策,所以下层决策变量y是上层决策变量x的函数,即y=y(x),这个函数一般称为反应函数。

一般来说,求解线性双层规划问题是非常困难的,Jeroslow指出线性双层规划是一个NP-hard问题,Ben-Ayed及Bard对此结论给出了简短的证明;Hallsen对性双层规划是强NP-hard问题给出了严格的证明。后来,Vicente指出,寻找线性双层规划的局部最优解也是NP-hard问题,不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的,它也可能是一个非凸问题,并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。

3 粒子群优化算法模型

3.1 基本粒子群优化算法

粒子群优化算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法,在PSO中,每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解,在每一次叠代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest,另一个极值是整个种群目前找到的最优解,这个极值是全局极值gBest。粒子在找到上述两个极值后,就根据下面两个公式来更新自己的速度与位置:

其中,Vk为迭代第k步粒子的速度,Xk为第k步粒子的位置,pBestk为第k步粒子本身所找到的最优解的位置,gBestk为第k步整个粒子群当前找到的最优解的位置;rand是[0,1]之间的随机数,c1和c2被称作学习因子,通常,c1=c2=2,w是加权系数,一般取值在0.1-0.9之间。

3.2 自适应粒子群优化算法

为了平衡PSO算法的全局搜索能力和局部改善能力,采用非线性的动态惯性权重系数,公式如下:

其中wmax、wmin分别表示w的最大值和最小值,f表示粒子当前的目标函数值,favg和fmin分别表示当前所有粒子的平均目标值和最小目标值。在上式中,惯性权重随着粒子的目标函数值而自动改变,因此称为自适应权重。

当各粒子的目标值趋于一致或者趋于局部最优时,惯性权重将增加,而各粒子的目标值比较分散时,惯性权重将减小,同时对于目标函数优于平均目标值的粒子,其对于的惯性权重因子较小,从而保护了改粒子,反之对于目标函数值差于平均目标值的粒子,其对于的惯性权重因子较大,使得该粒子向较好的搜索区域靠拢。

3.3 双层规划模型求解方法

双层规划问题是一个多目标优化难题,对于一个非线性双层规划问题,对其求解会更加复杂。粒子群优化算法结构简单,控制参数更少,本文将利用分层迭代的思想,采用改进的粒子群算法求解双层规划问题。算法的基本流程如下:

步骤1(初始化)初始化自适应粒子群算法中的参数;随机产生下层模型的初始解(需满足约束条件)。

步骤2 (求解上层规划)将下层模型的解代入上层模型,利用算法求解上层模型,获得上层模型的最优解。

步骤3(求解下层规划)将上层模型的解代入下层模型,利用传统优化方法求解下层模型,获得下层模型的最优解。

步骤4(判断)若满足算法终止条件(误差足够好或者达到最大迭代条件),则停止,否则转步骤2。

4 算例研究

下面通过几个双层规划模型的数值例子,来验证本文给出的自适应粒子群算法求解双层规划模型的可行性与有效性,并与参考文献中的结果做比较。

例1

例2

在上例中,取离子数为40,学习因子都取2,最大惯性权重为0.9,最小惯性权重为0.6,迭代步数取100,最后得到的结果和文献比较如表1所示。

从上述的例子结果可以看出,本文算法的计算结果和文献基本相符合,充分可以得出本文算法的有效性,另外,由于粒子群算法的简单与智能化,参数设定比较少,因此,在解决类似问题具有一定的优势。

5 结论

采用自适应粒子群算法求解双层规划模型是一项崭新的尝试,通过对算例的数值计算,表明本文提出的算法是非常有效的。自适应粒子群算法不仅能够有效的求解双层规划模型,而且具有一定的通用性和普遍性。本研究期望能为以合理的代价用智能算法求解大型复杂模型指明一条新的路径。

参考文献

[1]Kennedy J.Eberhart R.Particle swarm optimization[C].IEEE International Conference on Neural Networks(Perth,Austra1ia),IEEE Service Center,Piscataway,N J,1995,IV:1942-1948.

[2]Shi Y.Eberhart R.A modified particle swarm optimizer[C].IEEE International Conference on Evolutionary Computation,Anchorage,Alaska,May4-9,1998.

[3]孙会君,高自友.供应链分销系统双层优化模型[J].管理科学学报,2003,6(3):66-70.

[4]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.

[5]江燕,胡铁松等.基于粒子群算法的非线性二层规划问题的求解算法[J].运筹与管理,2006,15(2).

[6]刘佳,秦四平.不确定性决策在配送中心选址y元素中的应用研究[J].物流技术.2006.(12):52—54.

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

自适应权重粒子群算法篇4

由于传感器和天气等因素, 出现的图像清晰度、对比度下降等问题,严重影响后续的信息提取、模式识别等环节,必须要对图像进行增强处理以提高图像质量。非线性增强处理以更逼近于人类视觉效果应用广泛,但确定Beta 函数参数是一个复杂的问题,针对图像灰度分布的不同情况,一般采用人工和穷举法设置相应的灰度变换函数参数,没有自适应性和智能性,因此可以考虑利用智能优化算法来自动获取最佳参数。

粒子群算法(particle swarm optimization, PSO)是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性,然而具有唯一的内动力的粒子群系统当进化到一定程度后,粒子群中粒子间的差异减少,系统逐渐平衡,进化减缓甚至停滞。这影响到它探索得到最优解的能力。

本文将突变机制引入到传统的粒子群算法中提高系统进化的效率,并应用此算法自适应获取最佳非线性变换参数达到图像增强的目的。

1 图像非线性增强

1.1非线性变换及其不足

图像像素灰度变换可用如下最基本的形式表达:

$Ι_{x y}^{*} = f (i_{x y}) (1)$

式(1)中I为输出的增强图像像素点(x,y)的灰度值,f是非线性变换。一般对不同质量的图像则采用不同的变换函数,与此对应的变换函数大致有四类。

其中横坐标为原图像的灰度值,纵坐标为变换后图像的灰度。(a)变换适用于对较暗区域进行扩展;(b)变换适用于对较亮区域进行扩展;(c)变换表示对中间区域进行拉伸而对两端区域压缩;(d)变换表示对两端区域进行拉伸而对中间区域压缩。其中(c)和(d)两种变换函数可用于处理灰度集中于某一区域的图像。

每一种变换曲线都可以被一组参数所描述。Tubbs提出了一种归一化的非完全Beta 函数F(u)来自动拟合图像增强的这4类变换曲线[1]。该归一化的非完全Beta 函数F(u)定义为:

$\begin{array}{l} F (u) = B^{- 1} (α, β) \int_{0}^{u} t^{α - 1} (1 - t)^{β - 1} d t ； \\ 0 < α, β < 10 (2) \end{array}$

式(2)中,B(α,β)为Beta函数,表示如下:

$B (α, β) = \int_{0}^{1} t^{α - 1} (1 - t)^{β - 1} d t (3)$

通过调整α,β的值,就可以得到图1所示的各种类型的非线性变换曲线。

可以看出,关键就是确定Beta 函数中α,β的值来获得上面所示的各种类型曲线。然而确定这两个值是一个复杂的问题。常用的做法是根据图像灰度分布的不同情况,人工干预确定,这样存在三个不足:(1)不能自动完成增强任务;(2)人工设置参数的正确度,直接决定着增强效果;(3)耗费时间,毫无自适应、智能性可言。可见将自适应机制、自组织能力、自学习能力与传统的成熟算法相结合显得非常必要。

1.2像素非线性变换过程

设原始图像中像素点(x,y) 的灰度值为f(x,y),增强后的灰度值为f`(x,y),则像素非线性变换过程可归纳如下:

1.2.1 对原始图像像素点归一化

$u (x, y) = \frac{f (x, y) - i_{\min}}{i_{\max} - i_{\min}} 。$

其中imax和imin分别为原图像的灰度最大和最小值,0≤u(x,y)≤1。

1.2.2 利用非完全Beta 函数进行灰度变换

$\begin{array}{l} u^{'} (x, y) = Τ (u (x, y)) ； \\ 其中 0 \leq u^{'} (x, y) \leq 1 。 \end{array}$

1.2.3 计算增强后的图像灰度值f′(x,y)

f′(x,y)=(imax-imin)u′(x,y)+imin。

2 突变粒子群算法

2.1基本粒子群算法[2,3]

粒子群算法是Kennedy 和Eberhart 受鸟群觅食行为的启发于1995年共同提出的。基本原理是一个由m个粒子组成的群体在D维搜索空间以一定的速度飞行, 每个粒子在搜索时, 考虑到了自己搜索到的为最好点和群体内其他粒子的历史最好点, 在此基础上进行位置的变化。和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,没有遗传算法用的交叉(crossover)以及变异(mutation)操作,在大多数的情况下,所有的粒子可能更快的收敛于最优解。

粒子的进化方程为

$\begin{array}{l} v_{i j} = v_{i j} + c_{1} r_{1} (p_{i j} - x_{i j}) + c_{2}^{} r_{2} (p_{g j} - x_{i j}) (5) \\ {\begin{matrix} v_{i j} = v_{\max}, i f v_{i j} > v_{\max} \\ v_{i j} = - v_{\max}, i f v_{i j} < - v_{\max} ； \end{matrix} \\ x_{i j} = x_{i j} + v_{i j} (6) \end{array}$

式(5)、式(6)中,c1,c2为学习因子; r1,r2为在[0,1]区间内均匀分布的伪随机数; xij为粒子的位置; vij为粒子的速度。

为了使算法具有良好的全局寻优能力, Y. Shi和 Eberhart引入了惯性权重w[4],平衡全局和局部搜索能力,一般将它定为随迭代的次数线性减小,如由1.4到0,由0.9到0.4,由0.95至0.2等,从而形成了一个标准的PSO形式:

vij=wvij+c1r1(pij-xij)+c $_{2}^{}$ r2(pgj-xij) (7)

$\begin{array}{l} {\begin{matrix} v_{i j} = v_{\max}, i f v_{i j} > v_{\max} \\ v_{i j} = - v_{\max}, i f v_{i j} < - v_{\max} ； \end{matrix} \\ x_{i j} = x_{i j} + v_{i j} (8) \end{array}$

引入惯性权重的PS0算法进化规则由三部分构成:第1部分为粒子先前的速度;第2部分为“认知(cogntion)”部分,表示粒子本身的思考,即一个得到加强的随机行为在将来更有可能出现,并假设获得正确的知识是得到加强的,这样一个模型假定粒子被激励着去减小误差;第3部分为“社会(social)”部分,表示粒子问的信息共享与相互合作,即当观察者观察到一个模型在加强某一行为时,将增加它实行该行为的几率,即粒子本身的认知将被其他粒子所模仿。

2.2突变PSO算法[3]

进一步分析进化式(7)可知,PSO算法中有3个权重因子:惯性权重w、加速常数c1和c2。惯性权重w使粒子保持运动惯性,使其有扩展搜索空间的能力。加速常数c1和c2代表将每个粒子推向pbest和gbest位置的加速度:值较小时,允许粒子在被拉回之前可以在目标区域外徘徊;而值较大时则导致粒子突然的冲向或越过目标区域。

PSO算法进化的关键在速度。为使粒子不至越过目标区域太远,对粒子的速度加了限制:vmax。当vmax 较大时,粒子的飞行速度大,有利于全局搜索,但有可能飞过最优解;vmax 较小时,粒子可在特定区域内精细搜索,但容易陷入局部最优,一般取值为2.0。粒子的速度是根据自身与同伴的位置而变化的,所以粒子的速度还取决于粒子自身经历的最好位置和所有粒子经历的最好位置pbest和gbest。假设粒子xi正经历全局最好位置,那它将保持静止,其他粒子逐步向它靠拢,这样易陷于局部解。在加了惯性权重的基础上,当粒子xi经历全局最好位置时,该粒子只能做匀速运动,随着w的不断减小,该粒子几乎不变,仍有陷入局部解的可能。

通过粒子群算法的进化方程可以看出,它进化的唯一动力是各粒子之间的相互作用,这也就是一种内动力,具有唯一的内动力的粒子群系统当进化到一定程度后,粒子群中粒子间的差异减少,系统逐渐平衡,进化减缓甚至停滞。这影响到它探索得到最优解的能力。

为使PSO算法有更好的持续开发最优解的能力,本文在标准粒子群的基础上引入了突变机制,形成了突变粒子群算法,它能有效增大粒子间的差异性和非均匀性,打破平衡态,从而增强系统内动力以提高系统进化的效率。

突变机制指当粒子经历全局最好位置时,保存这个最好位置,同时随机产生一个新的种子,也就是说当产生了最优解时,增加一个新的扰动,扩大寻找的空间,更有利于找到全局最优解。

突变PSO算法的进化是将标准PSO算法的进化式子(7)改为:

vij=wvij+c1r1(pij-xij)+c $_{2}^{}$ r2(pp-xij) (9)

${\begin{matrix} v_{i j} = v_{\max}, i f v_{i j} > v_{\max} \\ v_{i j} = - v_{\max}, i f v_{i j} < - v_{\max} 。 \end{matrix}$

式(9)中pp用于保存粒子经历的全局最好位置。

突变PSO算法流程描述如下:

step1: 初始化,设定vmax、c1、c2、w和最大迭代次数N的值,产生原始种群并计算种群中个体的适应度f,记下pi和pg,pp保留pg的值,同时随机产生出得到pg的相应的新的个体;

step 2: 如果迭代次数等于N则转step 5,否则转step 3;

step3:种群按式(5)和式(4)进化,计算个体适应度fg;

step4:比较fs与f;如果fs<f则修改pi,产生新的pg,若pg的值优于pp,就用pp保存pg,同时随机产生出得到pg的相应个体,否则,转step2:

step 5:输出最优个体。

2.3图像增强适应度函数[5,6]

这里使用新设计的适用图像质量评价的适应度函数Fitness,其值越大,表明图像增强后的效果越好。一般算法中考虑的因素仅为与图像质量最相关的方差Fac,其实图像的信息熵E、像素差别Fbr、信噪改变量Inc以及紧致度C等性能参数对于图像质量的好坏也具有重要参考价值。据此,本文采用上述5个因素结合的表达式,即

Fitness=EInc[Fac+2.5C]+Fbr (10)

式(10)中,

$F_{a c} = \frac{1}{n} \sum_{x = 1}^{Μ} \sum_{y = 1}^{Ν} i_{x y}^{2} - (\frac{1}{n} \sum_{x = 1}^{Μ} \sum_{y = 1}^{Ν} i_{x y}^{})^{2}$ ;

$E = - \sum_{i = 0}^{L - 1} p_{i} \lg_{2} p_{i}$ ;

$F_{b r} = \sum_{x = 1}^{Μ - 2} \sum_{y = 1}^{Ν} (i_{x, y}^{} - i_{x + 2, y}^{})^{2}$ ;

$Ι_{n c} = \sum_{n (h) > t} 1$ ;

$C = \frac{Ρ^{2}}{A}$ ,即周长P的平方与面积A的比。

3 实验仿真

为验证本文算法的有效性,采用MATLAB7.0对同一幅较暗图像(图2)进行增强仿真实验[7]。分别采用一般的粒子群算法与本文改进的基于突变机制的粒子群算法对图2进行非线性增强比较,效果评价以处理后图像的直方图为标准。其实验结果图如图3所示。

从图3算法对应的灰度直方图可以看出,本文设计的基于突变机制的粒子群算法进行图像非线性增强,较一般的标准粒子群优化增强算法而言,灰度分布更加均匀宽广,对比度明显,视觉效果更好。

4 结论

本文提出了一种将突变机制引入到常规粒子群算法的改进型粒子群算法, 扩大了寻找的空间,更有利于找到全局最优解。利用本文的优化算法对图像进行了增强实验仿真,进而得到图像非线性增强Beta 函数的最优变换参数。通过Matlab仿真实验表明,该算法较使用标准粒子群算法的增强处理,在提高算法的搜索效率、收敛精度以及图像增强效果等方面有显著效果。

摘要：利用突变粒子群算法自动获取图像非线性增强函数的最佳变换参数,达到图像增强的效果。该算法基于粒子群算法原理,采用针对图像质量评价效果的新适应度函数(包括方差、信息熵、紧致度、信噪改变量以及像素差别五要素),提出一种基于突变机制的粒子群算法,有效增大粒子间的差异性和非均匀性,打破平衡态,从而增强系统内动力以提高系统进化的效率。实验表明,该算法具有较高的自适应性,即避免了陷入局部极小,加快了收敛速度,且增强质量评价明显提高。

关键词：图像增强,粒子群算法,突变,适应度函数

参考文献

[1] Tubbs J D.A note on parametric image enhancement.Pattern Recog-nition,1987;20(6):617—621

[2] Kennedy J,Eberhart R.Particle swarm optimization.Proceedings ofIEEE International Conference on Neural Networks.Perth,Australia,1995:1942—1948

[3]孙颖.微粒群算法的改进及其在图像预处理中的应用.南京:南京师范大学,2007

[4] Shi Y,Eberhart R C.Parameter selection in particle swarm optimiza-tion.In:Evolutionary programming.Porto V W,Saravanan N,Waa-gen D,et al.Eds.Berlin,Germany:Springer-Verlag,1998;VII:591—600

[5] Rosenfield A,Avinash C K.Digital picture processing.New York:Academic Press,1982:154—167

[6]孙勇强,秦媛媛.基于粒子群算法的彩色图像增强研究.徐州工程学院学报(自然科学版),2009;24(3):36—40

自适应权重粒子群算法篇5

关键词：自适应,正态云,造影增强

造影图像反映视网膜血管结构、血流动力学改变、血管病理生理变化及其相关结构的病理改变,广泛应用于视网膜、脉络膜及视神经疾病的鉴别诊断,但是造影过程中由于设备、操作熟练程度等问题出现模糊图像,为了提高成像的质量,需要将模糊变得清晰[1]。通常造影图像增强分为两种方式,一种是通过给人体注射剂量的方法,由于对人体有要求,这种方法的适合范围不是很广泛;另一种方法是通过技术方法实现,使病变组织与邻近正常组织间的密度差增大,从而提高病变显示率,这种方法正在进行普遍实施。

目前,通过技术方法实现的造影图像增强有小波变换、蚁群、鱼群、神经网络[2],但是它们都存在时效性差的缺点,粒子群算法是近期兴起的一种智能算法,具有参数设置简单、易于实现等优点,但是在数据优化的后期出现早熟现象,不利于数据找到最佳值。目前对粒子群算法提高,一般是从自身对其改进,比如变异粒子、差分粒子、裂变粒子等,都使数据寻优在一定程度上避免局部极值,但是无法避免粒子群自身的根本问题。

本文在粒子群算法的基础上,引入云模型算法,利用云具有随机性又有稳定倾向性的特性实现粒子动态优化,基于粒子个体适应值把粒子群分为3个云子群,且分别采用不同惯性权重的调整策略,通过正态云发生器产生新粒子代,增加自适应算子动态调整粒子交叉概率和变异概率,这样权重随着粒子适应度值的减小而减小,从而实现了较优粒子取得较小的权重,把造影图像灰度非线性最佳增强的参数组合问题转化为自适应云粒子群算法寻优问题,实验仿真得出的造影图像清晰,便于诊断。

1 自适应云粒子群算法描述

1.1 云模型

云模型是李德毅院士提出的一种定性定量转换模型,能够实现定性概念与其数值表示之间的不确定性转换[3],具有良好的数学性质,优势恰恰在于定性知识表示[4]。

设U是一个用精确数值表示的定量论域,C是U上的定性概念,若定量值x∈U是C的一次随机实现,x对C的确定μ(x)∈[0,1]是有稳定倾向的随机数,且μ:U→[0,1],有∀x∈U,x→μ(x),则x在论域U上的映射在数域空间的分布称为云,记为C(x),每一个x称为一个云滴[5,6]。云模型由许多云滴组成,并且可伸缩、无边沿、远观有形、近视无边,与自然现象中的云相似[7,8]。

1.2 云粒子群算法

基本粒子群算法对粒子惯性权重的调整策略不能反映实际优化搜索过程,容易出现早衰现象,云模型发生器把粒子看做云模型中的粒子,通过云计算来实现粒子动态优化[9],基于个体适应值把种群分3个云子群,且分别采用不同惯性权重的调整策略。

通过正向云发生器来产生粒子,正向云发生器的核心技术是通过中心极限定理生成正态随机数,在X条件产生的正向云算法为:在生成以En为期望值、He2为方差的一个正态随机数

En′i=NORM(En,He2) (1)

代入xi=x0,计算隶属度为

$μ (x_{i}) = \exp (- \frac{(x_{i} - E x)^{2}}{2 E n_{i}^{2}}) (2)$

从而生成一个数域中具有隶属度μ(xi)的云滴xi[10],多个云滴即可得到正态云模型的若干二维点[μ(xi),xi]。

如果在混沌云中为了检测云参数的特征值,通过逆向云发生器抽样云滴来实现[11]。每个粒子根据其个体极值,通过正态云发生器产生新粒子代,从所有粒子中选择适应度值最优的N个粒子作为父代,并选出父代中最优个体在云模型参数(Ex,En,He)控制下产生S个新粒子,通过适应度值排序得到子代S个粒子中的最优个体,当子代最优个体适应度小于父代最优个体的适应度时,进行全局最优位置的更新[12]。

在云粒子寻优过程中,其步骤为:

1) 初始化种群,计算各个粒子的位置,个体极值Pbest以及全局极值Gbest等。

2) 计算每个粒子的适应度f,更新Pbest,Gbest。

3) 判断是否达到云变异阈值M,若达到,则根据正态云发生器产生新粒子代更新,设全体粒子的全局最优点为Gbest,令正态云算子A(C(Ex,En,He))中:Ex=Gbest,En=2Gbest, $Η e = \frac{2 G_{b e s t}}{10}$ ,没有达到变异阈值转步骤4)。

4) 对每个粒子进化操作,设粒子i的个体极(小)值为Pbest,令正态云算子A(C(Ex,En,He))中:Ex=Pbest,En=2Pbest, $Η e = \frac{2 Ρ_{b e s t}}{10}$ ,根据正态云发生器产生一个新粒子j,并令i=j,完成进化操作。

5) 如果达到最大迭代次数输出Gbest,否则转到步骤2)。

1.3 自适应云粒子群算法

为了控制云模型中参数A(C(Ex,En,He))取定值导致算法存在“早熟”及收敛速度慢的问题,增加自适应算子动态调整粒子交叉概率Px和变异概率Pm,公式为

$Ρ_{x} = {\begin{cases} k_{1} \frac{f_{\max} - f^{'}}{f_{\max} - f_{a v g}}, f^{'} \geq f_{a v g} (f_{a v g} = \frac{1}{Ν} \sum f^{'}) \\ k_{3}, 其他 \end{cases} (3)$

$Ρ_{m} = {\begin{cases} k_{2} \frac{f_{\max} - f}{f_{\max} - f_{a v g}}, f \geq f_{a v g} \\ k_{4}, 其他 \end{cases} (4)$

式中:fmax是种群适应度的最大值;favg是平均值;f ′是交叉操作中两个体的适应度较大者;f是变异操作中单个个体的适应度[13,14];k1,k2,k3,k4是控制参数,取值范围是[0,1]。当f ′→fmax时,较优秀的个体几乎不参与交叉操作,f→fmax时,较优秀的个体几乎不参与变异操作[15]。

粒子权重生成的规则为

$ω = {\begin{cases} 0.2, f^{'} \geq f_{a v g} \\ 0.9, f \leq f_{a v g} \\ 0.9 - 0.5 \exp^{[\frac{- (f_{i} - E x)^{2}}{2 (E n^{'})^{2}}]} ‚ 其他 \end{cases} (5)$

式中:≥表示优于;≤表示次于。

随着粒子适应度的减小,由极限定理易可知: $0 < 0.5 \exp^{[\frac{- (f_{i} - E x)^{2}}{2 (E n^{'})^{2}}]}$ <1,从而保证了ω∈[0.4,0.9],权重随着粒子适应度值的减小而减小,从而实现了较优粒子取得较小的权重。

这样自适应交叉概率后的新云滴特征值为

${\begin{cases} E x = f_{a v g} \\ E n = \frac{(f_{a v g} - f_{\min})}{k_{1}} \\ Η e = \frac{E n}{k_{2}} \\ E n^{'} = n o r m r n d (E n, Η e) \end{cases} (6)$

这样自适应变异概率后的新云滴特征值为

${\begin{cases} E x = f \\ E n = \frac{(f_{a v g} - f_{\min})}{k_{3}} \\ Η e = \frac{E n}{k_{4}} \\ E n^{'} = R A Ν D Ν (E n, Η e) \end{cases} (7)$

这样既满足了快速寻优能力,又具有随机性,在适应度最大时并非绝对的零值,从而提高了避免陷入局部最优的能力[16]。

1.4 造影图像增强过程

把像素的灰度值作为云滴,完成图像特征的不确定性表示,用逆向云发生器得到云模型。使增强后的图像与视觉响应特性相匹配[17]。

云模型通过推理规则实现基于语言子集的非线性映射能力,假如用带X条件的云对象来构造单条定性。输入变量x激活不同X条件下云CGxi产生不同的μi,然后经过Y条件云CGyi产生云滴 $(y_{i}, μ_{i})$ ,这些云滴经过加权平均或逆向云CG-1输出,可以获得相应的推理结果,完成整个推理过程[18,19]。

利用云模型的定性定量转换特性来描述像素参数变量的调制匹配程度,在自适应云粒子群算法中将原图像中每个像素(x,y)的灰度值f(x,y)通过映射函数 $Τ (\cdot)$ ,增强变换图像后的灰度g(x,y),即

g(x,y)=T[f(x,y)] (8)

对人类视觉感兴趣的像素映射函数 $Τ (\cdot)$ 进行对数灰度变换

$g (x, y) = a + \frac{\ln [f (x, y) + 1]}{b l n c} (9)$

图像低灰度区扩展,高灰度区压缩。a,b,c是按需要可以调整的参数,求得最佳的a,b,c组合即可得到造影图像的最佳增强,这样把增强问题转化为自适应云粒子群算法寻优问题。

算法过程为:

1) 输入图像并确定像素的灰度值;

2) 对数灰度变换中的a,b,c参数进行数据寻优,转到自适应云粒子寻优过程;

3) 判断增强图像是否达到视觉效果,未达到转步骤2);

4) 输出增强图像。

2 实验仿真

图像增强所用程序为MATLAB7.0,运行环境:CPU为3.6 GHz,内存2 048 Mbyte,操作系统Windows XP,硬盘为SATA2接口。为了提高对比质量,下面的算法各进行30次蒙特卡罗仿真。

图1给出了肺部血管造影对比增强图像,从对比中可以看出自适应云粒子群算法增强图的造影效果最好,主动脉血管边沿清晰,甚至可以看到动脉的毛细血管,自适应云粒子群算法在造影图像增强过程中,云模型提高适应度较低的粒子个体的搜索能力以产生更大范围内的新个体,增强了算法的随机性;同时,在最大适应度附近的优秀个体在维持正态云的稳定倾向性时也具有随机性。

在图2中,云滴的隶属度反映了图像像素的灰度分布状况,在隶属度大的地方图像像素的灰度比较集中,通过空间灰度区域聚态,病变区域的灰度聚态特征介于低频背景和极高频噪声之间,利用这一特点可以用自适应云粒子群算法对病变的特征进行局部和全局增强,达到诊断目的。

3 总结

本文结合云模型和粒子群优化算法的基本思想,提出了一种基于自适应云粒子群算法。采用正态云发生器优化粒子,基于个体适应值把种群分3个云子群,且分别采用不同惯性权重的调整策略,粒子权重随着粒子适应度值的减小而减小,从而实现了较优粒子取得较小的权重,在造影图像增强中表现出良好效果,通过病变区域的像素空间灰度区域聚态,用自适应云粒子群算法对病变的特征进行局部和全局增强,以达到诊断目的。

自适应权重粒子群算法篇6

电力系统无功优化主要目的是在合理的电压质量要求下尽量降低网络损耗, 其主要控制手段有调节发电机端电压、控制有载调压变压器的分接头和可投切并联电容/电抗器。其中, 发电机端电压 (或无功出力) 是连续变量, 补偿电容器/电抗器和有载变压器分接头档位是整数变量, 因此, 无功优化是一个典型的整、实数混合的多变量、非线性的优化问题。

粒子群优化算法PSO (Particle Swarm Opti-mization) 最初源于对鸟群捕食行为的研究, 是一种新的进化计算方法 (Evolutionary Computation) , 也是一种群智能优化算法 (Swarm Intelligent Optimization) 。此算法及其在相关领域的应用已引起各国学者广泛关注, 被越来越多地应用于智能优化、模式识别、神经网络的训练等诸多领域。

1 电力系统无功优化的数学模型

本文采用有功网损最小为控制优化目标函数, 以发电机无功出力和节点电压为状态变量, 以有载调压变压器变比、无功补偿电容器容量和发电机端电压为控制变量, 数学模型如下:

等式约束方程为:

控制变量不等式约束:

状态变量不等式约束:

式中:NE为支路号集合, Ni为与节点i有关联的节点号集合, NPQ为P·Q节点号集合, NB为总的节点号集合, NG为发电机节点号集合, Nr为变压器支路集合, NC为补偿电容器节点集合;S为平衡节点;Gij为支路ij的电导;Bij为支路ij的电纳;Vi, Vj为节点ij的电压幅值;θij为节点ij的电压相角差;QCi为节点i的无功补偿容量。

2 自适应粒子群算法无功优化过程

采用连续变量和离散变量混合的实数编码, 求解步骤如下:

步骤1:输入系统数据, 初始化粒子群。首先输入系统的结构、网络数据和控制参数, 其中发电机节点电压的上下限、电容器容量的上下限、变压器分接头上下限等构成了解的可行域。其次确定粒子的维数M。

步骤2:计算目标函数值。对群体中的每个粒子, 分别进行潮流计算, 得到每组控制变量取值下的有功网损, 并判断是否违反节点电压以及发电机无功出力等约束, 将电压及发电机无功越界值作为罚函数项计入到目标函数。

步骤3:记录两个极值。比较所有粒子对应的目标函数值, 首先记录粒子i (i=1, 2, …, N) 当前的个体极值PBest (i) 及答应的目标函数值F (PBest (i) ) ;从PBest (i) 中确定整体极值GBest, 并记录GBest答应的目标函数值F (GBest) 。

步骤4:计算适应值判断可行解:计算各粒子适应值, 并验证是否是问题的可行解, 是可行解的粒子按适应值由小到大排序, 分类记录迭代结果。

步骤5:更新最优值:若粒子是问题可行解且适应值优于历史群体最优值, 则更新群体最优值;取问题可行解的前4个最好粒子替代历史其余粒子的最好解进行速度更新。

步骤6:混沌变异:若粒子相邻三代适应值无变化或变化率小于某极小值, 且此粒子的适应值不是群体最优值, 则此粒子陷入局优, 应对每维变量进行变异。

步骤7:输出问题的解, 包括发电机机端电压、补偿电容器组数和变压器分接头档位等控制变量的取值情况, 系统各节点电压、发电机无功出力等状态变量的数据, 以及对应的网损值。

3 算例仿真分析

为了检验上述利用粒子群优化算法求解无功优化问题的有效性, 本文使用IEEE30节点试验系统进行计算。系统参数均用标么值表示, 其基准功率是100MW。P-V节点和平衡节点的电压上下限设置为0.9和1.1。P-Q节点的电压上下限设置为0.96和1.04。表1列出了分别采用原对偶内点法和本文算法 (取群体规模N=30) 优化前后各变量的取值情况, 其中方法一为原对偶内点法, 方法二为本文粒子群优化算法。

可以看出采用粒子群算法优化后, 发电机无功出力和无功补偿都在约束范围内, 系统节点电压普遍得到了改善, 最低电压由0.94提高到1.02, 可以取得更好的经济效益。

4 实际算例分析

算例为七台河某地区电力系统, 有2台发电机, 6个并联电容器 (节点16、20、22、25、28、31) , 6台可调变压器, 系统负荷load S=125.24+j79.71, 并联电容器无功出力调节范围:节点16、20为-0.06~0.06;节点22、25为-0.06~0.18;节电28、31为-0.06~0.24;可调变压器抽头变化范围均为0.9~1.1。运用算法优化后, 网损显著下降, 其中本文提出的IDE算法的降损效果最好。系统无功优化前, 有9个节点电压标幺值低于0.95, 最低点电压发生在节点31, 其标幺值为0.874, 电压质量情况很不理想;优化后, 各节点电压质量明显提高, 最低节点电压 (节点31) 标幺值为0.99。图1为优化前后各节点电压曲线。

4 结论

本文提出了一种粒子群优化算法, 采用符合均匀分布规律的粒子作为初始粒子种群, 为确保更好地在全局范围搜索, 在粒子速度和位置更新时不仅仅考虑粒子的个体最优和群体最优两个极值, 提出了粒子自身探索机制。经过IEEE-30节点系统的计算分析, 此PSO方法具有优越的计算效率和良好的收敛性, 非常适用于求解电力系统无功电压的综合控制问题, 具有较强的实用价值。

参考文献

[1]Clerc M, Kennedy J.The Particle Swam Explo-sion, Stability and Convergence in a Multidi-mensional Com-plex Space[J].IEEE Trans on Evolutionary Computation, 2002, 6 (1) :58-73.

[2]张勇军, 任震, 李邦峰.电力系统无功优化调度研究综述[J].电网技术, 2005, 29 (2) :50-56.

自适应权重粒子群算法篇7

旅行商问题( TSP) 是典型的NP完全问题,随着问题规模的增大,解空间极具膨胀。对于大规模旅行商问题,常规递归搜索算法难于在容忍的时间内获得满意解。但由于旅行商问题具有广泛的应用价值,如智能交通控制、管道焊接最佳距离选择,网络路由路径选择、大规模电路图自动布图,智能物流配送,电力系统输电线路规划以及GPS路径导航等诸多领域问题的求解都能转化为旅行商问题模型,在不能获得全局最优的情况下,高效寻找高质量的近似解是当前解决这一问题的主要途径。近年来,多种启发式搜索方法都在这一领域获得了成功应用。目前求解旅行商问题的启发式搜索方法包括湖水能量优化算法、遗传算法、郭涛算法、量子算法、近邻搜索、杂草优化算法以及粒子群优化算法等[1,2,3,4,5,6,7,8]。

文献[9]成功实现了基本粒子群优化算法求解小规模旅行商问题,文献[10]提出的增强型自探索粒子群优化算法很好地解决了城市规模100 左右的旅行商问题,文献[11]在此基础上提出了改进,对于200 节点以内的旅行商问题,能够以较高概率获得当前已知全局最优解,但其依然属于随机搜索算法,没有利用进化过程信息,对于大规模旅行商问题很难获得高质量的解。为此,本文在原有算法中引入变异机制,同时对进化过程中获得的进化信息进行学习,提出自适应混合粒子群优化算法求解大规模旅行商问题。自适应性包括进化过程自适应进行、重要参数自适应变化和粒子结构依据进化信息自适应调整三个方面。算法进化分多批次自适应进行,每个批次包括两个阶段———第一个阶段,利用混合算法进行多次搜索,并将获得的多个局部最优解,并记录在周游边结构中,同时记录多次实验所获得的最佳周游路线; 第二阶段,首先,对第一阶段所产生的周游边结构进行学习,找出所有公共边,产生多个关键边序列段,每个序列段看成一个整体,以此缩小问题规模。用这些关键序列段和剩余单个节点集,再结合公共边结构中记录的边的情况,依概率重新初始化种群,同时用这些关键边序列段处理记录的最佳周游路线,使其和重新初始化后的种群具有相同的粒子结构,并把处理后的序列作为当前全局最优解,并清空周游边结构; 在此基础上继续进行下一个批次的进化搜索和记录周游边; 上述过程反复进行,直到在某批次的第一阶段多次进化都收敛于同一个局部最优解为止。仿真实验结果分析对比表明,这种自适应方法求解大规模旅行商问题能够获得高质量的近似解。

1 粒子群算法优化算法

PSO算法求解旅行商问题的基本迭代公式如式( 1 ) 和式( 2) 所示。基本粒子群优化算法及增强型自探索粒子群优化算法及其求解旅行商问题详细设计、参数说明与求解过程详见文献[9 - 11]。

2 旅行商问题简述

旅行商问题属于NP完全组合优化问题,解空间随着问题规模N呈阶乘增加。对称TSP问题的解空间大小为( ( N - 1) !/2) ,对于较大规模( N ≥ 18) TSP问题,传统递归搜索都不能在容忍时间内获得满意解,为此常被用于检测和验证启发式算法的有效性。旅行商问题描述如下。

有N个城市,从某一个城市出发,遍历完所有城市并回到出发城市,找出所有可能遍历路径中的最短路径。其形式化描述为: 给定一个连通图G( X,E) ,其中,X为城市节点的集合,E为赋权边的集合,即两两城市距离的集合。问题的目标是寻找一条周游距离最短的Hamilton周游回路。设城市节点集合为X ={ 1,2,…,N} ,采用双城市节点表示边,即E = { ( i,j,wij) i,j ∈EG,wij∈ R+} ,两个城市i和j之间的距离为wij,如果是对称问题,则两个城市之间来回的距离相等wij= wji。假设第i个粒子的表示为Xi= ( xi1,xi2,…,xik,…,xi N) ,1 ≤ xik≤ N,1 ≤ k ≤ N。则粒子i所表示的TSP周游路线总长度为:

假定从城市编号1出发,如果k=N,则k+1=1。目标找出f(Xi)最小的粒子位置Xi。若边(xik,xi(k+1))∈E,则存在正整数Wxikxi(k+1)∈R+,否则表示城市xik和城市xi(k+1)没有直接通路,设置Wxikxi(k+1)为一较大数值。

3 自适应混合粒子群优化算法

为了提高混合算法求解大规模TSP问题的能力,需要对进化过程获得的有用信息进行记录和利用,为此,本文提出周游边结构用以记录高质量周游路线边的分布。

3. 1 周游边结构

针对旅行商问题周游边为城市节点的顺序,为了能够反映局部最优解边的分布情况,本文采用双节点表示边,提出链式周游边结构,即记录每个节点之后出现过的所有节点情况,并且记录每个节点出现的频次,以此记录该边出现的频次,新出现的节点插入到链表最后。这样可以记录周游路线中一个城市节点边的情况,以数组方式管理所有城市节点。周游边结构如表1所示。

表1 中,城市节点结构用于描述与某个城市节点K相关联的边的情况。边的总数量用于描述与该城市节点K相关联边总数量。节点标记在生成关键边时,用来标记该城市节点是否已经输出到路径中,防止再次输出。边结构指针指向边结构,表示与K节点相关联的边的城市节点的情况。其中,城市节点编号描述与K相连的另一个城市节点的编号,频次表示该城市节点出现在K节点之后的总次数,边结构指针表示与K节点相关联的另一条边的情况。例如6 个城市节点TSP问题,单向记录周游路线( 1,2,3,6,4,5) 和( 1,2,3,5,6,4) 之后,其周游边结构记录信息如表2 所示。

从表2 中可以看出,经过记录上述两条周游边后,与城市节点2 单向相连的边只有1 条( 2,3) 并且出现2 次。如果该问题为对称TSP问题,即两两城市之间来回的距离相等,则将两条周游路线逆转后再单向记录一遍。即再将边( 1,5,4,6,3,2) 和( 1,4,6,5,3,2) 记录后,形成如表3 所示周游边记录信息表。

从表3 中可以看出,经过记录上述两条周游边及其逆转序列( 共4 条周游路线) 后,与城市节点2 单向相连的边只有2 条( 2,3) 和( 2,1) 并且都出现2 次。

3. 2 自学习进化信息生成关键边序列段

经过对多个高质量局部最优解周游边情况的记录,将得到能够反应高质量局部最优解周游边分布的信息结构。该结构能够反映与某城市节点k相连的所有边的情况,并按出现的频次排列。为了能够有效减少搜索空间,如果多个局部最优解都包含某条边,则该边将以较高概率出现在全局最优解中。本文称这些边为关键边,并采用如下策略寻找所有关键边。

针对对称旅行商问题,为了确保关键边能以高概率出现在全局最优解中,依据周游边结构特点,凡某节点k之后只有2 条边,说明与该节点连接的两条边将以高概率出现在全局最优解中,则这两条边为关键边而且相连,与之相关联的城市节点形成关键序列段。针对非对称TSP问题,凡某节点之后只有1 条边,说明与该节点连接的这条边顺序已定,至少这两个节点可以归约为一起。

对于6 城市对称TSP问题,从表3 可以看出与城市节点2相连的边有且只有2 条边,则边( 2,3) 和( 2,1) 为关键边,且共用同一个城市节点,则这两个关键边可以连接起来,形成关键边序列段,简称关键序列段,表示为: 1 - 2 - 3 或3 - 2 - 1,由于是对称问题故二者等价。关键序列段看成一个整体,原有6 个城市的TSP问题缩减为一个关键序列段和3 个城市节点的组合优化问题,原有问题规模从6 缩小到4,解空间得到有效缩减,由原来的120 条周游路线,缩减为12 条。对于大规模问题,缩减效果更佳明显。

如果是非对称TSP问题,则不需要对周游边进行逆转和二次记录,直接依据如表2 可以看出,节点1 后只有一条边( 1,2) ,节点2 后也只有一条边( 2,3) ,由于顺序已定,且共用同一个节点,故可以将二者合并,同样可以得到序列段1 - 2 - 3。

对于具有n个城市节点的TSP问题,采用类似的方式可以找到多个关键边,并将具有共用城市节点的关键边连接起来形成关键序列段。对于大规模TSP问题,通过上述方法可以获得多个关键序列段,为了提高后续进化的效率,继续利用周游边结构中记录有效信息重新初始化种群,采用策略如下。

首先要从公共边结构中删除( 标记) 序列段中间节点,避免再次出现在解序列中。其次,为了有效缩减搜索空间,由关键边组成的序列段不再改变。最后,为了提高收敛速度,避免无效搜索,继续利用公共边结构纪录的信息,依概率连接各个序列段或游离节点,即如果序列段边界节点及游离节点,具有多个可选节点,则根据随机概率进行分配选择。具体实现如下。

将关键边序列段和游离节点以集合形式组织起来( 总数量Gnumber = 序列段+ 游离节点= 问题规模总数- 每个序列段包含节点的总和+ 序列段个数) ,并编号。根据公共边结构所记录的边的情况( 出现概率) ,随机生成解序列。为了提高计算效率,对关键序列段做如下处理。

如果序列段中包含1 节点,则以第1 个关键序列段( 包含1节点) 为起始节点。否则,仍旧以1 节点为起始节点,其他节点依概率随机排列。

为了提高收敛的效率,采取精英保持策略,即使用记录多次实验的最佳局部最优解作为当前全局最优解,即学习的目标,用以指导种群在规模缩小后的高效指导作用。但该局部最优解与当前重新初始化后的种群中的个体具有不同的粒子结构,该粒子不具有关键序列段,需要用生成的关键序列段对其进行处理,使其具有和其他粒子相同的结构即可进行下一个轮回的进化计算。

通过上述方法可以将于大规模TSP问题约减为较小规模的TSP问题,然后继续使用混合粒子群优化算法进行求解多次,如果能够获得更好的解则更新原来记录的多个局部最优解信息,并在多次进化结束后继续进行学习和继续进化,如果多次进化都收敛与同一个解则算法终止。该解即为算法获得的最终解。

3. 3 自适应策略

为了提高算法的整体性能,在前期工作和实验总结的基础上,自适应性策略包括以下三个方面。

3. 3. 1 进化过程多批次分阶段自适应进行

为了算法尽可能获得高质量的近似全局最优解,整个进化过程分多批次分阶段自适应进行,每个批次包括两个阶段。第一阶段,进行多次混合搜索实验并记录每次搜索所得的最佳周游路线边信息于周游边结构。第二阶段,对周游边结构进行学习,获取关键序列段,并以此自适应调整粒子结构,重新初始化种群。同时记录多次实验的最佳解,并用关键序列段进行处理,使其与重新初始化的种群具有相同的粒子结构,该解即为下个批次实验第一阶段多次实验的当前全局最优解。算法不设定搜索的批次数,只设定第一阶段的进化搜索次数,搜索过程依据每次所获得的解自适应进行,如果在某批次第一阶段进化搜索都收敛于同一个局部最优解时,则退出搜索过程,算法整个进化过程结束。

3. 3. 2 粒子结构自适应变化

为了减少进化过程中的无效搜索,提高算法搜索的效率,提出了粒子结构自适应变化思想。算法在进化搜索的开始,粒子由一个个单独的城市节点构成,经过第一个阶段的进化,并对进化过程有用信息的学习,将多个关键边归结为一个关键序列段,并看作一个整体,该序列段中的节点顺序不再改变,从而减少了无效搜索的次数。例如: 6 个城市的TSP问题,开始时,粒子结构( 1,2,3,6,4,5) ,经过第一阶段进化以及对进化过程信息学习后,获得关键序列段1 - 2 - 3,则粒子结构可变为( 1 - 2 - 3,6,4,5) ,即粒子结构由关键序列段和自由城市节点组成。

3. 3. 3 进化参数自适应变化

为了提高算法的搜索效率,混合算法中的几个关键参数在进化中根据进化代数和问题规模( 关键序列段的引入,相当于问题规模缩小) 自适应变化。惯性权重依据进化代数自适应变化,如式( 4) 所示[10]。

另外,学习因子c1 和c2 依据问题规模分区间自适应设定。当问题规模N < 100 时,c1 = 0. 2,c2 = 0. 3,当500 > N ≥ 100,c1 = 0. 02,c2 = 0. 03,当N ≥ 500 时,c1 = 0. 002,c2 = 0. 003 。

最后,序列段调整算法中的序列段最大长度K依据问题归约规模N自适应变化,K = N/4 。

3. 4 混合粒子群优化算法

改进增强型自探索粒子群优化算法属于随机搜索算法,由于其采用黑板学习模型,会导致所有粒子向当前全局最优粒子靠拢,一旦陷入某局部最优的束缚,单靠粒子本身的学习和探索能力难于逃出束缚,限制了算法的全局搜优能力。为此,借鉴生物进化过程中出现的变异现象,在改进增强型自探索粒子群优化算法的基础上,再次引入变异机制,从而形成混合粒子群优化算法。增强型自探索粒子群优化算法及其改进求解旅行商问题实现过程详见文献[10,11]。

算法中粒子的位置信息是所有城市编号的一个全排列,速度为位置置换序列,通过改变置换序列,可以达到改变粒子位置的目的,从而实现粒子摆脱局部最优的束缚的目的。故算法中采用速度变异机制,简述如下。在算法中,设置一个种群最大停滞常数TZmax和一个种群停滞代数统计变量Bt,如果种群在某代进化后,当前全局最优没有得到任何改善,即没有搜索到比Pgbest更好的解,则Bt = Bt + 1,否则,Bt = 0。当Bt > TZmax时,算法进行速度变异,即通过轮盘赌算法选择一部分粒子,清除原有速度,重新随机生成。这样经过速度变异后的粒子会快速脱离原有位置,即逃离局部最优的束缚,在新的位置重新开始搜索,这样增大了其发现全局最优的机会,提高了算法的全局搜优的能力。

4 SAHPSO求解TSP问题算法流程

根据上述思想,自适应混合粒子群优化算法求解旅行商问题算法流程描述如下:

Step 1

设置所求解问题的系统参数,如问题的规模,两两城市之间的距离权值和种群规模以及边界条件等,设置每个阶段多次进化搜索的搜索次数Sn等。

Step 2

设置进化次数i = 1 。

Step 3

如果i > Sn ,则转Step13。如果关键序列段不为空,则使用关键序列段和游离节点,并根据周游边结构信息,初始化种群,并使用记录的最优解替换Pgbest,并根据关键序列段和游离节点信息设置当前搜索问题规模。否则,随机初始化种群,即随机产生位置向量和调整序,初始化Pbesti和Pgbest 。

Step 4

计算问题归约规模,并根据归约规模自适应设置学习因子c1 和c2,最大进化代数Mt,设置当前进化代数t = 0 。

Step 5

根据式( 3) 计算每个粒子的适应值f( Xi) ,如果该位置优于Pbesti,则Pbesti被当前位置替换; 否则Pbesti保持不变。

Step 6

在当前个体的最优解Pbesti中选择一个最优值,如果它优于Pgbest,则用其更新Pgbest 。

Step 7

按式(4)计算惯性权重w,并随机产生r1和r2。

Step 8

按式(1)和式(2)进行速度和位置更新。

Step 9

对每个粒子依据单点调整算法和序列段调整思想进行粒子增强型和改进增强型自探索搜索和位置更新。

Step 10

如果Pgbest没有得到改善,则Bt = Bt + 1; 否则,Bt = 0; 如果Bt > TZmax,则进行速度变异,并Bt = 0 。

Step 11

t = t + 1,如果t < Mt,转到Step 3,继续迭代; 否则终止迭代。Pgbest所记录的位置即为本次实验的最优解。

Step 12

将Pgbest记录于周游边结构,i = i + 1 ,转到Step3。

Step 13

如果Sn实验获得同一个解,则转Step 15。

Step 14

对周游边结构进行学习,获得关键序列段; 用获得的关键序列段处理Sn次实验所记录的最优解,并用该最优解作为下次进化的全局最优解,否则转Step 2。

Step 15

算法终止,多次获得的同一个解即为算法获得的最佳近似解,输出该解的周游线路图。

5 算例分析

本文实验采用Intel E7400 CPU,4 GB内存,Windows XP SP3操作系统,用Delphi 7. 0 开发Windows窗体单线程应用程序,能够实时显示进化过程信息和周游路线图实时绘制显示功能,故算法运行耗时偏高,CPU占用率约为50% 左右。

为了说明算法自适应策略的有效性,同时提高算法的执行效率和结果的可对比性,每个阶段都采用文献[11]中的实验策略,分别进行30 次独立实验( d1291 和Fl1400 两个实例,自学习后进行10 次独立实验) ,实验结果对比如表4 所示。误差对比如表5 所示。其中,ACOMGR为文献[2]中的方法,ILSBCO为文献[3]中的方法,Closet-point算法和CPBOA为文献[12]中的方法。表中“- ”表示文献没有对该算例进行求解。

从表4 可以看出,对于较大规模的9 个旅行商问题,本文提出的自适应混合粒子群算法( SAHPSO) 无论平均解的质量还是与已知最优解的误差都要远远小于文献[12]和文献[3]中的实验结果。平均每次求解的时间也在可接受的范围内,最长时间仅为4083 秒。对于Pcb442 和u724 两个实例,本文的算法获得的解劣于文献[2]中的结果,说明这两个实例存在的局部最优对本文求解方法影响较大。从表4 和表5 可以看出,随着问题规模的增大,平均求解时间随之增加,误差逐步变大( 特殊情况属于实验策略以及局部最优对算法求解的影响所致) 。

文献[11]改进增强型自探索PSO算法,所能求解的最大规模算例为Pr226 问题,多次实验获得的最佳解为80 373,平均解80 861. 01( 误差0. 612% ) ,而改进后的自适应混合PSO算法多次实验都能够无误差地收敛于已知最优解80 369,而且具备更大规模的求解能力,这说明了改进措施的可行性和有效性。另外,本文算法获得的最优解明显优于文献[1]中洪水能量算法发现的最优解为82 913( 误差3. 17% ) 。

对于d1291 实例,算法最终都收敛于同一个局部最优解53 101,误差为4. 53% ,其周游路线如图1 所示。对于Fl1400 实例,算法最终都收敛于同一个局部最优解20 392,误差仅为1. 32% ,该似解优于文献[2]中的结果,其周游路线如图2所示。

虽然实例Fl1400 比d1291 的规模大很多,但从图1 和图2的节点分布看实例Fl1400 的城市分布基本属于单环形分布,而实例d1291 属于多环形分布,故局部最优解对算法影响较大,这就是为什么规模小的反而误差较大的原因。从图1 和图2 可以看出,虽然算法获得的近似解不是全局最优解,但是其周游路线依然比较完美,没有交叉点。说明对于这两个求解实例,算法在较短时间内,获得了与已知最优解误差较小的高质量的近似解。

上述分析都说明了自适应混合粒子群优化算法求解较大规模TSP问题的可行性和有效性。

6 结语

本文针对改进增强型自探索粒子群优化算法求解大规模TSP问题的不足,提出了自适应混合粒子群优化算法求解较大规模TSP问题,通过多种自适应策略,分阶段自适应进化,算法获得解的质量明显提高。通过对多个标准TSP问题的仿真测试,实验结果对比分析说明了自适应混合粒子群优化算法求解大规模旅行商问题能够的获得高质量的解。但本文算法仅仅利用了多个局部最优解的交集信息,如何更进一步利用多个局部最优解隐藏的信息,并形成有效的启发式规则以高效求解更大规模的TSP问题是今后要研究的重点。

参考文献

[1]冯翔,马美怡,虞慧群.TSP湖水能量优化算法[J].计算机研究与发展,2013,50(9):2015-2027.

[2]冀俊忠,黄振,刘春年,等.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展,2010,47(3):434-444.

[3]苏晓勤,孙鹤旭,潘旭华.改进蜂群算法的旅行商问题仿真[J].计算机工程与设计,2013,34(4):1420-1424.

[4]安晶,徐森.一种结合粒子群优化理论改进的郭涛算法及其应用[J].计算机应用与软件,2014,31(2):296-299,320.

[5]李熠,马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报,2012,34(4):355-358.

[6]贾瑞玉,李亚龙,菅玉勇.求解旅行商问题的混合量子蚁群算法[J].计算机工程与应用,2013,49(22):36-39.

[7]饶卫振,金淳,黄英艺.求解TSP问题的最近邻与插入混合算法[J].系统工程理论与时间,2011,31(8):1419-1428.

[8]彭斌,胡常安,邵兵,等.求解TSP问题的混合杂草优化算法[J].振动测试与诊断,2013,33(S1):52-55.

[9]王翠茹,张江维,王玥,等.基于改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005,32(6):47-51.

[10]熊伟,张江维,张火林.增强型自探索粒子群优化算法求解TSP问题[J].华北电力大学学报,2009,36(6):69-74.

[11]Zhang Jiangwei,Si Wenjian.An Improved Enhanced Self-Tentative Particle Swarm Optimization Algorithm for TSP[C]//Sixth international conference on natural computation,Yantai,Shandong,China,2010,Piscataway,IEEE computer society,2010:279-283.

【自适应权重粒子群算法】推荐阅读：

自适应算法09-02