二进制蚁群进化算法
第33卷第3期自动化学报Vol.33,No.3 2007年3月ACTA AUTOMATICA SINICA March,2007
二进制蚁群进化算法
熊伟清1魏平1
摘要从生物进化角度将群体中的每只昆虫看成一个神经元，彼此之间通过随机、松散的连接组成一个神经网络；然后类似于人工神经网络模拟蚂蚁群体智能,提出了一个二元网络.由于采用二进制编码对单个蚂蚁的智能行为要求比较低，对应的存储空间相对较少，使得算法的效率有较大的提高.通过测试函数优化和多维0/1背包问题结果表明该算法具有较好的收敛速度和稳定性，非常好的求解结果.
关键词群体智能，模拟进化算法，二元网络，蚁群算法，遗传算法
中图分类号TP18
Binary Ant Colony Evolutionary Algorithm
XIONG Wei-Qing1WEI Ping1
Abstract Every insect is considered,from the viewpoint of biological evolution,to be a neural cell that constitutes a neural network in a casual and loose way of joint.Through simulating the ant swarm intelligence on the basis of human neural network,this paper advances a linear binary network.The binary code expects a low intelligence of each ant,and each path corresponds to a comparatively small storage space,thus considerably improving the e?ciency of computation. The test of function optimization and multi-dimensional0/1Knapsack proves that the computation has a good speed of convergence,a high stability and a perfect solution.
Key words Swarm intelligence,simulated evolution computation,binary network,ant colony algorithm,genetic algo-rithm.
1引言
蚁群优化算法是20世纪90年代提出的一种新型的模拟进化算法，它是由意大利学者Dorigo M 等人首先提出的[1,2],并应用于求解TSP问题、分配问题、Job-Shop调度问题等，取得了较好的结果.近几年在欧、美召开的有关会议上，蚁群优化算法已成为研究热点之一.
Holland的复杂自适应系统理论认为[3,4]：诸如人脑、免疫系统、生命系统、细胞、蚂蚁群以及人类社会中的政党、组织等都是并行相互作用的agent 组成的网络.从生物进化角度将群体中的每只昆虫看成一个神经元，彼此之间通过随机、松散的(软)的连接组成一个神经网络；然后类似于人工神经网络模拟人类大脑，“松散”的神经网络来模拟昆虫的群体行为.群居昆虫的集体，常表现出“智能”的行为如蜜蜂筑巢、蚂蚁觅食等.这种行为像一个预先设计并在总指挥监督下协同进行的过程，整个群体像一个有智慧的“人”，这就是所谓“群体智能”.
收稿日期2005-5-31收修改稿日期2006-7-16
Received May31,2005;in revised form July16,2006
国家自然科学基金(60272034，60472099)资助
Supported by National Natural Science Foundation of P.R.China(60272034，60472099)
1.宁波大学计算机科学与技术研究所宁波315211
1.Institute of Computer Science and Technology,Ningbo Uni-versity,Ningbo315211
DOI:10.1360/aas-007-0259
二进制表示法是最有效和最经济的数据表示法，自然界中最容易模拟和实现的是二值逻辑(如电子器件、神经元等).另外，随机神经网络中单个神经元往往只执行非常简单的操作，而整个系统则是并行连接，网络内部大量的连接使得少量神经元的损坏不会引起大的不良后果(蚁群系统中即使被踩死几只蚂蚁，系统仍然可以得到良好的解)，因此系统表现出极强的鲁棒性和抗干扰能力[4].对此，我们设计了随机二元蚁群网络.
研究结果已经表明：蚁群优化算法具有很强的发现较好解的能力，具有分布式计算、易于与其它方法相结合、鲁棒性强等优点.然而同时也发现了一些缺点，初期信息素匮乏需要较长的搜索时间，规模较大时容易陷入局优解.为了克服基本蚁群算法的不足，人们研究对其进行改进[1,2,5].遗传算法作为一种有效的全局并行优化搜索工具，具有简单、通用、鲁棒性强和适于并行分布处理的特点，但遗传算法也会存在由于各种原因过早向目标函数的局部最优解收敛，从而很难找到全局最优解，以及局部收索能力差等缺点[3].
为了克服它们各自缺点，在随机二元网络基础上，将遗传算法和蚁群算法进行融合，称之为二进制蚁群进化算法(Binary ant algorithm-genetic algorithm,BAAGA).
260自动化
学报33卷
2二进制蚁群算法的设计
假设：由众多简单的个体组成的群体，若具有
能通过之间的简单合作来完成一个整体的任务的能力，则称该群体具有“群体智能”[4].
“
简单个体”是指单个个体只具有很简单的能力，这种能力我们将用某一简单功能函数来表示.“简单合作”是指个体只能与其邻近的个体进行某种简单的通讯和协同动作(如蚂蚁在行进中遇到同伴，用触角传递信息的简单通讯能力以及共同搬动一个物体的协同动作能力)，或通过环境间接与其它个体通讯(如一蚂蚁将外激素留在环境中，而其它的蚂蚁可从留下的外激素中得到一些有用的信息).
在这种假设下，我们的“蚁群”就象一个随机连接的网络.
2.1二元蚁群网络设计
定义有向图：G=(C,L).其中顶点集C 为
{c 0(v s ),c 1(v 0N ),c 2(v 1N ),c 3(v 0N ?1),c 4(v 1
N ?1),...,
c 2N ?3(v 02),c 2N ?2(v 12),c 2N ?1(v 01,),c 2N (v 1
1)}其中，v s 为起始顶点，顶点v 0j
和v 1
j 分别用于表示二进制码串中b j 位取值为0和1的状态.即对于
j =2,3,,,N 在所有顶点j ，只有指向v 0j ?1和v 1
j ?1的两条有向弧，如图1所示.其中N 表示二进制编码的长度.
受DNA 计算中的双链结构的启发，可以在算法中增加一个互补算子，这样图1的二进制网络可以简化为图2.
最后设计了蚁群分工遍历的随机二元网络如图3所示，每一种蚂蚁遍历相应的二元网络自己的路径，然后对各种蚂蚁遍历的结果综合得到问题的解.在图3的N 表示不同网络块路径的长度，不同的网络块对应的路径长度可以不相同，本文为了描述方便统一定为长度N ，w 表示根据问题的不同所需要的网络块数.二元蚁群网络中，我们对蚂蚁进行分工，蚂蚁根据分工的不同遍历相应的网络块，蚂蚁释放的信息素留在经过的每条边上，作为智能体蚂蚁每次只需在眼前二条路中选择一条,蚂蚁的智能行为要求非常简单，而且每种蚂蚁遍历路径的关联矩阵只需2N 的空间,在下面的实验中算法的效率大大提高.
2.2二进制蚁群进化算法设计
2.2.1二进制蚁群算法模型
初始时刻，各条路径上信息量相等，设τi,j (0)=C (C 为常数,如取0.5),?τi,j =0(i,j =1,2,...,n ).蚂蚁k (k =1,2,...,m )在运动过程中，根据各条路径上的信息量决定转移方向.移动概
图1二进制网络Fig.1Binary network
图2简化的二进制网络
Fig.2Simpli?ed binary network
图3蚁群分工遍历的二元网络
Fig.3
Searching binary network of the division work
3期熊伟清等：二进制蚁群进化算法261率为
p k i,j (0)=
τα
i,j
(0)·ηβ
i,j
(0)
τα
i,j
(0)·η
i,j
(0)+τα
i,j
(1)·η
i,j
(1)
(1)
p k i,j (1)=1?p k
i,j
(0)(2)
其中，m是蚁群中蚂蚁的数量，p k
i,j
是在t时刻蚂蚁k由位置i转移到位置j的概率，α是轨迹的相对重要性(α≥0)，β是能见度的相对重要性(β≥0)，τi,j(0)是i,j连线上j为0的边残留的信息量,τi,j(1)是i,j连线上j为1的边残留的信息量.ηi,j(0)是i,j连线上j为0的边的能见度,ηi,j(1)是i,j连线上j为1的边的能见度.由于是二进制编码,蚂蚁无需具有记忆功能,只需根据面对的两条边留下的信息素大小选择.另外随着时间的推移，以前留下的信息逐渐消逝，ρ是轨迹的持久性(0≤ρ≤1)，用参数1?ρ表示信息消逝程度，经过n个时刻，蚂蚁完成一次循环，各路径上信息量要根据下式作调整.为了提高算法的效率，在每一次迭代之后，只有在这次迭代中取得最优路径的那一个体来释放信息素，而该个体更新信息素的公式如下：
τi,j(0)(t+1)=ρ·τi,j(0)(t)+?τ(3)
τi,j(1)(t+1)=ρ·τi,j(1)(t)+?τ(4)
其中?τ=1/f(s best),f(s best)是每一次迭代的最优解或者是全局最优解.这样做可以使求解速度大大提高[5].
2.2.2四个基本算子与步骤
基本算法有四个算子组成选择算子、交叉算子、变异算子和信息素更新算子组成.
定义1.(个体和个体空间)所谓l-个体X即是长度为的0和1字符串，简称个体；l称作个体的链长，l 个体的全体记作S={0,1}l，称作个体空间.
定义2.(母体和母体空间)所谓母体即是一对个体(X1,X2)，其中.所有母体的全体称为母体空间，即S2={(X1,X2|X1,X2∈S)}.
定义3.(种群和种群空间)所谓N－种群是N个个体组成的集合(个体允许重复)，简称种群.N称作种群规模，称S N={ X=(X1,X2,...,X N),X i∈S(i)≤N}为N-种群空间.
定义4.(适应度值)对于个体产生的效率称为适应值.适应值函数是个体空间S到正实数空间的映射，即适应值函数f:S→R+.
定义5.(信息素更新算子)信息素更新算子T g: S N→S，即在一个蚂蚁序列中选择一个最优个体信息素更新的映射，信息素更新算子概率为
P{T g=x i}=
f(x i)
N
k=1
f(x k)
(5)
定义6.(选择算子)在一个种群中选择一个个体的随机映射，选择算子T s:S N→S，则母体选择的概率为
P{T s(x)=(x i,x j)}=
f(x i)
k=1
f(x k)
·
f(x j)
k=1
f(xi)
(6)定义7.(杂交算子)：杂交算子是母体空间到个体空间的映射T c:S2→S.
1)设T c为单点交叉算子，对于任意(X1,X2)∈S2,Y∈S则
P{T c(X1,X2)=Y}=
k
l
(7)其中k=k(X1,X2,Y)为用单点杂交(X i,X j)可以生成Y的基因位置的个数.
2)设T c为单点随机交叉算子，P C为杂交概率，对于任意(X1,X2)∈S2,Y∈S则
P{T C(X1,X2)=Y}=
k·P
C
l若Y=X1
(1?P C)+k·P C
l其他
(8)
定义8.(变异算子)变异算子是个体空间到个体空间的随机映射T m:S→S其作用方式为独立地概率P m改变个体分量.P m称作变异概率.任给两个体X,Y∈S，有
P{T m(X)=Y}=P d
m
(X,Y)(1?P m)l?d(X,Y)(9)其中d(X,Y)表示X和Y之间的Hamming距离，即d(x,y)=
l
i=1
|x i?y i|,X=(x1,x2,...,x l), Y=(y1,y2,...,y l).
二元蚁群进化算法的基本步骤：
步骤1.随机产生初始解;
步骤2.遗传算法(交叉、变异和选择)进行多次进化，利用遗传算法所得到的解初始网络的信息素;
步骤3.判断是否满足循环结束条件，满足结束，不满足继续;
步骤4.蚂蚁遍历和信息素更新运算，并保留最优;
步骤5.对得到的解集合进行遗传算法(交叉、变异和选择)以及互补运算，并保留最优;
步骤6.使用最优更新信息素，转步骤3.
3二进制蚁群进化算法收敛性分析定义9.[6](马尔可夫链)设{ X n,n≥0}为一列
262自动化学报33卷
取值离散的随机变量，离散值的全体记为S={j},称S为状态空间.若对于任意n≥1,i k∈S(k n+1)有
P{ X n+1=i n+1/ X n=i n,..., X0=i0}=
P{ X n+1=i n+1/ X n=i n}
则称{ X n,n≥0}为马尔可夫链.
定义10.[8](齐次马尔可夫链)对任何正整数m,n，记马氏链{ X n}在m刻处于状态i且经过n步转移状态j的概率为P i,j(m,n)=P{ X m+1= j/ X m=i}如果上述转移概率与时刻m无关，即P i,j(m,n)=P(
i,j
n),则称马氏链{ X n}是齐次的.
定理1.[6]优胜者选择遗传算法所产生的种群序列{ X n,n≥0}是有限齐次马尔可夫链.
定理2.蚁群系统序列是一个典型的马尔可夫过程.
蚁群优化算法的每一步迭代对应随机变量X t=(τ(t),W(t)),t=0,1,...,其中，τ(t)为信息素痕迹,W(t)为长度L的0或1的排列.注意到第k只蚂蚁在t轮的转移由τ(t?1)决定，进一步，这个蚂蚁行走的路径和W(t?1)一起，共同决定了W(t)，在通过信息素的更新原则可以进一步得到τ(t).也就是说，X t+1的变化仅由X t决定，而与之前的状态无关，这是一个典型的马尔可夫过程.
定义11.[6]若一个马尔可夫过程{X t,t=0,1,...},对任给定的ε>0满足lim t→∞P{|X k?X?|}<ε=1，则称马尔可夫过程{X t,t=0,1,...}依概率1收敛到X?.
定理3.二进制蚁群进化算法的优化解序列是一个典型的马尔可夫过程.
由定理1和定理2知优胜选择遗传算法X(t+1)仅与X(t)有关，与迭代次数无关.同时，蚂蚁系统{τ(t+1),W(t+1)}仅与{τ(t),W(t)}有关，而与循环周期无关，本文设计的二进制蚂蚁算法模型每一次仅更新最优蚂蚁路径，它具有优胜选择遗传算法所有的特征因而BAAGA算法的优化解序列{x t,t≥0}是一个典型的马尔可夫过程.
定理4.[7]基于图的蚁群系统(graph-based ant sys-tem,GBAS)马尔可夫过程X t=(τ(t),W(t)),t= 0,1,...,依概率1收敛到X?=(τ?,W?)，其中W?为一条最优路径.
本文所提出的二进制蚁群进化算法是基于二元有向图，仍然是一种基于图的蚁群系统，文献[8]也给出了一般带权图的收敛性证明,因此可以得到定理5.
定理5.二进制蚁群进化算法的优化解马尔可夫序列以概率1收敛到X?=(τ?,W?)，其中W?为一条最优路径.4求解函数优化的二进制蚁群进化算法设计
函数优化问题：设F(x)是n维实数空间R n 到正实数R+的函数.对于x∈R n可与一个长度为N的二进制对应,于是求解max F(x)的问题可以转换为求解max{F(x),x∈{0,1}N}其中f(X)=S(F(e?1(X))是R到{0,1}N的编码映射,S是R+到R+的增函数.常采用二进制映射为固定长度N的二进制编码[7].
4.1求解函数优化的二元蚁群网络的设计
采用二进制编码.优化函数的维数决定了蚂蚁每一循环中需经过的路径数.蚂蚁走过的第一条路径对应函数的第一个变量，走过的第二条路径对应函数的第二个变量，以此类推.
对候选解{x1,x2,···}的每一变量x i用字长为N的二进制码串{b N b N?1···b2b1}表示，其中b j∈{0,1}，b L为最高位，b1为最低位.变量x i的左边界实数值为x i,min，右边界实数值为x i,max.整个随机二元蚁群网络如图2所示，其中，N表示每个变量二进制编码的长度，蚂蚁从高位向低位遍历.对于w维变量的函数优化，可以建立w种蚂蚁如图3所示，比较适合变量比较多，编码长度过长计算机不好表示的问题.
4.2函数优化的实验测试
测试函数来自参考文献[3].试验中我们取α=1,β=2,ρ=0.35,Gen(进化代数)=150, m(蚂蚁数目)=80.lenchrom(编码长度)=40, Q=1.0,P c=0.95,P m=0.05
测试函数1:
100·(x2
1
+x2)2+(1?x1)2,(?2.048≤x i≤2.048)
函数在(1，1)处有最小值0；每次运行一定代数后都能得到f(1,1)=0;
测试函数2：
5
i=1
int(x i),(?5.12≤x i≤5.12)
函数在(-5.12，5.12)存在全局最小值-30；可以得到多个解等于-30，其中之一为f(?5.11061,?5.08007)=?30.
3期熊伟清等：二进制蚁群进化算法263
测试函数3:1
1/K +
25
j =11/f j (x 1,x 2)
,其中
f ?1j (x 1,x 2)=c j +
2 i =1
(x i ?a ij )6,
?65.536≤x i ≤65.536,K =500,c j =j [a ij ]=
?32?160
16
32?32?16 (01632)
?32?32?32?32?32?16?16 (323232)
函数在(-32，-32)处，存在最小值0.998004.可以得到多个0.998004的解，其中之一是f (?31.9817,31.9991)=0.998004.测试函数5：
30 i =1
i ·x 4i +Gaussian(0,1),(?1.28≤x i ≤1.28)
函数在(0,0,...,0)存在最小值.可以得到
f (0,0...,0)=0.测试函数6：
0.5+sin 2
x 21+x 2
2?0.5[1.0+0.001(x 21+x 22)]
2
其中，?100≤x i ≤100(i =1,2)
函数在(x 1,x 2)=(0,0)处有一个全局最小值0.即f (0,0)=0.
从函数优化的测试结果看，反映了随机二元蚁群进化算法求解连续空间优化问题具有令人鼓舞的结果.
5求多维背包问题的算法设计
多维背包问题是带有一组约束的的背包问题.其描述如下存在重量分别为W [1],W [2],...,W [n ]和价值相应为V [1],V [2],...,V [n ]的n 个物品以及容量为C [1],C [2],...,C [m ]的m 个背包.要将尽量多的物品放入背包，在确保每个背包中物品不超出承重的前提下满足最大化背包中物品的总价值.这里设X [i ][j ]为二进制变量.如果物品i 被放入背包j 则X [i ][j ]=1，否则X [i ][j ]=0.则多维背包
问题的数学描述如下
max =m j =1n i =1
V [i ]X [i ][j ];(10)
s.t.
m j =1
X [i ][j ]≤1,j =1,2,...,m ;
n i =1
W [i ]X [i ][j ]≤C [j ],i =1,2,...,n ;
X [i ][j ]∈{0,1},i =1,2,...,n,j =1,2,...,m
因此背包问题是一个特殊的整数规划问题，也是一个NP 难问题.对于多维的背包问题在确定一个物品最多只能放入一个背包条件满足下它的时间复杂度为O (2m ·n ).在现实生活中使用背包理论解决的一些实际的问题都具有相当大的规模,需要寻找一些可行的方法来寻找尽可能优的解.
5.1算法设计
1)二元蚁群网络设计这里设X [i ][j ]为二进
制变量.如果物品i 被放入背包j 则X [i ][j ]=1，否则X [i ][j ]=0.对应的二进制网络如图3所示，其中w 代表背包的个数，n 为物品的个数.
2)适应度函数背包问题中个体的适应度函数是由个体解确定的所有背包中的物品的总价值来决定的.即：公式(10).
3)非法个体修正算子在产生新个体过程中不可避免地会产生一些非法的个体.为了保持种群中个体的合法性就需要对非法的个体进行修正，以获取合理的优良的个体.在个体基因位变换过程中对解进行实时判断修正，即当将一个基因位置为1时，判断是否打破约束，如果约束破坏则重新置0.
5.2实例测试
在本实例中，假设一个由100个物品以及3个背包组成的背包问题.为了对测试结果的分析更加直观方便.在这里，假设所有物品的价值密度相同.即将这里的整数0/1背包问题简化为，在不超出各个背包容量的情况下最大化所有背包内物品的总质量.即要求的价值最大，简化为质量最大(这里的质量都是整数的).在这里给出的100个物品的质量如表1.3个背包的容量分别为c [1]=3398,c [2]=1327,c [3]=1873.在这个实例中具有100个物品以及三个背包.我们取α=1,β=2,ρ=0.35,Q =1.0,P c =0.95,P m =0.1.
二维背包问题测试：选取c [1]=3398,c [2]=1327两个背包,c [1]+c [2]=4725.在这里测试的m (蚂蚁数目)=40,蚂蚁分工为2种，每一维20个蚂蚁遍历.进化代数200.每次运行可以得到4724以上的解.
264自动化学报33卷
表1物品质量表
Table1Weight table
253245243239239239238238237232231231230229228
227224217213207203201195194191187187177175171
169168166164161160158150149147141140139136135
132128126122120119115116114111110105105104103
939290797877767675736262616060
59575653535150444424238363428
42724221812107441
三维背包问题测试:使用了仿真实例中所有的三个背包c[1]=3398,c[2]=1327,c[3]=1873, c[1]+c[2]+c[3]=6598.在这里测试的m(蚂蚁数目)=60，蚂蚁分工为3种，每一维20个蚂蚁遍历.进化代数500,每次运行都可以得到6596以上的解.通过以上背包问题的测试,说明本文设计的蚂蚁算法对于多维背包问题的求解结果是令人满意的,并且算法速度快解比较稳定.表明了二进制蚁群进化算法对组合优化问题仍然具有良好的性能.
6结论
本文根据用“松散”的神经网络来模拟昆虫的群体行为，即建立一个松散的大脑－群体智能的随机结构的神经网络模型的启发，设计了一个二进制蚁群进化算法，该算法不仅适合可以求解连续参数优化的问题也适合求解离散的组合优化问题.通过函数优化和背包问题的求解，结果充分说明本文给出的二进制蚁群进化是实用而有效的,求解结果是令人满意的.
当然，对于群体智能的计算机理有待于进一步研究，我们认为从二元蚁群网络的角度的研究是比较合理的，也给多种进化算法的混合提供了框架，也便于算法的设计与实现.
References
1Dorigo M,Caro G D.Ant colony optimization:A new meta-heuristic.In:Proceedings of the1999Congress on Evolutionary Computation.Washington,DC,USA,1999, 1470～1477.
2Dorigo M,Gambardella L M.Ant colony system:A cooper-ative learning approach to the traveling salesman problem.
IEEE Transactions on Evolutionary Computation,1997, 1(l):53～66.
3Michalewicz Z.Genetic Algorithms+Data Structures= Evolution Programs.Berlin Heidelberg:Springer-Verlag, 19994Zhang L,Cheng J S.Loose brain–A mathema model of swarm intelligence.Pattern Recognition and Arti?cial In-telligence,2003,16(1):1～5
(张铃,程军盛.松散的脑袋—群体智能数学模型.模式识别与人工智能,2003,16(1):1～5)
5St¨u tzle T,Hoos H.The Max-Min ant system and local search for the traveling salesman problem.In:Proceedings of the IEEE International Conference on Evolutionary Com-putation and Evolutionary Programming.1997,309～314
6Gutjahr,W J.ACO Algorithms with guaranteed conver-gence to the optimal https://www.wendangku.net/doc/f95535212.html,rmation Processing Let-ters,2002,82(3):145～1538
7Li Qing-Hua,Li Ken-Li,Jiang Sheng-Yi,Zhang Wei.An Optimal Parallel Algorithm for the Knapsack Problem.
Journal of software,2003,14(5):891～896
(李庆华，李肯立，蒋盛益，张薇.背包问题的最优并行算法.软件学报,2003,14(5):891～896)
8Zhang Wen-Xiu.Leung Yee.Mathematical Foundation of Genetic Algorithms.Xi an:Xi an Jiaotong University Press, 2000
(张文修,梁怡.遗传算法的数学基础.西安:西安交通大学出版社, 2000)
熊伟清宁波大学副教授.主要研究方
向为进化计算、人工智能.本文通信作
者.E-mail:xwqdds@https://www.wendangku.net/doc/f95535212.html,
(Xiong Wei-Qing Associate profes-
sor at Ningbo University.His research
interest covers evolutionary computa-
tion and software engineering.Corre-
sponding author of this paper.)
魏平宁波大学副教授.研究方向
为进化计算,数据库.E-mail:
wpdds@https://www.wendangku.net/doc/f95535212.html,
(Wei Ping Associate professor at
Ningbo University.Her research in-
terest covers evolutionary computation
and database.)
差分进化算法介绍
1．差分进化算法背景 差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。 差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。它的全局寻优能力和易于实施使其在诸多应用中取得成功。 2.差分进化算法简介 差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE 的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。 3.差分进化算法适用情况 差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。它可以对非线性不可微连续空间的函数进行最小化。目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。 4.基本DE算法 差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。然后，变异向量的参数与另外事先确
差分进化算法及应用研究
湖南大学 硕士学位论文 差分进化算法及应用研究 姓名：吴亮红 申请学位级别：硕士 专业：控制理论与控制工程指导教师：王耀南 20070310
硕士学位论文 摘要 论文首先介绍了智能优化算法的产生对现代优化技术的重要影响，阐述了智能优化算法的研究和发展对现代优化技术和工程实践应用的必要性，归纳总结了智能优化算法的主要特点，简要介绍了智能优化算法的主要研究内容及应用领域。 对差分进化算法的原理进行了详细的介绍，给出了差分进化算法的伪代码。针对混合整数非线性规划问题的特点，在差分进化算法的变异操作中加入取整运算，提出了一种适合于求解各种混合整数非线性规划问题的改进差分进化算法。同时，采用时变交叉概率因子的方法以提高算法的全局搜索能力和收敛速率。用四个典型测试函数进行了实验研究，实验结果表明，改进的差分进化算法用于求解混合整数非线性规划问题时收敛速度快，精度高，鲁棒性强。 采用非固定多段映射罚函数法处理问题的约束条件，提出了一种用改进差分进化算法求解非线性约束优化问题的新方法。结合差分进化算法两种不同变异方式的特点，引入模拟退火策略，使算法在搜索的初始阶段有较强的全局搜索能力，而在后阶段有较强的局部搜索能力，以提高算法的全局收敛性和收敛速率。用几个典型Benchmarks函数进行了测试，实验结果表明，该方法全局搜索能力强，鲁棒性好，精度高，收敛速度快，是一种求解非线性约束优化问题的有效方法。 为保持所求得的多目标优化问题Pareto最优解的多样性，提出了一种精英保留和根据目标函数值进行排序的多目标优化差分进化算法。对排序策略中目标函数的选择方式进行了分析和比较，并提出了一种确定进化过程中求得的精英解是否进入Pareto最优解集的阈值确定方法。用多个经典测试函数进行了实验分析，并与NSGA-Ⅱ算法进行了比较。实验结果表明，本文方法收敛到问题的Pareto前沿效果良好，获得解的散布范围广，能有效保持所求得的Pareto最优解的多样性。 提出了一种新的基于群体适应度方差自适应二次变异的差分进化算法。该算法在运行过程中根据群体适应度方差的大小，增加一种新的变异算子对最优个体和部分其它个体同时进行变异操作，以提高种群多样性，增强差分进化算法跳出局部最优解的能力。对几种典型Benchmarks函数进行了测试，实验结果表明，该方法能有效避免早熟收敛，显著提高算法的全局搜索能力。提出了将该改进算法用来整定不完全微分PID控制器最优或近似最优参数的新方法。为克服频域中常用的积分性能指标如IAE，ISE和ITSE的不足，提出了一种新的时域性能指标对控制器性能进行测试和评价。用三个典型的控制系统对提出的ASMDE-PID控制器进行了测试。实验结果表明，该方法实现容易，收敛性能稳定，计算效率高。与ZN，GA和ASA方法相比，DE在提高系统单位阶跃响应性能方面效率更高，鲁棒性更强。 为了提高差分进化算法的全局搜索能力和收敛速率，提出了一种双群体伪并行差分
量子克隆进化算法
量子克隆进化算法 刘 芳,李阳阳 (西安电子科技大学计算机学院,陕西西安710071) 摘 要: 本文在量子进化算法的基础上结合基于克隆选择学说的克隆算子,提出了改进的进化算法———量子克 隆进化策略算法(QCES ).它既借鉴了量子进化算法的高效并行性又利用克隆算子来代替其中的变异和选择操作,以增加种群的多样性,避免了早熟,且收敛速度快.本文不仅从理论上证明了该算法的收敛,而且通过仿真实验表明了此算法的优越性. 关键词: 克隆算子;进化算法;量子克隆进化策略中图分类号: T N957 文献标识码: A 文章编号: 037222112(2003)12A 22066205 Quantum Clonal Evolutionary Algorithms LI U Fang ,LI Y ang 2yang (Institute o f Computer ,Xidian University ,Xi ’an ,Shaanxi 710071,China ) Abstract : Based on the combining of the quantum ev olutionary alg orithms (QE A )with the main mechanisms of clone ,an im 2proved ev olutionary alg orithm —quantum clonal ev olutionary strategies (QCES )was proposed in this paper.By adopting the high 2effec 2tive parallelism of QE A and replacing clone operator by mutation and selection of the classical ev olutionary alg orithms (CE A ),it has better diversity and the converging speed than CE A and av oided prematurity.The convergence of the QCES is proved and its superiori 2ty is shown by experiments in this paper. K ey words : clone operator ;ev olutionary alg orithm ;quantum clonal ev olutionary strategies 1 引言 计算是人类思维能力的最重要的方面之一,计算能力的提高与人类文明进步息息相关.从古老的算盘到现代的超级计算机,人类的计算技术实现了革命性的突破.综观当今,计算机的广泛应用已经并且仍在继续改变着我们的世界.一方面,人们为计算机的神奇能力所倾倒.另一方面,人们也为它无力完全满足实际的需要而烦恼.因此,加速计算机的运算速度以提高计算机的运算能力成为计算机科学的中心任务之一. 如何加快计算机的运算能力呢?这一问题大体可以从两个方面着手解决.一是制造更为先进的计算机硬件,另一则是设计恰当的计算机运算流程,后者可以称之为“算法”.一类模拟生物进化过程与机制来求解问题的自组织、自适应人工智能技术即进化计算(包括用于机器学习问题的遗传算法,优化模型系统的进化规划和用于数值优化问题的进化策略)的出现为我们寻找快速算法提供了新思路.进化计算是一种仿生计算,依照达尔文的自然选择和孟德尔的遗传变异理论,生物的进化是通过繁殖、变异、竞争、选择来实现的,进化算法就是建立在上述生物模型基础上的随机搜索技术.我们所熟悉的 遗传算法(G enetic alg orithms )[1],它通过模拟达尔文的“优胜劣汰,适者生存”的原理鼓励好的个体,通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体,同时寻找更好的个体,由此来模仿一切生命与智能的产生与进化过程.理论上已经证明:进化算法能从概率的意义上以随机的方式寻求到问题的最优解;但在实际应用当中随着问题的复杂和海量的数据量,也出现了一些不尽人意的情况,主要表现在:计算后期解的多样性差即易造成早熟,收敛速度慢等缺点.因此,为克服上述缺点关键是构造性能良好的进化算法. 在改进的进化算法中,有些是将传统寻优算法与遗传算法相结合提出了混合遗传算法[2,3],有些则另辟蹊径提出了新颖的学习算法———量子进化算法[4]和免疫进化算法[5],量子力学是20世纪物理学最惊心动魄的发现之一,量子计算是物理理论与计算机的成功结合,在量子体系中,一位的信息位不在是经典的1比特,而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit ),例如一个n 位二进制的串在量子体系中就可同时表示2n 个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[6].正是量子的 收稿日期:2003209210;修回日期:2003212210 基金项目:国家自然科学基金(N o.60133010);国家高技术研究发展计划(863计划)(N o.2002AA135080) 第12A 期2003年12月 电 子 学 报 ACT A E LECTRONICA SINICA V ol.31 N o.12A Dec. 2003
量子免疫算法1
报告正文 （一）立项依据与研究内容 1。项目的立项依据（研究意义、国内外研究现状及分析、附主要参考文献目录） （1）研究意义 随着石化能源危机的来临以及人们环保意识的加强，世界各国争相发展可再生新兴能源。风电装机容量每年以20％至30％的速度增长，其增长势头迅猛，据专家预测风力发电量在2020年将占全球发电总量的12％。风力发电已经成为解决世界能源问题的不可或缺的重要力量。 但随着投产的风力发电机数量和容量的不断增加，风力发电机组的运行维护、故障检测、诊断技术的优化和改进已成为风力发电亟待解决的新课题。长期以来，风力发电机一直采用计划维修与事后维修方式，计划维修即运行2500h和5000h 后的例行维护，如检查螺栓力矩，加注润滑脂等。该维修体制往往无法全面、及时地了解设备运行状况。而事后维修则因事前准备不足，从而造成维修工作旷日持久，损失重大。并且由于近年来大型风力发电机组研究的快速发展，其机械结构日趋复杂，不同部件之间的相互联系、耦合也更加紧密，一个部件出现故障，将可能导致整个发电过程中断。因此，有必要对风力发电机组的运行状态进行检测跟踪，对其故障征兆进行分析处理，预测分析风力发电机的故障趋势，减少事故发生造成的财产损失，也减少强迫停机的次数，降低发电机的维护费和提高发电机的可用性，指导风电机组的维护与维修。 目前的故障诊断方法虽然为诊断电机的故障起到了重要作用，但也存在如训练仿真模型耗时，需大量的先验知识，对故障样本的学习缺乏自主连续，实时性差等问题。为了提高故障诊断的准确性、实时性及鲁棒性，还需加强新方法的研究，特别是基于生物智能的新方法研究。近年来逐渐发展起来的基于生物免疫机理的人工免疫系统具有多样性、分布式、噪声忍耐、无教师学习、自组织、自适应等特点，不需要反面例子，结合了分类器、神经网络和机器推理等学习系统的一些优点，在复杂系统的故障检测与诊断中具有很大的潜力。通过研究人工免疫系统，可望产生更有效的风力发电机组故障诊断方法。 而传统的故障诊断技术主要依靠单一的故障特征来进行故障判定，且存在样本需求量大及诊断学习缺乏自主连续性等问题，远不能满足现代化生产的要求。受生物免疫系统启发而建立的人工免疫系统蕴含了噪声忍耐、自学习、自组织和自记忆等进化学习机理，为解决旋转机组故障诊断问题提供了一条新的思路，反面选择算法可以有效判断自我-非我状态，并成功地应用于振动信号异常检测，动态规模免疫算法能够通过学习进化保持记忆抗体的多样性，实现较好的故障分类效果，将以上思想应用于故障诊断之中，得到了风力发电机组状态监测与故障
基本差分进化算法
基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。由于DE 算法操作简单，寻优能力强，自提出以来引起了国内外学者的高度关注，目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群P 0001[,,]N =X x x L ，其中000T 1[,,]i i iN x x =x L ，p N 为DE 种群规模。DE 算法的核心思想在于采取变异和交叉操 作生成试验种群，然后对试验种群进行适应度评估，再通过贪婪思想的选择机制，将原种群和试验种群进行一对一比较，择优进入下一代。 基本DE 算法主要包括变异、交叉和选择三个操作。首先，在种群中随机选取三个个体，进行变异操作： 1123()t t t t i r r r F +=+-v x x x 其中1t i +v 表示变异后得到的种群，t 表示种群代数，F 为缩放因子，一般取(0,2]，它的大小可以决定种群分布情况，使种群在全局范围内进行搜索；1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。 然后，将变异种群和原种群进行交叉操作： 1,R 1 ,,R () or () () and ()t i j t i j t i j v rand j C j randn i u x rand j C j randn i ++?≤=?=?>≠?? 其中t 1,i j u +表示交叉后得到的种群，()rand j 为[0,1]之间的随机数，j 表示个体的第j 个分量，R C 为交叉概率，()randn i 为[1,,]N L 之间的随机量，用于保证新个体至少有一维分量由变异个体贡献。 最后，DE 算法通过贪婪选择模式，从原种群和试验种群中选择适应度更高的个体进入下一代： 11t 11 ()() ()()t t t i i i i t t t i i i f f f f ++++?<=?≥?u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。当试验个体1t i +u 的适应度优于t i x 时，
差分进化算法-入门
基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体，而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}12(),, ,t t t NP X t x x x =，()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =，则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =，222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群 体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。
免疫算法的克隆选择过程
免疫算法的克隆选择过程 % 二维人工免疫优化算法 % m--抗体规模 % n--每个抗体二进制字符串长度 % mn--从抗体集合里选择n个具有较高亲和度的最佳个体进行克隆操作 % A--抗体集合(m×n),抗体的个数为m,每个抗体用n个二进制编码(代表参数) % T--临时存放克隆群体的集合,克隆规模是抗原亲和度度量的单调递增函数% FM--每代最大适应度值集合 % FMN--每代平均适应度值集合 % AAS--每个克隆的最终下标位置 % BBS--每代最优克隆的下标位置 % Fit--每代适应度值集合 % tnum--迭代代数 % xymin--自变量下限 % xymax--自变量上限 % pMutate--高频变异概率 % cfactor--克隆(复制)因子 % Affinity--亲和度值大小顺序 %% clear all clc tic; m=65; n=22; mn=60; xmin=0; xmax=8; tnum=100; pMutate=0.2; cfactor=0.1; A=InitializeFun(m,n); %生成抗体集合A,抗体数目为m,每个抗体基因长度为n F='X+10*sin(X.*5)+9*cos(X.*4)'; %目标函数 FM=[]; %存放各代最优值的集合 FMN=[]; %存放各代平均值的集合 t=0; %% while t 《文献检索与科技论文写作》作业 学生姓名 年级专业 班级学号 指导教师职称 目录 第一部分文献查阅练习 (1) 第二部分文献总结练习 (7) 第三部分科技论文图表练习 (8) 第四部分心得体会 (11) 第一部分文献查阅练习 [1] 谭翠燕,梁汝强,阮康成.量子点在生命科学中的应用.生物化学与生物物理学报,2002 ,34(1):1-5. 摘要:近年来,量子点(半导体纳米微晶体)的研究引起国内外研究者的广泛兴趣 ,其研究内容涉及物理、化学、材料等多学科,已成为一门新兴的交叉学科。虽然量子点在生物学中的应用才刚刚起步,但是已经取得了有意义的进展，成为人们极为注意的一个热点。现就量子点的光学特性、制备方法以及在生物学中的研究进展和应用前景作一简要综述。 关键词：量子点；荧光光谱；蛋白质组学；生物大分子；生物芯片 [2] 张大鹏,黄丛林,王学臣,娄成后.葡萄叶片光合速率与量子效率日变化的研究及 利用.植物学报,1995,37(1):25—33. 摘要：在土壤供水充足的自然条件下,葡萄( VitisviniferaL.)光合子效率在上午最高、尔后下降 ,出现“中午降低”现象。上午光能截留高的叶片的光合量子效率较高 ,中午减叶片光能截留有利于缩小“中午降低”的幅度。一天中始终处于强光照射下的叶片的光合量子效率“中午降低”明显而持久 ,且在下午得不到恢复。光合速率与量子效率的日变化与叶肉对CO2阻力的变化密切相关 ,而与气孔下腔细胞间隙中CO2浓度变化关系不大。在人工气候室中土壤水分、空气湿度、叶温、CO2 浓度等环境因素稳定而适宜的条件下 ,饱和光强以上的光(1200μ mol · m- 2· s- 1)持续照射使葡萄叶片出现“光抑制”;用亚饱和光(1200μ mol · m- 2· s- 1) 和低光(200 μ mol · m- 2· s- 1)持续照射一定时间后,也使叶片光合量子效率比照射开始时随照射时间的持续而不断降低,出现类似于“光抑制”的现象。稍高于补偿光强的弱光(1 00 μ mol ·m- 2· s- 1) 持续照射下叶片光合量子效率稳定不变。讨论了“类似光抑制”现象。实验结果还认为葡萄叶片一天中叶肉阻力的变化与“光抑制”部分地相联。分析调控葡萄光合速率与量子效率日变化的内外因素,指出南北行向叶幕是改善葡萄群体光能利用最理想的受光面系统。 关键词：葡萄；光合量子效率；叶肉阻力；低光下光抑制；光合中午降低⒇ [3] 朱维良,蒋华良,陈凯先,嵇汝运.分子间相互作用的量子化学研究方法.化学进展,19 99年8月,第11卷第3期. 龙源期刊网 https://www.wendangku.net/doc/f95535212.html, 基于TSP的改进差分进化算法 作者：朱宇航伏楠 来源：《硅谷》2012年第17期 摘要: 针对TSP问题,提出一种改进的差分进化算法:利用贪心算法产生初始种群,定义特有的编码匹配函数进行变异操作,排序法修复变异个体,并采用顺序交叉,在变异操作之后,加入新的选择机制,防止交叉操作破坏变异出的优良个体,实验结果表明改进后的差分进化算法能够高效地解决TSP问题,体现良好的优化性能。 关键词: 差分进化算法;TSP;进化算法 0 引言 差分进化算法(DE:Differential Evolution)是一种模拟自然进化法则的仿生智能计算方法,在解决复杂的全局优化问题方面,DE的性能更加优秀,过程也更为简单,受控参数少[1],但由于DE 特有的差分操作的限制,DE被成功应用的领域多集中在连续优化领域,在离散优化领域的应用还相对较少[2]。 TSP(旅行商问题)作为典型的离散优化问题,是解决很多实际问题的最终转化形式,同时也是著名的NP难题,在短时间内求出其最优解非常困难,现有解法[3-4]在求解中都各有缺点.因此,研究将DE经过必要的改进后应用于TSP的求解具有重要意义。 1 改进DE算法 1.1 编码及匹配函数 适应度定义为:负的路径长度,使得路径长度越短,适应度值越大。 1.2 贪婪初始化 为提高初始种群的质量,采用贪婪的初始化方法.对于初始种群的每个个体,产生方法如下: step1:初始化待走城市列表List为包含所有城市的列表; step2:随机选择一个城市A作为起点,并将此点作为当前城市T,从List中移除; step3:从List中选择距离城市T最近的城市作为新的当前城市T,并将T从List中移除; step4:判断List是否为空,若是,则结束;若否,则转step3。 https://www.wendangku.net/doc/f95535212.html, 量子克隆遗传算法1 李阳阳1，焦李成1 1西安电子科技大学电子工程学院，西安(710071) E-mail: lyy_111@https://www.wendangku.net/doc/f95535212.html, 摘要：遗传算法是解决优化问题的一种有效方法。但在实际应用中也存在着收敛速度慢，早熟等问题，使得其结果极不稳定。本文将遗传算法和量子理论相结合并利用免疫系统中所特有的克隆算子，针对0/1背包问题，提出了一种改进的进化算法——量子克隆遗传算法(QCA)。它能有效的避免早熟，且具有收敛速度快的特点。 关键词：遗传算法量子克隆遗传算法 0/1背包 中图分类号：TN957 1.引言 进化计算是一种仿生计算，依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的，进化算法就是建立在上述生物模型基础上的随机搜索技术。我们所熟悉的遗传算法(Genetic Algorithms)[1]，它通过模拟达尔文的“优胜劣汰，适者生存”的原理鼓励好的个体，通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体，同时寻找更好的个体，由此来模仿一切生命与智能的产生与进化过程[2][3]。理论上已经证明：进化算法能从概率的意义上以随机的方式寻求到问题的最优解；但在实际应用当中随着问题的复杂和海量的数据量，也出现了一些不尽人意的情况，主要表现在：计算后期解的多样性差即易造成早熟，收敛速度慢等缺点。因此，为克服上述缺点关键是构造性能良好的进化算法。 量子力学是20世纪物理学最惊心动魄的发现之一，量子计算是物理理论与计算机的成功结合，在量子体系中，一位的信息位不在是经典的1比特，而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit)，例如一个n位二进制的串在量子体系中就可同时表示n 2个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[4]。正是量子的并行性使得原来传统计算机无法解决的复杂问题以惊人的速度得以解决,但在量子计算机尚未构成的情况下，为了充分利用量子计算的高效并行性，本文借用了量子计算中的量子编码，继承了免疫克隆策略[5]中的克隆算子将二者相结合，提出了量子克隆遗传算法，并将其应用于0/1被包问题上，与传统进化算法相比较,它具有收敛速度快、寻优能力强的特点。 1本课题得到高等学校博士学科点专项科研基金（项目编号：20030701013）资助。 - 1 - 第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 antum evolutionary algorithm GA O H ui 1 ,X U Guan g 2hui 1 ,Z H A N G R ui 2 ,W A N G Zhe 2ren 1 (1.School of Communication Science and Engineering ,Harbin Institute of Technology ,Harbin 150090,China ;2.School of Automation ,Harbin University of Science and Technology ,Harbin 150080,China.Correspondent :GAO Hui ,E 2mail :zr_gh @https://www.wendangku.net/doc/f95535212.html, ) 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 个量子比特的量子 差分进化算法-入门 基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}1 2 (),,,t t t NP X t x x x =L ，() 1 2 ,,,T t t t t i i i iD x x x x =L 为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,,,)t t t t T i i i iD v v v v =L ，则 123() 1,2,,D t t t t ij r j r j r j v x F x x j =+-=L (1) 其中111112(,,,)t t t t T r r r r D x x x x =L ，222212(,,,)t t t t T r r r r D x x x x =L 和333312(,,,)t t t t T r r r r D x x x x =L 是群体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。 差分进化算法（DE）[1]是Storn 和Price 在1995 年提出的一种基于种群差异的进化算法，DE是一种随机的并行搜索算法。差分进化计算和其他进化计算算法一样，都是基于群体智能理论的优化算法，利用群体内个体之间的合作与竞争产生的群体智能模式来指导优化搜索的进行。与其他进化计算不同的是，差分进化计算保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了进化操作的复杂性。差分进化计算特有的进化操作使得其具有较强的全局收敛能力和鲁棒性，非常适合求解一些复杂环境中的优化问题。 最初试图使用向量差进行向量种群的混洗，以此来解决切比雪夫多项式适应性问题。DE 通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质上是一种基于实数编码的具有保优思想的进化算法。该算法实现技术简单，在对各种测试问题的实验中表现优异，已经成为近年来进化算法研究中的热点之一。 差分进化算法基本原理 基本的差分进化算法是基于候选方案种群的算法，在整个搜索空间内进行方案的搜索，通过使用简单的数学公式对种群中的现有方案进行组合实现的。如果新的方案有所改进，则被接受，否则被丢弃，重复这一过程直到找到满意的方案。 设 f 是最小化适应度函数，适应度函数以实数向量的形式取一个候选方案作为参数，给出一个实数数值作为候选方案的输出适应值。其目的是在搜索空间的所有方案p 中找到m 使得f(m) ≤f(p)。最大化是找到一个m 使得f(m) ≥f(p)。 设X=(x1, x2,…, xn)∈?n是种群中一个个体，基本的差分进化算法如下所述： ?在搜索空间中随机地初始化所有的个体。 ?重复如下操作直到满足终止条件（最大迭代数或者找到满足适应值的个体） o 对于种群中的每个个体： ●随机地从种群中选择三个彼此不同的个体a，b 和c。 ●选择一个随机索引R ∈{1, ..., n}，n 是被优化问题的维数。 ●通过对每个i ∈{1, ..., n}进行如下的迭代计算可能的新个体Y = [y1, ..., yn] 生成一 个随机数ri~U(0,1)； ●如果(i=R)或者(ri 移动无线信道中Hata 模型的仿真分析 宋卫星 潘 和 过宝宝 胡仲羽 （陕西理工学院，陕西 汉中 723001） 【摘 要】移动无线信道模型的建立及仿真实验对移动通信的研究具有重要意义，文章详细分析了移动无线信道中的Hata 模型，并对路径损耗进行了仿真，为进行无线通信工程的设计、仿真和规划提供参考。 【关键词】无线信道；Hata 模型；仿真 【中图分类号】TN911 【文献标识码】A 【文章编号】1008-1151(2011)01-0021-01 （一）引言 无线信道建模是其他无线通信技术设计的基础，无线信道是任何一个无线通信系统中电波传播过程中必不可少的组成部分，它是连接发射机和接收机的媒介，其特性决定了信息论的容量，即无线通信系统的最终性能限制。由于电磁波在无线信道中受到反射、绕射、散射、多径传播等多种因素的影响，导致无线信道不像有线信道那样固定且容易预测，也给无线信道中电磁信号的传播特性分析过程带来了很大的不确定性。因此无线信道的建模是无线通信系统研究中的难点和重点，而无线信道的传播特性对于无线系统的设计、仿 真和规划却有着十分重要的作用。 在无线通信系统中，电波传播经常在不规则地区。在估 计预测路径损耗时，要考虑特定地区的地形地貌，包括简单 的曲线形状和多山地区以及障碍物等因素的影响。在无线通 信系统的工程设计中，常采用电波传播损耗模型来计算无线路径的传播损耗，建立这些模型的目的是为了预测特定点或 特定区域的信号场强。本文对移动无线信道中的Hata 模型进行了详细的分析，并对其路径损耗进行了仿真模拟。 （二）Hata 模型的基本原理 1.Okumura 模型 Okumura 模型是预测城区信号是使用最广泛的模型之一，它使适用的频率范围为150～1925MHz，适用的距离是1～100km，模型要求的基站高度为30～1000m。模型的路径损耗可表示为： 50)(,)()(f m u te re A R E A L L A f d G h G h G =+???， （1） 其中50L 为传播路径损耗值的50%， f L 为自由空间传播损耗， mu A 为自由空间中值损耗，()te G h 为基站天线高度增益因子，()re G h 为移动台天线高度增益因子，AREA G 为环境类型的增益。mu A 和AREA G 是频率的函数，Okumura 给出了相应的曲线，可直 接使用。()te G h ，()re G h 根据下面的公式计算 ()20lg(/200), 301000()10lg(/3) 3()20lg(/3) 310te te re re re re G h h m h m te G h h h m re G h h m h m re =<<=<=<< （2） Okumura完全基于测试数据，在许多情况下，通过外推曲线来获得测试范围以外的值。通常预测和测试路径损耗的偏差为10dB到14dB。 2.Hata 模型 Hata 模型是广泛使用的一种中值路径损耗预测的传播模型，适用于宏蜂窝的路径损耗预测，根据应用频率的不同，Hata 模型分为Okumura-Hata 模型和COST-231Hata 模型，Okumura-Hata 模型适用的频率范围为150MHz～1500MHz，主要用于900MHz；COST-231Hata 模型，是COST-231工作委员会提出的将频率扩展到2GHz 的Hata 模型扩展版本。 Okumura-Hata 模型是根据测试数据统计分析（Okumura 曲线图）得出所作的经验公式。以市区传播损耗为标准，其他地区在此基础上进行修正。Okumura-Hata 模型路径损耗 50()L dB 计算的经验公式为： 5069.5526.16lg 13.82lg 44.9 6.55lg lg ()()()c te re te cell terrain L dB f h h h d C C α=+??+?++， （3） 其中c f 为传输频率(MHz)；te h 为发射有效天线高度；re h 为接收有效天线高度；d 为收发之间的水平距离，单位为km；()re h α为有效天线修正因子，是覆盖区大小的函数。 对于中、小城市，有效天线修正因子为： ()(1.11lg 0.7)(1.56lg 0.8)re c re c h f h f dB α=???，（4） 对于大城市、郊区、乡村，有效天线修正因子为： ()8.29(lg1.54) 1.1() 3.2(lg11.75) 4.97300300re re c h h dB h h dB f MHz re re f MHz c αα=?<=?≥，，， （5） cell C 为小区类型校正因子，不同环境下其取值不同。 城市：0cell C ＝；郊区：()22lg /28 5.4cell C f =??； 乡村：24.78(lg f )18.33lg 40.98cell c c C f =???。 terrain C 为地形校正因子，它反映一些重要的地形环境因素 对路径损耗的影响，合理的地形校正因子取值可以通过传播模型的测试和校正得到，也可以人为的设定。 在d 超过1km 时Hata 模型的预测结果与Okumura 模型非常接近，该模型适用于大区制移动通信系统，但不适合小区半径为lkm 左右的个人通信系统。 科学和技术研究欧洲协会将hata 模型扩展到2GHz，COST-231 Hata 模型路径损耗50()L dB 计算的经验模型公式为： 5046.333.9lg 13.82lg ()(44.9 6.55lg )lg c te re te cell terrain M L f h h h d C C C α=+??+?+++，（6） 式(6)中M C 为大城市中心校正因子，对于中（下转第31页） 【收稿日期】2010-11-12 【作者简介】宋卫星（1958－），男，河南孟州人，陕西理工学院物理系高级实验师，从事电子技术研究。量子文献检索
基于TSP的改进差分进化算法
量子克隆遗传算法
实数编码量子进化算法
差分进化算法-入门
差分进化算法综述概况
移动无线信道中Hata模型的仿真分析