变异算法范文

2024-06-01

变异算法范文（精选7篇）

变异算法第1篇

1 用于连续空间优化的蚁群算法研究

该文提出的用于连续空间优化的指导变异蚁群算法,其主要思想是将将连续空间按点的方式进行离散化,对离散化的点采用十进制编码,在此离散化的基础上,采用ACS中的状态转移方式,使蚁群收敛到全局最优点的邻域内,再对蚁群算法搜索到的最优点采用局部搜索技术,找到全局最优点。下面就该文中的一些关键点进行说明并假定所有的优化问题都是求最小值,所有的目标函数值大于0。

1.1 连续空间的离散化

该文采用基于十进制的点离散方式将待优化问题的问题空间每一维进行离散化。设第i维的定义域为[xi1,xi2],要求精确到小数点后r位。则第i维共有(xi2-xi1)×10r个点。用十进制来表达这些点最少需要的十进制位数为int(xi2-xi1)+r位,其中int(xi2-xi1)表示大于(xi2-xi1)的最小整数。由此可以确定优化问题定义域中各维的位数pi,由此将第i维离散化成一个10行pi位的矩阵,将各维的矩阵相连接就组成一个10行n列的矩阵来表示优化问题的问题空间(n为问题空间各维矩阵的列数的和)。对每一列的各行,其行号变化从0到9表示在这一列上可能的取值。由此将连续空间转换成一个在10行n列矩阵上取值的离散空间。可以根据需要在这些离散点上存储信息,如信息素,一般信息素初始化时信息素矩阵pheromone的初始值为1,则初始化后信息素矩阵可表示为表1所示。

1.2 信息素矩阵的初始化

目前关于连续空间优化的蚁群算法都是将信息素初始化为一个常量值(如1)后,在迭代时所有蚂蚁根据状态转移规则进行选择,确定在各步时的选择,再对最优蚂蚁所经路径进行信息素更新。为了使蚂蚁在一定程度上对选择的值所属的区间有所认识,该文提出在信息素矩阵的初始化之后,将连续空间每一维变量分成相同个数的较大的子区间,从第一个子区间到最后一个子区间,先在各维的相同子区间内随机取值(各维都在第i个子区间内随机取值),然后计算相应值的目标函数值,更新相应路径上的信息素值。在上述的离散化方式中,可以依次选取各维离散矩阵的第一列的各位,各维中的其他列中的位随机选择,以此组成所求问题的一个候选解来计算目标函数值。

1.3 信息素更新

对每次迭代中的最优解需进行信息素更新,更新公式为:

其中volatile为信息素挥发系数,τij(t)表示信息素矩阵中第i行第j列在t时刻时的信息素强度,f(t+1)为第t+1次迭代时最优解的目标函数值。

1.4 状态转移公式

采用上述的离散方式后,蚂蚁在选择下一个节点时只有十种选择,该文采用的状态转移公式与ACS中的状态转移公式一样,即当随机数q

1.5 变异

蚂蚁选择一个数字后,为使蚂蚁探索未知节点或向更好的点靠近,对蚂蚁所选择的数字进行变异。其思想是蚂蚁选择一个数字后以一定概率p0变异为与所选数字直接相邻的某一个数字。

为了指导蚂蚁向未探索节点或比当前节点更好的节点变异,可建立一矩阵visible,其大小与信息素大小相同10行n列,visible矩阵值的值可按如下方法构建:

1)visible矩阵的初始化。最初定义域离散后的每个节点都未被探索,因此visible矩阵应该初始化为某一值,表示节点未被探索。该文中将visible中每个元素初始化为0,表示每个节点都没有被探索过。

2)visible矩阵的更新。设每一次迭代中有m只蚂蚁构建新的候选解,m只蚂蚁中的每一只蚂蚁构建一个候选解后,根据候选解的目标函数值来更新visible矩阵。对候选解经过的每一个节点,若其值为0,表示此节点以前未被探索,则更新为此候选解的目标函数值;否则比较visible中此节点上存储的值与候选解的目标函数值的大小,若后者较小,则将visible中此节点的值更新为候选解的目标函数值。因此visible矩阵更新可以表示式(3),其中visibleij(t+1)的值为:f(t+1),若第t+1次迭代最优解经过信息素矩阵第i行第j列且visibleij(t)=0;min(f(t+1),visibleij(t)),若第t+1次迭代最优解经过信息素矩阵第i行第j列且visibleij(t)!=0;visibleij(t),第t+1次迭代最优解不经过信息素矩阵i行第j列。

构造了visible矩阵中,就可以用来指导蚂蚁变异,若蚂蚁在构建候选解的过程中已经选择了某一节点,且该节点要进行变异,只须比较visible矩阵中选择的节点所在列中与选择的节点直接相邻的两个节点上的值的大小,选择值较小的节点为变异后的值。

1.6 局部搜索--步长加速法

在蚁群算法中,为获得期望的精度而使迭代次数大大增加,为了减少运算量,该文利用蚁群算法在较少的迭代次数少收敛到优化问题最优解的较小的邻域内某点,再从蚁群算法的搜索到的最优点用步长加速法来搜索最优解,这样可以大大减少运算量。其算法流程见文献[5]。

2 指导变异蚁群算法的算法流程

本节介绍新蚁群算法的主要流程,主要过程如下:

1)蚁群算法初始化,包括蚂蚁数目ant_num、迭代次数iteration、信息素挥发系数volaolittion(2-14)tile、信息素相对重要程度系数Alpha、伪随机比例因子Q0等。

2)根据待优化问题的定义域和各维的精度要求,确定各维变量离散化后的点的数目,以及表示这些点的十进制数的位数。

3)根据2)的结果确定信息素矩阵大小,初始化信息素矩阵pheromone和visible(visible矩阵的大小及作用见上一节)。

4)对各维,按最高位分别取0、1、2、3、4、5、6、7、8、9其余各位随机取值的方式来确定在各维上的一个值,在各维上的取值组成一个候选解计算目标函数值,根据此函数值按式(1)进行信息素更新,同时按式(3)更新visible矩阵。

5)开始进行迭代,每一次迭代按式(2)选择下一个节点,构造候选解,选择候选解中最优的解来更新pheromone矩阵和visible矩阵直到迭代结束或结束条件出现。

6)以蚁群算法寻得的最优解出发,用步长加速法进行寻优,显示求得的最优解。

3 实验仿真

仿真实验中参数设置如下:蚂蚁数量为5,蚂蚁迭代次数为300,信息素挥发系数为0.1,信息素相对重要系数2,变异概率0.1。因为测试函数值都大于0,因此设定当迭代次数大于等于300或目标函数值最小值与0的绝对值小于1e-3时蚁群算法迭代结束。

例1 Percy函数

此函数在(0,0)点处有最小值3。

例2 Levy函数

此函数有多个局部最优解,全局最优解x*=(1,1,…,1),最优值f(x*)=0。

例3 Rastrigin函数

此函数有多个局部最优解,全局最优解x*=(0,0,…,0),最优值f(x*)=0。

用该文提出的算法对以上三个测试函数优化,对每个测试函数连续运行十次,若每次找到的最优点达到要求的精度或找到的最优目标函数值与理论最优值差的绝对值小于1e-3,则认为此次运算收敛。运算结果见下表,表中的收敛率为运行十次中的收敛次数所占百分比,计算目标函数次数为十次运算中调用目标函数的平均值。

从上表可以看出,应用该文提出的蚁群算法对连续函数进行寻优,均能获得满足精度要求的最优解。

为了比较该文算法的性能,该文用文献[6]中用到的无约束全局最小优化测试函数进行测试,并将优化结果与[6]中的优化结果进行比较,测试函数见相关文献

由于Branin函数、Martin&Gaddy函数以及Sphere model函数不能从相关文献中获得测试数据,因此文献[6]作者自已编写遗传算法(GA)程序来进行优化,将其优化结果与作者提出的CACO(continuous ACO,连续蚁群优化算法)进行比较,其中遗传算法采用9-18位二进制位来表示测试函数中各维变量,群体规模在15-50之间,使用单点交叉。GA算法与CACO算法以及该文算法对这三个函数的优化比较见图2,其中对每个测试函数,各个算法都运行25次,若能达到要求的精度则认为优化运算成功,优化运算成功的次数占总运行次数的比率为成功率。

从上表可以看出,对这三个测试函数,该文提出的算法都能收敛到全局最优解,且计算复杂性大大优于遗传算法,同时该文提出的算法的计算复杂性稍微优于CACO,在某些情况下大大好于CACO。从表中可以看出,对Sphere model函数,该文提出的算法比GA和CACO调用目标函数次数有大幅的减少,这可能是Sphere model函数对该文算法中的信息素初始化比较敏感,所以能快速收敛。

4 结束语

该文详细介绍了蚁群算法在连续空间优化上的一些关键问题如连续空间的离散化,以及在离散化了的连续空间上的状态转移方式。同时也详细阐述了该文提出的新型高精度蚁群算法的几个关键方面,并用实验对该文提出的算法进行测试,结果表明与遗传算法、连续蚁群优化算法、模拟退火算法相比,该文提出的算法计算复杂性大大减少。

参考文献

[1]Coloni A,Dorigo M,Maniezzo V.Ant system:Optimization by a colony of cooperating agent[J].IEEE Trans on Systems,Man and Cybernet ics-Part B:Cybemeties,1996,26(l):29-41.

[2]Thomas Stützle,Holger H.Hoos.MAX-MIN Ant System[J].Future Generation Computer Systems,2000,16:889-914.

[3]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):1351-1356.

[4]陈烨.带杂交算子的蚁群算法[J].计算机工程,2001(12):74-76.

[5]粟塔山,彭维杰,周作益,等.最优化计算原理与算法程序设计[M].长沙:国防科技大学出版社,2001:83-86.

一种变异的改进粒子群优化算法第2篇

粒子群优化算法(PSO)是由Kennedy和Eberhart等于1995年发明的一种基于群智能的进化计算技术[1,2],来源于对鸟群捕食的行为研究。后来shi等人[3]引入惯性权重,形成了当前的标准版本。PSO的优势在于概念简单,容易实现并且没有许多参数需要调整,目前已经成功应用于结构设计、神经网络[4]、多目标优化[5]等工程优化中。

PSO算法收敛速度较快,但会出现早熟收敛,甚至不收敛的情况,尤其对于多峰函数而言不能令人满意,对高维函数优化在求解质量上和速度上有些缺点。对PSO算法进行改进提高优化性能为该领域的一个研究热点。相继出现了一些改进的算法,然而这些算法在一定程度上改善了算法的优化性能,但很难在搜索精度和早熟收敛之间达到平衡。针对上述缺点,本文提出了一种改进的粒子群算法,该算法引入了合作算子[6],在迭代优化过程中对粒子进行两种合作策略的变异,使粒子群体保持多样性。本文分析了粒子速度更新公式的基础上,提出了动态改变粒子的粒子分享个体最优和群体最优的信息比例的方法,使算法初期具有全局搜索能力,后期具有较好的搜索精度。实验结果表明,该算法具有较好的优化效率。

2. 粒子群算法介绍

2.1 PSO算法基本原理

PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个叫做个体极值,记为Pi。另一个极值是整个种群目前找到的最优解,这个极值是全局极值,记为Pg。

设搜索空间为D维,总粒子数为n,第i个粒子表示为xi=(xi1,xi2,…xi D);第i个粒子的历史最优位置记为Pi=(pi1,pi2,…pi D);整个群体经历过的最好位置记为Pg=(pg1,pg2,…pg D),粒子速度记为Vi=(vi1,vi2,…vi D)。则对于每一代,每个粒子的位置根据如下方程变化。

其中c1和c2是非负常数并且通常取值为2,称为学习因子。r1和r2是介于[0,1]之间的随机数。每一维粒子的速度都会被限制在一个最大速度Vmax,如果某一维更新后的速度超过用户设定的Vmax,那么这一维的速度就被设定为Vmax,即vid∈[-Vmax,Vmax]。

2.2 算法流程

标准PSO的算法流程如下:

Step1:初始化所有粒子,包括随机位置和速度;

Step2:评价每个粒子的适应值;

Step3:对每个粒子,将其适应值与其经历过的最好位置Pi作比较,如果较好,则将其作为当前的最好位置Pi;

Step4:对每个粒子,将其Pi与全局所经历的最好位置pg作比较,如果较好,则重新设置pg;

Step5:根据公式(1)和(2)进行速度和位置(解)的迭代;

Step6:重复Step2～Step5,直到满足算法停止迭代的条件。

3. 改进的粒子群优化算法(IPSO)

标准的PSO算法中,若粒子找到一个最优位置,则其他粒子会迅速向其靠拢,此时若最优位置为局部最优,则粒子就可能陷入早熟收敛。这样就导致了粒子群体不能在优化空间重新搜索和运动。为了使粒子能进一步进化和继续优化,本文采用了合作算子对历史最优粒子进行变异的方法。这样不仅使变异后历史最优粒子更好地引导粒子的运动,使粒子摆脱局部收敛。还可以进化整个种群的最优粒子,更好地搜索最优解,提高搜索精度。同时对最优粒子采取保序策略,确保群体最优解向好的方向进化。

3.1 合作算子

设两个个体粒子为p1=(x1,x2,…xD)和p2=(y1,y2,…yD)。如果∈(0,1)

合作策略1中,q和r由式(3)产生:

其中,βk为0和1之间的随机数。

合作策略2中,由式(4)产生:

其中,1

3.2 对运动公式进行动态调整

由于算法的优化效果取决于粒子运动的两个公式,所以改动公式,就相当于是粒子的运动发生了变化,进而产生不同的优化效果。

从公式(1)可见,粒子速度更新由三部分完成。第一部分反应粒子当前速度的影响,联系粒子当前的状态,起到了平衡全局和局部搜索的能力;第二部分反应认知模式的影响,即粒子本身记忆的影响,使粒子具有全局搜索能力,避免陷入局部极小;第三部分反应社会模式的影响,即群体信息的影响,体现粒子间的信息共享。令准1=c1r1,准2=c2r2,显然准1和准2是介于0和2之间的随机数。显然在算法初期应该增加粒子的群体搜索能力,这样必须加强粒子本身记忆的影响,削弱群体最优粒子的影响。这时,令准1=1+准1/2,准2=准2/2,这样就有,准1∈(1,2),准2∈(0,1),较好地增加了个体经验对粒子速度的影响,提高群体多样性,从而增加算法的全局搜索能力,有效增强避免早熟收敛能力。算法后期,由于大部分粒子都聚集在最优粒子周围,为了找到更好的结果,需要增加最优解附近的搜索,需要最优粒子分享更多的信息给整个种群。这时,令准1=准1/2,准2=1+准2/2。这样粒子局部搜索能力得到了加强,提高了优化精度。

4. 仿真实验和结果分析

本文采用了标准PSO算法和改进算法进行实验,并将结果进行对比。两种算法采用相同的参数设置。线性下降的惯性权重的变化范围是[0.3,0.9]。实验中的种群规模设置为30,粒子的维数为30,最大的迭代次数为1000次。CS设置为0.5,保证粒子的两种变异方式都能平均地采用。两个测试函数如下:

Rastrigin函数

f1(x)=-10cos(2πxi)+10],xi∈[-5.12,5.12],大量局部最优点的复杂多峰函数。

Griewank函数

算法迭代次数为1000次。算法对每个函数独立运行30次,取最优值和平均最优值作对比。结果如表1。

从表中的测试结果中,可以看出本文IPSO算法的最优收敛值和平均收敛值要优于标准PSO,这充分说明了IPSO算法具有更好的搜索精度,较强的抗早熟能力和较快的收敛速度,并且算法也具有较好的稳定性。

5. 结论

本文提出的改进PSO算法,对于每次迭代,粒子群体之间采用合作算子进行变异进化,合作算子通过粒子之间相互作用来增加彼此的适应度,提高了算法的收敛速度和精度。对于算法不同阶段粒子运动公式的改变,可以较好地平衡粒子的全局搜索和局部搜索的能力,避免算法陷入早熟收敛。通过对2个基准测试函数的仿真,证明了本文的IPSO算法对于高维、多极值点的函数有较好的效果。

摘要：为了解决粒子群优化算法容易陷入局部最优和后期搜索精度不高的问题,提出了带有合作算子的改进粒子群算法。合作算子和粒子运动公式的动态调整改善种群的多样性并且提高了搜索精度。从算法的收敛性、准确性和稳定性等方面对这种改进算法进行分析和实验,发现均优于标准粒子群优化(PSO)算法。

关键词：粒子群算法,合作算子,群智能

参考文献

[1]Kennedy J,Eberhart R.Particle swarm optimization[A].Proc IEEE Int Conf on Neural Networks[C].Perth,1995.1942-1948.

[2]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[A].Proc 6th Int Symposium on Micro Machine and Human Science[C].Nagoya,1995.39-43.

[3]Shi Y,Eberhart R.A modified particle swarm optimizer[C].In:IEEE World Congress on Computational Intelligence,1998:69-73.

[4]王建芳,李伟华.基于扩展的T-S模型的PSO神经网络在故障诊断中的应用[J].计算机科学,2009,36(9):224-245.

[5]刘衍民,牛奔,赵庆祯.基于交叉和变异的多目标粒子群算法[J].计算机应用,2011,31(1):82-84.

变异算法第3篇

差分演化算法 (Differential Evolution, DE) 是由Storn和Price提出的一种基于随机搜索的用于解决函数优化问题的群智能算法[1], 该算法原理简单、实现容易、鲁棒性强, 目前已经成功在模式识别、机械工程等多个科学与工程领域得到了应用[2,3]。

为了改善DE算法的性能, 近十年来众多研究人员对DE中的变异策略和参数F、CR进行了深入的研究, 提出了众多改进方法。

为加快DE算法的收敛速度, 同时保持种群个体的多样性, 本文提出一个基于混合变异策略和参数自适应调整的动态差分演化算法 (COSADDE) , 算法选用3种变异策略 (DE/rand/1、DE/rand/2、DE/current-to-pbest[4]) 作为候选池, 计算每种策略的历史成功率, 每个个体采用轮盘赌的机制从候选池中选取一个变异策略进行变异, 算法采用动态机制让变异交叉生成的优秀候选个体直接替换目标个体, 参与后续个体的进化来加快算法的收敛速度, 实验表明COSADDE算法能取得较好的求解精度。

2 差异演化算法

DE主要含有变异、交叉、选择三种操作[5], 其基本思想如下:

(1) 在当前种群pop中随机选择三个不同的目标个体p1, p2, p3按公式1生成差分变异个体hi, 其中i≠p1≠p2≠p3, η为缩放因子

(2) 将目标个体xi与变异个体hi按公式2进行交叉操作生成试验个体ui

(3) 从目标个体xi与试验个体ui中选出一个作为下一代的个体

3 混合变异的动态差分演化算法

3.1 动态差分演化

经典DE算法, 第i代种群中的个体在演化过程中一直保持不变, 某目标个体演化产生的优秀个体进入下一代, 在本代后续个体演化中并不发挥作用, 要到本代结束后才在第i+1代中参与演化, 这样的机制对一定程度上影响了DE算法的收敛速度。COSADDE算法采用动态变异机制进行演化, 对于第i代种群中的目标个体Xi, G通过变异、交叉操作之后形成的试验个体ui, G, 如果f (ui, G) <f (Xi, G) , 则用ui, G直接替换Xi, G, 在后续个体的演化操作中Xi, G将参与其中, 这种动态变异机制使当前种群中个体经演化操作得到的优秀染色体不必等到下一代, 而是直接就参与到本代后续个体的演化, 将能较好地提高算法收敛的速度。COSADDE与DE的流程框架对比如图1所示。

3.2 混合变异策略

变异操作是DE产生后代个体的主要方式, 目前有以下种常用的变异算法:DE/rand/1、DE/rand/2、DE/best/1、DE/best/2、DE/current-to-rand/1、DE/target-to-best/1。JADE算法提出了一个新的DE/current-to-pbest策略, 这些策略各有优、缺点, 由于不同类型的测试函数有着各自的特点 (如单峰、多峰、噪声等) , 对不同变异策略敏感度不同, 在进行函数优化的时候, 采用单一的策略往往难于取得比较好的效果。

综合利用各种变异策略的优点, 本文的算法中设置一个变异策略候选池, 在候选池中设置三个策略DE/rand/1、DE/rand/2、De/current-to-pbest, 其中DE/rand/1具有良好的全局探索能力, 并可无偏向的随机选择新的搜索反向[6], DE/rand/2策略能产生比DE/rand/1/bin更多的不同试验向量来, 可较好的改善种群的多样性[7], DE/current-to-pbest/1/bin策略能较快的加速算法的收敛[8], 通过这三种策略的组合, 能取得较好的收敛速度同时又能保持种群的多样性避免”早熟”。

每个目标个体xi变异时, 从候选池中选择一个策略进行变异, 达到每一代、每一个个体选用的策略都不相同的目的。为了让效果好的变异策略更多的发挥作用, 对每个变异策略设置一个成功率pk, G来记录在当前第G代种群的前LP代内, 第k种策略产生的候选解被选择进入下一代的概率, pk, G越高, 表示第k种策略在前续的演化中表现越好, 则在本代个体进行轮盘选择的时候, 被选中的概率也就越高。pk, G的计算如公式 (4)

其中

1) nsk, g:在第g代第k个策略产生的所有候选个体中能被选中进入下一代的个数k=1, 2, 3。

2) nsk, g:在第g代第k个策略产生的所有候选个体的个数k=1, 2, 3。

3) ε=0.01, 用于避免初始时sk, g取值为0。

4) LP:记录变异策略在当代之前发生作用的代数, 根据文献[3]的建议, 取值为50。

4 实验与结果

为了验证COSADDE算法的有效性, 选用文献[5]所列的13个典型的测试函数上进行实验, 环境CPU为Intel Core i3, 内存为4GB, 采用Mat Lab编码实现。本文将COSADDE算法的实验结果与近年来提出的3种代表性的DE算法:Sa DE[5]、JADE[7]、Co DE[8]进行对比, 表1、2分别给出了4种算法在D=30、D=100时求解函数得到的平均误差和标准差。算法的参数设置为:NP=50, 最大函数评价次数为FES=10000*D, 每个算法独立运行25次, 为客观评价算法在每个测试函数上的差异程度, 对所实验得到的数据进行在0.05显著水平下的双侧t-检验, “+”、“-”、“≈”表示算法的性能优于、劣于、相当于COSADDE算法。

从表1可以看出, 当D=30时, COSADDE算法在12个函数中不差于其他算法, 特别是在f1, f3, f5三个函数上效果明显, 而在f6, f8, f9, f11, f12, f13等7个函数与其他算法相差不大, 均能取得全局最优解或接近最优解, 当D=100时, 从表2可以看出, 与其他4种算法对比, COSADDE总体效果更加明显, 比Co DE、j DE、Sa DE分别有11、9、8个函数更优, 特别是在f12、f11、f9三个函数上表现更明显。因此, COSADDE总体上的性能优于其它4种对比算法, 且受维度影响更小, 算法鲁棒性较强。

5 结论

为提高DE算法的求解优化问题的性能, 本文提出了一种基于混合变异策略和参数自适应调整的动态差分演化算法, 算法采用优秀试验个体在本代直接替换目标个体, 让优秀基因参与后续个体的演化, 能较好地提高算法的收敛速度, 对于每个个体从包含3种变异策略 (DE/rand/1、DE/rand/2、DE/current-topbest) 的候选池中, 根据每种策略的历史成功率, 选取一个策略进行变异, 这三种策略能较好地平衡收敛速度和种群的多样性, 避免算法陷入早熟。实验中用13个测试函数与其他典型的DE算法进行性能对比, 仿真结果表明, COSADDE算法在大部分函数上的求解精度更高。

摘要：为提高差分演化算法的收敛速度和求解精度, 提出了一种基于混合变异策略和参数自适应调整的动态差分演化算法, 该算法首先选用3种变异策略作为候选池, 通过记录各策略的历史效果来设置其候选概率, 每个个体采用轮盘赌的机制从候选池中选取一个变异策略进行变异, 在选择时采用动态机制让变异交叉产生的优秀试验个体直接替换目标个体来提高算法的收敛速度, 算法的变异算子F、交叉算子CR根据进化中的反馈信息自适应动态调整。利用13个不同类型的经典测试函数进行实验, 结果表明算法在收敛速度和求解精度上具有比较好的优势。

关键词：差分演化,动态变异,混合策略

参考文献

[1]Storn R, Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization, 1997, 11 (4) :341-359.

[2]Das S.Differential evolution:A survey of the state of the art[J].IEEE Transactionson Evolutionary Computation, 2011, 15 (1) :4-31

[3]Storn R, Price K.Home Page of Differential Evolution.http://www.icsi.berkeley.edu/~storn/code.html

[4]QinAK.Differentialevolutionalgorithmwithstrategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation, 2009, 13 (2) :397-416

[5]Qin A K, Suganthan P N.Self-adaptive differential evolution algorithm for numerical optimization[C].Proceedings of IEEE Congress on Evolutionary Computation.Edinburgh, UK, 2005:1785-1791.

[6]王丛佼, 王锡淮.基于动态自适应策略的改进差分进化算法[J].计算机科学, 2013, 11 (40) :265-266

[7]梁静, 周钦亚.基于混合策略的差分进化算法[J].郑州大学学报 (工学版) , 2013, 9 (34) :59-60

基于变异MD5的快照差分算法第4篇

对于增量数据检测方法在理论上的研究成果最初由斯坦福大学的W. J. Labio和 H. Garcia-Molina在1995年发表的一份技术报告[2]中提出, 他们从数据库的连接算法如Nested-Loop Join、Merge Join等出发引申出多种可用于比较大型数据库快照比较的算法。并在此研究基础上, 1996年在文献[3]中他们又分析总结出了适用于数据仓库的几种高效的快照差分算法, 包括Sort Merge、Partition Hash、Window算法等。

1快照差分算法

1.1问题的形式化描述

对于快照差分问题, 在文献[4]中有如下描述:有两个快照SF1, SF2, 目标是产生一个输出△F={r1, r2, …, rn}, 其中rn为增量记录元组。增量元组的形式以及他们的语义为

(1) :

快照SF1中存在关键字为Ki的记录, 而快照SF2中不存在关键字为Ki的记录。这意味着对源表执行了删除操作, 删除了一条关键字为Ki的记录。

(2) :

快照SF1中不存在记录, 而快照SF2中存在记录。这意味着对源表执行了插入操作, 新插入一条记录。

(3) :

快照SF1中存在记录, 快照SF2中存在记录, 其中Bj是Bi的更新。这意味着对源表执行了更新操作, 将记录的Bi更新为Bj。即SF1通过△F 中每个记录的变换后变换成SF2, 即SF1+△F= SF2。

1.2 Sort Merge 简介

Sort Merge的过程为:算法的输入是旧快照SFundefined (有序) 、新快照SF2, 首先对输入的新快照SF2进行排序, 生成有序的快照SFundefined;然后依次扫描SFundefined、SFundefined中的元组从一端开始加以逐一比较, 将其中失配值较小的元组作为被删除元组或被插入元组输出到差分结果中去。

输入:SFundefined (有序) 、SF2 (无序)

输出: Fout (快照增量) , SFundefined (有序)

方法:

(1) SFundefined←排序 (SF2) ;

(2) rundefined←从SFundefined中读取下一个记录;

(3) rundefined←从SFundefined中读取下一个记录;

(4) while (r1!=NULL∧r2!=NULL)

(5) if ( (r1=NULL) V (r1.K>r2.K) )

(6) Fout←输出 ()

(7) rundefined←从SFundefined中读取下一个记录;

(8) else if ( (r2=NULL) V (r1.K

(9) Fout←输出 ()

(10) rundefined←从SFundefined中读取下一个记录;

(11) else if (r1.K=r2K)

(12) if (r1.B!=r2B)

(13) Fout←输出 ()

(14) r2←从SFundefined中读取下一个记录;

(15) r1←从SFundefined中读取下一个记录;

算法1

采用多路归并排序时需要2×|F |×log|M| | F |的IO量来对一个具有|F|大小的文件进行排序, 所以本算法的总IO量为2×|SF2 |×log|M| | SF2 | + |SF2| + |SF1|。当然这是最原始的方法, 我们可以将排序过程的最后一次归并和对快照的比较同时进行, 这样算法IO量就可以减少到2s×|SF2 |s×log|M| | SF2 | +|SF1| (详见文献[3]) 。

2基于压缩的Sort Merge算法

2.1压缩技术简介

压缩可以在多个层次和有多种压缩方法, 其相应的处理方法和效率不尽相同。本节提出元组压缩的概念、并把元组压缩的利弊提出来, 在下一节中详细讨论使用的压缩算法, 在本节简单的将其说明为compress (x) 。

元组压缩意思是指将一个元组压缩为一个较小的元组, 而这个压缩可以是对字段进行分别压缩, 也可以是对字段进行组合压缩。在本文提出的算法中采用的是不压缩元组的关键字K, 而把元组余下的字段B组合压缩为b, 即b = compress (B) , 即将元组压缩为。

元组压缩的优势很多, 可以把快照文件的大小减小, 这样在排序时就减少排序的总的IO量;或者甚至可以将以前不能完全放入内存中的快照压缩到可以完全放入内存, 使排序操作可以在内存总一次进行, 使快照的散列桶算法 (注:另一种快照差分算, 详见文献[3]) 的快照能够完全散列到内存中的桶中进行运算;而且压缩的快照文件还可以节省进行快照备份占用的磁盘空间。

当然压缩也有其劣势, 如可能会导致两个不同的元组在压缩后具有相同值, 导致快照差分可能产生错误的结果。然而估算一下出现错误的可能时间, 经过分析这个时间是否完全可以忍受的。比如, 将元组中的B压缩为一个64位的长整数, 那么两个不同的B可能压缩出同一个长整数的可能是2-64, 当然随着需要比较的元组增多相应的出错的概率也增加。假设每天比较512M的快照, 快照中每个元组具有256位, 这样可以推算出现错误的期待时间。512M的文件中可以有221即2097152个元组, 这样一天不出现错误的概率为

Pday= (1-E) rec (F) ≈ (1-2-64) 2097152 公式 (1)

再用这个概率, 就可以算出在出现错误前可以期待的时间Ngooddays为

undefined公式 (2)

因此, 得出结果是8.7961E+12天或者说2.4099E+10年, 由此得出的这个结果是惊人的大, 在非数字敏感行业, 这个数字都将是可接受的。这个数字还是在所得出的冲突序列是随机序列的情况下, 然而一般存在于我们的文件中的元组都是特定领域有意义的序列, 所以从现实使用上来说, 还得除以一个随机序列在其领域有意义的比率。虽然这个比率是难以估计的, 但是可以想象这个比率肯定是比较小的, 这样又继续增加了错误发生前我们可以期待的时间到K×Ngooddays。考虑一下一般的增量检测所使用的情形, 如建设各种数据仓库或者数据挖掘等, 可以对于这样的一个极小的差错率和出现差错的期待时间间隔是完全可以接受的。

2.2压缩的Sort Merge算法描述

下面提出基于压缩的Sort Merge算法, 同时将之前提到的对原始的算法的改进引入现在的算法中, 那么我们现在的算法的描述如下:

输入:SFundefined (有序) 、SFundefined (无序)

输出: Fout (快照增量) , SFundefined (有序)

方法:

(1) SFundefined←压缩 (SF2) ;

(2) SFrunundefined←排序 (SF2c) 一直到最后一次归并前;

(3) rundefined←从SFundefined中读取下一个记录;

(4) rundefined←从SFrunundefined中读取下一个记录;

(5) SFundefined←输出 () ;

(6) while (r1!=NULL∧r2!=NULL)

(7) if ( (r1=NULL) V (r1.K>r2.K) )

(7a) 利用r2.K到SF2中读取出未经压缩的r2.B;

(8) Fout←输出 ()

(9) rundefined←从SFrunundefined中读取下一个记录;

(10) SFundefined←输出 () ;

(11) elseif ( (r2=NULL) V (r1.K

(12) Fout←输出 ()

(13) rundefined←从SFundefined中读取下一个记录;

(14) elseif (r1.K=r2.K)

(15) elseif (r1.b!=r2.b)

(15a) 利用r2.K到SF2中读取出未经压缩的r2.B;

(16) Fout←输出 ()

(17) rundefined←从SFrunundefined中读取下一个记录;

(18) SFundefined←输出 () ;

(19) rundefined←从SFundefined中读取下一个记录;

算法2

如上算法的描述, 其中在 (7a) 和 (15a) 中读取元组B部分时, 默认的结构是在SF2中含有包含元组K的索引。因为在常见的数据库管理系统或者常用的文件系统中, 如果对某一文件需要经常进行随机的修改, 那么正确的设计就必须对文件或者表建立一个索引, 以提高系统的性能。上面的算法IO开销为 |SF2| +|SF2c| + 2 ×|SF2c |× log|M| | SF2c | + |SF1c| + N×|r2|。假设一个元组压缩前后的比例为k, 且前后快照大小相差不大其大小为kF, 这样原始非压缩时的IO量减去现有IO量可近似的被化简为2F× (k×log|M| (k×F) –2×log|M|F) 或2F× (k×log|M| (k×F) – 2) 。由于使用基于压缩算法的前提是上式中的k较大, 那么上面两个式子的括号部分明显的将大于零, 所以算法的IO量有显著减少。

2.3压缩算法的选择

计算技术发展至今已经有大量的压缩算法, 主要的算法都可以归结为将原始记录通过hash函数的方式散列为一个整数的方式。对于一般的hash函数常见的评价标准有:①随机均匀分布性, ②每个输入位对每个输出位的影响均等性, ③任意两个输出位间相互独立性, ④能够产生相同值的两对源数据不可预知性 (不可逆推) 等。在这些评价标准中, 最后一个标准是密码学研究的重点内容, 主要是为了保持被压缩内容的保密性和不可逆推。然而对于此文中的应用来说压缩是用在内部进行的, 不存在对其进行恶意的攻击, 寻找相同的hash值对来制造错误。标准④在文献[5]等文献中有大量的相关讨论, 但是它不是本文应用要求的重点, 本文的应用只需要前面三个性质得到充分的保证。

MD5算法是在文献[6]中提出的一个被广泛使用的称为信息摘要的压缩算法, 其主要过程包括了对字符串的填充 ( Padding) 、分段求摘要 (Digesting) 和最终摘要的输出 ( Outputting) 三个步骤。其中填充是指首先需要对信息进行填充, 使其字节长度对512求余的结果等于448。在填充完成后, 再往后面附加一个以64位二进制表示填充前信息的长度, 使现在的信息字节长度等于N ×512 +448 +64 = (N +1) ×512, 即长度恰好可以被512整除。输出相对更简单, 将结果根据需要的格式把64位 (bit) 的长整数输出即可。其中分段求摘要是算法的核心, 下面介绍算法的处理过程, MD5 的分段求摘要的函数是:

digesti = f ( Mi , digesti- 1 ) 公式 (3)

其中, Mi 是填充后报文的第i段, 是64 × 8位 (bit的字符串; digesti 是第i 次分段求得的摘要 ( d0 是一个给定的常数) , 均是128 位 (为便于处理, 分成了四个32 位的长整数) 的字符串。公式 (1) 在具体计算中又分为四轮 (Rounds) , 可以用公式表示如下:

digesti = f 5 ( f 4 ( Mi , f 3 ( Mi , f 2 ( Mi , f 1 (Mi , digesti- 1 ) ) ) ) , di- 1 ) 公式 (4)

其中, f i ( i = 1 , 2 , 3 , 4 ) 是第i 轮的计算函数, f 5 是四轮完成之后的一次操作 (实际上就是用digei - 1 与f 4 产生的四个32位的长整数分别相加) 。而其中四轮主要用到的处理函数分别为:

F (X, Y, Z) = (X And Y) or ( (Not X ) And Z)

G (X, Y, Z) = (X And Z) or ( Y And (Not Z) )

H (X, Y, Z) = (X Xor Y Xor Z)

I (X, Y, Z) = ( Y Xor (X or (Not Z) ) )

其实这四轮的处理都是极其相似的, 而且在MD4中只有前三轮的处理, 其实算法使用四轮循环的主要原因是基于我们前面讲到的hash函数评价标准中的标准④。然而我们已经讲到在我们的使用环境中, 标准④不是重点, 所以我们可以将这四轮循环减少为每次只进行一轮, 为了保持算法的一致性四轮处理方法在处理过程中循环使用。

于是我们得到改进后的算法为

digesti = f 5 (f i%4 (Mi , digesti- 1) , di- 1 ) 公式 (5)

对得到的算法我们首先讨论其各个输出位的独立性:我们用逆推的方法, 因为原始算法中的四轮循环都是相似的, 如果我们假设有一轮不具有独立性, 那么整个四轮都是不具独立性, 所以最后的结果也将不具有独立性, 这样最终原始算法将不符合hash算法的基本评价标准, 所以每轮处理的输出位间都是具有独立性的。

再用用单尾χ2检验对标准①进行测试检验。这个长整数具有64位 (bit) , 是一个非常大的数, 直接对其分布进行χ2检验的话将会非常的困难。因此在检验中我们将得到的hash值表示位16进制的方式, 对其每一个16进制位的分布来进行χ2检验。如果用分解的方式, 对长整数的每一个位进行求χ2, 验证每一位都服从0到15的各个整数的均匀离散分布。

undefined公式 (6)

得出第一轮处理后每一位16进制数的χ2值分别为

由于xundefined (5) =34.267, 而34.267大于上表中的所有值, 所以可以确定结果是符合1-α=0.995域内的均匀离散分布。实验相同的检验方法对后面的三轮得到的结果进行χ2检验, 他们都是符合1-α=0.995域内的均匀离散分布的。

通过这个方法可以得出输入数据中的每一位对输出的每一位的绝对影响是基本均等的 (由于篇幅的限制, 不列出实验数据) 。

改进的算法将原始算法每段的四轮处理改为每次只进行一轮, 由于压缩算法的主要处理过程就是对报文的处理, 这样除去算法的原始数据录入速度的因素, 变异的算法在速度上可以比原始算法快到3/4左右。具体速度这里不进行测试, 而是在最后直接测试基于变异的MD5算法和基于原始MD5算法的快照差分的差别。

2.4应用测试

本节将对前面提出的算法进行试验数据的测试和比较, 对原始的Sort Merge, 使用原始MD5的压缩的Sort Merge算法和使用改变后的MD5算法的Sort Merge三个算法进行实验数据的测试, 并对其结果进行比较。其实验数据如图1所示。

在实验中源表的元组长度被设置得比较大 (每个元组2.5K左右) , 且只具有相对较短的关键字, 将使原始元组大小除以压缩后元组大小的比例称之为元组压缩比, 即本实验的元组压缩比达到50/1的比例左右。这样的元组压缩比算法的效率得到较明显的提升, 但是算法的速率提升是随着元组压缩比相关的, 并不是任何元组压缩比下算法都能达到这样的效率提升。即由于压缩代价, 当压缩带来的效率提升小于压缩的代价时, 压缩算法的速率会小于原始算法。这个临界值跟压缩算法的速度有关, 不同的系统因其CPU, 内存等的不同临界值将会产生变化, 所以本算法具体的适用范围需要用户根据自身系统进行测试确定。同时测试结果也表明基于变异MD5的算法相对基于原始MD5的算法速率有一定的提升, 这样基于变异MD5的快照差分算法适用范围也随之增加。

3结束语

本文介绍和分析了快照的概念和原始的Sort Merge算法, 根据其代价分析提出了基于压缩的快照差分算法的思想。选用被广泛使用的MD5算法作为基础, 并根据其特点和实际需求进行了简化。将简化后的变异的MD5算法运用到压缩的Sort Merge算法中。实验数据表明, 采用基于变异的MD5的Sort Merge压缩算法相对于原始的无压缩算法和基于原始MD5算法的压缩算法在适用的元组压缩比下处理效率上有一定的提升。当然在文中也提到本文提出的算法在使用上是有一定限制和适用范围的, 比如在对数据敏感的行业应用时是受到限制的, 在元组压缩比低于那个临界值时算法并不能提供效率的提升。

摘要：如何有效、及时地检测和抽取信息源的增量数据是数据仓库及各种数据集成的首要问题, 而对于简单的数据源通常用比较数据源两个时刻的快照的方法来检测增量数据。本文从传统Sort Merge快照差分算法代价和效率入手, 分析提升其效率和速度的可能方法, 并提出基于变异的M5的Sort Merge算法, 有效减少比较的数据量和输入输出的数据量, 显著的提高了算法的效率。

关键词：快照差分,增量检测,MD5,SortMerge

参考文献

[1]王欣, 左春.企业级数据复制平台的构建方案.计算机工程与应用, 2003, (03) .

[2]W.J.Labio and H.Garcia-Molina.Comparing very large database snapshots.Technical Report STAN-CS-TN-95-27, Computer Science Department, Stanford University, June 1995.

[3]W.J.Labio and H.Garcia-Molina.Efficient Snapshot Differential Algorithms for Data Warehousing.In Proceedings of VLDBConference, Bombay, India, September 1996.

[4]W.J.Labio and H.Garcia-Molina.Efficient Snapshot Differential Algorithms for Data Warehousing.In Proceedings of VLDBConference, Bombay, India, September 1996.

变异算法第5篇

关键词：微粒群算法,变异,三目标,无功优化,方差

无功优化( Reactive Power Optimization,RPO) 是在各种约束条件下,通过调整发电机端电压、可调变压器变比、电容器补偿容量等控制变量来使电力系统的无功分布达到最优,从而保证电力系统的高效稳定运行。本文在传统的无功优化模型基础上,引入静态电压稳定裕度,建立了以节点电压偏移最小,有功网损最少以及电压稳定裕度最大为目标的优化模型。

微粒群算法( Particle Swarm Optimization,PSO) 是一种群智能优化算法[1]。该算法参数简单,收敛速度快,作为寻优的一种工具,为众多学者所熟悉。但标准PSO算法存在着容易陷入局部极值,出现早熟等不足[2]。

基于标准PSO的上述不足,本文引入了一种自适应变异微粒群算法( Adaptive Mutation Particle Swarm Optimization,AMPSO)[3],并将其首次应用于三目标电力系统无功优化问题。该算法根据动态监控微粒群的聚集状况,增加随机扰动,对聚集的微粒进行变异,并自适应调整惯性权重,使该算法既能逃离局部极值防止早熟,又能提高收敛速度和精度。通过对IEEE-14节点系统的仿真计算,并与标准PSO及差分进化算法( Differential Evolution,DE) 进行比较,验证了本算法解决RPO问题的可行性及优越性。

1 三目标无功优化模型

1. 1 目标函数

本文以电压偏移和有功网损最小及电压稳定裕度最大为目标,建立优化模型。其中

( 1) 有功网损Ploss( 经济性)

式中,N为系统网络总支路数; δi,δj是节点i和j的电压相角; Gk( i,j) 为支路k的电导; Vi,Vj是节点i、j的电压。

( 2) 电压偏移dv( 安全性)

式中; Vi为负荷节点i的实际电压; Vi*为期望电压值且; ΔVimax为最大电压偏差,ΔVimax= Vimax-Vimin;N为系统负荷节点数。

( 3) 静态电压稳定裕度( 稳定性)

式中,λmin是雅克比矩阵的最小特征值。

1. 2 约束条件

( 1) 功率约束。保持功率平衡

式中,Pi为有功功率; Qi为无功功率。

( 2) 变量约束。控制变量

式中,VG为发电机的端电压; T为可调变压器的变比;QC为补偿电容发出功率。

状态变量

式中,VL为负荷节点电压; QG为发电机无功出力。

1. 3 归一化处理

考虑到各目标函数量纲不同,不能进行统一加权,故作如下归一化处理

式中,Ploss0,dv0分别为有功网损和电压偏移的初始值; Plossmin,dvmin分别为进行单目标优化时得到的最优值; VSM本身无量纲,为使所求各目函数有统一的最小值形式,故取倒数。归一化得到的总的目标函数为

式中,w1,w2,w3分别为各目标函数的权值,且w1+w2+w3=1。

2 微粒群算法

2. 1 标准微粒群算法

微粒群优化算法( PSO) 是一种根据鸟群觅食行为,Kennedy和Eberhart提出的一种智能优化算法[4],参数较少,易于实现。PSO算法中每个微粒的速度和位置根据个体的历史最好位置和群体最好位置进行更新。式如下

式中,vij( k) 和xij( k) 分别为为微粒i在第k次迭代中速度和位置的第j维分量; ω 为惯性权重; c1、c2为学习因子; pbestij( k) 为微粒i个体极值点位置的第j维分量;gbestj( k) 为微粒群体全局极值点位置的第j维分量; r1、r2为[0,1]之间的随机数。

2. 2 自适应变异微粒群算法

由式( 9) 可看出,当群体全局极值点位置gbest长时间不变,微粒在搜索过程中会逐渐接近gbest,此时微粒速度的更新主要由个体极值点的位置pbest决定,其速度会逐渐减小,则整体微粒群会呈现一种趋同性,这种趋同性会导致微粒出现“聚集”现象,若此处为一局部最优,则该算法就会出现早熟现象。若在算法早熟时,通过改变微粒的全局极值,则微粒的速度就会发生变化,向其他方向进行搜索,从而跳出局部最优,进而找到全局最优值。鉴于此,本文通过分析微粒的聚集程度,来对微粒进行变异操作。

设fi为微粒i的适应度值,则由式( 11) 可得出n个微粒的平均适应度值。根据式( 12) 确定微粒群的归一化定标因子f,按照式( 13) 得出整个微粒群体的适应度方差 σ2。

式( 12) 表明,微粒群群体适应度方差反映了微粒群的收敛程度,σ2越小,则群体越接近于收敛,相反,微粒群体处于随机搜索状态。

为使算法在出现早熟时,微粒向其他空间搜索,根据群体的适应度方差来确定群体全局极值变异的概率Pk,按下式[3]计算

式中,Pk为群体全局极值在第k次迭代中变异的概率; σk2为群体适应度方差在第k次迭代中的值; Pmin和Pmax分别是全局极值变异概率的最小值和最大值。

对于全局极值,采用增加随机扰动的方法[5]对其变异

η 是服从Gauss( 0,1) 分布的随机变量。

2. 3 调整学习因子和惯性权重

使学习因子能够异步时变[6],如式( 16) 所示

式中,c1f,c1i,c2f,c2i均为常数,本文取c1f= 0. 5,c1i= 2. 5,c2f= 2. 5,c2i= 0. 5; t为当前迭代次数; tmax为最大迭代次数。

采用式( 17) 进行惯性权重 ω 的调节

式中,λ 为控制因子,ωmax和 ωmin分别为惯性权重的最大值和最小值。

2. 4 无功优化步骤

步骤1 导入算法的基本参数包括种群规模,最大迭代次数,微粒变异概率的最大值,最小值等,以及对应电力系统中的潮流数据。

步骤2 对每一个微粒进行初始化,包括每一个微粒的初始位置,速度,初始个体极值和全局极值。

步骤3 按式( 16) ~ 式( 17) 对学习因子,惯性权重自适应更新; 按式( 9) ~ 式( 10) 对微粒速度,位置进行更新。

步骤4计算各微粒的适应度值并更新微粒个体、全局极值。

步骤5 根据式( 11) ~ 式( 13) 分别计算微粒的平均适应度值、定标因子、适应度方差。

步骤6 根据式( 14) 计算变异的概率Pk,随机产生数r∈[0,1],若r<Pk,则按式( 15) 进行变异,否则直接跳向步骤7。

步骤7 更新微粒群体全局极值。

步骤8 判断是否满足算法终止的条件,若符合则停止运行,输出最终的全局最优值,否则跳转步骤3继续执行。

3 算例及结果分析

3. 1 测试数据

以IEEE-14 节点系统为例进行测试分析,具体变量设置如下: 节点1 设置为平衡节点,节点2,3,6,8 设置为PV节点,节点9 为电容补偿节点,其余的节点均为PQ节点。支路5-6,4-7,4-9 为变压器支路[7]。发电机的端电压在[0. 95,1. 10]之间变化( 标幺值,该系统的基准容量为100 MVA,下同) ; 变压器变比调节区间为[0. 90,1. 10],调节步长为0. 012 5; 电容器可调节区间为[0. 00,0. 50],调节步长为0. 05,Pmax= 0. 5,Pmin= 0。该系统在优化前各优化目标的值分别为0. 1338、2. 945 0、0. 518 0[8,9]。

3. 2 优化结果分析

表1 为本算法与其他算法得出的数据比较。表1中有功网损、电压偏移数值由图1 和图2 中最终收敛值反代入式( 7) 所得。由表1 可知,三目标优化后效果均比优化前有明显提高,AMPSO算法在有功网损上比DE、PSO算法分别减少了0. 71% 和0. 58% ,比优化前减少8. 3% ; 电压偏移,电压稳定裕度的优化效果也明显优于另外两种算法。

由图1 可知,AMPSO算法在优化有功网损过程中,在迭代次数接近20 代时,就逐渐趋于稳定,接近80 代则完全稳定,而其他两种算法均是80 代后才稳定,可见AMPSO算法优化过程中收敛速度较快,且有功网损数值明显小于另外两种算法,而有功损耗越小,则表明经济性越好。

由图2 可知,AMPSO算法在优化电压偏移过程中,最终优化值虽然与另外两种算法较接近,但一开始收敛速度就较快,明显快于另外两种算法,且最终优化值也小于DE和PSO算法。可见该算法的优势还是可观的,而电压偏移越小,则表明电网的安全性越高。

由图3 可知,AMPSO算法在优化电压稳定裕度过程中,相比另外两种算法,在收敛速度上明显较快,且该算法电压稳定裕度较大,而裕度越大,则更有利于电网的稳定性。

各算法优化后的负荷节点电压的分布图如图所示。

由图4 可看出,AMPSO算法优化后各节点电压幅值均无越限,相比DE和PSO算法,各节点电压值更接近额定值,波动较小,优化后对电压有较大的改善。

综合以上可知,AMPSO算法在同时对3 个目标进行无功优化过程中,三目标均有了较大改善,且相比其他算法,无论在速度上还是最终优化值上都较优,可见该算法不仅提高了解的质量和精度,也加快了收敛的速度,故可更好地解决无功优化问题。

4 结束语

本文建立了三目标优化模型,采用自适应变异的方式对微粒进行改善,克服了标准微粒群算法易陷入局部最优,出现早熟的不足,对惯性权重和学习因子进行自适应调整,提高了算法的收敛速度和精度。将该算法应用于IEEE-14 节点系统中,通过比较,结果表明了该模型和算法在解决多目标无功优化问题的优越性和实用性,为求解多目标无功优化问题,提供了一个新方法。

参考文献

[1]盛四清,李婧,田文树.群智能算法在电力系统无功优化中的应用[J].电力科学与工程,2008,24(1):1-4.

[2]马立新,单冠华,屈娜娜.基于改进粒子群算法的电力系统无功优化[J].控制工程,2012,19(6):1077-1080,1084.

[3]叶德意,何正友,臧天磊.基于自适应变异粒子群算法的分布式电源选址与容量确定[J].电网技术,2011,35(6):155-160.

[4]史丽萍,王攀攀,胡泳军,等.基于骨干微粒群算法和支持向量机的电机转子断条故障诊断[J].电工技术学报,2014,29(1):147-155.

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

[6]马立新,王宏宇.基于非支配解的多目标粒子群无功优化[J].控制工程,2014,21(5):748-752.

[7]张伯明,陈寿孙,严正.高等电力网络分析[M].2版.北京:清华大学出版社,2007.

[8]冯士刚,艾芊.带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用[J].电工技术学报,2007,22(12):146-151.

变异算法第6篇

田口算法( Taguchi method,TM) 是一种新型的全局优化算法[5],该方法由日本的田口玄一博士在20世纪70年代提出,至今已经被广泛应用于诸多领域,如化工、机械工程、电力电子等行业[6,8],但田口算法在电磁方面的应用还很少见,本文将利用田口算法优化设计多层吸波材料。与遗传算法[9]、模拟退火算法[10]、粒子群算法[11]等群智能优化算法相比,TM最大的特点就是能够有效降低实验次数, 达到快速收敛的目的。但TM在优化多局部极值的复杂问题时存在前期收敛速度很快,到后期收敛速度变慢而陷入局部极值的缺点。针对此问题,文献 [12]提出了一种改进方案,引入了新解的邻域随机生成机制和内循环搜索机制,使改进后的田口算法能够成功的跳出局部极值。但由于内循环搜索机制的引入,使得算法迭代次数大大增加,不能很好的体现田口算法实验次数少的优势。

根据遗传算法的变异原理[9],本文在文献[12] 的基础上将变异算子引入基本田口算法,给出了一种基于变异机制的田口算法( mutation-based Taguchi method,MTM) 。分别对两种变异方式进行了讨论, 并利用性能最佳的变异方式优化设计了多层吸波材料的厚度及其电磁参数。

1 基本田口算法

TM的一个重要特征就是利用正交表OA( N,k, s,t) 来设计各参数水平值的组合[13]。其中,N表示实验次数; k表示可能安排的最多参数个数,当实际参数个数k' < k时,取OA的子矩阵OA'( N,k',s,t) ,根据正交表的性质,OA'( N,k',s,t) 也具有正交特性[14]; s表示参数的水平数,通常3个水平数就已经足够解决大多数问题; t表示强度即参数因子之间的相关性,当强度为2时,只考虑参数两两之间的影响,如果强度为3,则同时考虑三个参数之间的影响,当强度增加时,实验次数会急剧增加,通常强度取2对于大多数问题都是有效的。表1所示为一种正交表OA( 9,4,3,2) ,当此正交表用于设计实验时,行数表示每次循环迭代的实验次数为9次; 需要优化的参数个数为4个; 每一列中的数字1、2、3表示每个参数因子可能的3种取值水平,例如,若参数x1的取值范围为[- 1,0],则对应的1、2、3水平的取值为 - 0. 75、- 0. 5、- 0. 25; 正交表OA( 9,4,3,2) 的每行描述了参数因子水平值的组合,共有9种组合; 表1中t = 2表示考虑了参数间的两两相互作用,任选两列,可得到9组组合数据( 1,1) ,( 1,2) ,( 1,3) ,( 2,1) ,( 2,2) ,( 2,3) ,( 3,1) ,( 3,2) ,( 3, 3) ,可见每组数据在OA矩阵的行中出现的次数是相同的。

本文的设计实验中用xn|im 表示第n个参数在第i次迭代时的m水平值,则各代xn|i1 、xn|i2 和xn|i3 由式( 1) ~ 式( 3) 确定:

式中,Xnmin 、Xnmax 分别为参数取值范围的下限和上限; rr为指数衰减因子;为初始水平差值,即参数相邻两个水平值的差。

TM的另一个重要特征是利用信噪比判断各参数水平值组合的优劣[15]。由公式( 4) 得到每个参数、每个水平的平均信噪比:

式( 4) 中,ηi= - 20lg( Fitness) 。若需要寻求适应度函数Fitness的最小值,则最大平均信噪比所对应的参数水平值为当前代最优解 ; 若需要寻求Fitness的最大值,则最小平均信噪比所对应的参数水平值为当前代最优解。接着,用最优水平值组合进行确认实验,这个确认测试是必要的,因为这是一个基于正交表的实验,最优水平值组合并不包含在其中。从最优组合中获得的适应度值被视为当前代的适应度值。当达到收敛限δ时,结束程序。

2 基于变异机制的田口算法

2. 1 算法描述

基本田口算法一旦陷入局部极值,便无法跳出, 在算法迭代后期,容易早熟收敛。本文借鉴遗传算法中的变异思想,对参数水平值引入变异操作,增加新的搜索空间,使算法具有更好的跳出局部极值的能力,降低陷入局优的风险。MTM的算法流程图如图1所示。

讨论的变异算子有三个,分别为均匀变异算子、高斯变异算子和柯西变异算子。变异方式有两种, 一是参数的2水平值变异; 二是参数的1水平值和3水平值变异。第一种方式利用变异算子对父代最优解进行变异操作得到子代参数2水平值,子代参数1水平值和3水平值的产生方法与基本田口算法一致,从而保证了算法既具有基本田口算法实验次数少、收敛快速的优点,又能在陷入局部极值时跳出,更好的进行全局搜索; 第二种变异方式则利用变异算子对参数的1水平值和3水平值进行变异操作。同时,MTM还采用自适应内循环机制,尽量减少算法迭代次数,提高算法执行效率。

2. 2 参数的 2 水平值变异

该变异方式中,均匀变异公式为:

式中,ξU为变异步长,越大,ξU越大,可以有效阻止算法过快收敛,陷入局部极值,表示对应参数当前最大平均信噪比表示对应参数当前最小平均信噪比; U( 0,1) 为服从均匀分布的随机变量; xn|bestLeveli表示当前最佳参数水平值组合; 0 < μ < 1为二级变异步长,调节变异强度; Li+1为搜索空间。

高斯变异公式为:

式中,; N( 0,1) 为服从标准正态分布的随机变量。

柯西变异公式为:

式中,; C( 0,1) 为服从标准柯西分布的随机变量。

2. 3 参数的 1 水平值和 3 水平值变异

与参数的2水平值变异方式不同,这种变异方式子代参数的2水平值为父代最优解xn|i-1bestLevel,子代参数的1水平值和3水平值按照变异公式产生。

均匀变异公式为:

高斯变异公式为:

柯西变异公式为:

式中,xmin和xmax分别为当前搜索空间的下边界和上边界。0 < μ < 1调节变异强度。

3 数值仿真实验

3. 1 测试函数

为了测试变异田口算法的性能,选取下列9个测试函数进行测试。

函数1: Sphere函数是一个单极值函数,其最优值为min[f1( x) ] = f1( 0,0,…,0) = 0。

函数2: Rosenbrock函数是一个极为复杂且很难收敛的单极值函数,全局最优值为min[f2( x) ] = f2( 1,1,…,1) = 0 ,位于一个狭长的抛物线山谷底部。

函数3: Schwefel函数是一个单极值函数,其最优值为min[f3( x) ] = f3( 0,0,…,0) = 0。

函数4: Quadratic函数是一个单极值函数,其最优值为min[f4( x) ] = f4( 0,0,…,0) = 0。

函数5:Penalized函数min[f5( x) ]= f5(1,1,…,1) = 0。

函数6: Rastrigin函数是复杂的非线性多峰值函数,存在大量的按正弦拐点排列的很深的局部最优点,其最优值为min[f6( x) ] = f6( 0,0,…,0) = 0。

函数7: Griewank函数是一个多锋函数,其最优值为min[f7( x) ] = f7( 0,0,…,0) = 0。

函数8: Ackley函数是一个多锋函数,其全局最优值落在边缘上,此函数具有大量局部最优点,其最优值为min[f8( x) ] = f8( 0,0,…,0) = 0。

函数9: Schaffer函数是二维的复杂函数,具有强烈震荡的性态。具有无数个极小值点,其最优值为min[f9( x) ] = f9( 0,0) = 0。

3. 2 仿真结果及分析

数值实验中,衰减因子rr均取0. 75,收敛限制δ取0. 000 1。MTM最大内循环次数Nin取3,最大迭代次数M取100。分别用两种方式变异的田口算法对各个测试函数独立进行50次实验。

在解决实际问题时,数据的量纲往往不同,且有时数量级相差悬殊,因此选用变异系数Cv ( 样本标准差与样本均值之比) 衡量算法的稳定程度。Cv值越大,表明样本数据分布越离散,算法越不稳定。反之,则表明算法越稳定。将MTM与TM进行对比, 实验结果如表2所示。

从表2中可以看出,采用参数的2水平值变异方式,从50次测试算法所寻最优解中的最优值可知,三种变异算子改进的田口算法在寻优精度上差别不大。从三种变异算子的变异系数Cv可以看出, 高斯变异算子的稳定度相对较好。从平均迭代次数可以看出,对于单峰函数,柯西变异算子改进的算法寻优效率低于其他两种变异算子; 对于多峰函数,则均匀变异算子改进的算法寻优效率较低。从表2中也可以看出,采用参数的1水平值和3水平值变异方式,总体上寻优稳定度不及采用参数的2水平值变异方式。与TM相比,两种变异方式的MTM迭代次数虽然增加了,但在寻优精度上能达到更好的效果。

不同测试函数的适应度函数值进化曲线如图2所示。比较各图中参数的2水平值变异与参数的1、3水平值变异方式进化曲线可以看出,两种变异方式找到全局最优所需迭代次数相差不大。优化多峰函数所需迭代次数基本要多于优化单峰函数所需迭代次数。

综合考虑算法的寻优精度、寻优稳定度和寻优效率,参数的2水平值高斯变异田口算法能够在较短的搜索时间内稳定、有效地收敛到最优解,性能最佳。

4 吸波材料中的分层优化

本文研究的情况是涂层层数k = 5 ,每层厚度d的取值范围为0 ~ 2 mm,有金属基底( 最靠近金属基底的涂层设为第1层) 。入射波为均匀电磁波,垂直入射,频率f的范围为2 ~ 20 GHz。Z0表示第一层吸波材料与基底之间的输入波阻抗,由于基底为金属,所以Z0= 0。因篇幅所限,实验中所使用材料的电磁参数参见文献[9]。第i层与第i + 1层涂料界面处的输入波阻抗如递推公式( 21) 所示:

式( 20) 中,μi、εi表示相应涂层的磁导率和介电常数;表示第i层吸波材料的特性阻抗;

表示相应涂层的传播常数。

当电磁波由空气入射到波阻抗为Zk -1的k层吸波材料表面时,表面的反射系数如公式( 22) 所示:

通常用公式( 23) 所示功率反射率来衡量吸波效果。

反射率越小,吸波效果越好。优化设计多层吸波材料的适应度函数可设定如公式( 24) 所示:

根据上文中的讨论结果,利用性能最佳的参数2水平值高斯MTM优化设计各个涂层的厚度及材料,并与TM进行比较。选择正交表OA( 27,10,3, 2) 进行实验,衰减因子rr均取0. 75,收敛限制取0. 000 1; MTM内循环次数取3,最大迭代次数取100。设计得到的吸波材料各层参数如表3所示,两种算法优化后吸波材料的反射系数如图3所示。

将表3中算法的迭代次数与正交表实验组数相乘,再加上确认实验的次数即可得到TM及MTM适应度函数总计算次数分别为924、2072,相比较群智能优化算法动辄成千上万次的适应度函数计算量, TM及MTM的效率要高得多。

由表3中的数据及图3可以看出,相比较TM, 虽然MTM迭代次数有所增加,但它优化得到的材料厚度更薄,平均反射率更低。MTM优化后的最大反射率为 - 17. 126 9 d B,且在2. 5 GHz处达到最大吸波峰值 - 25. 565 5 d B。

5 结语

变异算法第7篇

网格[1]是利用物理网络将地理上广泛分布的存储资源、软件资源、带宽资源、计算资源、数据资源、信息资源、知识资源等连成一个逻辑整体,为用户提供一体化应用和信息服务。而网格资源调度[2]作为网格计算中的关键技术已经逐步成为网格计算研究领域的一个焦点。网格资源调度程序主要是为网格任务和网格资源寻找到一种较为优化的匹配策略,是个NP困难问题[3]。近年来随着一些仿生算法的兴起,已经有越来越多的学者将诸如遗传算法[4]、蚁群算法[5]等一些经典算法引入网格资源调度中去,从一定程度上优化了网格资源调度的效率但是也存在着一些缺陷,例如算法收敛速度过慢、对初始值的依赖性过大、容易陷入局部最优解等。

文献[6]提出了一种模拟鱼觅食的人工鱼群算法AFSA(Artificial Fish swarm Algorithm),该算法具有良好的搜索全局极值的能力、前期具有较快的收敛速度、对初值和参数选择不敏感、较强的鲁棒性等优点,但在后期往往收敛速度较慢、算法获取的一般不是精确最优解而是大量聚集在最优解周围的较优解。文献[7]提出一种蟑螂算法CSO(Cockroach Swarm Optimization),该算法的原理是通过蟑螂向其他蟑螂的所获得的“局部最优解”和种群“全局最优解”移动搜索的方式来取得最优解的。算法的回巢、平等搜索策略虽然使得算法具有很强的局部搜索能力,但同时也造成了大量的无效搜索,导致系统开销增大、效率低下,这种情况在种群数量变大的情况下显得更为明显。食物再分配策略虽然使得算法有一定的摆脱局部最优解获得全局最优解的能力,但是也存在着很大的随机性、盲目性。为了解决上述问题在平等搜索策略和食物再分配策略中分别引入禁忌表和差分进化变异算子。将这种改进后的蟑螂算法和人工鱼群算法实现动态融合,前期利用人工鱼群算法快速收敛特性获得的一些较优解来构造蟑螂种群,后期发挥差分进化变异蟑螂算法快速的局部搜索能力在次优解的周围快速搜索可能的最优解;同时它的变异特性有使得算法可以摆脱局部最优解的限制。

1 网格任务调度问题描述

在网格环境中任务调度问题的实质就是将这n个相互独立的任务T={T1,T2,…,Tn}分配到m个异构可用资源(处理单元PE),P={P1,P2,…,Pm},使得任务总完成时间最小。

定义1 元任务调度指的是一次调度的所有任务不存在任务之间相互依赖的关系。

定义2ETC矩阵任务在网格资源上的期望执行时间矩阵,其中元素ETCij表示任务Ti在资源Pj上的期望执行时间。

定义3CTij 任务Ti在资源Pj上的期望完成时间,即任务Ti在资源Pj上的期望执行时间ETCij加上资源pj上前面任务的总执行时间。假设Ri为任务Pi的到达时刻,Bi为任务Pi执行的开始时刻,所以有CTij=bi+ETCij。

当任务Ti被调度到特定的资源Pj上执行时,令CTi=CTij,表示任务Ti执行完成时间,则任务集合T的执行完成时间为:

makespace(T)=max(CTi) Ti∈T

即为任务T完成的耗时量,耗时量是网格系统的重要度量参数,同时也是任务调度的目标函数。

2 人工鱼群算法和差分进化变异蟑螂算法动态融合

如何寻找在一个动态的融合点是个非常关键的问题,将直接影响到网格任务调度算法的性能。本文采取的方法是:(1) 每次迭代完成后提取若干个适应度大的解组成精英种群,计算最优解和这些精英种群中每个个体之间的距离;(2) 通过这些距离值计算出种群中精英解和最优解的差异度;(3) 为平均差异度设定一个变化范围,在迭代过程中统计平均差异度连续出现在设定范围内的的次数,若达到一定次数则可认为人工鱼群算法已经收敛,则终止人工鱼群算法转入差分进化变异蟑螂算法。

3 设计与实现

3.1 人工鱼群算法(AFSA)

(1) 变量编码方式

传统的人工鱼群算法多用于解决连续域的问题,而网格资源调度问题则是属于典型的离散域的问题,因此在本文中对决策变量采用的是一种基于集合的资源-任务间接编码方式,假设有m个网格资源,n个任务。具体做法如下:变量中的每一位都是一个集合,变量中集合的数量等于资源数,每一个集合的编号则代表资源编号,每个集合中则包含的则是该资源所分配到的任务。如下所示:

Xi=(Ri1,Ri2,…,Rim)

Ri1={T1,T2,…,Tk}

Ri2={Tk+1,Tk+2,…,T2k}

…

Rin={Tp,Tp+1,…,Tn}

当资源数m为3,任务数n为7,则编码为 (R1,R2,R3)=( {1,3},{6,7},{2,4,5} )。

表示将任务1、3分配到资源1上;任务6、7分配到资源2上;任务2、4、5分配到资源3上。

(2) 适应度值的计算

$f i t n e s s = \frac{1}{\max_{i = 1}^{m} (Μ C Τ i)} \times β$

MCTi表示资源i完成分配给它的所有任务所花费的时间,m表示为网格环境中资源的数量,β为适应度值的调节系数。

(3) 觅食行为(AF_Prey)

设人工鱼当前所处的状态为Xi,在其视野范围(Visual)内随机选择一个状态Xj,如果Yi<Yj(Xj的食物密度大于Xi),则向该方向前进一步;反之,再重新随机选择状态Xj。判断是否满足前进的条件;尝试了try_number次后,如果仍然不满足前进的条件,则执行其他行为。

(4) 聚群行为(AF_Swarm)

设人工鱼当前所处的状态为Xi,探索其邻域的伙伴数目nf,如果视野范围内伙伴中心位置Xc有较多的食物并且不太拥挤,则向中心位置Xc前进一步;否则执行其他行为。

(5) 追尾行为(AF_Follow)

设人工鱼当前所处的状态为Xi,探索其视野范围内状态最优的邻居Xmax,如果Xmax食物密度大于当前位置的食物密度,并且xmax的邻域内伙伴的数目nf满足nf/Fish_size<δ,表明xmax的附近有较多的食物并且不太拥挤,则向xmax的位置前进一步;否则执行觅食行为。

(6) 随机行为(AF_Random)

就是在其视野中随机选择一个状态,然后向该方向移动一步。

(7) 人工鱼群算法迭代终止的条件确定

针对人工鱼群算法迭代终止的条件确定,本文采用前面提到的方式来动态融合的思想来解决这个问题。

定义4 变量Xi和变量Xj之间的“距离”,在本文中指的是两种资源分配方式之间的差异,具体表示如下:

Distance(Xi,Xj)

$\begin{array}{l} = D i s t a n c e ((R i 1 ‚ R i 2 ‚ \dots ‚ R i n) ‚ (R j 1 ‚ R j 2 ‚ \dots ‚ R j n)) \\ = \sum_{k = 0}^{n} (| R i k - R j k |) \end{array}$

|x-y|为属于x而不属于y的元素个数。

定义5 差异度

$d i f f e r e n c e = \frac{\sum_{i = 1}^{k} D i s t a n c e (X b e s t, X i)}{k \times m a x d}$

Yj∈精英种群(即种群中适应度较高的若干个解组成的集合),Xbest为最优解,k为精英种群中个体的数量,maxd为种群中个体之间理论上的最长距离值。

定义6 差异度出现频率

$d f = \frac{m}{r u n t i m e s}$

其中,runtimes表示算法总的运行次数,m为差异度值在设定范围内连续出现的次数,一般m取值以10到15为宜。

difference可以反映出种群中一部分较优的解与最优解之间的聚集情况,当difference在某个范围内连续多次出现则表明人工鱼群算法已处于或是近似于处于收敛的状态,可以结束人工鱼群算法而切换至差分进化变异蟑螂算法。本文设置算法总的运行次数runtimes=100、df=0.1,经过多次实验发现difference取值为[0.79,08)之间,可以获得比较好的计算结果。

3.2 差分进化变异蟑螂算法(DECSO)

(1) 回巢策略

每只蟑螂在完成向全局最优解和个体最优解的爬行之后,会回到自己的初始位置。

(2) 引入禁忌表的平等搜索策略

在传统的蟑螂算法中每只蟑螂在向全局最优解和个体最优解爬行寻求优化解的过程中都会引起其他蟑螂的追随。这种搜索方式极容易造成算法效率的低下。因此为了提高搜索效率、加快搜索速度在算法中为每只蟑螂引入禁忌表,每只蟑螂在完成向某个个体最优解搜索之后都会将其加入禁忌表;每只蟑螂在搜索之前先查询禁忌表,若该个体最优解出现在禁忌表中,则不向该目标移动;每只蟑螂在更新过自身的个体最优解的时候都会将其他蟑螂禁忌表中的该个体最优解删除。

(3) 食物再分配策略

差分进化DE(Differential Evolution)算法[8]是一种全局并行搜索算法。根据差分进化的原来,定义差分进化变异算子如下:

定义7 差分进化变异算子

Triali=F1×(GBest-PBesti)+(F2-0.5)×

(PBestk-Pbestj) (i≠j≠k)

其中F1,F2为变异因子、GBest表示全局最优解、PBest为种群中任一个体的最优解,F1取值一般为0.5,F2为[0,1]之间的随机数。由于有GBest的引导作用,降低了个体变异的盲目性;PBest的引导增加了个体变异的多样性,容易跳出局部最优解。

3.3 人工鱼群算法和差分进化变异蟑螂算法的衔接

选取人工鱼群终止时种群中适应值最好的前10%个体来初始化差分进化变异蟑螂算法种群初始值和个体最优解。

3.4 基于人工鱼群算法与差分进化变异蟑螂算法动态相融合任务调度算法流程

1) 初始化人工鱼群算法控制参数,人工鱼的个体数量(fish_Size)、算法迭代次数(runtimes)、鱼的视野范围(Visual)、觅食尝试次数(try_number)、拥挤度因子(δ)、步长(step)、基准最优解数量(Top_N);

初始化差分进化变异蟑螂算法控制参数蟑螂数量(cockrocah_size)、差分变异算子控制参数(F)、局部最优变量到全局最优变量距离控制参数(Distance_To_GBest);

2) 设置人工鱼群算法终止条件;

3) 随机生成鱼群算法的初始种群;

4) for(n=0; n < runing_times; n++)

{

取每条个体鱼Xn;

AF_Prey(Xn);

AF_Swarm(Xn);

AF_Follow(Xn);

If(觅食失败 and 聚群失败 and 追尾失败)

AF_Random(Xn);

Else

选取其中的最优解更新公告板;

If(满足人工鱼群算法终止条件)

转移至5;

}

5) s=n,取鱼群中前10个最优解初始化蟑螂种群和PBest;

For(;s< runing_times;s++){

For(i=0;i< cockrocah_size;i++){

For(j=0;j< cockrocah_size;j++){

If(i≠j and PBestj 不在Ci的禁忌表中)

Ci向着PBesti方向移动,并记录下移动过程中的位置信息

}

取Ci移动过程中的位置信息与PBesti做比较,若优于PBesti则将其替换;

将PBestj存入Ci的禁忌表中;

}

For(k=0;k< cockrocah_size;k++){

If(fitness(PBestk) > fitess(GBest))

Gbest替换为PBestk;

}

种群中所有的蟑螂个体返回初始位置(回巢);

For(i=0;i< cockrocah_size;i++){

Ci向着GBest方向移动,并记录下移动过程中的位置信息

If(fitness(Ci) > fitess(PBesti)) Gbest替换为PBesti;

}

For(i=0;i< cockrocah_size;i++){

If(fitness(PBesti) > fitess(GBest))

Gbest替换为PBesti;

}

种群中所有的蟑螂个体返回初始位置(回巢);

按照定义7的方式对每个个体的PBest做差分进化变异处理

}

4 仿真实验与分析

本文的仿真实验采用人工鱼群算法与差分进化变异蟑螂算法动态融合算法(AFSADECSO)、人工鱼群算(AFSA)和蟑螂算法(CSO)处理任务调度问题,并比较它们的性能和结果。仿真平台为GridSim[9],实现语言为Java,操作系统为Win7。算法参数设置如表1所示。

图1、图2、图3的实验结果分别是进行了10次实验之后的平均值。

从图1的实验结果来看在小容量的任务调度方面AFSADECSO算法比起AFSA算法和CSO算法有一定的优势,但是优势并不明显,但当任务数量逐步增加的时候AFSADECSO算法逐渐显示出比AFSA算法和CSO算法更大的优势来。从图2的实验结果来看在网格资源的利用率方面AFSADECSO算法比起AFSA算法和CSO算法也有很大的优势。

而从图3的实验结果来看改进后的蟑螂算法和人工鱼群算法相融合比起单独的AFSA算法和CSO算法在获得全局解的精度上和收敛速度都有比较大的优势。

摘要：深入分析人工鱼群算法和蟑螂算法的特点基础,提出一种改进式蟑螂算法。将差分进化变异因子、禁忌表分别引入到蟑螂算法,加快了算法的搜索速度和获得全局最优解的能力。采用权衡种群中最优个体和精英个体之间的差异度的方式将改进后的蟑螂算法和人工鱼群算法动态融合。仿真实验表明将这种动态融合后的算法解决网格任务调度问题可以获得较好的调度效果。

关键词：网格,任务调度,人工鱼群算法,蟑螂算法,差分进化

参考文献

[1]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002:8-13.

[2]尚明生.网格计算中的任务调度算法研究[D].四川:电子科技大学,2007.

[3]Laforenza D.Grid programming:some indications where we are headed author[J].Parallel Computing,2002,28(12):1733-1752.

[4]Lee Wang,Howard Jay Siegel,Vwani P Roychowdhury,et al.Task matc-hing and scheduling in heterogeneous computing environmentsusing a ge-netic-algorithm-based approach[J].Journal of Parallel and Distributed Computing,1997,47(1):8-22.

[5]Dorigo M,Stzle T.Ant Colony Optimization[M].MIT Press,Cambridge,2004.

[6]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22:32-38.

[7]程乐.新的仿生算法—蟑螂算法[J].计算机工程与应用,2008,44(34):44-46.

[8]Storn R,Price K.Differential evolution-a simple and efficient adap-tive scheme for global optimization over continuous spaces,TR-95-012[R].Berkeley:International Computer Science Institute,1995.

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【变异算法】相关文章：

一种动态变异概率的遗传算法09-14

生物变异05-17

变异特性06-08

变异技术06-12

变异特点08-21

动态变异08-22

变异鱼07-14

心率变异检测05-09

变异系数法06-30

传承与变异07-16