薇老大
范文一：量子进化算法
量子进化算法
第23卷第2期工程数学学报v0l_23No.2
2006年04月CHINESEJOURNALOFENGINEERINGMATHEMATICSApr.2006
文章~-:1005—3085(2006)02—0235—12
量子进化算法木
杨淑媛,焦李成,刘芳
(西安电子科技大学智能信息处理研究所,西安710071)
摘要:进化算法是解决优化问题的一种有效方法,但在实际应用中也存在收敛速度慢,早熟等问题,大
大影响了其应用效果.本文将进化算法和量子理论结合,提出一种新的理论框架.量子进化理论
及其学习算法.算法借鉴量子理论,采用量予染色体的表示形式,能使一个染色体同时表示多个
状态;模拟量子坍塌的随机观察能带来丰富的种群:同时构造具有量子特点的交叉变异算子,能
在防止算法早熟的同时使算法更快收敛.本文不仅从理论上证明了这一理论框架的全局收敛性,
仿真计算也表明了此算法的优越性.
关键词:量子染色体:概率:进化;收敛
分类号:AMS(2000192B99中图分类号:TP181文献标识码:A
1引言
依照达尔文的自然选择和孟德尔的遗传变异理论,生物的进化是通过繁殖,变异,竞争和
选择来实现的,进化算~(EvolutionaryAlgorithms--EA)就是建立在上述生物模型基础上的一
种随机搜索技术.它起源于Holland提出的遗传算法(GeneticAlgorithms--GA)【lJ,F0gel对于
2]以及Rechenberg和Schwefel 优化模型提出的进化规~lJ(EvolutionaryProgramming--EP1【
用
于数值优化问题的进化策略(EvolutionaryStrategies--ES)【0].理论上已经证明:它们均能从概
率的意义上以随机的方式寻求到问题的最优解.但将EA用于各种实际问题后,也出现了一些
不尽人意之处,主要表现在:容易产生早熟,收敛速度慢,局部寻优能力差等.这是自然进化
和生命现象的不可知性的结果,也是EA最明显的缺陷之一一收敛难问题(包括收敛速度慢和
未成熟收敛).可以看出:EA之所以能使个体得到进化,首先是采用选择操作选出比较好的
个体,使个体逐渐趋于最优,同时采用交叉变异等进化操作,通过它们的破坏性影响保证产生
新的个体,从而生成更好的个体,更重要的是可以维持群体的多样性,即EA总是在追求群体
的收敛性和个体的多样性之问的平衡.若选择压力不足,则算法的收敛速度慢,若选择压力太
大,个体的多样性又不够,算法易陷入局部最优.
分析可以发现:EA没有利用进化中未成熟优良子群体所提供的信息,因而收敛速度很慢.
事实证明:在进化中引入好的引导机制可以增强算法的智能性,提高搜索效率.现有EA的许
多改进工作也正是致力于这一方面,它们主要是针对特定问题,采用启发式知识来人为的指
导
和约束进化,这依赖于设计者对问题的认识程度,也将算法复杂化.21世纪科学技术的发展愈
加开放,学科间的联系也日益紧密,我们能否借鉴其它学科的知识,应用一种更自然的机制,
来描述进化过程,从而更高效的解决计算科学中的问题呢?下面我们就借鉴物理学中的量子理
论来研究进化算法.
收稿日期:2003-06—02.作者简介:杨淑嫒(1978年10月生1,女,博士,讲师,研究方向:锗能信息处理
基金项目:博士点基金(20030701013).
236工程数学学报第23卷
人类在发掘生物进化机制,进行‖仿生‖研究的同时,也受物理学的启发而萌发了‖拟
物‖的思想.二者相互渗透,取长补短,产生了许多成功的理论,模拟退火算法就是由物理学
推动发展的动力系统得到生物进化思想完善的产物【4J.量子力学是20世纪最惊心动魄的发现之
一
,它为信息科学在下个世纪的发展提供了新的原理和方法.由于量子硬件实现的难度,量子
计算机还不能在短期内实现,但是它对人类思维和学习方法所带来的革命性作用以及量子计算
所特有的性质对经典理论的冲击,都是不可忽略的.我们能否将量子理论运用到经典的算法中
去,通过对经典的表示作一些调整,使其具有量子理论的优点,从而进行一些类量子的计算来
实现更为有效的算法呢?基于上述讨论,本文将进化算法与量子理论相结合,提出一种新的理
论框架一量子进化理论及其学习算法.它基于量子计算的概念和理论,使用量子比特编码染色
体.由于量子的概率幅表示,一个量子染色体可以同时表示多个状态的信息.因此,模拟量子
坍塌的随机观察可带来更丰富的种群.量子染色体的变异能使当前最优个体的信息能够很容易
的用来控制变异,使种群以大概率向着优良模式进化,加快收敛.另外,受量子干扰启发的量
子全干扰交叉能够比传统进化算子更好的克服早熟现象的发生.
2量子进化算法
2.1量子染色体
在量子信息论中,信息的载体不再是经典的比特,而是一个一般的二态量子体系一它可以
是一个二能级的原子或离子,也可以是一自旋为1/2的粒子或具有两个偏振方向的光子,所有
这些体系,均被称为量子比特(Qubit);区别于经典比特,量子比特可以处于0,1两个本征态
的任意叠加状态,而且对量子比特的操作过程中,两态的叠加振幅可以相互干涉,这就是量子
相干性:量子计算机对每一个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些
经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的计算结果,这种计算称为
量子并行计算『51.一个量子比特的状态可以取值0或1,其状态可以表示为:
)=Ql0)+l1),(1)
其中复数Q,代表相应状态出现的概率,lQl,分别表示量子比特处于状态0和1的概率,
满足+一1.EA常用编码方式有二进制编码,十进制编码和符号编码.在量子进化
算法中(QuantumEvolutionaryAlgorithm--QEA),使用一种新颖的基于量子比特的编码方
式,即用一对复数定义一个量子比特位.一个具有m个量子比特位的系统可以描述为:
茇l:
粥I]】?则系统的状态可以表示为:
1000)+100)+1010)+101)+Il00)+Il0)+ll10)+ll11)
第2期杨淑媛等:量子进化算法237
上面结果表示状态l000),l001),l010),l011),l100),l101),l110),I111)出现的概率分别为3/32,
9/32,1/32,3/32,3/32,9/32,1/32,3/32,即这个3量子比特系统表示了8个状态叠加的信息;而且
随着趋于1或0,量子染色体收敛于一个状态,这时多样性消失,算法收敛.
2.2算法描述
QEA是一种和EA类似的概率算法,种群由量子染色体构成,在第t代的种群为Q(t1:
{口i,qt,…,},其中佗为种群大小;m为量子染色体的长度;口为定义如下的染色体:
=
一
lQ1,j:,2,,几一
IJ
下面给出QEA的一般步骤:
?进化代数初始化:T=0:
?初始化种群Qft);
?由Q(t)生成P?t:
?个体交叉,变异操作,生成新的P(t);(一般可以省略)
?评价群体P(t)的适应度,保存最优解;
?停机条件判断:当满足停机条件时,输出当前最优个体,算法结束,否则继续;
?更新Q(t),T=T+1,转到?;
由以上描述可以看出:QEA与EA的不同仅仅在于增加了?和?这两步.?表示通过观
察Q(t)的状态,产生一组解P(t)={zi,xi,…,z),每个长为m的普通解X0=1,.,Tt)是
由量子概率幅(i=1,.,m)得到的.如在二进制情况下的观察过程可以是:产生一个属
于[0,1】的随机数,若它大于IQ,X中相应的位取1,否则取0;在?中,可以采用不同的策
略来进化Q(t),例如随机产生;采用传统进化操作,还可以根据量子的叠加特性和量子变迁
的理论,运用一些合适的量子门变换来产生新的Q(t),但由于概率归一化的条件,变换矩阵必
须是酉正矩阵.常用的量子变换矩阵有:异或门,旋转门和Hadamard变换门等f61.
2.3进化机理分析
一
个好的优化算法在处理利用积累信息和探索未知空间之间的矛盾时必须采用折中的
策略,既利用积累信息搜索当前空间,又要兼顾对未知空间的搜索;既要加快算法的收敛
速度,还要克服早熟现象.那么针对这些矛盾,QEA采用了什么策略呢?首先,在搜索过
程中,QEA通过选择使具有较高适应度的个体不断增多,并且模拟量子坍塌,执行状态观
察产生新的个体,不断探索未知空间,像EA那样,使搜索过程得到最大的积累收益.其
次,QEA采用量子染色体的表示形式,使一个染色体上同时携带多个状态的信息,是状态观
察带来丰富种群的基础;再次,QEA对量子染色体采用一种‖智能‖变异的策略来引导进
化,使种群以大概率向着优良模式进化,另外,QEA模拟量子的相干特性构造了一种新的交
叉算子一‖全干扰交叉‖,用来克服进化后期的早熟.
2.3.1量子变异一加快收敛
和普通编码方式不同,QEA中的量子染色体是一种概率表示,因此对概率的交叉是没有物
理意义的,所以交叉是作用于量子染色体的唯一遗传算子,首先给出下面两种量子变异.
?量子变异1:EA中通常的变异操作是一种随机变动,没有有效利用进化过程中产生的信
息.下面方法针对二值问题,它由当前最优解反推出一个指导量子染色体,然后在它的周围随
机散布量子染色体作为下一代的量子种群,有点类似于概率遗传算法,但是操作却简单的多,
简单描述为:
Q9d.(,)=Q×Pc.拍.t(,)+(1一a)×(1一Pc.惦.t(,)),(6)
238工程数学学报第23卷
Q(t+1)=Q口id.(t)+b×normrnd(O,1),(7)
其中.幻.t(,)为第t代时得到的最优个体;Q.id.(,)为指导量子染色体;a为.tb.t
的影响因子;b为量子变异的方差.显而易见,采用2.2所述的观察方式,为得到染色体P=(1
1001),只需令量子染色体Q为(00110),即Q=户.如果P是全局最优解,则种群中的
量子染色体越接近Q,得到最优解的概率越大.a的值越小,量子种群受Qguid.(t)的影响越
大;当a=0时,观察Q口id.(t)将以概率1得到P.一般取a?[0.1,0.5】,b?[0.05,0.15】.
?量子变异2:在量子理论中,状态间的转移是通过量子门变换矩阵实现的,我们发现:用
量子旋转门的旋转角度同样也可表征量子染色体中的变异操作.可以设计下面的变异算子:
r]
(?)=I..()n(?I(8)一l
sin(0)cos(O)j一
表示量子旋转门,旋转变异的角度A0可由表1得到.
表1:变异角度
best.f(x)>f(best)AOt.>0Ot.<0t=0=0
00假00000
00真00000
01假00000
01真0.Ol?r一11士10
10假0.Ol?r一11士10
10真0.Ol?r1—10士1
11假0.Ol?r1—10士1
11真0.017r1.10士1
其中xi为当前染色体的第i位;besti为当前的最优染色体的第i位;f(x)为适应度函
数,AO为旋转角度的大小,控制算法收敛的速度;表格中最后一列控制旋转角度的方向,保
证算法的收敛.为什么这种旋转量子门能够保证算法很快收敛到具有更高适应度的染色体昵?
下面用一个直观的图说明量子旋转门的构造.例如当=0,best=1,f(x)>f(best)时,为
使当前解收敛到一个具有更高适应度的染色体,应增大当前解取1的概率,即要使Q变大,则
若(OLi,)在第一,三象限,0应向顺时针方向旋转;若(Ozi,)在第二,四象限,0应向逆时
针方向旋转,如图1所示.此外我们还可以构造其他变异算子,例如采用或设计其他量子变换
门等.
2.3.2量子交叉一克服早熟
交叉是EA的另一种搜索最优解的手段,通常采用的交叉操作如单点交叉,多点交叉,均
匀交叉,算术交叉等,它们的共同点是限制在两个个体之问,当交叉的两个个体相同时,它们
都不再奏效.在这里,我们使用量子的相干特性构造一种新的交叉操作一‖全干扰交叉‖.在
这种交叉操作中,种群中的所有染色体均参与交叉.若种群数为5,染色体长为9,表2示出其
中的一种具体操作:它是一种按对角线重新排列组合的交叉方式,其中每个大写字母代表交叉
后的一个新染色体,如A(1)一A(2)..A(9),我们称这样的交叉方式为‖全干扰交叉‖.
第2期杨淑媛等:量子进化算法239
l
J
1
—,‘
/\\\j
\一.1门
一—一l一/0
,
,
/
——/
图1:量子门旋转示意图
表2:全干扰交叉
lA(1)E(2)D(3)c(4)B(5)A(6)E(7)D(S)C(9)
2B(1)A(2)E(3)D(4)c(5)B(6)A(7)E(8)D(9)
3C(1)B(2)A(a)E(4)D(5)c(6)B(7)A(S)E(9)
4D(1)c(e)B(3)A(4)E(5)D(6)c(7)B(8)A(9)
5E(1)D(2)c(a)B(4)A(5)E(6)D(7)c(8)B(9)
上面仅给出一种方式,我们还可以采用不同的方法产生‖交叉基因位‖来实施交叉.这种
量子交叉可以充分利用种群中的尽可能多的染色体的信息,改进普通交叉的局部性与片面性,
在种群进化出现早熟时,它能够产生新的个体,给进化过程注入新的动力.这种交叉操作借鉴
的是量子的相干特性,可以克服普通染色体在进化后期的早熟现象.
2.4量子进化算法的结构框架
类似于EA,我们将QEA也分为量子遗传算法,量子进化规划和量子进化策略.
2.4.1量子遗传算法(QuantumGeneticAlgorithm—QGA)
从1975年GA的通用理论框架由密西根大学教授John.H.Halland首次建立以来,GA已经
在自然与社会现象模拟,工程计算等方面得到了广泛的应用【7—91.QGA可以描述为:
?进化代数初始化:t=O;
?初始化种群Qft);
?由Q(t)生成P(t):随机产生一个f0,l】间的数,若它大于I,取l,否则取0;
?个体交叉,变异操作,生成新的P(t):(一般可省或仅用量子交叉.)
?评价群体P(t1的适应度,选择操作;
?停机条件判断:当满足停机条件时,输出当前最优个体,否则继续:
?更新Q(t),t=t+l,转到?:
2.4.2量子进化规划(QuantumEvolutionaryProgramming—QEP)
EP对生物进化过程的模拟是着眼于物种的进化过程【l01,不使用个体重组算子,所以,
变异是EP唯一的搜索最优个体的方法,最常用的是高斯变异算子.假设群体中某一个个
2401==程数学学报第23卷
体X={X,X,…X)经过变异后得到X={,….,,n),则新个体的组成元素是:
X.=Xi+O‖i.(0,1)
=
i
(i=1,2,…,仡)
(i=1,2,一?,仡)
(9)
(10)
其中(0,1)表示对每个下标i都重新取值的均值为0,方差为1的正态分布随机变量,系
数,是特定的参数,根据特定的优化任务调整.可以证明:若采用高斯变异和联赛选择产
生后代,EP可以渐进收敛到问题的全局最优解.它的缺点是进化求优的时间一般很长.在这
里我们采用如下的量子变异算子.
表3:量子变异
z>bestiXi=bestiz<bestif(x)f(best)/X0
假假真假一0.01不
假假真真一0.001不
假真假真土0.01不
真假假假0.01不
真假假真0.001不
其中X,best.分别为当前染色体和当前最优染色体;f(x)为适应度函数;AOi为旋转角.对
于实数编码问题,由Q(t)生成p(t)的操作是:对染色体q的每一个基因位,实施X=
floor(q×10)+1,(mi1),而对于其他形式的编码问题,我们只要将量子染色体的幅度变
换到所求解的问题区间,即需要构造不同的观察方式,而变异角度的产生与此类似.QEP可
以描述为:
?根据求解的精度确定搜索空问的维数,假设搜索空间Q是一个仡维空间,于此相对
应,搜索点就是一个仡维向量,然后随机生成初始种群Q(t);
?由Q(t)生成P(t)(根据编码采用不同的观察方式:)
?对P(t)进行进化操作:(可省.)
?对当前的父代群体进行变异操作得Q(t),由Q(t)生成新个体P(t);
?计算当前第t代父本种群的适应度,联赛选择,其过程描述如下:
5.1乱个父代个体P(t)和它经过变异后所产生的乱个子代个体合并在一起,组成一个
含有纨个个体的个体集合{P(,)uP(,)).
5.2对这个个体集合中的每一个个体fP(,)uP(,)),从这个个体集合中随机选取其他q个
个体(其中q1是选择运算的参数),比较这q个个体和个体之间适应度的大小,把其
中适应度比的适应度还要高的个体的数目作为的得分.
5.3按个体集合fP(,)uP(,))中每一个个体得分的大小对全部2个个体做降序排
列,选择前乱个个体作为进化过程中的下一代群体P(t+1)的个体集合.这样,每代群体中
的最好个体总能够确保被保留到下一代去.
?判断停机条件,Q(t)=Q(t),t=t+l,转至?.
第2期杨淑媛等:量子进化算法241
2.4.3量子进化策略QuantumEvolutionaryStrategies—QES1
20世纪60年代,柏林理工大学的Rechenberg和Schwefel等先驱在对生物的进化的研究成果
进行分析与理解的基础上,借鉴其相关内容和知识,特别是遗传进化方面的理论与概念,针对
处理流体动力学中弯管形态的优化问题,提出并发展了一种新的优化算法一进化策略f111.其
中组成进化群体的每一个个体表示成两部分,一部分是可以取连续值的向量,另一部分是一个
微小的变动量.这个变动量通常由步长?Rn(态分布的标准方差)确定,即群体中的每一
个个体都可以表示为X=x,;但是实际上影响变异操作的不仅仅是变动量的大小,还
有变动量的方向一回转角,它可以用来调整个体进行变异操作时变异量的方向,回转角有时在
某些问题中比步长具有更重要的地位.因此人们提出一种更合理的个体表示:X=x,,Q,,
回转角Q?R(一)/代表正态分布时的协方差.假设群体中某一个个体X=x,经过变异
后得到的一个新个体是X=fX,Q,则新个体的组成元素是:
=
.
exp[r.N(0,1)+丁.(0,1)](=1,2,…,n),(11)
X=Xi+Q.N(0,)(i=1,2,?一,n),(12)
其中丁和丁分别表示变异操作时的整体步长和个体步长.QES的详细描述如下『121:
?将搜索空间转化为一个n维实数空问,于此相对应,搜索点就是一个n维向量x?
R,随机初始化种群Q(t1;
?由Q(t)生成P(t),根据不同问题采用不同的观察方式;
?对P(t)进行进化操作;(可省.)
?对当前的父代群体进行进化操作得Q(t),由Q(t)生成新个体P(t);
?评价群体Q(t)的适应度,确定性选择,采用量子交叉.
QES中常用的选择操作主要有两种:一种是从个父代个体中选择出u(1札)个适
应度最高的个体,将它们保留到子代中,称之为(札,)一QES;另一种是从U个父代个体和它所
产生的个子代个体合并在一起,并从这合并而成的个子代个体中选取U个适应度最高个体,将
它们保留到子代中,叫做(+)一QES,可以任取一种.由于在QES中,选择运算是按照一种
确定的方式来进行的,每次都是从当前群体中选出一个或几个适应度最高的个体保留到下一代
个体中,容易产生早熟,因此这里采用量子交叉操作.
?判断停机条件,Q(t)=Q(t),t=t+l,并转至?.
2.5量子进化算法的收敛-陛
定理1设P为一n阶可归约矩阵:
P=
[曼],c3
其中C是一个mXm的基本随机矩阵,而且R,T?0,则
一
…
limpk=
Ck
i
州0
242工程数学学报第23卷
定理2QEA是全局收敛的.为了研究EA的全局收敛性,已经提出了很多分析模
型【l3】.1990年Eiben提出EA的一种抽象表示,将进化过程定义为马尔可夫链,利用转移概
率矩阵相乘来进行状态的变换,分析得出EA收敛到最优解的条件.QEA与EA类似,仅多
出了由Q生成P和变异Q的过程.我们以二值问题为例讨论QEA的收敛性.假设染色体长
度为,种群规模为?,对于染色体的取值是离散的0,1的GA,种群所在的状态空间大小
是2NL,而对于OEA,由于Q的取值是连续的,理论上种群所在的状态空间是无限的,但因
实际运算中Q是有限精度的,设其维数为V,则种群所在的状态空间大小则为?L.算法的
状态转换过程可用如下的Markov链来描述:
算法的整个过程可表示为:
Q一(一一)一Q.
不(+)=7r()×ClM1S1U,
U=F(p()),
p():口()
,
口(,+):口()×C2M2S2,
(16)
(17)
设中间种群的规模为,则种群和中间种群所在的状态空间分别为{0,1)?L,{0,1)?L,算
法的状态转移矩阵可用交叉,变异,选择矩阵C,,S来表示,其中C,,S分别
为2?L×2?L,2?L×2?L,2?L×2?L阶随机矩阵,由交叉选择算子的含义可知:
(18)
其中口(t)为1×VNL维的量子染色体的概率分布向量,p(?,不(),均为1×2(?+)L维的普
通染色体的概率分布向量,为由量子染色体生成普通染色体的u×2N维的概率转移
矩阵;C2,M2,均为VNL×VNL维随机矩阵,Cl,M1,S1,为2(?+)L×2(?+)L阶的块对
角矩阵.讨论解空间{0,1uv1卜(为讨论的方便,我们令N:N),此时每一状态均由N
+1个串长L的个体组成,第一个个体被称为超个体,只起标志,记录作用,不参与进化.
状态空间中状态依次为一,2,{0,1)中的个体按适应度大小排列为:Xl,-一,X2,
则经过遗传算子的作用,空问{0,1中的状态(X,)变为状态(,,)的概率由矩
阵P:C】M】S】确定,其中C1,M】,S1分别为块C,,S组成的块对角矩阵:
C1=
C
C
C
M1=,S1=
(19)
由于经算法中的‖最优保持‖后,如果当代产生的最优个体优于超个体,则用当前最优个体代
替超个体,否则保持不变,所以我们引入2(?+)L×2(?+)L阶随机矩阵来表示这种升级运
1?????j
0
—..................L
:
S
1?????j
0
―
—..................L
1.
C
第2期杨淑媛等:量子进化算法243
算,其中矩阵U的每行仅有一个元素为1,其余元素均为0,它可表示为:
则算法的状态转移矩阵为:
U=
P+=P.U=C1M1S1U:
U11
u21U22
CMSU11
CMSU21CMSU22
CMSU2L,
1CMSU2L,
2.??CMSu2L.
2L
(20)
(21)
以上过程均与GA类似,不同的是,这里的升级运算不仅受P自身进化过程的影响,而且
受到Q的作用,当通过新的Q产生的P中出现了优于当前代的超个体的解时,便更新超个
体.因为CMS为一正的随机矩阵,由上文知:U11为2(I代表单位阵),t是至少
一
对角元为0的下三角阵,则:
CMSU11=CMS>0
CMSU21
CMSu2L,1
?0
CMSU22
CMSU2L,
1…CMSU2L
,
2L
?0.(22)
从而由定理1知:liIrI(P+)存在,而且liIrI(P+)=(P1,P2,…P2,0,…,0)与初始分布
向量?(o)的初值无关.因为已知f0,1}‘+1)中前2L个状态的第一个个体均为取全局最优
值的个体1,若记P为t时刻算法处于状态i的概率,并且记为其中适应度最高的个体
为Xl的所有状态的集合,则p(–,)=?P,从而liIrIp(–f)=P1+??.+p2=1,
即此时算法是收敛的.
3仿真实验
背包问题是一个典型的组合优化问题,描述如下:假设有价值与重量Wi已知的?件
物品和一个最大容重为的背包,选择哪些物品装入该背包可在其容量约束限制之内装入
物品的总价值最大?我们先以N=8,V=45为例,考察QEA的性能.首先用一个二
进制串代表问题的一个可能解,染色体的每个基因位可能的取值为1和0,1代表将该物品装
入,0代表不将该物品装入.问题归结于在28=256种装入方式中找到满足要求且装入物品的总
价值最大的一种.256种装入方式的总重量如图2所示.满足条件的有7个个体,只有一个最优
解一V=45,C=32.设最大终止代数1000,GA的变异和交叉概率分别为0.7,0.1,QEA中
省略普通染色体的进化,量子染色体采用变异策略1,为检验文中提出的变异策略的有效性,
我们给出了不使用量子变异,而是随机产生量子染色体的算法的结果,在这里,姑且称之
为QA.图3给出了lOO次试验的平均结果.
244工程数学学报第23卷
1?
90
?
70
一
印
加
30
20
1O
0
??一一
}凝
l5..}雏}
j
…
C=3
…
2&__|,;:
勰!..!r;
童蠡《
!
.::…一::
C=26
艄‘黔f—IC=26?=23
C1ic=2o
图2:256种可能装入的重量
各算法性能比较(100次的统计结果)
图3:进化1000代的结果
图中括号后的数字代表种群的大小.我们以量子染色体数目为l为例,观察量子染色体的
变化:开始量子染色体各基因位的幅度值是相等的,即所有可能的个体以相同的概率出现,
期望最后最优个体以概率l出现,图4分别给出了进化不同代后个体出现概率的统计结果.考
虑m----50,V=1000,采用量子变异策略2的情况.在GA和混合遗传算法(HGA)中,假设
种群大小为80,最大终止代数为500,变异和交叉的概率分别为0.7,0.1.表4给出了50次试验
不同算法的结果.观察量子进化算法的最大值,最小值和平均值的收敛曲线可以看到:对于上
述背包问题采用如前所述的QEA,当进化到第11代时,已出现最优解3103/1000,而且种群集
中在3096/999,3098/998,3093/997,3095/996等周围.当进化到第50代时,最优解在种群中
的比例已占到半数以上凸_05
04
03
02
01
1?次的统计结果僵子染色体的数日为1时)
-
501叩150200250
2900代后的概率分布
图4:500代,1000代,1500代,2000代后的个体出现概率
表4:算法结果对比
GA13791323077/999
HGA183453103/1000
QEA1123103/1000
贪心算法003036/996
本文在借鉴量子理论和分析进化算法缺点的基础上,提出一种将量子理论与进化理论相结
合的量子进化算法框架,算法引入量子比特来编码染色体,构造了量子进化算子一量子变异和
量子交叉,并证明了其全局收敛性.对应于进化算法,本文详细给出了该框架之下的三个算法
一
量子遗传算法,量子进化规划和量子进化策略.理论分析和仿真结果都表明:此算法收敛速
度快,种群多样性好,能有效克服早熟现象,类似的结果在国内外还未见报导.
参考文献:
【1]HollandJH.Geneticalgorithmsandclassifiersystems:foundationsandtheirapplications[C]//Proce
edings
oftheSecondInternationalConferenceonGeneticAlgorithms.Hillsdale,NJ:LawrenceErlbaumAssoc
iates,
1987:8289
【2】FogelLJ,OwensAJ,WalshMJ.ArtificialIntelligenceThroughSimulatedEvolution[M】.Chichester:
JohnWiley,1966
【3】KlockgetherJ,SchwefelHP.Two-phasenozzleandhollowcorejetexperiments[C]//ElliottD.(eds.)
Proc11thSympEngineeringAspectsofMagnetohydrodynamics.PasadenaCA:CaliforniaInstituteof
Technology,March24—26,1970:141—148
【4】张讲社,徐宗本,梁怡.整体退火遗传算法及其收敛充要条件[J].中国科学(E
辑),1997,27(2):154-164
246T程数学学报第23卷
5】王安民.计算的量_『匕跃[J】.物理,2000,29(6):351—357
6】HeyT.QuantumComputing:AnIntroduction【J】.Computing&ControlEngineeringJournal,
1999,10(3):105—112
7】
AlenVarsek.TanjaUrbancic,BodganFilipic,Geneticalgorithmsincontrollerdesignandtuning[J】.IEEE
TransSMC,1993,23(5):1330—1339
8】
MillerG,ToddP,HedgeS.Designingneuralnetworksusinggeneticalgorithm[C]//ProceedingsoftheThird
InternationalConferenceonGeneticAlgorithmsandTheirapplications,DJSchaffer,Ed.SanMateo,CA:
MorganKaufmann,1989:360—369
9】
GoldbergDE.Geneticalgorithminsearch,optimization,andmachinelearning[M】.MA:Addison—We
sley,
Reading,MA,1989
10】
11】
12】
13】
FogelDB.Asymptoticconvergencypropertiesofgeneticalgorithmsandevolutionaryprogramming:anal—
ysisandexperiments[J].CyberneticandSystems:AnIntJ,1994,25(3):389—407
KlockgetherJ,Schwe~lHP.Two-phasenozzleandhollowcorejetexperiments[C]//ElliottD.(eds.)Proc
1lthSympEngineeringAspectsofMagnetohydrodynamics.PasadenaCA:CaliforniaInstituteofTech—
nology,March24—26,1970:141—148
杨淑媛,刘芳,焦李成.‖量子进化策略‖.J].电子学报,第12A期,第29卷,2001年12月
NixAE,VoseMD.ModelinggeneticalgorithmswithMarkovchains[J1.AnnMathArtifIntell,1992,5:79-88
TheQuantumEvolutionaryAlgorithm
YANGShu—yuan,JIAOLi—cheng,LIUFang
(InstituteofIntelligentInformationProcessing,XidianUniversity,Xi‘an710071)
Abstract:Anovelkindofalgorithm,calledthequantumevolutionaryalgorithms—QEA,isproposed
bycombiningquantumtheorywithevolutionarytheory.Itisakindofevolutionaryalgorithmwiththe
formofquantumchromosome,therandomobservationwhichsimulatesthequantumcollapsecanbring
diverseindividuals.andtheevolutionaryoperatorscharacterizedbyquantummechanismareintroduce
d
tospeedupconvergenceandtoavoidprematurity.Thepapernotonlyprovestheglobalconvergence
ofQEA,butalsoprovidessimulationexperimentstoproveitssuperiorityoveritscounterpart.
Keywords:quantumchromosome;probability;evolution;convergence
范文二：实数编码量子进化算法
第 23卷 第 1期
Vol. 23No. 1
控 制 与 决 策
Cont rol
and
Decision
2008年 1月
J an. 2008
收稿日期 :2006210211; 修回日期 :2007201224.
基金项目 :交通部西部交通建设科技项目 (200431882053) .
作者简介 :高辉 (1969— ) , 男 , 吉林松源人 , 博士生 , 从事智能控制 、 智能交通系统等研究 ; 徐光辉 (1964—
) , 男 , 辽宁锦州人 , 副教授 , 博士 , 从事城市轨道交通和交通系统动力学的研究 .
文章编号 :100120920(2008) 0120087204
实 数 编 码 量 子 进 化 算 法
高 辉 1, 徐光辉 1, 张 锐 2, 王哲人 1
(1. 哈尔滨工业大学 交通科学与工程学院 , 哈尔滨 150090; 2. 哈尔滨理工大学 自动化学院 , 哈尔滨 150080)
摘 要 :为求解复杂函数优化问题 , 基于量子计算的相关概念和原理 , 提出一种实数编码量子进化算法 . 首先构造了 由自变量向量的一个分量和量子比特的一对概率幅为等位基因的三倍体染色体 , 增加了解的多样性 ; 然后利用量子 旋转门和依据量子比特概率幅满足归一化条件设计的互补双变异算子进化染色体 , 实现局部搜索和全局搜索的平 衡 . 标准函数仿真表明 , 该算法适合求解复杂函数优化问题 , 具有收敛速度快 、 . 关键词 :量子计算 ; 量子进化算法 ; 实数编码量子进化算法 ; 中图分类号 :TP18 文献标识码 :A
R eal 2coded qu GA O H ui 1
, , Z H N R ui 2
, W A N G Zhe 2ren
1
(1. School of and Engineering , Harbin Institute of Technology , Harbin 150090, China ; 2. School of , Harbin University of Science and Technology , Harbin 150080, China. Correspondent :GAO Hui , E 2mail :zr_gh@sina.com )
Abstract :In order to optimize the complex f unctions , a real 2coded quantum evolutionary algorithm is proposed based on the relational concepts and principles of quantum computing. Real 2coded triploid chromosomes , whose alleles are composed of a component of the independent variable vector and a pair of probability amplitudes of the corresponding states of a qubit , are constructed to keep the population diversity. The complementary double mutation operator , which is designed according to the probability amplitudes of a qubit f ulfilling the normalization conditions , and the quantum rotation gate are used to update chromosomes and realize a good balance between exploration and exploitation. Simulation results on benchmark functions show that the algorithm is well suitable for the complex function optimization , and has the characteristics of rapider convergence , more powerf ul global search capability and better stability.
K ey w ords :Quantum computing ; Quantum evolutionary algorithm ; Real 2coded quantum evolutionary algorithm ; Function optimization
1 引 言
进化算法在求解复杂函数优化和组合优化问题 中得到广泛应用 , 但仍存在 “ 早熟” 和 “停滞” 现象 . 为 解决这些问题 , 借鉴量子计算的概念和原理 , 人们提
出了量子进化算法 (Q EA ) [123]. Q EA 采用基于量子 比特概念构造的量子染色体 , 增加解的多样性 , 以克 服 “ 早熟” 现象 ; 并利用当前最优染色体信息 , 使用量 子旋转门更新量子染色体 , 确保进化的方向性 , 以避 免 “停滞” 现象 . 然而大量研究表明 [426], 尽管 Q EA 在求解组合优化问题时比传统进化算法表现出更优 良的性能 , 但不适合求解复杂函数优化问题 . 为此 ,
本文提出一种实数编码量子进化算法 (RCQ EA ) . RCQ EA 利用待求解复杂函数自变量向量的一个分
量和量子比特的一对概率幅组成染色体的等位基 因 , 进而构造实数编码三倍体染色体 , 以增加解的多 样性 , 并利用量子旋转门和依据量子比特概率幅满 足归一化条件而设计的基于高斯变异的互补双变异 算子一起进化染色体 , 实现算法局部搜索和全局搜 索的平衡 . 标准函数仿真表明 ,RCQ EA 求解复杂函 数优化问题具有很好的性能 .
2 量子进化算法 (QEA)
在 Q EA 中 [5], 用一个具有 n 个量子比特的量子
控 制 与 决 策 第 23卷 寄存器来表达长度为 n 的量子染色体 , 即
1… αi … n
β
1… βi …
. (1)
式中 αi 和 βi 分别为量子比特 |0〉 态和 |1〉 态的概率
幅 , 且满足归一化条件 |αi |2+|βi |2=1, i =1, 2,
… , n. 一个量子染色体可表征解空间中任意解的叠
加态 , 叠加性是量子染色体增加解的多样性的根本
原因 . 通过随机测量 , 一个量子染色体以概率的形式
坍塌到一个二进制形式的解 . Q EA 采用量子旋转门
作为进化策略 , 使当前解逐渐逼近搜索到的最优解 ,
并将需要的结果以概率的形式增加 , 不需要的结果
则以概率的形式减弱 . 量子旋转门可描述为
R (θ) =
cos θ-sin
sin θcos
, (2)
式中 θ为旋转角 .
态之间的转换 ,
Q EA (如背包问题 ) 时 , 表
现出优良的性能 , 但不适合于求解复杂函数优化问
题 . 原因在于 Q EA 对解空间终归是以二进制形式表
示 , 这就决定了 Q EA 包含以往任何以二进制形式表
示解空间的进化算法在求解复杂函数优化问题时具
有的诸如繁琐的编 、 解码过程 , 以及随着函数维数的
增加和求解精度的提高 , 引起染色体编码 “ 长度灾” ,
并导致搜索效率低下等缺点 .
3 实数编码量子进化算法 (RCQEA)
RCQ EA 算法的基本思路是 :首先构造实数编
码三倍体染色体 ; 然后 , 利用量子旋转门和根据实数
编码三倍体染色体的具体形式设计的基于高斯变异
的互补双变异算子一起进化染色体 , 并通过离散交
叉实现染色体之间的信息交流 , 扩大算法搜索范围 ;
最后 , 通过进化操作产生新的染色体 , 采用 “爬山”
选择 , 加快算法收敛速度 . RCQ EA 算法的基本模型
如图 1所示 . 图中 :p t u (u =1, 2, … , N
) 和 p t v (v ≠ u )
均为实数编码三倍体染色体 , b t 为当代最优染色体 .
图 1 实数编码量子进化算法基本模型
3. 1 实数编码三倍体染色体
复杂函数优化问题可描述为
J =min (f (x ) ) ,
x =(x 1, … , x i , … , x n ) ∈ R n ,
x i ∈ [x i , min , x i , max ], i =1, 2, … , n. (3) 式中 :x i , min 和 x i , max 分别为自变量向量 x 的分量 x i 的下界和上界 , n 为复杂函数的维数 . 实数编码三倍 体染色体的等位基因由复杂函数自变量向量 x 的一 个分量 x i 和量子比特的一对概率幅 [αi βi ]T 组成 , 即 [x i αi βi ]T ; 染色体长度由复杂函数的维数决定 . 则实数编码三倍体染色体可描述为
x 1… x i … x n
α
1… αi
1i n
, (4)
i .
. 2
EA 算法对群体中的每一个染色体实施单 基因变异 , 即每次仅对染色体的一个基因位进行变 异 , 其余基因位则保持不变 , 从而构成新染色体 . 文 献 [7]已证明 , 单基因变异比全基因变异具有更高 的搜索效率 . 设第 t 代时的群体为 P (t ) ={p t 1, … , p t j , … , p t N }, 对于染色体 p t j , 随机选择第 i 基因位 [x t j , i αt j , i βt j , i ]T , 对变量 x t j , i 按下式进行高斯变异 :
x t+1, k
j , i =x
t
j , i +(x i , max -x i , min ) N (0, (
σt , k j , i ) 2) . (5) 式中 :k ∈ {α, β}; (σt , k j , i ) 2为高斯变异的方差 , 取值为 (σt , k j , i ) 2=
|αt j , i |2, k =α;
|βt j , i |2/5, k =β.
(6)
由式 (5) 可知 , 当 (σt , k j , i ) 2较大时 , x t+1, k
j , i 可能超出 可行解空间的范围 , 为此作如下处理 :
if x t+1, k
j , i >x i , max ,
t hen x t+1, k
j , i =2x i , max -x t+
1, k
j , i ; (7)
if x t+1, k
j , i
t hen x t+1, k
j , i =2x i , min -x t+
1, k
j , i . (8)
重复式 (7) 或 (8) , 直到使 x t+1, k
j , i 位于可行解空间 . 若由式 (5) 生成的新染色体优于原染色体 , 则 为有效进化 , 此时 αt+1j , i =αt j , i , βt+1j , i =βt j , i ; 否则为无效 进化 , 并由形如式 (2) 的量子旋转门更新 αt j , i 和 βt j , i , 即
t+
j ,
i
βt+1
j , i
=
cos (Δθt j , i ) -sin (Δθt j , i
sin (Δθt j , i ) co s (Δθt j , i )
αt
j , i
βt
j ,
. (9) 式中 Δθt j , i 为量子旋转门的旋转角 , 且 Δθt j , i 设计为
Δθt
j , i =sgn (
αt j , i βt j , i ) θ0exp (t
|αt j , i |+γ
) . (10) 其中 :θ0为初始旋转角 , γ为进化尺度 , θ0和 γ控制旋 转角的大小 , 进而控制算法的收敛速度 ; 符号函数 sgn (? ) 控制旋转角的方向 , 以确保算法收敛 . 若染色体同一基因位连续发生多次无效进化 , 除采用式 (9) 和 (10) 更新 αt j , i 和 βt j , i 外 , 还辅以式 88
第 1期 高 辉等 :实数编码量子进化算法
(11) 以加大 αt
j , i 和
βt j , i 更新的尺度 , 进而达到由算法 的进化状态自适应调整进化过程的目的 .
αt+1j , i =αt+1j , i /(fix (c i /5) +1) ,
βt+1j , i
=-(αt+1j , i ) 2
.
(11)
式中 :fix (?
) 为取整函数 , c i 为第 i 基因位发生连续 无效进化次数 . 由式 (9) ~(11) 可以看出 , |αt j , i |
2
随着进化代数的增加将逐渐减小 , 实现了对当前解
邻域的 “求精” 搜索 ; 而 |βt j , i |2
随着进化代数的增加 而逐渐增加 , 实现了对解空间大范围的 “求泛” 搜 索 , 互补双变异算子即由此而来 . 设 “求精” 搜索和 “ 求泛” 搜索次数分别为 m 1和 m 2, 一般 m 1>m 2.
RCQ EA 每隔一定的进化代数 τ实施离散交叉 , 即对于指定的染色体 p t u , 色体 p t
v
(u ≠ v ) , 以 1/2位 , 生成 2c t t
[x t c, i αt c, i βt c, i ]
T x t u, i u, i t u, i
]T
, r <0.>
[x
t v , i
α
t v , i βt v , i
]T
, r ≥ 0. 5.
(12)
式中 :[x t c, i αt c, i
βt c, i ]T
, [x
t u, i αt u, i βt u, i
]T
和 [x
t v , i αt v , i
βt v , i ]T 分别为染色体 c t 1或 c t 2, p t u 和 p t v 的第 i 基因位 ;
r 为 [0, 1]区间随机数 . 当待求解复杂函数自变量向
量的各分量有较强相关性时 , 离散交叉对于避免陷 入局部极值点非常重要 . 3. 3 算法流程
Step1:参数初始化 .
Step2:群体初始化 . 生成形如式 (4) 的三倍体
染色体群体 P (t ) ={p t j }, j =1, 2, … , N , N 为群体 规模 .
Step3:评价种群 . 对群体中的每个染色体进行
评价 , 选出最优染色体 b t .
Step4:算法停止判断 . 当满足停止条件时 , 输
出最优解 b t , 算法结束 ; 否则 , 继续下一步 .
Step5:进化染色体 .
Step5. 1:“ 求精” 或 “ 求泛” 搜索 .
Step5. 1. 1:对于选定的染色体 , 以等概率随机
选择染色体第 i 基因位 , 由式 (5) 对基因位中表示自 变量向量分量的变量实施高斯变异 , 生成新染色体 .
Step5. 1. 2:对新染色体进行评价 , 并采用 “爬
山” 选择 . 即如果是有效进化 , 则用新染色体替换原 染色体 , 并清除连续无效进化次数 c i ; 否则 , 原染色 体保持不变 , 并累加连续无效进化次数 c i .
Step5. 1. 3:若 “ 求精” 或 “求泛” 搜索次数未达
到设定次数 , 转 Step5. 1. 1; 否则 , 更新 b t , 继续 .
Step5. 2:对于选定的染色体 , 以等概率随机选
择染色体第 i 基因位 , 如果该基因位存在无效变异 , 则由式 (9) ~(11) 更新基因位中的概率幅 .
群体中全部染色体均进行 Step5. 1~Step5. 2操作 .
Step5. 3:离散交叉 . 如果满足交叉条件 , 依适 应值顺序选 k (k ≤ N ) 个优秀个体按式 (12) 分别进 行 m 3次交叉 , 生成新染色体 , 并采用 “爬山” 选择 . 同时 , 清除染色体各基因位连续无效进化次数 , 更新
b t
.
Step6:t =t +1, 转 Step4.
4Q ,M 2[EA 性能 .
min F 1=
∑ D
i =1
x
2i
, (13)
式中 :自变量 x i ∈ [-100, 100], 维数 D =30.
min F 2=-20exp (-0. 2
∑ D
i =1
x 2
i ) -exp (
D
∑
D
i =1
co s (2πx i
) ) +20+e , (14)
式中 :自变量 x i ∈ [-32, 32], 维数 D =30.
min F 3=
4000
∑
D i =1
x 2
i -
∏
D
i =1
co s
()
+1,
(15)
式中 :自变量 x i ∈ [-600, 600], 维数 D =30.
min F 4=10D +
∑
D
i =1
(x 2i -10co s (2
πx i ) ) , (16)
式中 :自变量 x i ∈ [-5. 12, 5. 12], 维数 D =30.
测试函数均在 x =(0, … , 0) 处存在全局最小 值 0.
1) Q EA :群体规模 N =10, 自变量分量均采用 18位二进制数表示 , 则量子染色体长度为 540, θ0=0. 05π, ε=0. 01, 局部迁移间隔为 600代 .
2) M 2ES :μ=1, λ=6, k =2, σ0=2.
3) RCQ EA01:RCQ EA 的群体规模 N =1, 初 始旋转角 θ0=0. 4π, 进化尺度 γ=0. 05, 连续 “求 精” 搜索次数 m 1=6, 连续 “ 求泛” 搜索次数 m 2=2.
4) RCQ EA10:RCQ EA 的群体规模 N =10, 交 叉间隔 τ=500, 选择优秀个体数 k =2, 每个个体连 续交叉次数 m 3=6, 其他参数与 RCQ EA01相同 .
算法均以最大运行代数为终止条件 , 最大终止 代数取为 5000, 各种算法分别独立运行 30次 .
运算结果见表 1. 数据表明 , 尽管 RCQ EA01和 M 2ES 有大致相同的计算复杂度 , 但 RCQ EA01的性
能优于 M 2ES , 原因在于 RCQ EA01使用实数编码三
9
8
控 制 与 决 策 第 23卷
倍体染色体 , 增加了解的多样性 , 并利用量子旋转门
和互补双变异算子进化染色体 , 实现了全局搜索和
局部搜索的平衡 . 而 RCQ EA10的性能又明显优于
RCQ EA01, 原因不仅在于染色体个数的增加 , 更重
要的是使用离散交叉扩大了搜索空间 . 算法 Q EA 则
不适合复杂函数优化问题 . 数据分析表明 ,RCQ EA
求解复杂函数优化问题时表现出更强的全局搜索能
力 、 更好的稳定性和鲁棒性 .
表 1 各种算法求解复杂函数优化问题的统计结果
函数 算 法 平均值 最优值 最劣值 方差值
F 1
Q EA 2. 94891. 80944. 18390. 8861
M 2ES 7. 4e 2123. 5e 2133. 3e 2118. 2e 212
RCQ EA011. 6e 2164. 1e 2201. 3e 2154. 2e 216
RCQ EA104. 4e 2217. 0e 2246e 221
F 2
Q EA 0. 85321. 0.
M 2ES 1. 3. 0e 266. 7e 27
RCQ EA015. 102. 0e 211
1. 4e 294. 4e 210
RCQ EA109. 5e 2121. 5e 2122. 5e 2126. 3e 213
F 3
Q EA 0. 98520. 92161. 04590. 0519
M 2ES 0. 15720. 05630. 37090. 0875
RCQ EA010. 032400. 07620. 0286
RCQ EA100000
F 4
Q EA 45. 5128. 0258. 3011. 7352
M 2ES 0. 09431. 0e 2120. 99500. 2862
RCQ EA015. 2e 245. 6e 2145. 2e 231. 6e 23
RCQ EA102. 8e 21405. 6e 2142. 8e 214
图 2给出了各算法在 30次独立运行中最优值
的平均值随代数变化的情况 , 从求解质量和收敛速
图 2 各种算法求解复杂函数优化问题性能比较
度两个方面再次表明了 RCQ EA 的优良性能 . 一方 面 , 在整个进化过程中 ,RCQ EA01和 RCQ EA10优 于 Q EA 和 M 2ES , 而 RCQ EA10优于 RCQ EA01; 另 一方面 ,RCQ EA01求解 F 1和 F 2时 , 收敛速度优于 Q EA 和 M 2ES , 而求解 F 3和 F 4时 , 与 Q EA 和 M 2ES 一样出现了 “ 早熟” 和 “ 停滞” 现象 , 而 RCQ EA10却 始终保持良好的收敛速度 .
5 结 语
本文提出的实数编码量子进化算法 , 其核心在 , 利 , 加快收敛速度 . 仿真 适合于求解复杂函数优化问题 . RCQ EA 的性能 , 扩大 RCQ EA 的 应用范围则是需要进一步研究和解决的问题 . 参考文献 (R eferences)
[1]Hey T. Quantum computing :An introduction [J ]. Computing and Control Enginerring Journal , 1996, 10 (3) :1052112.
[2]Narayanan A , Moore M. Quantum 2inspired genetic algorithms[C ].Proc of IEEE Int Conf on Evolutionary Computation. Nagoya :IEEE Press , 1996:61266. [3]Han K H , Kim J H. G enetic quantum algorithm and its application to combinatorial optimization problems [C ]. Proc of the 2000IEEE Congress on Evolutionary Computation. Piscataway :IEEE Press , 2000, 7:13542 1360.
[4]Han K H , K im J H. Quantum 2inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Trans on Evolutionary Computation , 2002, 6(6) : 5802593.
[5]Han K H , K im J H. Quantum 2inspired evolutionary algorithms with a new termination criterion , H εgate , and two 2phase scheme[J].IEEE Trans on Evolutionary Computation , 2004, 8(2) :1562169.
[6]Zhang G X , Jin W D , Hu L Z. Quantum evolutionary algorithm for multiobjective optimization problems [C ]. Proc of the 2003IEEE , Int Symposium on Intelligent Control. Houston :IEEE Press , 2003, 10:7032708. [7]王湘中 , 喻寿益 . 适用于高维优化问题的改进进化策略 [J].控制理论与应用 , 2006, 23(1) :1482151.
(Wang Xiang 2zhong , Yu Shou 2yi. Improved evolution strategies for high 2dimensional optimization[J].Control Theory and Applications , 2006, 23(1) :1482151. ) 09
范文三：量子多目标进化算法基本框架
The Procedure of the QMOEAs’ Basic Framework Begin
t ← 0
i) Initialize Q (t )
ii) A (t ) ={ }, C (t ) = { }
iii) While (not termination condition) do
t ← t +1
iv) Make P(t) by observing the state of Q(t-1) v) Evolve P (t )
vi) Make C (t ) = Mf ( P (t ) U C (t -1), ≤ )
\\ Normally this step is eliminated.
vii) Rebuild the archive set A (t)
\\ Here A(t) ? Mf( P(t) U A(t-1), ≤ ) and maximize \\ the diversity of those chosen elements in A(t). viii) Make Q (t ) by updating Q (t -1) on Q-gates. End
End
范文四：量子进化算法研究现状综述
第 26卷 第 3期 V ol. 26No. 3
控 制 与 决 策
Control and Decision
2011年 3月 Mar. 2011
量 子 进 化 算 法 研 究 现 状 综 述
文章编号 :1001-0920(2011)03-0321-06
钱 洁 , 郑建国 , 张超群 , 王 翔 , 阎瑞霞
(东华大学 旭日工商管理学院,上海 200051)
摘 要 :在介绍基本量子进化算法 (QEA)的基础上 , 重点归纳总结了最近几年量子进化算法在算法机理和性能方面 以及在算法的种群改进、 编码扩展、 算子创新、 算法融合等应用方面的研究成果 , 进而提出了量子进化算法在模式理 论、 多目标进化、 算法研究、 应用等方面进一步的研究内容 .
关键词 :量子进化算法;量子计算;进化计算
中图分类号 :TP301文献标识码 :A
Reviews of current studying progress on quantum evolutionary computation
QIAN Jie , ZHENG Jian-guo , ZHANG Chao-qun , WANG Xiang , YAN Rui-xia
(GloriousSun School of Business and Management , Donghua University , Shanghai 200051, China . Correspondent: QIAN Jie , E-mail :qj@mail.dhu.edu.cn)
Abstract :By introducing basic theory of quantum-inspired evolutionary algorithm(QEA),this paper makes a summary on the research of QEA with performance and mechanism, the population improvement, representation extension, operator innovation, integration with other algorithms and its application. Hence several contents of further study of QEA in the aspects of application, algorithm studying, multi-objective evolutionary, and pattern theory, are proposed.
Key words :quantum-inspired evolutionary algorithm ; quantum computing ; evolutionary computation
1引 言
Narayanan 等人 [1]于 1996年首次将量子理论与 进化算法相结合 , 提出了量子遗传算法 (QIGA)的概 念 ; 2000年 , Han 等 人 [2]提 出 了 一 种 遗 传 量 子 算 法 (GQA),然后又扩展为量子进化算法 (QEA)[3], 实现 了组合优化问题的求解 . 该算法用量子位编码表示 染色体 , 用量子门更新完成进化搜索 , 具有种群规模 小、 收敛速度快和全局寻优能力强的特点 . 目前 , 量子 进化算法的研究已经取得一些成果 , 文献 [4]总结了 量子进化算法的研究进展 , 该文主要基于 2006年以 前的文献 . 最近几年又相继出现了许多相关重要研究 成果 , 所以本文旨在归纳总结关于量子进化算法在最 近几年国内外具有代表性的研究成果 , 并指出进一步 的研究方向 .
本文首先给出 QEA 的简要概述 ; 然后分类总结 了 QEA 近年来的研究领域以及所取得的成果 ; 最后 指出了进一步的研究方向 . 2量 子 进 化 算 法 概 述
Han 等人 [3]提出的 QEA 采用量子比特编码 , 一个 量子比特表示为 ∣ ψ? =α∣ 0? +β∣ 1? , α和 β为复数 . 在 第 t代的染色体种群为
Q(t) ={qt1, qt2, ? ? ? , qtn}.
其中 :n为种群大小 ; t为进化代数 ; qtj为染色体 , 即 qtj=
[
αj1αj2? ? ? αjm
βj1βj2? ? ? βjm
]
, j=1, 2, ? ? ? , n.(1)式中 :m表示染色体长度 , 满足 ∣ αji∣ 2+∣ βji∣ 2=1. 算 法流程描述如下 :
Begin
1) t=0, 初始化种群 Q(0), 所有 q0j(j=1, 2, ? ? ? , n) 中的 α0jβ0j都被初始化为 (1/
√
, 1/
√
.
2) 对初始种群中的各个体实施测量 , 得到一组状 态 P(0)={x01, x02, ? ? ? , x0n}. x0j(j=1, 2, ? ? ? , n) 是长 度为 m的串 , 每一位 x0ji(i=1, 2, ? ? ? , m) 为 0或 1, 是
收稿日期 :2010-07-17; 修回日期 :2010-09-10.
基金项目 :国家自然科学基金项目 (70971020/G010301).
作者简介 :钱洁 (1974? ), 男 , 副教授 , 博士生 , 从事进化计算的研究;郑建国 (1962? ), 男 , 教授 , 博士生导师 , 从事智能计 算、 数据挖掘等研究 .
根据量子比特的概率 ∣ α0ji∣ 2或 ∣ β0ji∣ 2测量得到的 . 测量 过程为 :随机产生一个数 r,r∈ [0, 1]. 若 r>∣ α0ji∣ 2, 则 测量结果 x0ji=1; 否则 , 取 0.
3) 对各状态 f(x0j) 进行适应度评价 .
4) 记录下最佳个体状态 B0及其适应度值 f(B0) .
5) While 非结束状态 do
Begin
① t=t+1;
② 对种群 Q(t? 1) 实施测量 , 得到一组状态 P(t) ; ③ 对各状态进行 f(xtj) 适应度评价 ;
④ 利用量子门 U(t) 更新 Q(t) ;
⑤ 保存 B(t? 1) 和 P(t) 中的最佳解到 B(t) ; ⑥ 记录下 B(t) 中最佳个体状态 b
End
End
3主 要 研 究 成 果
QEA 算法具有种群分散性好、 全局搜索能力 强、 收敛速度快且易于与其他算法融合等优点 . 近几 年 , 国内外许多重要文献对 QEA 算法进行了更进一 步的研究 , 主要体现在以下几方面 .
3.1算 法 机 理 及 性 能 研 究
这类研究大多从分析 QEA 算法的运行机理入 手 , 类比分析 QEA 与其他经典进化算法的区别和相 似性 . 具有代表性的有 Ming 等人 [5]从概率角度分析 QEA, 从量子的 “ 波粒二向性 ” 分析量子在进化过程中 的特点 , 将传统遗传算法 (GA)和 QEA 借助 “ 波粒二 向性 ” 特征进行了类比 , 如表 1所示 .
表 1QEA , GA 波粒二向性类比
遗传算法 GA 量子进化算法 QEA
由一系列个体组成进化种群 由一系列量子组成概率系统 平均个体适应度值 能量
种群选择压力与多样性的竞争 熵与能量之间的竞争
种群汇聚 自由能量降低
最优解 从不平衡状态到平衡状态
从表 1可以看出 :QEA 的进化与 GA 的进化在本 质上具有相似性 , QEA 的种群是由量子组成的概率系 统 , 其个体适应度评价为量子的能量 , 进化过程是量 子的熵和能量的一种竞争 , 最终求得最优解时量子熵 降低 , 种群趋于聚集 , 进化过程是种群从一种不平衡 状态到平衡状态的转变 . QEA 进化的本质是种群的量 子从处于不确定状态到最终确定状态的过程 , 量子被 检测到为 0或者 1的概率趋于确定 , 其熵值也趋于最 小 . 另外 , 文献 [6]利用量子的纠缠态理论解释说明了 遗传算法的本质 , 认为遗传算法计算在本质上是一种 量子并行计算 . Micha¨e l [7]和 Zhou 等人 [8]都从分布式 估计算法 (EDA)的角度分析了量子进化算法 , 认为两 种算法共同特征是利用概率模型进行演算 , 并从概率 模型、 抽样选择、 学习替换和种群结构等方面进行了 类比 , 得出了 QEA 的实质是一种 EDA 的结论 .
通过图 1的比较可以看出 :EDA 通过个体分布建 立概率模型 , 并利用该概率模型进行样本采样以产生 新种群 ; 而在 QEA 中 , 则通过对量子比特的概率幅测 量、 坍缩的方法产生新种群 , 坍缩的方法与 EDA 样本 采样相对应 , 它能使种群向更高适应度方向进化 . 从 实验分析得出 , QEA 相对 EDA 更具有优势 , 主要体现 在以下两方面 :一是量子编码样本具有多样性 ; 二是 其概率模型具有自适应性调节能力 . 另外 , KaiFan 等 人 [9]对 QEA 算法的特性进行了分析 , 对比了 QEA 与 经典遗传算法、 粒子群算法在解决静态、 动态函数 优化问题的性能差别 , 并分别测试了二进制、 十进制 编码情况下这几种算法对低维、 高维函数的优化效 果 . 结果表明 :在静态环境下 , QEA 求解结果和运行时 间都优于其他几种算法 ; 在动态环境 , QEA 稳定性更 好 , 且运行时间更少 , 改进的 QEA 算法更适合动态环 境下高维实空间问题 .
(a)EDA (b)QEA 图 1QEA 与 EDA 进化方式比较
3.2种 群 改 进
量子比特编码能用较小的种群规模表示问题的 多个解 , 所以种群的规模、 结构等对算法性能影响较 大 . 此类研究主要可归纳为如下几方面 :
1) 种群结构的改进 . Najaran 等人 [10]将 QEA 的 种群结构进行了分类 . 按图 2所示可分为 :环型、 网 格型、 二叉树型、 簇型、 方格型、 Km,n型、 阶梯型和 交叉阶梯型等 . 文献 [10]利用测试函数寻优对比分 析了不同种群结构算法的性能 , 结果表明网格型 为 QEA 性能最好的种群结构 . Alba 等人 [11]将网格型 的种群结构细分为正方形、 长方形、 长条形等 , 设 计了根据个体的适应度值和群体的熵来动态调节 群体结构的 QEA, 这种算法能很好地兼顾勘探和 开采能力 . Ali Nodehi 等人 [12]提出了基于网格结构 的 QEA, 在这种结构中每个节点表示一个个体 , 这种 结构能保持种群的多样性 , 可有效避免早熟和陷入局 部极值 . 另外 , Guo 等人 [13]利用复杂网络理论类比量 子进化中的各个个体间关系 , 复杂网络中小世界原理 为量子进化个体间关系提供了一种借鉴 , 为达到这种
种群弱链接 , 算法将种群分解成局部小群 , 各小群进 行局部进化 , 这种种群结构能有效避免算法早熟
.
(a) (b) ( )
c (d) (e) (f)K m n ,
(g) (h)
图 2种群结构分类
2) 种群大小的改进 . Ali Nodehi 等人 [12]利用函数 动态改变 QEA 种群大小 , 当种群增加时 , 随机新加 入的种群改善了种群的多样性 ; 当种群减少时 , 去 掉种群中比较差的个体 , 可以缩小搜索范围 , 加快 算法的收敛 . Tayarani 等人 [14]利用环形作为种群结 构 , 以保证每个个体只与 2个邻居相邻 , 并在进化过 程中使用正旋函数改变种群大小 , 以保持种群多样
性 . Imabeppu 等人 [15]在粗粒度并行量子遗传算法的 基础上 , 针对种群间个体迁移的方式 , 提出一种成对 交换的算法 , 该算法与局部、 全局优秀个体迁移不同 , 它在所有种群个体中只选择 n/2对个体进行交换 . 对 0-1问题的求解证明了所提出的算法具有局部搜索和 全局搜索的优势 . 3.3编 码 扩 展
QEA 算法设计之初为量子比特编码 , 在进化中 测量产生二进制串 , 所以算法对多参数和高维问题的 求解受到了限制 . QEA 编码的扩展成为研究的热点 , 一些具有代表性的改进可归纳如下 :
1) 概率实数编码 . Cruz 等人 [16]定义了一种实数 编码方式的 QEA, 该思想是将个体中每个分量用 gij
=(pij, oij) 表示取值空间 , 它表示为一矩形区域 , 其
中 pij表示变量取值的坐标中心 , oij为矩形取值空间 的宽度 , 矩形的高度为 ? ij=1/(oij/N) , N为变量个 数 , 个体表示为 qi={gi1, gi2, ? ? ? , gig}. 该编码利用高 度表示概率 , 例如表 2表示的是两个体 q1, q2的初始 值 . 图 3表示了表 2中两个体 q1和 q2的概率实数编 码 . 图 3中 , 个体 q1由中心为 ? 5, 宽度为 20的 g11矩 形框及中心为 0, 宽度为 20的 g12矩形框组成 . 图 4表 示两个体 q1和 q2进行交叉的结果 . 从图 4可以看出 ,
当 2个个体进行交叉时 , 是将 q1和 q2分别代表的矩形 区域进行叠加来产生新的个体 , 叠加后的矩形框高度 表示在该区域取值的概率 . 用这种方式编码的量子进 化算法 , 对高维函数优化测试结果显示具有更好的收 敛速度和寻优精度 . 覃朝勇等人 [17]在此基础上引入了 势能的概念 , 并用于高维函数优化 , 也取得了较好的 性能 .
表 2
概率实数编码示例
个体
编 码
q1g11=(? 5, 20) , g12=(0, 20) q2
g21=(5, 20) , g22=(5,
20)
(a) q g 111(b) q g 1
12(b)
q g 222( )
q g 221c
图 3
q1, q2概率实数编码
-20020(a)q q g 121,
(b)q q g 122,
0.10
0.0400.080.060.02
图 4
q1, q2交叉
2) 三倍 体 编 码 . Li 等人 [18]提 出了 一种 量 子位 Bloch 球面坐标编码 . 图 5表示 Bloch 球中的一个点对 应一个量子比特 , 因此量子比特 ∣ ψ? 可描述为
∣ ψ? =[cos?sin θsin ?sin θcos θ]T .
按照这种方式 , 将量子位的 3个 Bloch 球面坐标作为 基因位 , 则可将量子比特编码转换为 Bloch 球面编码 , 表示如下 :
pi=
cos ?i1sin θi1sin ?i1sin θi1
cos θ
i1
...
cos ?insin θinsin ?insin θincos θ
in
. (2)
这种编码能够避免因对量子位测量产生二进制串所 带来的随机性 , 可用于连续优化问题 , 能够扩展全局 最优解的数量 , 提高获得全局最优解的概率 . 另外 , 高 辉等人 [19]提出了一种三倍体实数编码 , 即
pj=? ? ?
xj1xj2? ? ? xjnαj1αj2? ? ? αjnβj1βj1? ? ? βjn
? ?
? .
(3)
该编码由自变量的一个分量与量子比特组成 , 算法设 计了互补双变异算子来进化个体 . 这种算子融合了量 子旋转门和量子比特归一化条件 , 实现了局部搜索与 全局搜索的平衡 .
y
图 5Bloch 球面坐标表示量子比特
3) 混合二倍体编码 . Zhao 等人 [20]采用改进的二 倍体编码形式 , 即
p(t) ={x1x2? ? ? xnθ1θ2? ? ? θn}
θi=arcsin
(xi
? a) , (4)其中 x∈ [a,b]为定义域区间 , 是实数 . 该文利用这种 编码提出了一种基于 QEA 的模糊神经网络模型 . 另 外 , 申抒含等人 [21]提出一种多进制概率角复合位编 码 QEA, 将量子位的概率幅表示法转化为复合位的概 率角表示法 , 采用随机观测方法得到观测个体 , 采用 概率角增减的方式对个体进行更新 . 其编码形式为
pi={φ11φ12? ? ? φ1i
φ21φ22? ? ? φ2i}φ1i+φ2i=90, (5)
其中 0<><90. 该算法适用于采用任意进制编="" 码问题="" .="" 实验表明="" ,="" 算法在适用范围、="" 搜索能力和运算="" 速度上均具有较为明显的优势="" .="" 3.4算="" 子="" 创="">
基本 QEA 与一般进化计算不同 , 没有选择、 交 叉、 变异等算子 , 所以修改并提出新算子融入 QEA 中 便成为研究方向 , 具有代表性的有 :
1) 粒子群算子 . Wang [22]和周殊等人 [23]采用粒子 群优化算子调节量子旋转门 , 并根据 QEA 自身概率 特性 , 引入了最优解方差函数来评价该算法的稳定性 能 .
2) 免疫算子 . Hongjian 等人 [24]将免疫的概念引 入 QEA, 免疫算子在保留原算法优良特性的前提 下 , 力图有选择、 有目的地利用待求问题中的一些特 征信息或先验知识 , 抑制或避免求解过程中的一些重 复或无效的工作 , 以提高算法的整体性能 . Haoteng 等 人 [25]提出了基于混沌理论的免疫 QEA, 该算法应用 混沌免疫理论并依据小生境机制将初始个体划分为 实数编码染色体的子群 , 各子群应用免疫算子的局域 搜索能力找出优化解 .
3) 克隆算子 . 李阳阳等人 [26]提出一种基于量子 编码的免疫克隆算法来求解 SAT 问题 , 算法中采用量 子位的编码方式表达种群中的抗体 , 采用量子旋转门 和动态调整旋转角策略对抗体进行演化 , 加速原有克 隆算子的收敛 , 利用克隆算子的局部寻优能力强的特 点 , 在各个子群体间采用量子交叉操作来增强信息交 流 , 以提高种群的多样性 , 防止早熟 .
4) 模拟退火、 模糊算子 . 王毅等人 [27]借鉴模拟 退火算法 , 根据进化代数及个体的适应度值修正传 统 QEA 旋转门函数的旋转角度值 . 焦嵩鸣等人 [28]利 用模糊推理的方法 , 自适应地改变旋转角的大小 , 该
方法有效地提高了算法的计算精度和收敛速度 .
5) 文化算子 . Cruz 等人 [29]在 QEA 中引入了文化 算子 , 该思想借鉴了文化算法中规范知识的概念 , 用 以描述当代种群的有效搜索空间范围 , 规范知识可以 规避不在该范围内个体 , 引导个体进入有效区域搜 索 , 算法收敛速度和精度都得到了提高 .
6) 其他算子 . AraujoM 等人 [30]利用多目标优化对 量子进化中的旋转角参数进行计算 , 算法分 2个层次 , 上层为求解多个测试函数的旋转角和旋转方向参 数 , 将得到的参数用于底层的量子进化优化过程 . Xing 等人 [31]利用两点交叉算子对量子旋转门调整进 行改进 , 其核心思想是确保在任何状态下以较大的概 率使当前解收敛到一个具有更高适应度的染色体 . 3.5
算 法 融 合
在最优化理论中有 “ 无免费午餐定理 ”(NFLT)之 说 . 因此 , 不同进化算法的融合以解决不同优化问 题成为研究方向 . 此类研究主要将传统进化算法与 QEA 结合 , 主要有 :
1) 融合群智能算法 . Md Amjad 等人 [32]将粒子群 优化 (PSO)嵌入到 QEA 中 , 用量子比特表示一粒子和 粒子的位置 , 测试显示该改进加快了算法的聚集速 度 . 李盼池等人 [33]提出了求解连续空间优化问题的量 子蚁群算法 , 每只蚂蚁携带一组表示蚂蚁当前位置信 息的量子比特 , 采用量子旋转门更新蚂蚁携带的量子 比特 , 该算法可使搜索空间加倍 , 搜寻效率更高 .
2) 融合差分进化 . Wang 等人 [34]将差分进化的思 想借鉴到量子算法中 , 差分擅长局域搜索 , 量子进化 擅长全局搜索 , 这种结合可使算法搜索更高效 .
3) 融合膜计算 . Zhang 等人 [35]利用生物细胞中 抽象出来的计算模型 -P 系统来构造并行量子进化计 算 , 并用于求解组合优化问题 , 与常见的几种 QEA 算 法相比具有一定优势 .
4) 融合多智能体协同进化 . Zhao 等人 [36]提出了 多 agent 的 QEA, 算法定义了 agent 的进化、 比较、 全
局变异等算子 , 这种进化机制可使多个种群协同进 化 . 覃朝勇等人 [37]提出了多智能体协同 QEA, 一个智 能体代表优化问题的一个可能解 , 智能体之间通过量 子进化实现竞争及学习 , 以提高个体的竞争能力 . 另外 , 许多学者将 QEA 与其他 (比如混沌优化、 分布式估计、 进化策略、 遗传算法、 克隆免疫等 ) 智能 算法进行了融合 , 限于篇幅 , 在此不再赘述 .
3.6典 型 应 用
鉴于 QEA 的若干优越性 , QEA 目前已在诸多领 域得到应用 . 一些具有代表性的应用归纳如下 :
1) 神经网络优化 . Maojun Cao 等人 [38]将量子进 化用于神经网络训练学习 , 训练误差、 收敛速度等 方 面 比 BP 神 经 网 络 的 性 能 都 有 改 善 . De Pinho 等 人 [39]利用二进制 -十进制混合编码训练神经网络 , 以 解决信用分类问题 .
2) 经济、 生产管理、 工程问题 . KaiFan 等人 [9]利 用实数编码的 QEA 克服股票预测中的关键问题 , 取 得了比其他算法好的效果 . Mani 等人 [40]将一种可自 适应的 QEA 应用于陶瓷研磨优化问题 , 取得了较好 效果 ; Zhang 等人 [41]将基于 QEA 的小波支持向量机 (SVM)应用于城市交通人口流量预测 ; Vlachogiannis 等人 [42]利用初始值设置优化 QEA, 缩小了搜索空间 , 并成功地应用于电力控制系统 ; Zheng 等人 [43]将 QEA 应用于排课复杂问题的求解 .
3) 在信息系统中的应用 . Xing 等人 [44]利用多种 群 QEA 解决了在 WDM 网络中的 QoS 多播路由问题 ; Liu 等人 [45]提出了一种基于 QEA 的 web 服务用户感 知 QOS 算法 ; Hsiung 等人 [46]提出了基于 QEA 的符号 控制器 , 并应用于嵌入式系统 , 取得了较好效果 . 近几年 , QEA 在许多研究领域得到应用 , 限于篇 幅 , 在此不再赘述 .
4进 一 步 研 究 方 向 及 内 容
QEA 已成为目前计算智能领域的研究热点之 一 , 归纳起来 , 以下几方面的工作尤其值得进一步探 讨 :
1) 模式理论研究 . 对于量子在进化中的行为、 运 行机理的研究是模式研究的重点 . 另外 , 描述量子进 化计算的规律、 算法性能、 收敛性以及复杂性分析也 有待进一步研究 .
2) 算法研究 . QEA 综合了量子计算与进化计 算 , 因此可进一步吸取量子计算的研究成果 , 充分利 用量子比特的特点探索具有真正量子并行性的进化 计算 . 另外 , 将已有的智能计算取得的研究成果更好 地融入到 QEA 中 , 以提高算法的性能 , 开发更为有效 且更具普适性的混合 QEA.
3) 多目标优化研究 . 目前 , 多目标进化是进化计 算的研究热点 , 尤其处理高维多目标优化是一个难 题 , 所以研究基于 QEA 的高维多目标优化算法具有 重要意义 .
4) 应用研究 . 注重在一些尚未涉及到的领域的应 用研究 , 尤其在高维函数、 离散、 多目标、 强约束、 不 确定等优化问题上的应用 .
总之 , QEA 随着量子计算及智能计算技术的发 展 , 许多新的理论、 新的应用将被引入 , 其前景值得学 者关注 .
参考文献 (References )
[1]Narayanan A, Moore M. Quantum inspired genetic algorithms[C].Proc of IEEE Int Conf on Evolutionary Computation. Nagoya, 1996:61-66.
[2]Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]. Proc of the Congress on Evolutionary Computation. LaJolla, 2000:112-117.
[3]Han K H, Park K H, Lee C H. Parallel quantum inspired genetic algorithm for combinatorial optimization problem[J].IEEE Trans on Evolutionary Computation, 2001, 5(1):1422-1429.
[4]王凌 . 量子进化算法研究进展 [J].控制与决策 , 2008, 23(12):1321-1326.
(WangL. Advances in quantum-inspired evolutionary algorithms[J].Control and Decision, 2008, 23(12):1321-1326.)
[5]Ming Wei Y L D J. A new evolutionary algorithm based on quantum statistical mechanics[C].IEEE Congress on Evolutionary Computation. Aussois, 2008:1722-1777. [6]Wang P. Explaining the implicit parallelism of genetic algorithm and computational complexity by quantum theory[C].Int Symposium on Computer Science. New York, 2008:463-467.
[7]Michael Platel. Quantum inspired evolutionary algorithm a multimodel EDA[J].IEEETrans on Evolutionary Computation, 2009,13(6):1218-1231.
[8]Zhou S, Sun Z. A new approach EDA:Quantum inspired genetic algorithm with only one chromosome[J].Advances in Natural Computation, 2005, 3612(6):141-150.
[9]Fan K, Brabazon A. Quantum inspired evolutionary algorithms for ?nancial data analysis[C].Proc of the Conf on Evolutionary Computing. Tehran, 2008:133-143. [10]Najaran T, Akbarzadeh M. Improvement of quantum evolutionary algorithm with functional sized population[J]. Applications of Soft Computing, 2009, 46(2):389-398.
[11]Alba E, Dorron B. The exploration exploitation tradeoff in dynamic cellular genetic algorithms[J].IEEE Trans on Evolutionary Computation, 2005, 9(2):126-142.
[12]Ali Nodehi M T F M. A novel functional sized population quantum evolutionary algorithm for fractal image compression[C].Proc of the 14th Int CSI Computer Conf. Tehran, 2009:564-568.
[13]Guo J, Sun L, Wang R. An improved quantum genetic algorithm[J].Genetic and Evolutionary Computing, 2009, 10(1):14-18.
[14]Tayarani N Akbarzadeh. A sinusoid size ring structure quantum evolutionary algorithm[C].IEEE Conf on Cybernetics and Intelligent Systems. Chengdu, 2008: 1165-1169.
[15]Imabeppu T, Nakayama S, Ono S. A study on a quantum-inspired evolutionary algorithm based on pair swap[J]. Arti?cial Life and Robotics, 2008, 12(1):148-152. [16]Andr éCruz Vargas. Quantum evolutionary algorithm for numerical optimization[J].Studies in Computational Intelligence, 2008, 121(7):115-132.
[17]覃朝勇 , 郑建国 . 一种实数编码量子进化算法及其收敛 性 [J].控制与决策 , 2009, 24(6):56-60.
(QinC Y , Zheng J G. Real coded quantum inspired evolutionary algorithm and its convergence[J].Control and Decision, 2009, 24(6):56-60.)
[18]Li P, Li S. Quantum-inspired evolutionary algorithm for continuous space optimization based on Bloch coordinates of qubits[J].Neurocomputing, 2008, 72(1/2/3):581-591. [19]高辉 , 徐光辉 , 张锐 , 等 . 实数编码量子进化算法 [J].控制 与决策 , 2008, 23(1):87-90.
(GaoH, Xu G H, Zhang R, et al. Real coded quantum evolutionary algorithm[J].Control and Decision, 2008, 23(1):87-90.)
[20]Zhao S, Xu G, Tao T. Real-coded chaotic quantum-inspired genetic algorithm for training of fuzzy neural networks[J].Computers Mathematics with Applications, 2009, 57(11/12):2009-2015.
[21]申抒含 , 金炜东 . 多进制概率角复合位编码量子进化算 法 [J].模式识别与人工智能 , 2005, 18(6):657-663. (ShenS H, Jin W D. Multinary compound states of probability angel coded quantum inspired evolutionary algorithm[J].Pattern Recognition and Arti?cial Intelligence, 2005, 18(6):657-663.)
[22]Wang Y , Feng X Y , Huang Y X, et al. A novel quantum swarm evolutionary algorithm and its applications[J]. Neurocomputing, 2007, 70(4/5/6):633-640.
[23]周殊 , 潘炜 . 一种基于粒子群优化方法的改进量子遗传 算法及应用 [J].电子学报 , 2006, 34(5):897-901.
(ZhouS, Pan W. A Novel quantum genetic algorithm based on particle swarm optimization method and its
application[J].Acta Electronica Sinica, 2006, 34(5):897-901.)
[24]Hongjian Q, Fangzhao Z. An application of new quantum inspired immune evolutionary algorithm[C].20091st Int Workshop on Database Technology and Applications. Bruges, 2009:468-471.
[25]Haoteng B Y . A new mutative scale chaos optimization quantum genetic algorithm[C].Chinese Control and Decision Conf. Yantai, 2008:1547-1549.
[26]李阳阳 , 焦李成 . 求解 SAT 问题的量子免疫克隆算法 [J].计算机学报 , 2007, 30(2):176-183.
(LiY Y , Jiao L C. Quantum-inspired immune clonal algorithm for SAT problem[J].Chinese J of Computers, 2007, 30(2):176-183.)
[27]王毅 , 牛奕龙 , 齐华 . 三维医学图像分割的改进量子进化 搜索算法 [J].系统仿真学报 , 2008, 20(11):2942-2945. (WangY , Niu Y L, Qi H. Improved quantum inspired evolutionary algorithm for 3D medical images segmentation[J].J of System Simulation, 2008, 20(11): 2942-2945.)
[28]焦嵩鸣 , 韩璞 , 黄宇 . 模糊量子遗传算法及其在热工过程 模型辨识中的应用 [J].中国电机工程学报 , 2007, 27(5): 87-92.
(JiaoS M, Han P, Huang Y . Fuzzy quantum genetic algorithm and its application research in thermal process identi?cation[J].Proc of the Chinese Society for Electrical Engineering, 2007, 27(5):87-92.)
[29]Da Cruz A, Pacheco M, Vellasco M. Cultural operators for a quantum-inspired evolutionary algorithm applied to numerical optimization problems[J].Arti?cial Intelligence and Knowledge Engineering Applications, 2005, 356(2): 1-10.
[30]Araujo M, Nedjah N, de Macedo Mourelle L. Quantum-inspired evolutionary state assignment for synchronous ?nite state machines[J].J of Universal Computer Science, 2008, 14(15):2532-2548.
[31]Xing Z, Duan H, Xu C. An improved quantum evolutionary algorithm with 2-crossovers[J].Advances in Neural Networks-ISNN, 2009, 5551(9):735-744.
[32]Md Amjad. Hybrid real coded quantum evolutionary algorithm based on particle swarm[C].Proc of 12th Int Conf on Computer and Information Technology. Dhaka, 2009:13-17.
[33]李盼池 , 李士勇 . 求解连续空间优化问题的量子蚁群算 法 [J].控制理论与应用 , 2008, 25(2):237-241.
(LiP C, LI S Y . Quantum ant colony algorithm for continuous space optimization[J].Control Theory and Applications, 2008, 25(2):237-241.)
(下转第 331页 )
范文五：量子进化算法背包问题 程序
clear all;
clc;
format long;
c = [220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 56 50 30 20 15 10 8 5 3 1]
w = [80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1]
NUM = 200;
DEM = 50;
fitnessbest=0;
%%
for i=1:NUM
for j=1:DEM
a(i,j)=1/sqrt(2.0);
b(i,j)=1/sqrt(2.0);
end
end
%%
for i=1:NUM
for j=1:DEM
random=rand(1);
if random>(a(i,j)*a(i,j))
x(i,j)=1;
else
x(i,j)=0;
end
end
end
%%
for i=1:NUM
fittemp(i)=0;
weight(i)=0;
for j=1:DEM
fittemp(i)=fittemp(i)+c(j)*x(i,j);
weight(i)=weight(i)+w(j)*x(i,j);
end
if weight(i)<>
fitness(i)=fittemp(i);
else
fitness(i)=0;
end
end
%%
for i=1:NUM
if fitness(i)>fitnessbest
for j=1:DEM
xbest(j)=x(i,j);
end
end
end
%%
k=1;
while k<>
for i=1:NUM %observation Q(t) and obtain P(t) for j=1:DEM
random=rand(1);
if random>(a(i,j)*a(i,j))
x(i,j)=1;
else
x(i,j)=0;
end
end
end
for i=1:NUM %Evaluate P(t) according to fitness fittemp(i)=0;
weight(i)=0;
for j=1:DEM
fittemp(i)=fittemp(i)+c(j)*x(i,j);
weight(i)=weight(i)+w(j)*x(i,j);
end
if weight(i)<>
fitness(i)=fittemp(i);
else
fitness(i)=0;
end
end
for i=1:NUM %Update Q(t) according to Q-Gate for j=1:DEM
angletemp=angle(x(i,j),xbest(j),fitness(i),fitnessbest,a(i),b(j)); a(i,j)=a(i,j)*cos(angletemp)-b(i,j)*sin(angletemp);
b(i,j)=a(i,j)*sin(angletemp)+b(i,j)*cos(angletemp);
end
end
%%
for i=1:NUM
if fitness(i)>fitnessbest
fitnessbest=fitness(i);
for j=1:DEM
xbest(j)=x(i,j);
end
end
end
fitnessbestout(k)=fitnessbest;
k=k+1;
end
disp('*************************************************************') disp('函数的全局最优位置为:')
Solution=fitnessbest
disp('最后得到的优化极值为:')
Result=xbest
%%
x=1:200;
plot(x,fitnessbestout);
disp('*************************************************************')
function result=angle(x,xbest,fitness,fitnessbest,a,b)
if (x==0)&&(xbest==0)
theta=0;
elseif (x==0)&&(xbest==1)&&(fitness<>
theta=0;
elseif(x==0)&&(xbest==1)&&(fitness>=fitnessbest)&&(a*b>0) theta=-0.05*pi;
elseif(x==0)&&(xbest==1)&&(fitness>=fitnessbest)&&(a*b<0) theta="">
elseif(x==0)&&(xbest==1)&&(fitness>=fitnessbest)&&(a==0) theta=-0.05*pi;
elseif(x==0)&&(xbest==1)&&(fitness>=fitnessbest)&&(b==0) theta=0;
elseif(x==1)&&(xbest==0)&&(fitness elseif(x==1)&&(xbest==0)&&(fitness<><0) theta=""> elseif(x==1)&&(xbest==0)&&(fitness elseif(x==1)&&(xbest==0)&&(fitness elseif(x==1)&&(xbest==0)&&(fitness>=fitnessbest)&&(a*b>0) theta=0.025*pi; elseif(x==1)&&(xbest==0)&&(fitness>=fitnessbest)&&(a*b<0) theta=""> elseif(x==1)&&(xbest==0)&&(fitness>=fitnessbest)&&(a==0) theta=0; elseif(x==1)&&(xbest==0)&&(fitness>=fitnessbest)&&(b==0) theta=-0.025*pi; elseif(x==1)&&(xbest==1)&&(fitness elseif(x==1)&&(xbest==1)&&(fitness<><0) theta=""> elseif(x==1)&&(xbest==1)&&(fitness elseif(x==1)&&(xbest==1)&&(fitness elseif(x==1)&&(xbest==1)&&(fitness>=fitnessbest)&&(a*b>0) theta=0.025*pi; elseif(x==1)&&(xbest==1)&&(fitness>=fitnessbest)&&(a*b<0) theta=""> elseif(x==1)&&(xbest==1)&&(fitness>=fitnessbest)&&(a==0) theta=0; elseif(x==1)&&(xbest==1)&&(fitness>=fitnessbest)&&(b==0) theta=-0.025*pi; else theta=0; end result=theta;
