变异算法

变异算法（精选七篇）

变异算法篇1

关键词：变异系数,标准差,平均数

变异系数是衡量资料中各观测值变异程度的一个统计量。当进行两个或多个资料变异程度的比较时,如果度量单位与平均数相同,可以直接利用标准差来比较。如果单位和(或)平均数不同时,比较其变异程度就不能采用标准差,而需采用标准差与平均数的比值(相对值)来比较。标准差与平均数的比值称为变异系数,记为C·V。变异系数可以消除单位和(或)平均数不同对两个或多个资料变异程度比较的影响。

例1:10头母猪第一胎的产仔数分别为:9、8、7、10、12、10、11、14、8、9头。试计算这10头母猪第一胎产仔数的标准差和变异系数。

此例n=10,经计算得:Σx=98,Σx2=1000,代入标准差计算公式得:

即10头母猪第一胎产仔数的标准差为2.0976头,变异系数为21.40%。

那么如何在Visual Foxpro中实现变异系数的算法呢?下面就结合一次学生的考试成绩来实现变异系数的算法。

例2:一表名为student(zkzh c(9),yw n(6,0),sx n(6,0),yy n(6,0),wl n(6,0),hx n(6,0),;sw n(6,0),zf n(6,0))

基于混沌和动态变异的蛙跳算法篇2

混合蛙跳算法是进化计算领域兴起的一种新型优化算法,它是由Muzaffar Eusuff和Kevin Lansey于2003年提出的一种基于群体的协同搜索方法[1]。该算法模拟青蛙群体寻找食物时,按种群分类进行思想传递的过程,将整个群体青蛙间能够交流的全局广泛搜索和子群内青蛙个体信息能够交流的局部深度搜索相结合[2],使算法向着全局最优解方向进行。与其他优化算法相比,SFLA结合了基于遗传基因的元进化算法MA(memetic algorithm)和基于群体觅食行为的粒子群算法PSO(particle swarm optimization)的特点,具有概念简单、参数少、易于编程实现及寻优能力强的优势。

作为重要的优化工具,SFLA已广泛应用于连续优化问题、离散优化问题、聚类问题,多变量PID控制器参数调节问题等领域。而如何避免陷入局部最优和提高算法的收敛速度也成为该算法的一个研究热点。文献[3]为提高SFLA的收敛效率,提出在SFLA深度搜索方向上融合极值动力学优化算法。文献[4]针对SFLA易陷入局部最优,求解精度低的缺点,提出利用差分进化中的变异思想对SFLA的更新策略进行局部扰动。文献[5]引入遗传算子增加对局部极值的扰动以避免陷入局部最优,同时对青蛙移动策略进行了优化,从而提高算法的性能和解的质量。文献[6]在全局搜索中加入自适应logistic序列的混沌变异操作,同时结合个体适应度和进化代数自适应调整变异尺度,从而提高算法最优解的精度。受此启发,本文先利用Tent映射构成的混沌序列初始化青蛙群体,从而提高初始解的质量。再通过引入群体适应度方差可知各青蛙的聚集程度,对于适应度方差较小的青蛙,取较大的变异概率进行变异操作;反之,对于适应度方差较大的青蛙,取较小的变异概率进行变异操作。因此新算法可根据各青蛙的位置动态地调整变异概率,达到跳出局部最优解的目的。

1 SFLA介绍

对于d维问题,随机生成F只青蛙(解)组成初始群体,第i只青蛙可以表示为Xi=(xi1,xi2,…,xid),将种群内青蛙个体按适应度降序排列。然后将整个群体分为s个子群,每个子群包含n只青蛙,满足F=s×n。第1只青蛙被分入第1个子群,第2只青蛙被分入第2个子群,…,第s只青蛙被分入第s个子群,第s+1只青蛙被分入第1个子群。依此类推,直到所有青蛙分配完毕[7]。

在每个子群中,具有最好适应度的青蛙记为Xb,最差适应度的青蛙记为Xw,而整个群体中具有最好适应度的青蛙记为Xg,对每个子群进行局部搜索,每次迭代只更新子群中的最差青蛙,更新策略为:

Di=rand( )·(Xb-Xw) (1)

Xw=Xw(当前位置)+Di (-Dmax≤Di≤Dmax) (2)

式中,Di表示分量i上移动的距离;rand( )是0到1之间的随机数;Dmax是青蛙允许移动的最大距离。

经过更新后,如果得到的解Xw优于原来的解Xw(当前位置),则取代原来种群中的解;否则用Xg取代Xb,重复执行更新策略式(1)、式(2);如果仍然没有改进,则随机产生一个新解取代原来的Xw。重复这种更新操作,直到设定的迭代次数,就完成一轮各子群的局部搜索。然后将所有子群的青蛙重新混合排序,划分子群,进行下一轮的局部搜索,如此反复直到满足终止条件。

2 基于混沌和动态变异的蛙跳算法(新算法)

2.1 用混沌序列产生青蛙群体

初始群体的分布性质严重影响整个算法的收敛性能。若初始群体性质差,不但会造成算法收敛速度慢,而且会使算法不收敛。在SFLA中,随机生成的初始群体的各青蛙都集中在解空间的某一局部区域,很容易使算法陷于局部最优。因此,本文利用混沌的遍历性初始化青蛙群体以增强群体的多样性,从而提高初始解的质量。

混沌是非线性系统中一种普遍的现象,且混沌运动能在一定范围内按其自身的“规律”不重复遍历所有状态,这种遍历性可作为搜索过程中避免陷入局部最优的一种有效的优化工具,因而,混沌优化搜索比随机搜索更具优越性[8]。其优化算法的主要思想是:首先产生一组与优化变量数目相同的混沌变量,将混沌运动的遍历范围放大到优化变量的取值范围,然后利用混沌变量的遍历性、随机性进行搜索。

一个好的混沌模型能提高混沌变异的概率,本文用能产生均匀序列且迭代速度快的Tent映射构造混沌模型,可以提高初始解的速度和精度,Tent序列的迭代公式如下:

$Ζ_{m + 1} = {\begin{cases} 2 Ζ_{m} 0 \leq Ζ_{m} \leq 0.5 \\ 2 (1 - Ζ_{m}) 0.5 \leq Ζ_{m} \leq 1 \end{cases} (3)$

式中,Zm为混沌变量,m为迭代次数。

在(0,1)范围内,随机产生一个Q维的向量Z1=(Z11,Z12,…,Z1Q),应用式(3)得到M个分量Z1,Z2,…,ZM,将Zi用式(4)表示,通过计算适应度值,从M个初始种群中选择适应度值较优的F个(青蛙)作为初始解。

xij=aj+(bj-aj)Zij (4)

式中,i=1,2,…,M;j=1,2,…,Q。

2.2 群体适应度方差

各青蛙的位置可通过其适应度值来体现,由适应度值可知群体中青蛙的聚集程度,因此引入群体适应度方差来衡量解的质量。

设群体青蛙总数为F,第i只青蛙的自适应度值为fi,群体适应度值的平均值为favg,适应度方差δ(t)2定义为:

$δ (t)^{2} = \sum_{i = 1}^{F} (\frac{f_{i} - f_{a v g}}{f}) (5)$

式中,f是限制适应度方差的大小,它的取值随式(6)变化;δ(t)2为第t次迭代的适应度方差;t=itj×titk,itj为当前子群内的迭代次数,it为子群内迭代总次数;titk为当前混合迭代次数,tit为混合迭代总次数,j∈[1,it]的整数,k∈[1,tit]的整数。

$f = {\begin{cases} \max | f_{i} - f_{a v g} | i f \max | f_{i} - f_{a v g} | > 1 \\ 1 o t h e r w i s e \end{cases} (6)$

从式(5)、式(6)可知,群体适应度方差反映群体中所有青蛙的“收敛”程度,δ(t)2越小,则青蛙群体越趋于收敛;当δ(t)2=0时,则群体各青蛙的自适应度值几乎相同,算法陷于局部最优或达到全局最优;反之,青蛙群体处于随机搜索阶段。

2.3 动态变异操作

为了让青蛙在算法陷入局部最优之前找到新的搜索方向,动态变异操作应根据青蛙聚集程度来确定,即变异操作的概率应随群体的适应度方差的大小而改变:

P(t)=Pmax-(Pmax-Pmin)(δ(t)2/F) (7)

式中,P(t)为第t次迭代中群体全体极值的变异概率;Pmax为当前变异概率的最大值;Pmin为当前变异概率的最小值;F为群体青蛙总数。

从式(7)可知,当群体的适应度方差较小时,变异概率取值较大;反之,当群体的适应度方差较大时,变异概率取值较小。算法可根据各青蛙的位置来动态调整变异概率的大小,即若青蛙在最优解附近,群体适应度方差较小,则应取较大的变异概率进行变异操作;反之,若青蛙距最优解较远,群体适应度方差较大,则应取较小的变异概率进行变异操作,从而使算法达到跳出局部最优的目的。

对于Xg的变异操作,采用如下变异方程:

X′g = Xg + ξN(0,1)Xg (8)

式中,ξ为变异参数;N(0,1)是均值为0且方差为1的随机变量;X′g为变异后的全局最优。

2.4 新算法的流程

Step1 参数初始化,青蛙种群数F,子群数s,每个子群内青蛙数n,子群内迭代总数it,混合迭代总数tit;变异参数ξ,变异概率Pmin、Pmax;

Step2 利用式(3)混沌Tent序列初始化青蛙群体;

Step3 对每只青蛙,计算其适应度值f(xi)(即目标函数值),按照f(xi)以降序对青蛙群体进行排序并分为s个子群;

Step4 确定每个子群中的Xb、Xw及群体全局最优Xg,对每个子群中最差青蛙按式(1)、式(2)进行更新,直到设定的迭代总次数it,对更新后的子群进行混合,取代原来的群体;

Step5 利用式(5)、式(6)计算群体的适应度方差;

Step6 利用式(7)计算变异概率,并按照式(8)对全局最优解Xg进行变异操作,得到全局最优解X′g;

Step7 用X′g代替当前群体中全局最优解Xg;

Step8 若当前迭代次数达到预定设定的最大次数tit,则迭代停止,输出最优适应度值的相关信息,算法结束,否则转到Step3。

3 仿真实验

3.1 参数设置与测试函数的选择

为了测试本文算法性能,选取算法的平均最优适应度值、标准差、CPU运行时间及迭代曲线最为评价标准。平均最优适应度值是对所有实验次数得到的函数适应度值取算术平均数,平均最优适应度值越小,表明与理论值越接近,算法性能越好。

采用文献[9]中建议的参数设置,青蛙总数F=200,子群数s=20,子群内迭代总次数it=10,混合迭代总次数tit=500;变异参数ξ=0.5,变异概率Pmin=0.01、Pmax=0.1。选取6个经典的连续函数[10]进行测试,并与标准蛙跳算法SFLA、文献[10](ISFLA1算法,该算法是将生物学中的吸引排斥思想引入到混合蛙跳算法中,修正了更新策略,从而保持了子群的多样性。)进行比较,表1为测试函数的基本情况。

3.2 收敛性测试

取测试函数维数为30,预设精度为10-9,若算法在500次迭代中,最终结果满足精度要求,则该次运算算法收敛,反之为不收敛。算法收敛率为收敛次数与函数运行次数的比值。称算法收敛时,满足预设精度的迭代次数的最小值为算法的收敛代数,若最终优化结果不满足预设精度的要求,则该次收敛代数为指定迭代次数。平均收敛代数为各次收敛代数之和与函数运行次数的比值,实验结果如表2所示。

3.3 不同维函数的测试

函数变量维数D=30,每种算法运行30次,3种算法对6个测试函数的实验结果如表3～表8所示。比较6个表中的计算结果可知,在相同迭代次数及相同精度要求的前提下,新算法得到的平均最优适应度优于其他两种算法,并且标准差和CPU平均运行时间较小。由此可知新算法与SFLA、ISFLA1相比有较好的全局搜索能力和较高的收敛精度,有效避免了早熟现象。可见本文在SFLA中引入混沌初始化群体和动态变异操作是可行的。

3.4 高维函数的测试

为测试新算法对高维函数的求解能力,取函数变量维数D=100,3种算法对6个测试函数的迭代曲线如图1～图6所示。

Ackley是复杂的多峰函数,具有全局最小值0,在搜索后期新算法快速收敛,能较快地得到最优适应度值。Griewank是均匀的多峰函数,它考察算法的全局寻优能力,由于新算法中引入了动态变异操作,对群体适应度方差较小的解以较小的概率变异,而对群体适应度方差较大的解以较大的概率变异。从而避免陷于局部最优,对算法的早熟具有很好的抑制作用。对Schafferf7非均匀的多峰函数的实验说明,新算法具有更好的收敛速度,在摆脱局部极值,提高收敛精度等方面均有明显的优势。

从图1～图6可知,由于新算法采用混沌Tent序列初始化群体,因而得到较好的初始解(初始适应度值较小),而SFLA和ISFLA1初始群体随机分布,故初始解较差。由于新算法可根据群体适应度方差动态调整变异概率,故使算法能很快地获得最优解,从而使迭代次数较少,而ISFLA1无此操作,在最优解附近徘徊时间较长,使得迭代次数较多,运行时间较长,易陷入局部最优。

4 结语

本文针对混合蛙跳算法易陷入局部最优、收敛速度慢的问题,提出改进的蛙跳算法。该算法就3方面进行了改进:(1) 用混沌Tent序列初始化青蛙群体,提高初始解的质量从而减少迭代时间;(2) 引入群体适应度方差反映群体中所有青蛙的“收敛”程度,并可以判断解的优劣;(3) 变异操作的概率应随群体的适应度方差的大小而改变,对较差解选取较大的变异概率,使得算法向全局最优解靠近。实验结果表明,无论是二维还是高维问题,新算法都得到了良好的效果。SFLA优化算法已取得了较多的研究成果,但在优化复杂问题时,各参数的设置仍比较薄弱,这也是今后研究的方向。

摘要：针对混合蛙跳算法SFLA(shuffled frog leaping algorithm)易陷入局部最优、收敛速度慢的问题,提出一种改进的混合蛙跳算法。该算法首先用混沌的Tent序列初始化青蛙群体以增强群体的多样性,提高初始解的质量;再根据每只青蛙的群体适应度方差值选取不同的变异概率,有效增强了SFLA跳出局部最优解的能力。通过对6个经典函数的仿真测试,结果表明,新算法比SFLA和ISFLA1的寻优能力更强,迭代次数更少,解的精度更高。

关键词：混合蛙跳算法,混沌优化法,动态变异,适应度方差,更新策略,全局最优

参考文献

[1]Eusuff M M,Lansey K E.Optimization of water distribution network de-sign using the shuffled frog leaping algorithm[J].Journal of water sources planning and management,2003,129(3):210-225.

[2]赵守法.蛙跳算法的研究与应用[D].华东师范大学软件学院,2008.

[3]骆剑平,陈泯融.混合蛙跳算法及其改进算法的运动轨迹及收敛性分析[J].信号处理,2010,26(9):1428-1433.

[4]赵鹏军.基于差分扰动的混合蛙跳算法[J].计算机应用,2010,30(10):2575-2577.

[5]欧阳,孙元姝.基于改进混合蛙跳算法的网格任务调度策略[J].计算机工程,2011,37(16):1-3.

[6]葛宇,王学平,梁静.自适应混沌变异蛙跳算法[J].计算机应用研究,2011,28(3):945-947.

[7]Babak Amiri,Mohammad Fathian,Ali Maroosi.Application of shuffled frog-leaping algorithm on clustering[J].Adv Manuf Technol,2009,45:199-209.

[8]单梁,强浩,李军,等.基于Tent映射的混沌优化算法[J].控制与决策,2005,20(2):179-182.

[9]Elbeltagi E,Hegazy T,Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53.

基于高斯变异的自适应猴群算法篇3

关键词：猴群算法,自适应,高斯变异

0 引言

在智能算法不断推陈出新的现在, 猴群算法 (Monkey Algorithm, MA) 作为新兴智能优化算法, 摆脱了以往启发式算法“维数灾难”[1,2]的困扰。该算法通过模拟大自然中猴群爬山行为, 设计出爬、望和跳三个过程来求解多维、多峰函数[3,4]的优化问题。但由于MA中的参数过多、固定, 使得算法后期的收敛速度减缓;并且算法的性能跟参数设置有很大的关系, 如果参数设置不准确, 就会丧失猴群多样性, 易发生算法过早收敛, 陷入局部最优的情况[5], 从而无法获得全局最优解。针对这个缺点, 文献[6]通过引入欧氏距离来增强猴群的多样性, 并加入和声算法中的随机扰动机制, 以提高其全局搜索能力;文献[7]引入望过程参数递增机制, 提高了算法后期的收敛速度;文献[8-9]引入混沌搜索, 通用参数避免陷入局部最优, 提高算法性能。但这些方法在搜索性能和寻优能力上都不同程度地存在一些不足, 鉴于此, 本文提出一种基于高斯变异的自适应猴群算法 (简称GAMA) 。

1 猴群算法的自适应改进过程

1.1 自适应步长[9]和视野

原猴群算法采用固定的步长和视野。算法初期具有较快的收敛速度, 但在后期, 算法的的收敛较慢。为了弥补这一不足, 提出了如下改进:

1.1.1 步长衰减变化策略:

step=step·θ, 其中θ∈ (0, 1) 为衰减因子, 随着迭代的进程而自适应地减小步长大小;在算法前期, 使用较大的步长, 可以增强全局搜索能力;但随着迭代的进行, 如果仍然采用初始步长, 会使搜索的结果不精确, 故自适应地减小步长, 有利于在算法的后期增强局部的搜索能力。

1.1.2 视野递增变化策略:

Visual (new) =Visual (old) +Visual (old) ·ρ, 其中ρ为递增因子。因为猴群算法利用跳过程来摆脱局部最优的困扰, 在算法前期, 赋予一个较小的跳半径, 使其能够保持搜索的精度;但在算法运行后期, 如果跳的距离过短, 就可能陷入局部最优值。

即使猴群算法的跳过程从机制上来讲是为了跳出局部最优, 但由于参数的人工初始化设置等原因, 猴群算法也会陷入局部最优值。为此, 本文进一步提出了以下改进。

1.2 猴群的高斯变异

什么是高斯变异[11]?高斯变异就是在原有个体的状态上加一个服从高斯分布的随机向量。高斯分布 (Gaussian distribution) , 也称作为正态分布 (Normal distribution) , 在数理统计及其概率论学科当中占有举足轻重的地位。同样, 在数学、物理等诸多领域都有着重大的影响力。若随机变量X服从一个数学期望为μ、方差为σ2的高斯分布, 记为N (μ, σ2) 。其概率密度函数为:

期望值μ决定了其位置, 其标准差σ决定了分布的幅度。由于正态分布的特征和性质, 在自然界中很多现象和随机因素均可近似地用正态分布描述。

针对猴群算法而言, 在迭代过程中, 处于最优位置上的猴子很容易陷入局部最优解, 以至于在多次迭代过程中, “最优值”都不变。例如, 函数。猴群算法 (采用固定步长和固定视野) 寻优就陷入了局部最优值69895.516361, 出现的次数占总迭代次数的52.9%, 并且实际寻得的最优解0.625722跟理论值0也相差很多。为了避免这一情况的出现, 使猴群能够摆脱局部极值的束缚, 较早的开始收敛, 我们对猴群中的最优个体增加一个随机扰动项, 该扰动项服从高斯分布。即对寻优过程得出的最优值在二十次迭代运算未发生改变的情况下, 对最优猴位置采取Gauss变异, 表达式为Xbest_new=Xbest_old+Gauss (0, 1) ·Xbest_old, 其中Gauss (0, 1) 为标准正态分布。这样能够使算法较早跳出局部最优值, 易实现全局收敛 (详见第3节) 。

2 改进的猴群算法

2.1 改进的猴群行为描述

2.1.1 猴群初始化过程

正整数M表示猴群的群体规模, 猴群的个体位置由Xi= (xi1+xi2, …, xin) , i=1, 2, …, M表示, x对应着优化问题中的决策变量, M对应着决策变量的个数。

2.1.2 (步长衰减) 爬过程

(1) 随机生成向量Δxi= (Δxi1, Δxi2, …, Δxin) , 满足:

其中α (α>0) 为爬过程中的步长, k (k=1, 2, …) 表示爬的次数, 即爬过程中的迭代次数。

(2) 计算:其中向量

(4) 如果y满足函数条件, 则用y来替换xi, 否则xi不变;

其中θ (0<θ<1) 表示递减因子。可以看出每次迭代步长递减, 这样有利于在算法的后期运行中, 保证解得精确度, 增强局部搜索能力。

重复步骤 (1) 至 (5) , 当k满足条件时循环结束。

2.1.3 (视野递增) 望过程

经过爬过程, 目标函数达到了当前最优。之后, 猴子开始眺望, 观察周围领域是否存在比当前山峰更高的山峰, 即是否存在更优解。如果存在, 则跳到更高的山峰, 更新当前的位置。望过程如下:

(1) 随机从视野范围 (xij-βIter, xij+βIter) 内产生实数y= (y1, y2, …yn) 。其中Iter为当前的迭代次数;

(2) 如果f (y) ≥f (xi) 时, 并且y满足函数条件, 则用y来替换xi;否则重复步骤 (1) 直到找到合适的y或者满足一定的运行次数为止;

(3) 以y做为初始位置, 重复爬过程。

2.1.4 (在视野范围内) 跳过程

(2) 令yi=xij+θ (pj-xij) , 若y= (y1, y2, …, yn) 可用, 则令xi=y;否则重复步骤 (1) (2) ;

爬→望→爬→跳过程完成了一次迭代过程, 在每次迭代过程中, 视野β随迭代次数的增加而递增, 即βIter+1=βIter+βIter·ρ, 其中ρ为递增因子, 这就是1.1.2节所讲的视野递增变化策略, 其中Iter为当前迭代次数, N为总迭代次数。

2.2 改进后算法的基本流程

改进后算法的基本流程如下:

(1) 计算初始化过程, 定义计算所需的初始条件, 设置相关的参数;

(2) 通过2.1节的猴群行为得出当前迭代下的最优函数值;

(3) 对该最优函数值进行判断, 判断其在二十次迭代中都未发生变化, 则跳转步骤5, 进行高斯变异;否则, 进入下一次循环迭代;

(4) 判断是否达到最大循环迭代次数, 若满足, 则输出计算的结果;不满足, 则返回步骤 (2) ;

(5) 对处于最优位置的猴子进行Gauss变异, 生成的新猴群重复步骤 (2) 的操作;

(6) 当总迭代次数达到最大设定次数时候终止。

说明:步骤 (5) 就是猴群的高斯变异。

3 GAMA性能测试

为测试改进后猴群算法的性能, 这里采用以下五个经典验证函数对其进行验证:

MA和GAMA参数设置如表1所示。在Microsoft Visual C++平台上, 通过C++编程算法, 运行电脑配置为Win7、Intel Core i3 M3502.27GHz处理器、2G内存。寻优测试结果见表2。

对于测试函数f1~f5, MA和GAMA迭代对比过程见图1~图5。

对所有函数, 算法连续运算20次。其中函数f1的寻优结果对比见图6。可见MA和GAMA算法运算20次最优值都不变, 限于篇幅, 其余函数的不同算法对比结果不再一一列出。

本文还将GAMA算法与遗传算法 (GA) 和粒子群算法 (PSO) 做对比研究, 对测试函数f1~f5的求解结果见表3。

此外, GAMA算法还实现在不同维数下的寻优结果, 见表4。

注:测试函数f4的维数为5时, 迭代总次数设置为80次.

4 结果分析

4.1 GAMA和MA寻优性能比较

4.1.1 收敛精度

从表2的测试结果可以看出, 针对测试函数1~5, GAMA算法找到的值0.004545、0.022183、-1566.646323、-3611.783171和0.004006都要比MA算法找到的最优值0.625722、0.686747、-1566.597321、-3472.150206、0.495808更加地接近理论最优解。尤其是对函数f1、f3、f5, 在保留小数点后两位的情况下, 我们可以认为GAMA算法成功找到了理论最优解。

但MA和GAMA算法对函数4的寻优结果-3611.783171、-3472.150206并不理想, 与理论最优值-8379.658相差较远, 这有待进一步改进。但无论如何, 在精度方面GAMA算法都要优于MA算法。

4.1.2 收敛速度

从图1~图5可以看出, 除了函数f4, 针对其余函数GAMA在算法进行高斯变异后就开始收敛, 虽然变异后值较大, 但开始迭代的时间要快于MA算法。并且观察图1~图5中收敛的区域, 可以发现, GAMA算法在收敛时, 迭代图形的陡峭程度要比MA算法高。换言之, GAMA算法有着较快的收敛速度和“下坡能力”。但对于函数f4, MA和GAMA的收敛速度相当。

4.1.3 稳定性

将MA算法与GAMA算法对5个函数各运行20次, 如f1的算法对比结果见图6 (其他测试函数对比结果类似) 。由图可见, 对于20次运算结果, MA和GAMA都保持一致, 不会出现偶尔一两次运算结果不一样的情况, 这也足以说明GAMA算法较稳定。

4.2 GAMA与遗传算法 (GA) 和粒子群算法 (PSO) 寻优结果比较分析

为了较全面地体现GAMA的特性, 我们将GAMA算法与GA和PSO算法进行比较, 同样地对函数f1~f5进行寻优测试, 结果如表3所示。可以看出, 除了测试函数4, 其余的测试函数GAMA算法在寻得结果的精度方面都很大程度地优于GA算法。PSO算法一直以其实现容易、精度高、收敛快等优点著称, 故在求解函数f1、f2时找到了理论最优值0和局部极值0.0142, 要较优于GAMA算法寻得的结果0.004545和0.022183, 误差仅在0.455%~0.80%之间;对于函数f1、f5, GAMA算法在精度方面的优势就有着较明显的体现, 比PSO寻得的结果更加接近理论值。

4.3 GAMA在不同维数下寻优结果分析

正如引言所述, 一般的算法难以避免维数的灾难。基于此, 我们选取不同的维数5、10、20、30、40、50、60来测试GAMA算法求解高维问题的能力及其稳定性。从表4可以看出, 不同维数下的寻优结果, 没有较大的波动。如函数f1, 在不同维数下寻得的结果0、0、0.004545、0.012961、0.029157、0.047024、0.073767只有少许的增长幅度;对测试函数f3、f4的结果f (3) min=-78.33236n、f (4) min=-418.9829n跟维数有着直接的关系, 所以寻得的结果会不同。但如果将最优值除以各自的维数, 那么不同维数下寻得的结果波动性很小。故GAMA算法与MA算法一样, 对维数的敏感度较低 (MA算法维数敏感度可参考文献[9]) , 不会陷入维数的灾难。

5结束语

一种改进变异算子的混合遗传算法篇4

遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架,它不依赖于问题所属的具体领域,已广泛应用于函数优化[2]、自动控制[3]、机器人学[4]、图像处理[5]、遗传编码[6]、机器学习[7]等领域。

标准遗传算法存在的不足主要表现为:(1) 遗传算法的早熟现象(即很快收敛到局部最优解而不是全局最优解)是迄今为止最难处理的关键问题。(2)快要接近最优解时在最优解附近左右摆动,收敛较慢。

本文根据遗传算法的特点,改进遗传算法的变异算子,并结合局部搜索算法,给出一种融合遗传搜索和模式搜索的混合遗传算法,以提高算法的性能。实验仿真结果表明,改进后的算法在收敛速度、精度和稳定性方面均有明显的提高。

1 遗传算法原理

遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可以编成其他进制码)即基因,若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异的运算,经过多次重复迭代直至得到最后的优化结果。标准遗传算法(也称为基本遗传算法或简单遗传算法,Simple Genetic Algorithm,简称SGA)只使用选择算子、交叉算子和变异算子,其遗传进化操作过程简单,是其它遗传算法的基本框架。

2 融合标准遗传搜索和模式搜索的混合遗传算法

2.1 算法的设计

本文提出的改进措施之一是:为防止早熟收敛,在进化过程中加速淘汰差的个体,增加解的多样性,将变异算子分为强制性变异算子和随机性变异算子,即当种群中的个体适应度低于某个值(强制性变异算子)时,强制该个体发生变异,若无满足条件的个体,则按随机性变异算子进行随机变异。

本文提出的另一个改进措施是:针对标准遗传算法全局搜索能力强而局部搜索能力弱的问题,把遗传算法和局部搜索算法有机地结合起来,是改进遗传算法性能的一个卓有成效的方法。这种混合型算法不仅模拟了生物种群的学习过程,而且事实上还模拟了种群的个体在其生命周期内具有学习行为这一生物现象。本文采用标准遗传搜索算法与模式搜索算法结合起来以优化搜索性能。模式搜索法[8]又称作“步长加速法”或“Hooke-Jeeves方法”,该算法主要由两种移动过程组成:探测移动和模式移动。探测移动时沿坐标轴方向的移动,模式移动则是沿相邻两个探测点连线方向上的移动。两种移动模式交替进行,目的是寻找函数值下降(上升)的最佳方向。在进化过程中,选取每代适应度最优的个体,以最优个体x为坐标原点交替进行模式移动和交叉移动,得到一个临时个体x’,如果x’的适应度优于x,则用x’取代x进入下一代种群。

融合标准遗传搜索和模式搜索的混合遗传算法。

①确定算法的初始参数(主要包括最大迭代次数、交叉算子、强制性变异算子、随机性变异算子)。

②确定编码方式。

③置k=0,随机产生初始种群undefined。

④计算每个个体适应度f(x1),…,f(xN),最优个体保留,其余N-1个由交叉产生。

⑤采用轮盘赌策略进行选择,令undefined,其中,PPi为累计概率,Pi为个体的选择概率,其计算公式为:undefined,其中,f(xi)为个体的适应度。共转轮N次(N为种群个体数),选取N个母体,每次转轮时,随机产生0到1之间的随机数r,当PPi-1≤r

⑥随机产生交叉点,单点交叉杂交得到N-1个中间个体。

⑦判断这N个中间个体中有无低于强制性变异算子约定的适应度的个体,有则转向⑧,无则转向⑨。

⑧将低于强制性变异算子约定适应度的个体进行变异。

⑨根据随机性变异算子约定概率对中间个体进行变异。

⑩从经变异后的N个中间个体中选取最优个体,以最优个体为坐标原点进行模式搜索,若能得到更优解,则以更优个体取代原个体进入下一代,反之则保留原个体。

(11)检验新的种群undefined是否满足停止准则,若满足则停止并输出结果,否则返回到④。

2.2 算法的收敛性分析

由本文给出的算法步骤可知,本算法是结合杰出者选择遗传算法和强制“劣汰”算法的混合遗传算法。

定理 “优胜劣汰”遗传算法是齐次马尔可夫链,且种群序列undefined;n≥0}以概率1收敛到满意种群集M*,即undefined

证明:对于任意undefined,当j≠i0时

undefined

而

undefined

于是undefined;n≥0}是齐次种群马尔可夫链。由

3 实验结果与分析

为对此改进算法性能进行测试,本文用几个经典寻优算法评价函数进行评测。测试平台:服务器DELL Power Edge 2650(双XEON CPU 2.4G,内存 1GB),操作系统Windows Server 2003,采用Matlab R2009b编程对表1中所列函数进行仿真测试。

设定种群规模为20,进化代数为100,对标准遗传算法SGA和本文给出的改进遗传算法MGA分别进行100次仿真实验测试,结果如表2所示。

以上六个函数为寻优算法的经典测试函数。Camel函数有6个极小点,其中有2个(-0.0898,0.7126)和(0.0898,-0.7126)为全局最小点。Griewank 函数和Rastrigin函数为高频多峰函数,搜索空间大,常规寻优方法很难奏效。 Schaffer函数最大值峰周围有一个圈脊,它们的取值均为0.990283,算法寻优很容易停滞在局部极大值。Schwefel's函数是一个典型的欺骗问题,有1个全局极小值点取值近似为-837.9658,在(420.9687,420.9687)处,距离另一个局部最优点很远,因此如果陷入局部最优就很难跳出。Rosenbrock函数特点是每个等高线是一个窄长弯曲的山谷,形状象香蕉,俗称香蕉函数,能有效的评价算法性能。从表2可以看出,改进后的遗传算法在收敛速度和稳定性方面比经典遗传算法都有了很大的提高。

4 结束语

最佳个体保留及强制性变异算子的引入模拟了自然界优胜劣汰的进化机制,加速了遗传算法的寻优过程,强制性变异机制也增加了染色体的多样性,防止早熟收敛。同时,标准遗传搜索法与模式搜索法均不需要计算导数,这两种寻优算法各有所长,将二者有机结合起来应用有效地提高了算法成功率。

参考文献

[1]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[2]Bramlette M F.Initialization,Mutation and Selection Methods inGenetic Algorithms for Function Optimization[C].Proc ICGA 4,1991:100-107.

[3]Karr C L.Design of an Adaptive Fuzzy Logic Controller Using a Ge-netic Algorithm[C].Proc ICGA 4,1991:450-457.

[4]周明,孙树栋,彭炎午.基于遗传模拟退火算法的机器人路径规划[J].航空学报,1998,19(1):118-120.

[5]Talbi E,Bessière.P.A Parallel Genetic Algorithm for the GraphPartitioning Problem[C].Proceedings of ICS,1991:312-320.

[6]Michalewicz Z.Genetic Algorithms+Data Structures=EvolutionPrograms[C].Springer Verlag,1992.

[7]Goldberg D E.Genetic Algorithms in Search,Optimization and Ma-chine Learning[M].Addison Wesley Publishing Company,1989.

变异算法篇5

近年来,多目标优化问题MOP(Multi-objective Optimization Problem)求解已成为演化计算的一个重要研究方向,而演化算法(EA)是一类基于种群的搜索算法,可并行搜索多个目标,在搜索过程中可以将最优解保存到下一代,这些正是求解多目标优化问题所希望的。多目标演化算法研究的主要目标是使算法种群收敛到Pareto前沿,且具有良好的分布广度和均匀程度。NSGA[1]、NSGA-Ⅱ[2]、SPEA2[3]、PAES[4]等都是目前比较具有代表性的多目标演化算法,它们分别采用“小生境技术”、“排挤距离”、“最近邻居法”、“网格法”来维护群体多样性。受到上述研究的启发, 本文从更好地维护解的多样性出发, 给出一种基于动态拥挤距离的多目标优化演化算法,并根据个体的级数设计了一种自适应变异步长的柯西变异算子,对变异越界处理进行了改进。实验证明算法具有更好的收敛性与多样性。

1MOP中的一些基本概念

不失一般性,考虑下列n个自变量和m个目标函数的多目标函数优化问题:

Minimize y=f(x)=(f1(x1,…,xn),…,fm(x1,…,xn))

其中x=(x1,…,xn)∈X⊂Rn,y=(y1,…,ym)∈Y⊂Rm,x为决策(参数)向量,X为决策空间,y为目标向量,Y为目标空间。

定义1 优劣性

向量u=(u1,…,um)优于向量v=(v1,…,vm)(记为u≺v),当且仅当∀i∈{1,…,m},满足ui<=vi ,并且∃j∈{1,…,m}使得ui<vi。

定义2 Pareto最优解

设a∈X,X′为X的子集,若X′中不存在优于a的向量,则称a为关于子集X′的非劣解或关于子集X′的Pareto最优解,若a为关于X的非劣解,则a简称为非劣解或Pareto最优解。

定义3 Pareto前沿

对于给定的MOP f(x)和Pareto最优集(P*),Pareto前沿(Pf*)定义为:

Pf*={u=f(x)|x∈P*}

定义4 非支配集

设有解集P,P中的个体q不被任何其他个体支配,则q是P中的非支配个体;P的非支配个体构成的子集称为P的非支配集。即= {q|q∈P且不存在q`∈P使得q`≺q}。

2基于动态拥挤距离的自适应变异演化算法

2.1群体多样性保持策略

保持群体多样性在实际中有着重要意义,它能够给决策者提供更多合理的选择。另外对于目标函数数目很多的优化问题,会由于搜索空间的维数过高,使得群体个体之间很难进行优劣性比较,有时甚至会出现所有个体皆非支配解。且在优化后期,群体中各个体已经基本上逼近Pareto前沿,从而使进化选优无法正常地进行下去。如何解决这个问题呢?

解的分样性主要体现在解分布的广度和均匀程度。关键问题在于如何刻画解分布的广度和均匀程度。例如: 小生境技术、超网格、信息熵[5]、个体密度等。本文采用个体的拥挤距离来维持群体的多样性,且具有动态性。

个体的拥挤距离是针对种群中一层非支配个体而言。个体i的拥挤距离计算公式定义如下:

$d_{i} = \frac{1}{m} \sum_{k = 1}^{m} | f_{k}^{i + 1} - f_{k}^{i - 1} |$

其中:m为目标的维数;fik为第i个个体在第k维目标上排序后的第k维目标值。下面以一个二维目标的情况来说明拥挤距离的计算过程。图1中的实心点表示同一非劣前沿上的个体。则个体i的拥挤距离:

$d_{i} = \frac{1}{2} [| f_{1}^{i + 1} - f_{1}^{i - 1} | + | f_{2}^{i + 1} + f_{2}^{i - 1} |]$

实际上为图中两虚线段之和的一半。通常我们认为种群中个体之间的距离越小, 分布度就越差, 那么进化算法就是要淘汰这些密集的点。显然, 拥挤距离 di 的值越小, 个体i就越落在拥挤区域, 反之个体 i 位于稀疏区域。

现在有一个问题,如果当前非支配集中个体的数目大于规定种群数,则要按拥挤距离从小到大一次性淘汰多余个体数。显然,这种策略比较粗糙。因为一次种群维护只需计算一次个体的拥挤距离,如果一次性淘汰所有拥挤距离小的个体,则会出现个体之间的个体缺失,使得解的分布性较差。再由于某些个体可能在某些维目标上的差值很大,而在另些维目标上的差值却很小,使得这些个体的拥挤距离较小;但某些个体在各维目标上的差值均相差不大,使得这些个体的拥挤距离较大,此时会误认为前面那些个体的分布性较后面这些个体要差,而事实刚好相反。

针对上述拥挤距离的不足,本文提出了一种称为动态拥挤距离的多样性保持策略。

对于第一个不足,本文采取这样的策略:在种群维护过程中,每淘汰一个个体就重新计算种群中剩余个体的拥挤距离;对于第二个不足,本文根据下式来计算个体i的动态拥挤距离:

ddi=di/log(1/si)

其中 $s_{i} = \frac{1}{m} \sum_{k = 1}^{m} (| f_{k}^{i + 1} - f_{k}^{i - 1} | - d_{i})^{2}$ 为个体i在各维目标相邻个体拥挤距离的方差,它能反映各维目标拥挤距离的差异程度,差异程度较大的个体被保留的机会就越大。

2.2多父体杂交算子[7]

从当前群体中任意选取M个个体,通过它们的非线性组合形成新个体v*:

$v^{*} = \sum_{i = 1}^{Μ} a_{i} x_{i}$

其中 $\sum_{i = 1}^{Μ} a_{i}$ 满足=1 ,-0.5<=ai<=1.5。

其中,系数ai范围不设为常见的[0 ,1],是为了让杂交算子能搜索到由该M个个体所张成的子空间的外缘,即凸空间,增加算子搜索能力。

2.3变异算子的设计

在进化算法中,变异算子是一种非常重要的算子。它具有一定的局部随机搜索能力,可加强进化算法的鲁棒性、多样性。进化算法中常用的变异算子主要有:均匀变异、非均匀变异、高斯变异、柯西变异、多项式变异等。本文利用Pareto占优对个体进行排序并分级,1级代表最好,2级次之,以此类推。并根据个体的级数,设计了一种自适应变异步长的柯西变异算子。具体定义如下:

x′i=xi+C(0,σ)

其中C(0,σ)表示以0为中心,尺度参数为σ的Cauchy分布的随机数。而尺度参数为σ即变异步长,在本文中也表示个体的级数。这种变异操作,可使非支配个体采用较小的变异步长进行局部搜索;其他个体采用较大的变异步长,保证解在可行域空间中能进行全局搜索。

多目标优化算法在执行变异操作时,经常会出现越界这种情况。常规的处理方法是取端点值,研究表明使用这种越界处理方法效果比较很差。根本原因在于,多目标优化问题是一组最优解,不是单个最优解,这势必增加与之相对应的变异操作规模,越界的概率也会加大。而常规的越界处理方法会造成种群多样性的丧失。

下面提出改进的越界处理方法:

其中lk和uk分别是解向量取值范围的下限和上限,r为[0,1] 之间的随机数。

这种改进的越界处理方法,可以弥补因越界处理而造成的种群多样性的损失,因为变异后的值有50%的概率等于变异前原来的值。

2.4算法描述

本文算法的详细步骤如下:

1) 令进化代数t=1,随机产生一个规模为N的初始父代群体。

2) 从当前群体中任意选取M个个体和随机产生1个个体(可增加种群的多样性和全局搜索能力,使得解集具有良好的分布度),对这(M+1)个个体采用多父体杂交产生1个后代。

3) 从当前群体中任意选取2个个体进行变异操作,产生2个后代。

4) 对这(N+3)个个体进行非支配排序分级,对每一级别中的个体计算动态拥挤距离, 再根据群体多样性保持策略,淘汰动态拥挤距离最小的3个个体。

5) 如停机规则满足则停机,否则t=t+1,并转步骤2)。

3数值实验

3.1测试函数

多目标优化问题的测试函数的设计比单目标优化问题的设计要复杂得多。一般将测试函数设计成具有多模型、欺骗性、孤立最优点等特征的函数。

本文使用3个典型的测试函数来检验新算法的性能。

实验函数T1:

$\begin{array}{l} Μ i n i m i z e Τ_{3} (x) = (f_{1} (x_{1}), f_{2} (x)) \\ f_{1} (x_{1}) = x_{1} \\ g (x_{2}, \dots, x_{m}) = 1 + 9 * \sum_{i = 2}^{m} x_{i} / (m - 1) \\ h (f_{1} ‚ g) = 1 - \sqrt{\frac{f_{1}}{g}} \\ m = 10, x_{i} \in [0, 1], i = 1, \dots, m \end{array}$

这个问题的Pareto最优解集为g(x2,…,xm)=1,其均衡面为凸集。

实验函数T2 :

$\begin{array}{l} Μ i n i m i z e Τ_{1} (x) = (f_{1} (x), f_{2} (x)) \\ f_{1} (x) = 1 - \exp (- \sum_{i = 1}^{3} (x_{i} - \frac{1}{\sqrt{3}})^{2}) \\ f_{2} (x) = 1 - \exp (- \sum_{i = 1}^{3} (x_{i} + \frac{1}{\sqrt{3}})^{2}) \\ x = (x_{1}, x_{2}, x_{3}) ‚ x_{i} \in [- 4, 4], i = 1, 2, 3 \end{array}$

函数T1的Pareto最优解集为, $x_{1} = x_{2} = x_{3} \in [\frac{- 1}{\sqrt{3}}, \frac{1}{\sqrt{3}}]$ 。

实验函数T3:

$\begin{array}{l} Μ i n i m i z e Τ_{4} (x) = (f_{1} (x_{1}), f_{2} (x)) \\ f_{1} (x_{1}) = x_{1} \\ g (x_{2}, \dots, x_{m}) = 1 + 10 (n - 1) + \\ \sum_{i = 2}^{m} (x_{i}^{2} - 10 \cos (4 \times p i \times x_{i}) \\ h (f_{1} ‚ g) = 1 - \sqrt{\frac{f_{1}}{g}} \\ m = 10, x_{1} \in [0, 1], x_{i} \in [- 5, 5] ‚ i = 2, \dots, m \end{array}$

这个问题含有219个局部Pareto最优集,它能够测试算法处理多峰函数的能力。当g(x2,…,xm)=1时可求得全局Pareto最优阵面。当g(x2,…,xm)=1.25时可以求得局部Pareto最优阵面。

3.2实验结果及算法性能评估

评估多目标优化问题的算法性能指标主要有:最优群体的逼近性、分布均匀性、算法的时间复杂度及收敛速度等。但在实际问题中,决策者往往只对某一范围的最优解感兴趣,故本文只评价测试函数最终获得的最优解集的逼近性、均匀性及本文算法的时间复杂度,并与经典算法NSGA-Ⅱ进行比较。

3.2.1 算法的时间复杂度

设目标数为m群体规模为N,算法的时间复杂度取决于:

1) 非支配排序, ο(mN2);

2) 计算个体的拥挤距离,ο(mNlog(N));

3) 种群在杂交变异后最多有N+3个个体,将它们分别依m个目标进行排序,以计算个体的拥挤距离进行裁减操作。该步骤的时间复杂度为O(m(N+3)log(N+3))。

一般情况下取m≤N,则本文算法总的时间复杂度取上述分析结果中的最大值ο(mN2)。NSGA-Ⅱ是一种经典的快速非支配排序多目标精英遗传算法。设它们的群体规模为L,其时间复杂度为ο(mL2),令群体规模N=L,则它与这两种算法在最坏情况下具有相同的时间复杂度。

3.2.2 最优群体的逼近性与均匀性

引用文献[8]定义的GD来度量最优群体的逼近性, 文献[9]定义的SP来衡量最优解的分布均匀性。

实验在MATLAB中进行,参数种群数N=70,杂交个体数M=9,运行最大代数为3000代。将本文算法和经典的NSGA-Ⅱ算法独立运行30次,然后统计两种算法所得Pareto最优解集的均匀性(SP)与逼近性(GD)的最好、均值和方差,以此作为衡量算法性能的标准。图2至图7为从30次运行中随机选择的一次运行结果,从实验曲线可以看到本文算法求出的Pareto前沿在逼近性方面要优于NSGA-Ⅱ。表1至表3为两种算法对测试函数的SP与GD的统计结果,从表中数据可看出,在解集的逼近性和均匀性方面本文算法对3个测试函数的标准方差都明显小于经典的NSGA-Ⅱ 算法,这说明本文算法性能更稳定、更具鲁棒性。

4结语

本文从更好地维护解的多样性出发, 针对拥挤距离的不足,提出一种基于动态拥挤距离的分布性保持策略,它可避免造成某些区域个体密集,另一些区域个体稀疏的现象。在进行多父体杂交操作时,引入随机算子,增加了种群的多样性和全局搜索能力,使得解集更具良好的分布度同。再根据个体的Pareto排序级数设计了一种有效的自适应变异步长的柯西变异算子,并对变异越界处理进行了改进。最后通过实验证明本文算法具有更好的收敛性与多样性。

摘要：多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。根据个体的非支配排序级数设计了一种自适应变异步长的柯西变异算子,对变异越界处理进行了改进;并定义和使用动态拥挤距离来保持群体中个体的均匀分布。最后通过对测试函数的实验,验证了算法的可行性和有效性。

关键词：演化算法,多目标优化,自适应变异,动态拥挤距离

参考文献

[1]Srinivas N,Deb K.Multiobjective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.

[2]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Trans on Evolutionary Com-putation,2002,6(2):182-197.

[3]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pa-reto evolutionary algorithm[R].Zurich:Computer Engineering and Networks Laboratory(TIK),Swiss Federal Institute of Technology(ETH)Zurich,2001.

[4]Knowles J D,Corne D W.The pareto archived evolution strategy:A new baseline algorithm for pareto multiobjective optimization[C]//Congress on Evolutionary Computation.Piscataway:IEEE,1999:98-105.

[5]朱学军,陈彤,薛量,等.多个体参与交叉的Pareto多目标遗传算法[J].电子学报,2001,29(1):106-109.

[6]崔逊学,李淼,方廷健.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能,2001,14(3):291-296.

[7]Guo Tao,Kang Li-shan.A new Evolutionary Algorithm for Function Optimiza-tion[J].Wuhan University Journal of Natural Sciences,1999,4(4):409-414.

[8]Van Veldhuizen D A,lamont G B.Multiobjective evolution ary algo-rithm research:A history and analysis[R].Department Elec.Com-put.Eng.,Graduate School of Eng.,Air ForceInst.Technol.,Wright-Patterson AFB,OH.Technical Report TR-98-03,1998.

变异算法篇6

1.1初始化种群

在QDPSO中,直接采用量子位的概率幅作为粒子当前位置的编码,随机初始化量子粒子群中粒子的两个位置;产生初始种群为Pi:

设粒子当前搜索到的最优位置为Pil

整个种群目前搜索到的最优位置Pig为

如果量子粒子i的位置优于它对应的,则设置为当前位置为第i个粒子的新的两个位置并进行更新;粒子Pi上量子位幅角增量的更新位置算式为

粒子Pi上量子位概率幅增量的更新位置算式为

量子粒子更新后的两个新位置为

在QDPSO中,由于粒子的遍历空间每维均为[-1,1],将每个粒子占据的2个位置由单位空间I=[-1,1]n映射到优化问题的解空间。粒子上量子位的每个概率幅对应解空间的一个优化变量。记粒子Pj第i个量子位为,则相应的解空间变量为

1.2变异处理

为了增加种群多样性,首先给定变异概率Pm,对每个粒子赋值一个(0,1)之间随机数randi,若randi

2交叉变异因子机制的粒子群优化算法

基于交叉变异因子机制的粒子群优化算法的基本思想包括4部分:早熟判断机制的方法、Pareto最优解更新策略、基于交叉杂交算子和变异算子的改进机制。早熟判断方法是为早熟收敛而进行的判断;Pareto最优解更新策略是得到不断更新的最优解在临时储备器中的集合,为以后的交叉和变异个体选取做准备。交叉杂交是为了配对个体中随机选择杂交位置并进行杂交,杂交的目的是为了产生适应值更高的个体,从而使各代个体都向前进化;变异目的是改进算法的局部搜索能力并维持群体的多样性。

2.1 PSO的早熟现象及早熟判断机制

粒子群优化算法在搜索过程中,如果某粒子发现一个当前最优位置,其他粒子将迅速向其靠拢。如果该最优位置为一局部最优点,粒子群就无法在解空间内重新搜索,这就是所谓的“早熟收敛”现象。为解决这个问题,而引入早熟收敛判断机制。早熟收敛预防与处理的统一框架。

早熟收敛判断是早熟处理的基础。设粒子群的粒子数目为m,fi为第i个粒子的位置,favg为粒子群目前的平均位置,为粒子群的群体位置方差[2],定义为

其中是归一化定标因子,其作用是限制的大小。的取值采用如下算式

算式(13)表明,群体位置方差反映的是粒子群中所有粒子的“聚集”程度。越小,则粒子群的“聚集”程度就越大,若算法不满足结束条件,“聚集”将使群体失去多样性而陷入早熟状态,故当

2.2 Pareto最优解更新策略

Pareto最优解更新策略是在求解优化问题时设置了2个存储解的集合即最优解临时储备器Q1和Q2,并设定存储最优解的个数。经过迭代操作后,则将所得最优新解加入到最优解临时储备器中,然后比较新加入的解和存储器中的其他解,将次于新解的解从最优解临时储备器中删除,这种更新反复进行,得到更新的最优解的集合,为以后的交叉和变异做准备。

2.3交叉算子改进策略

交叉是随机抽取临时储备器Q1和Q2中的一个体进行配对,然后在配对个体中随机选择杂交位置进行杂交,交叉算子在算法中起着关键作用,它是产生新个体的主要方法。杂交的目的是为了产生适应值更高的个体,从而使各代个体都向前进化。交叉算子的设计和实现与所研究问题密切相关。

引理1:基于黄金分割(0.618法)交叉算子:黄金分割法是一种一维极小化问题的近似最优策略的搜索方法,即沿某一已知方向求目标函数的极小点法。它具有较强的局部搜索能力,利用近似最优策略构造交叉算子,可以很快跳出局部最优,交叉后的两个新体为

引理2:基于Fibonacci法的交叉算子:Fibonacci法是一种一维极小化问题的最优策略搜索算法,即沿某一已知方向求目标函数的极小点法。它同样也具有较强的局部搜索能力,利用最优策略构造交叉算子,可以很快跳出局部最优,交叉后的两个新体为

多点交叉算子在母体的基因串中随机设置多个交叉点,然后以一定概率在交叉点所分隔的基因段中进行段交换[3]。

引理3:基于数值计算方法的“取大”、“取小”交叉算子:这种交叉方法跟常规“一点”实数型交叉方法相比,在数值计算上显示了优越性。具体实施方法如下:

(1)按轮盘选择规则从临时存储器Q1、Q2中分别选出一条染色体Xi和Xj;

(2)由Xi和Xj按位“取大”运算产生一个字串C1;

(3)由Xi和Xj按位“取小”运算产生一个字串C2。

例如:选择的两条染色体为Xi:85078652,Xj:65140698

则由“取大”、“取小”运算产生的两个子串分别为

C1:85178698,C2:65040652

易知这种交叉方法使子代继承了双亲的同型基因。

2.4变异算子的改进策略

变异算子是改进算法的局部搜索能力,并维持群体的多样性,防止出现早熟现象。

引理4:基于最速下降法的变异算子:最速下降法具有计算速度快、方向性和局部搜索能力较强的优点,利用它的这一优点构造均匀变异算子[4],可以很快跳出局部最优。方法如下:记第i代P(i)的第j个染色体的第k个分量为Xijk,对其进行变异操作时,不再是二进制字符“1”、“0”之间的跳变,也不是[Sk,tk]内取随机数,其修正值为

改进的变异算子能够不断开拓问题解的新空间,增强算法的全局搜索能力。

2.5混合粒子群算法的实现

根据粒子群优化算法结构的开放性,把交叉算子、变异算子和粒子群算法结合起来,用交叉和变异来处理粒子群的早熟收敛问题。首先运行两个粒子群算法操作,只要有一个粒子群算法处于早熟收敛状态,就从各自的临时储存器中随机抽取一个个体进行交叉和变异处理,迭代N次后,把搜索到的最优解向量作为粒子群算法的全局最优解向量,从而引导粒子快速跳出局部最优,加快收敛速度,提高了算法的精度。

算法流程如下:

(1)对2个粒子群同时进行初始化:设定有关参数,初始化粒子群中粒子的位置。

(2)首先令每个粒子的最优位置pi为当前粒子所在的位置,并计算其对应的适应度;令全局最优位置pg为当前群体中具有最优适应度的粒子的位置。

(3)对于粒子群中的所有粒子执行如下操作:1)根据算式(1)和算式(2)更新粒子的位置;2)如果粒子i的位置优于它对应的当前位置,则pi设置为第i个粒子的新位置;把其中一个粒子群优化算法通过算式(1)、算式(2),得到全局最优解储存到临时储存器Q1,迭代N次,另一个粒子群通过算式(1)、算式(2)得到全局最优解储存到临时储存器Q2,迭代N次(Q最优解的个数远小于N)。

(4)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(5)。

(5)用Q1,Q2中的最优解来根据算式(3)计算群体适应度方差,并判断

(6)随机取出Q1,Q2中的个体,根据改进的交叉算子算式(4)进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解还存储在各自的储存器中并替换最差的最优解。

(7)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(8)。

(8)随机取出Q1,Q2中的个体,根据改进的交叉算子算式(5)进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解还存储在各自的储存器中并替换最差的最优解。

(9)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则执行步骤(10)。

(10)随机取出Q1,Q2中的个体,根据引理3的交叉算子进行个体交叉,把交叉得到的2个个体根据算式(1)和算式(2)更新粒子的位置;把迭代N次得到的结果放到各自的Q中,然后在各自的Q中选取一个个体根据变异算子算式(6)分别进行变异操作,迭代N次;把最后得到的最优解存储在各自的储存器中并替换最差的最优解。

(11)用Q1,Q2中的最优解来判断算法收敛准则是否满足,如果有一个满足,执行步骤(12),否则判断设定算法迭代次数是否小于设定的次数,如果是则执行步骤(3),否则执行步骤(12)。

(12)当满足条件后,取出Q1和Q2中的最优解进行对比,最后输出最优解。

3改进后混合算法的验证

利用这个改进混合粒子群算法用六峰值驼背函数[4]来验证。

六峰值驼背函数

该函数共有6个局部极小点,其中(-0.898,0.7126)和(0.898,-0.7126)为全局最小点,最小值为f(-0.898,0.7126)=f(0.898,-0.7126)=-1.031628。

对此函数利用数学分析中的单纯形搜索方法,随机产生初始点,计算极值结果如表1所示[5]。

这些点中最好的是-1.031621,最差的是-0.798968,均值是-0.9564460。

对改进的混合算法设计参数如下:混合粒子群算法和遗传算法各优化50次。两种算法种群都取20,限定代数500。混和粒子群参数:变异概率Pm=0.05。GA参数:变异概率Pm=0.05,交叉概率Pc=0.7,用改进后的混合粒子群算法,遗传算法[6]对六峰值驼背函数进行再次计算结果分别如表3和表2所示(在“最大”、“最小”法交叉时,都随机选取3位来操作)。

这些点中最好的是-1.0316,最差的是-1.0297,均值是-1.0352。

这些点中最好的是-1.03160,最差的是-1.01013,均值是-1.02723。与传统的单纯形搜索方法及遗传算法搜索结果相比,混合粒子群算法优势是明显的。其得到最优值更接近理论上的最优值。

摘要：针对量子粒子群优化算法在处理高维复杂函数时存在收敛速度慢、易陷入局部最优等缺点,提出了基于黄金分割法、最速下降法、Fibonacci法、“取大”、“取小”法的新算法,同时把遗传算法中交叉、变异算子引入量子粒子群算法中。

关键词：数值计算方法,量子粒子群算法,算子,黄金分割法,最速下降法

参考文献

[1]李士勇.求解连续空间优化问题的粒子群算法[J].电子学报,2007,40(35):50-52.

[2]Eberhart R C.Hu X.Human tremor analyis using particle swarmoptimization[C].In the Proceeding of the IEEE Congress onevolutionarycomputation(CEC 1999),Washinggon D C:IEEE Press,1999:1927-1930.

[3]金聪.启发式遗传算法及其应用[J].数值计算与计算机应用,2003,(1):30-35.

[4]吴仕勇.基于数值计算方法的遗传算法的优化研究[J].计算机工程与设计,2009,30(12):2966-3025.

[5]褚蕾蕾.计算智能的数学基础[M].北京:科学出版社,2002:14-32.

变异算法篇7

目前常用的特征波长选择方法,如相关系数法、回归系数法等大多具有较强的主观性[4]; 模拟退火算法[5,6]具有收敛速度慢以及参数敏感等缺点; 无信息变量消除算法[7,8]得到的变量数依旧较多; 连续投影算法[9]易受到建模变量的影响导致在外部验证时预测结果不理想; 而遗传算法虽然收敛速度慢,但能较好地处理约束,具有良好的全局搜索能力[10,11,12]。本文在紧凑遗传算法( Compact Genetic Algorithm,CGA) 的基础上,提出了基于变异的紧凑遗传算法( Mutation - Based Compact Genetic Algorithm,m CGA) ,通过不同模型的预测结果比较,该算法不仅缩短了运行时间,且在一定程度上简化了模型,减少了无关变量的干扰,提高了农药检测的预测精度。

1 原理与算法

1. 1 农药检测原理

选取没有缺陷,且大小相当的花椰菜作为试验样品,模拟正常的农药喷撒方式对试验样品进行添加。采用TENSOR 27 傅里叶红外光谱仪( 德国Bruker) ,光谱范围为8 000 ~ 350 cm- 1,分辨率为1 ~ 0. 4 cm- 1。采用红外光谱仪照射试验样品,经过红外光的吸收后得到花椰菜样品的红外光谱,并采用Matlab 7. 11( The Math Works,Natick,USA) 软件对相关数据进行处理,根据光谱变量建立模型来预测所测农药的浓度。然而由于多个变量之间的相关性会影响模型的预测精度,本文提出了基于变异的紧凑遗传算法,该算法能减少建立模型所需的变量数目,降低成本,解决多重共线性问题,并提高模型的预测精度。

1. 2 紧凑遗传算法原理

CGA的基本思想是构造一个概率向量( PV) ,其长度与染色体的长度一样。概率向量中的每一个元素的值代表了染色体各个基因位上编码( 二进制) 取1的概率。概率向量的每个元素初始化值都为0. 5。根据概率向量,随机产生两个新个体,通过竞争选择两个个体中的winnner,概率向量朝着winner方向进行更新。但CGA具有未成熟和收敛速度慢的问题,因此提出一种基于变异的紧凑遗传算法。

1. 3 基于变异的紧凑遗传算法原理

算法提出一个变异算子,变异概率为0. 1。根据PV,产生一个个体( individual) ,为更好地保证算法的收敛性,文中将这个个体作为优秀个体,经过位变异后产生一个新个体( new) ,通过两个个体之间的竞争,选择胜出个体,概率向量朝胜出个体方向更新,即概率向量的元素值会增加或减少1 /n。基于变异的紧凑遗传算法能够减少迭代次数,提高CGA的性能。m CGA实现波长选择的算法步骤如下,其中波长变量的数目为m,n定义为算法的种群大小。

( 1) 当PV没有收敛,初始化概率向量,设定每个变量被选取的概率均是0. 5,即for i = 1 to m do PV[i]=0. 5; ( 2) 根据概率向量产生优秀个体,即individual =generate( PV) ; ( 3) 评估产生的优秀个体的适应度,即elite_fitness = evaluate( individual) ; ( 4) 当PV没有收敛时,通过位变异产生新个体,说明产生了新波长变量的组合形式,即new = mutation( individual) ; ( 5) 再对产生的新个体的适应度进行评估,即new_fitness = evaluate( new) ; ( 6) 两个个体进行竞争,产生胜出个体,winner =tournament( individual,new) ; ( 7) 朝胜出个体方向更新PV,改变了每个变量被选的概率,即

( 8) 若P V没有收敛,转到步骤( 2) ,PV表示最终解,即通过算法得到了每个变量被选取的概率,淘汰了无信息变量。

2 试验评价

评价指标选取预测均方根偏差( Root - Mean -Square Error of Prediction,RMSEP) 对模型进行评估。RMSEP可用来评估模型的预测浓度与测量浓度的偏离程度。该值越小,说明模型的预测效果越好。构建矩阵X,矩阵的行和列分别代表花椰菜样本和光谱变量,设定向量Y,向量的行代表获得的每个样本的实际农药含量。根据Kennard - Stone算法[13],对实验样本进行划分,选择201 个样本作为校正集( Xcal,Ycal) ,109个样品作为验证集( Xval,Yval) 。校正集是用来建立预测模型,系数矩阵 β 根据式( 1) 可计算

根据式( 2) ,结合验证集可用来预测所检测农药的浓度

最终,通过预测均方根偏差,即式( 3) 来评估该模型

式中,N代表样本的总数量;yi是所测农药浓度的测量值;是通过式(2)计算的预测值,通过计算预测均方根偏差,可获得更精确的预测模型。

3 结果与分析

表1 列出了紧凑遗传算法,基于变异的紧凑遗传算法,简单遗传算法( Simple Genetic Algorithm,SGA)的预测均方根偏差( RMSEP) 的最大值、最小值与平均值。由表1 可看出,m CGA的平均预测均方根偏差为0. 198,而SGA的平均RMSEP值为0. 289,精确度提升了31. 49% ,CGA的平均RMSEP值为0. 241,精确度相比SGA提升了16. 61% 。并可看出根据m CGA得到的预测均方根偏差的最大值比CGA和SGA的预测均方根偏差的平均值小,因此通过预测误差来看,m CGA与其他算法比较具有更好的预测性能。

图1 是根据SGA得到的预测值和测量值结果对比,图2 和图3 分别是根据CGA和m CGA得到的甲胺磷预测结果和实际结果的对比,图中黑线代表最佳拟合线,其中横坐标代表测量值,纵坐标代表预测值。通过Matlab进行拟合后,经过简单遗传算法得到的预测值和测量值的相关系数为0. 897 5,而通过紧凑遗传算法得到的相关系数为0. 942 8,通过基于变异的紧凑遗传算法得到的相关系数为0. 973 6,通过以上数据对比,可看出基于变异的紧凑遗传算法预测结果的线性拟合,比紧凑遗传算法及简单遗传算法的效果好。对比SGA和m CGA的拟合结果,尤其是数据值在1. 4 ~5. 9 之间以及7. 5 ~ 11. 9 之间结果更明显。实验结果表明,基于变异的紧凑遗传算法具有更好的优化性能,因此对甲胺磷含量的预测效果更好。

4 结束语

本研究提出一种基于变异的紧凑遗传算法来进行变量筛选,通过该算法能够剔除不相关变量。实验结果表明,通过与紧凑遗传算法,简单遗传算法比较,体现了基于变异的紧凑遗传算法在预测精度上的优越性。通过基于变异的紧凑遗传算法得到的预测均方差平均值为0. 198,与其他算法相比较大地提升了预测精度,因而预测结果也更准确。

摘要：为了简化农药检测的预测模型,提高模型预测精度,采用红外光谱技术结合基于变异的紧凑遗传算法对波长变量进行筛选,一定程度上减少了无信息变量和干扰变量。通过不同算法选择的波长变量建立预测模型,mCGA得到的预测均方根偏差平均值是0.198,而与mCGA比较的紧凑遗传算法、简单遗传算法得到的预测均方根偏差平均值分别为0.241、0.289,mCGA具有最小误差。结果表明,采用mCGA进行变量选择,能有效提高模型收敛速度及模型准确度,实现农药含量快速高效的检测。

本文来自古文书网(www.gwbook.cn)，转载请保留网址和出处

语用变异01-17

2025年计算机网络实习报告计算机网络专业实训模板(9篇)01-17

计算机网络专业个人简历范文4篇01-17

变异系数法01-17

2025年计算机网络个人简历(模板9篇)01-17

生物变异01-17

空间变异01-17

遗传变异算子01-17

信息变异01-17

书籍变异设计01-17

注：本文为网友上传，旨在传播知识，不代表本站观点，与本站立场无关。若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL：66553826@qq.com