下载文档原格式
动态蚁群遗传混合算法的研究及应用（河北工程学院，河北邯郸056038）摘要：蚁群算法是一种源于大自然生物世界的仿生类算法，该算法采用分布式并行计算和正反馈机制。
易于与其他方法结合，具有很强的鲁棒性和适应性，但存在搜素时间长、易陷入局部最优解的缺点。
为了克服这一缺点, 文中给出一种新的蚁群算法——动态蚂蚁遗传混合算法。
在基本蚁群算法中引入变异机制, 采用最佳融合点评估策略来交叉地调用两种算法。
动态地控制遗传算法与蚂蚁算法的调用时机，并设计了相应的信息素更新方法，有效减少了算法的冗余迭代次数，提高了搜索速度,同时引入迭代调整阈值控制算法后期的遗传操作和蚂蚁规模，加快了种群进化速度，从而更快地找到最优解。
该法具有较快的收敛速度，节省计算时间，实验结果表明该方法是行之有效的。
关键词：蚁群算法; TSP问题; 遗传算法; 动态蚂蚁遗传混合算法1 引言蚁群算法 (Ant Colony Algorithms，ACO）又称蚂蚁算法。
是一种用来在图中寻找优化路径的机率型技术。
蚂蚁在寻找食物时，总是能找到较短的路径。
受到蚁群系统信息共享机制的启发，意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该算法应用到求解旅行商问题（TSP)和二次分配问题（QAP)中。
取得了一系列较好的实验结果。
解决一些实际问题也有很好的效果。
但蚁群算法同其它生物进化算法一样存在过早收敛易陷入局部极小值等问题。
结合其它优化算法形成混合蚁群算法是克服这些缺点的有效手段。
遗传算法(genetic algorithm，GA)以决策变量的编码作为运算对象，在优化过程中借鉴生物学中染色体和基因的概念，模拟自然界中生物和遗传进化等机理，通过个体适应度来进行概率选择操作，通过交叉变异产生新的个体，从而遗传算法具有较强的全局性。
为克服蚁群算法搜索速度慢、易陷入局部最优等缺点。
本文提出了一种新的动态蚁群遗传混合算法(Dynamic Ant Algorithm -Genetic Algorithm，DAAGA)。
蚁群算法与遗传算法的混合算法近年来，混合算法作为一种特殊的人工智能技术，受到了许多研究机构和企业的广泛关注。
其中，蚁群算法与遗传算法的混合算法（下称混合算法）具有一定的特殊优势，可以有效解决复杂的模式识别、信息检索和最优化问题。
本文从蚁群算法和遗传算法的基本思想出发，深入剖析混合算法的基本构成、优点以及企业的应用场景，以期能够更好地认识和掌握这一技术。
一、蚁群算法与遗传算法：基本思想1、蚁群算法：蚁群算法是一种仿生、基于群体智能的算法，它是以蚂蚁搜寻食物的行为模式为模型，从而实现最优解搜索的过程。
它由计算机模拟蚁群行为进行最优化搜索，以解决困难的问题。
蚁群算法的核心思想是：利用一群蚂蚁以同源的形式对不同的最优解进行搜索，通过了解蚂蚁的可供选择的信息和搜索结果，从而实现进化规律。
2、遗传算法：遗传算法是一种基于生物遗传的群体智能模拟算法，它采用“多体、多次、随机”的搜索原理，模拟生物在自然选择中进化的过程，最终得到最优解。
遗传算法主要通过对初始群体进行繁殖和变异，得到新一代群体，并按照某种适应性评价准则，逐渐改良算法求解。
二、混合算法的基本构成混合算法是将蚁群算法和遗传算法两者相结合，综合利用其优势而研究出来的一种智能算法。
它通过引入染色体编码对解空间进行搜索，从而充分利用两种算法的优点，实现最优解的搜索和挑选。
其基本构成包括：（1）蚁群算法：利用蚁群算法搜索最优解，主要由局部搜素和全局新种群构成;（2）遗传算法：采用遗传算法构建最优解，主要由适应性函数、编码、交叉、变异等过程组成;（3）编码：采用双编码方式，利用蚁群算法得到的最优解作为初始种群，再利用遗传算法的交叉和变异技术，最终构成混合最优解;（4）评价函数：采用基于路径编码的评价函数，根据遗传算法求得的最优解来计算蚁群搜索出来的最优解;（5）迭代：采用混合算法进行迭代，一般采用多次，可以通过增加遗传算法的个体迭代次数，改变蚁群算法的更新概率等方法，来改变最优解搜索的结果。
遗传算法与蚁群算法结合遗传算法1、基本思想2、算法原理3、代码实现4、结果截图5、总结1·基本思想吸取两个算法的优点，优缺互补，克服两个算法的缺点，利⽤了遗传算法的快速时间效率，优于蚂蚁算法的时间效率。
并且求解精度效率优于遗传算法。
这样就提⾼了两个算法结合的算法时间效率和求解精度。
2、算法原理这个算法的原理是先利⽤遗传算法的快速性、全局收敛性和随机性求出结果，结果产⽣有关问题的初始信息素分布，遗传算法执⾏完在运⽤蚁群算法，在⼀定初始信息素分布的情况下，充分利⽤蚁群算法并⾏性、正反馈性、求解精度效率⾼的特点。
3、代码实现%mainclear;clc;%%%%%%%%%%%%%%%输⼊参数%%%%%%%%N=50; %%城市的个数M=100; %%种群的个数ITER=500; %%迭代次数%C_old=C;m=2; %%适应值归⼀化淘汰加速指数Pc=0.8; %%交叉概率Pmutation=0.05; %%变异概率%%⽣成城市的坐标pos=randn(N,2);%%⽣成城市之间距离矩阵D=zeros(N,N);for i=1:Nfor j=i+1:Ndis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;D(i,j)=dis^(0.5);D(j,i)=D(i,j);endend%%⽣成初始群体popm=zeros(M,N);for i=1:Mpopm(i,:)=randperm(N);%随机排列，⽐如[2 4 5 6 1 3]end%%随机选择⼀个种群R=popm(1,:);figure(1);scatter(pos(:,1),pos(:,2),'rx');%画出所有城市坐标axis([-3 3 -3 3]);figure(2);plot_route(pos,R); %%画出初始种群对应各城市之间的连线axis([-3 3 -3 3]);%%初始化种群及其适应函数fitness=zeros(M,1);len=zeros(M,1);for i=1:M%计算每个染⾊体对应的总长度len(i,1)=myLength(D,popm(i,:));endmaxlen=max(len);%最⼤回路minlen=min(len);%最⼩回路fitness=fit(len,m,maxlen,minlen);rr=find(len==minlen);%找到最⼩值的下标，赋值为rrR=popm(rr(1,1),:);%提取该染⾊体，赋值为Rfor i=1:Nfprintf('%d ',R(i));%把R顺序打印出来endfprintf('\n');fitness=fitness/sum(fitness);distance_min=zeros(ITER+1,1); %%各次迭代的最⼩的种群的路径总长nn=M;iter=0;while iter<=ITERfprintf('迭代第%d次\n',iter);%%选择操作p=fitness./sum(fitness);q=cumsum(p);%累加for i=1:(M-1)len_1(i,1)=myLength(D,popm(i,:));r=rand;tmp=find(r<=q);popm_sel(i,:)=popm(tmp(1),:);end[fmax,indmax]=max(fitness);%求当代最佳个体popm_sel(M,:)=popm(indmax,:);%%交叉操作nnper=randperm(M);% A=popm_sel(nnper(1),:);% B=popm_sel(nnper(2),:);%%for i=1:M*Pc*0.5A=popm_sel(nnper(i),:);B=popm_sel(nnper(i+1),:);[A,B]=cross(A,B);% popm_sel(nnper(1),:)=A;% popm_sel(nnper(2),:)=B;popm_sel(nnper(i),:)=A;popm_sel(nnper(i+1),:)=B;end%%变异操作for i=1:Mpick=rand;while pick==0pick=rand;endif pick<=Pmutationpopm_sel(i,:)=Mutation(popm_sel(i,:));endend%%求适应度函数NN=size(popm_sel,1);len=zeros(NN,1);for i=1:NNlen(i,1)=myLength(D,popm_sel(i,:));endmaxlen=max(len);minlen=min(len);distance_min(iter+1,1)=minlen;fitness=fit(len,m,maxlen,minlen);rr=find(len==minlen);fprintf('minlen=%d\n',minlen);R=popm_sel(rr(1,1),:);for i=1:Nfprintf('%d ',R(i));endfprintf('\n');popm=[];popm=popm_sel;iter=iter+1;%pause(1);end%end of whilefigure(3)plot_route(pos,R);axis([-3 3 -3 3]);figure(4)plot(distance_min);%交叉操作函数 cross.mfunction [A,B]=cross(A,B)L=length(A);if L<10W=L;elseif ((L/10)-floor(L/10))>=rand&&L>10W=ceil(L/10)+8;elseW=floor(L/10)+8;end%%W为需要交叉的位数p=unidrnd(L-W+1);%随机产⽣⼀个交叉位置%fprintf('p=%d ',p);%交叉位置for i=1:Wx=find(A==B(1,p+i-1));y=find(B==A(1,p+i-1));[A(1,p+i-1),B(1,p+i-1)]=exchange(A(1,p+i-1),B(1,p+i-1));[A(1,x),B(1,y)]=exchange(A(1,x),B(1,y));endend%连点画图函数 plot_route.mfunction plot_route(a,R)scatter(a(:,1),a(:,2),'rx');hold on;plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);hold on;for i=2:length(R)x0=a(R(i-1),1);y0=a(R(i-1),2);x1=a(R(i),1);y1=a(R(i),2);xx=[x0,x1];yy=[y0,y1];plot(xx,yy);hold on;endend%染⾊体的路程代价函数 mylength.mfunction len=myLength(D,p)%p是⼀个排列[N,NN]=size(D);len=D(p(1,N),p(1,1));for i=1:(N-1)len=len+D(p(1,i),p(1,i+1));endend%变异函数 Mutation.mfunction a=Mutation(A)index1=0;index2=0;nnper=randperm(size(A,2));index1=nnper(1);index2=nnper(2);%fprintf('index1=%d ',index1);%fprintf('index2=%d ',index2);temp=0;temp=A(index1);A(index1)=A(index2);A(index2)=temp;a=A;end%适应度函数fit.m，每次迭代都要计算每个染⾊体在本种群内部的优先级别，类似归⼀化参数。
蚁群算法与遗传算法的混合算法蚁群算法（Ant Colony Optimization，ACO）和遗传算法（Genetic Algorithm，GA）都属于启发式算法的范畴，它们分别从不同的角度对问题进行建模和求解。
蚁群算法以模拟蚁群觅食行为为基础，通过信息素和启发式规则指导蚂蚁解空间；而遗传算法通过模拟进化过程，利用交叉和变异运算生成新的个体，并适应性地选择个体进行下一代的繁衍。
两者在解决问题时有各自的局限性，因此将两种算法相结合，形成混合算法，可以克服各自的缺点，实现更有效的求解。
蚁群算法具有较强的全局能力，但其速度较慢，且可能会陷入局部最优解。
而遗传算法能够在过程中较快地收敛到局部最优解，但有可能会陷入局部最优解无法跳出。
因此，将两者结合起来，可以同时利用蚁群算法的全局和遗传算法的局部特性。
混合算法的基本思想是，将蚁群算法作为全局策略，用于生成一组较优的解，然后利用遗传算法在这组解中进行局部优化，以寻找最优解。
整个混合算法的流程如下：1.初始化蚁群相关参数和遗传算法的相关参数，包括蚁群大小、信息素更新速率、遗传算法的种群大小、交叉和变异的概率等；2.使用蚁群算法生成一组初始解，并计算每个解的适应度；3.利用遗传算法从初始解中选择适应度较高的一部分个体，作为种群；4.对种群进行交叉和变异操作，生成下一代个体；5.计算下一代个体的适应度；6.如果满足停止条件（如达到指定迭代次数或找到满意解），则输出结果；否则，返回第3步，继续优化。
在混合算法中，蚁群算法和遗传算法的相互作用可以通过以下几种方式实现：1. 优选策略（Elitism）：将蚁群算法生成的一组解合并到遗传算法的种群中，在遗传算法的选择过程中保留一些蚁群算法生成的优秀个体，以避免遗传算法陷入局部最优解。
2.信息素启发式规则：将蚁群算法的信息素启发式规则应用于遗传算法的交叉和变异操作中，以指导交叉和变异过程中的方向，增加遗传算法的全局能力。
粒子群蚁群混合算法
粒子群蚁群混合算法是一种优化算法，将粒子群算法和蚁群算法相结合，利用它们各自的优点进行优化。
该算法通常用于解决复杂的优化问题，如多目标优化、非线性优化等。
在粒子群蚁群混合算法中，粒子群算法模拟了一群鸟或昆虫在搜索环境中的行为，通过粒子的位置和速度来探索解空间。
而蚁群算法则模拟了蚂蚁在寻找食物时的行为，通过蚂蚁遗留的信息素来引导搜索过程。
粒子群蚁群混合算法中，粒子群算法的速度和位置更新公式如下： $$v_i^{t+1} = wv_i^t + c_1r_1(pbest_i - x_i^t) +
c_2r_2(gbest - x_i^t)$$
$$x_i^{t+1} = x_i^t + v_i^{t+1}$$
其中，$v_i^t$表示粒子$i$在$t$时刻的速度，$x_i$表示粒子
$i$在$t$时刻的位置，$pbest_i$表示粒子$i$的个体最优解，$gbest$表示全局最优解，$w$是惯性因子，$c_1$和$c_2$是学习因子，$r_1$和$r_2$是随机数。
蚁群算法则通过信息素的更新和挥发来实现搜索过程，信息素更新公式如下：
$$tau_{ij}^{t+1} = (1-rho)tau_{ij}^t + Deltatau_{ij}^t$$ 其中，$tau_{ij}$表示从节点$i$到节点$j$的信息素浓度，$rho$是信息素挥发系数，$Deltatau_{ij}$是信息素增量。
粒子群蚁群混合算法中，将粒子群算法和蚁群算法的更新公式相
结合，实现了更加高效的搜索过程。
该算法的应用范围广泛，可用于机器学习、神经网络等领域的优化问题。
收稿日期:2008-02-29;修回日期:2008-04-14。
基金项目:国家863计划项目(2005AA1Z2060)。
作者简介:徐金荣(1982-),男,江苏泰州人,硕士研究生,主要研究方向:普适计算、人工智能、计算机网络; 李允(1971-),男,重庆人,副教授,博士,主要研究方向:普适计算、实时嵌入式操作系统; 刘海涛(1982-),男,江西萍乡人,硕士研究生,主要研究方向:嵌入式操作系统; 刘攀(1983-),男,湖北当阳人,硕士研究生,主要研究方向:计算机CAD 、人工智能。
文章编号:1001-9081(2008)08-2084-04一种求解TSP 的混合遗传蚁群算法徐金荣1,李 允1,刘海涛1,刘 攀2(1.西南交通大学信息科学与技术学院,成都610031; 2.西南交通大学CAD 中心,成都610031)(xu_jin_r ong@ )摘 要:结合遗传算法和蚁群算法,提出了一种求解TSP 的基于启发式遗传信息的蚁群遗传算法。
该算法由蚁群遗传算法和基于启发式遗传信息的蚁群算法两部分组成。
蚁群遗传算法将蚁群算法和遗传算法结合起来,提高了遗传算法的种群的多样性;基于启发式遗传信息的蚁群算法是将启发式遗传信息加入到蚁群算法中,防止蚁群算法对信息素过分依赖,缩小最优解的搜索空间。
HGI 2ACG A 算法是将启发式遗传信息加入到蚁群遗传算法中,可以提高蚁群算法的收敛速度和寻优能力。
实验结果表明,HGI 2ACG A 算法在收敛速度和收敛精度上均优于ACG A 和AC A 算法。
关键词:遗传算法;蚁群算法;信息素;启发式遗传信息;旅行商问题中图分类号:TP301.6 文献标志码:AHybr i d geneti c an t colony a lgor ithm for traveli n g s a les man problemXU J in 2r ong 1,L I Yun 1,L IU Hai 2tao 1,L IU Pan2(1.School of Infor m ation Science and Technology,Southw est J iaotong U niversity,Chengdu S ichuan 610031,China ;2.CAD Center ,Southw est J iaotong U niversity,Chengdu S ichuan 610031,China )Abstract:A ne w Heuristic Genetic I nf or mati on based Ant Col ony Genetic A lgorith m (HGI 2ACG A )t o s olve Traveling Sales man Pr oble m s (TSP )was p r oposed .HGI 2ACG A ’s t w o sub 2algorith m s are Ant Col ony Genetic A lgorith m (ACG A )and Heuristic Genetic I nf or mati on based Ant Col ony A lgorith m (HGI 2ACA ).ACG A enhances genetic algorith m ’s populati on diversity and reduces the search domain,while HGI 2ACA eli m inates the creati on of invalid t ours and als o avoids depending on pher omone excessively .A combinati on of genetic inf or mati on and pher omone leads t o a significant i m p r ovement inperfor mance .The strategy of HGI 2ACG A algorith m can i m p r ove convergence rate and capacity of searching op ti m al s oluti on .Experi m ental results show that the p r oposed algorith m generally exhibits a better s oluti on and a higher rate of convergence f or TSP than ACG A and ACA.Key words:Genetic A lgorith m (G A );Ant Col ony A lgorith m (AC A );pher omone;heuristic genetic infor mati on;Traveling Sales man Pr oble m (TSP )0 引言TSP 问题即给定一组N 个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。
动态蚁群遗传混合算法1动态蚁群遗传混合算法的研究及应用（河北工程学院，河北邯郸 056038）摘要：蚁群算法是一种源于大自然生物世界的仿生类算法，该算法采用分布式并行计算和正反馈机制。
易于与其他方法结合，具有很强的鲁棒性和适应性，但存在搜素时间长、易陷入局部最优解的缺点。
为了克服这一缺点, 文中给出一种新的蚁群算法——动态蚂蚁遗传混合算法。
在基本蚁群算法中引入变异机制, 采用最佳融合点评估策略来交叉地调用两种算法。
动态地控制遗传算法与蚂蚁算法的调用时机，并设计了相应的信息素更新方法，有效减少了算法的冗余迭代次数，提高了搜索速度,同时引入迭代调整阈值控制算法后期的遗传操作和蚂蚁规模，加快了种群进化速度，从而更快地找到最优解。
该法具有较快的收敛速度，节省计算时间，实验结果表明该方法是行之有效的。
关键词：蚁群算法; TSP问题; 遗传算法; 动态蚂蚁遗传混合算法1 引言蚁群算法 (Ant Colony Algorithms，ACO）又称蚂蚁算法。
是一种用来在图中寻找优化路径的机率型技术。
蚂蚁在寻找食物时，总是能找到较短的路径。
受到蚁群系统信息共享机制的启发，意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该算法应用到求解旅行商问题（TSP)和二次分配问题（QAP)中。
取得了一系列较好的实验结果。
解决一些实际问题也有很好的效果。
但蚁群算法同其它生物进化算法一样存在过早收敛易陷入局部极小值等问题。
结合其它优化算法形成混合蚁群算法是克服这些缺点的有效手段。
遗传算法(genetic algorithm，GA)以决策变量的编码作为运算对象，在优化过程中借鉴生物学中染色体和基因的概念，模拟自然界中生物和遗传进化等机理，通过个体适应度来进行概率选择操作，通过交叉变异产生新的个体，从而遗传算法具有较强的全局性。
为克服蚁群算法搜索速度慢、易陷入局部最优等缺点。
本文提出了一种新的动态蚁群遗传混合算法(Dynamic Ant Algorithm -Genetic Algorithm，DAAGA)。
该算法采用最佳融合点评估策略来交叉地调用两种算法，其框架是用蚂蚁算法的解作为遗传操作的种子，每当种群进化接近停滞时，调用蚂蚁算法。
这种结构可以动态地控制遗传算法和蚂蚁算法的调用时机，再配合相应的信息素更新方法，可以提高算法的收敛速度和收敛性能；同时这种算法还引入了迭代调整阈值来控制算法后期的遗传操作和蚂蚁规模，即在种群已进化至最优解附近，遗传算法作用减少时，只做变异操作以减少算法计算工作量，增加蚂蚁规模以更快地找到最优解。
2 基本蚁群算法的原理蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。
它是从对蚁群行为的研究中产生的。
自然界中，诸如蚂蚁、蜜蜂等群居昆虫，虽然个体昆虫的行为极其简单，但由单个简单的个体所组成的群体却表现出非常复杂有序的集体行为。
经过大量观察研究，仿生学家发现，蚂蚁个体之间通过一种称之为信息素( pheromone) 的物质进行信息传递。
从而能相互协作，完成复杂的任务。
蚁群算法计算过程主要包括两个阶段：信息素的积累阶段和蚂蚁间的相互协作阶段，前者包括各候选解积累的信息不断调整自身结构的过程，即蚂蚁不断选择从信息素量大的路径上通过，使得此路径上蚂蚁留下的信息素越来越大，而信息素量小的路径，则蚂蚁选择的概率越来越小，会逐渐被淘汰；在蚂蚁的协作阶段，候选解相互间用过信息交流，一起发现更为优越的路径，产生更优的解。
通过人工模拟蚂蚁搜索食物的过程，我们称这种算法为“人工蚁群算法”。
为了说明人工蚁群系统的原理, 我们先简要介绍一下蚂蚁搜索食物的具体过程。
这里用图1形象说明自然界蚂蚁的觅食行为，图2形象说明“人工蚁群算法”的路径搜素原理和机制。
Fig. 1. An example with real anta) Ants follow a path between points A and E.b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability.c) On the shorter path more pheromone is laid down.Fig. 2. An example with artificial antsa) The initial graph with distances.b) At time t=0 there is no trail on the graph edges; therefore, ants choose whether to turn right or left with equal probability.c) At time t=1 trail is stronger on shorter edges, which are therefore, in the average, preferred by ants.2.1基本蚁群算法的数学模型蚁群算法的寻优是在有向图G'=(C,L,Γ)上通过三个准则（转移概率准则、局部调整准则和全局信息素调整准则）加以实现的。
（1）转移概率准则：[][][][])1(,,0)()()()()(k k ir ir ij ij k ij allowed s allowed j t t t t t p allowedk N ⊂∈⎪⎪⎩⎪⎪⎨⎧=∑⊂，否则βαβαητητ 其中allowed k ={C-tabu k }表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，τij (t)为从i 城市到j 城市的路径信息素。
α表示轨迹的相对重要性，α值越大，蚂蚁选择该路径的可能性就越大。
如果α过大其选择的随机性就越小，容易陷入局部最优解，反之α过小易造成算法收敛程度过慢；β为期望启发式因子，表示能见度的相对重要性,β越大，则该状态状态转移概率越接近于贪心规则；ηij (t)为启发函数,ηij (t) =1/d ij ；式中d ij 表示相邻两个城市之间的距离。
对蚂蚁k 而言，d ij 越小，则ηij (t)越大，p ijk 也就越大。
显然，该启发函数表示蚂蚁从元素（城市）i 转移到元素（城市）j 的期望程度。
（2）局部调整准则这种局部调整准则模仿了真实世界的外激素挥发原则，随着时间的推移而历史信息素逐步挥发。
蚁群算法中，经过h 个时刻，两个元素状态之间的局部信息素数量可根据以下调整： )2()/(1)()1()(m in 00nl t h t ijij =+-=+τξττξτ其中，[]1,0⊂ξ，min l 表示集合C 中量个最近元素之间的距离。
（3）全局信息素调整准则（t+n ）时刻在路径(i, j)上的信息量可按如下规则进行调整)4()()()3()()()1()(1t t t t n t m k k ij ij ij ij ij ∑=∆=∆∆+-=+ττττρτ 式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累， ρ的取值范围为[0，1), Δτij (t)表示本次循环中路径(i, j)上的信息素增量，初始时刻 Δτij (t) =0, Δτijk (t) 表示第k 只蚂蚁在本次循环中留在路径(i, j)上的信息量。
Ant-Cycle 模型对)(t kij τ∆的定义 ⎪⎩⎪⎨⎧=∆）（否则）过（只蚂蚁在本次循环中经若第5,0,)(,j i k K kij L Q t τ 2.2以基本蚁群算算法求解TSP 问题为例，具体步骤如下：(1)参数初始化。
令时间t=0和循环次数Nc=0，设置最大循环次数Ncmax, 将m 个蚂蚁置于n 个元素(城市)上，令有向图上每条边(i, j)的初始化信息量τij (t)=const, 其中const 表示常数，且初始时刻Δτij(0)=0(2)循环次数Nc ← Nc+1。
(3)蚂蚁的禁忌表索引号k=1。
(4)蚂蚁数目 k ←k+1 。
(5)如果到了算法规定的H 时刻，根据式（2）进行信息素挥发。
(6)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市)j 并前，{}ktabu C j -∈。
(7)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。
(8)若集合C 中元素(城市)未遍历完，即k<m ，则跳转到第(4)步，否则执行第(8)步。
(9)根据公式(3)和式(4)更新每条路径上的信息量。
(10)若满足结束条件，即如果循环次数Nc ≥ Ncmax 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。
3 蚁群遗传混合算法原理及流程3.1最佳融合点评估策略传统的蚂蚁遗传混合算法使算法整体收敛速度偏慢。
对此，本文提出一种最佳融合点评估策略来交叉地调用两种算法。
首先，用蚂蚁算法的解作为遗传操作的种子，优化遗传算法的初始种群，再用最佳融合点评估策略来判断是否调用蚂蚁算法，一旦进化的种群满足最佳融合点的条件，则开始调用蚂蚁算法，运用蚂蚁算法局部寻优能力强的特点继续寻找最优解。
这种动态交叉调用的策略可以更好地结合两种算法的优点，使这种DAAGA 算法可以得到全局搜素速度和局部寻优最强的特点。
最佳融合点评估策略来交叉地调用两种算法具体步骤如下：步骤1：调用蚂蚁算法，生成初始种群，更新全局最优解。
步骤2：用蚂蚁算法生成的解种群和全局最优解作为遗传操作的种子，优化遗传算法的初始种群。
步骤3：开始遗传操作，灭此生成的种群都用最佳融合点评估策略来进行评估，看是否转向蚂蚁算法。
最佳融合点评估策略如下。
（1）是指遗传操作的最小迭代次数min NG 和最大迭代次数max NG ( max min NG NG <)（2)在设定的迭代次数范围内，如果连续n 代，都满足)6(1-∆<∆n f f n其中，n n n f f f --=∆m ax （nf max 表示遗传算法第n 代种群的最大适应度值，nf -表示遗传算法第n 代种群的平均适应度值）3.2信息素更新方法的改进动态蚁群遗传算法，从遗传算法每一代种群中找出最优的个体，以此作为启发信息来再次更新信息素。
同时，由于新算法采用最佳融合点评估策略来保证了算法的种群进化方向，与传统方法相比该法可更快地反应出各路径的优劣，以尽快找到最优解。
设L gb 为现有种群中最优解的值，在全局最优解更新信息素时，L gb 设定为全局最优解的值，则利用蚂蚁算法的解。
遗传算法每代最优个体以及全局最优解来更新信息素的规则如下：)7(/1)()()()1(gb best best L t t t t ij ij =∆∆+=+ττρττ其中3.3迭代调整阈值设计遗传算法有良好的全局收敛性，蚁群算法有良好的局部寻优能力。
