遗传算法与蚂蚁算法的融合

一种遗传蚁群融合算法的函数优化求解问题摘要:遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索方法,可直接对结构对象进行操作,但是如果兼顾收敛速度和解的品质两个指标,单纯的遗传算法未必表现出原理本身的优越性。

针对上述问题,提出一种新的遗传蚁群融合算法,利用蚁群算法的正反馈机制,来提高遗传算法运行的速度和效率,从而更好更快的解决函数优化求解问题。

关键词:遗传算法蚁群算法算法融合函数优化遗传算法[1](genetic algorithm,GA)是一种模拟自然选择和遗传进化机制的优化算法,它是由美国Michigan大学的Holland教授于20世纪70年代提出的。

它的主要特点是简单、通用、鲁棒性强,适用于并行分布处理,应用范围广。

蚁群算法[2](ant colony algorithm,ACA)是由意大利学者Dorigo于20世纪90年代初在他自己的博士论文中提出。

它是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法,该算法采用了正反馈并行自催化机制,具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法结合等优点。

但是它的缺点是运算初期信息素匮乏,求解速度缓慢。

优化问题的求解在遗传算法研究中占很大比重,诸如TSP等组合优化问题一直是遗传算法十分活跃的研究课题。

尽管遗传算法比其它传统搜索方法有更强的鲁棒性,但它对于算法计算过程中的反馈信息却没有利用,往往由此导致无为的冗余迭代,从而使得求解的效率不断降低。

且遗传算法更善长全局搜索而局部搜索能力却不足。

遗传算法可以用极快的速度达到最优解的90%左右,但要达到真正的最优解则要花费很长的时间。

一些对比实验还表明,如果兼顾收敛速度和解的品质两个指标,单纯的遗传算法方法未必比其它搜索方法更优越。

为此,除了要进一步改进基本理论和方法外,还要采用和神经网络、模拟退火或专家系统等其它方法结合的策略。

许多研究结果表明,采用这种混合模型可有效提高遗传算法的局部搜索能力,从而进一步改善其收敛速度和解的品质。

动态蚁群遗传混合算法的研究及应用（河北工程学院，河北邯郸056038）摘要：蚁群算法是一种源于大自然生物世界的仿生类算法，该算法采用分布式并行计算和正反馈机制。

易于与其他方法结合，具有很强的鲁棒性和适应性，但存在搜素时间长、易陷入局部最优解的缺点。

为了克服这一缺点, 文中给出一种新的蚁群算法——动态蚂蚁遗传混合算法。

在基本蚁群算法中引入变异机制, 采用最佳融合点评估策略来交叉地调用两种算法。

动态地控制遗传算法与蚂蚁算法的调用时机，并设计了相应的信息素更新方法，有效减少了算法的冗余迭代次数，提高了搜索速度,同时引入迭代调整阈值控制算法后期的遗传操作和蚂蚁规模，加快了种群进化速度，从而更快地找到最优解。

该法具有较快的收敛速度，节省计算时间，实验结果表明该方法是行之有效的。

关键词：蚁群算法; TSP问题; 遗传算法; 动态蚂蚁遗传混合算法1 引言蚁群算法 (Ant Colony Algorithms，ACO）又称蚂蚁算法。

是一种用来在图中寻找优化路径的机率型技术。

蚂蚁在寻找食物时，总是能找到较短的路径。

受到蚁群系统信息共享机制的启发，意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该算法应用到求解旅行商问题（TSP)和二次分配问题（QAP)中。

取得了一系列较好的实验结果。

解决一些实际问题也有很好的效果。

但蚁群算法同其它生物进化算法一样存在过早收敛易陷入局部极小值等问题。

结合其它优化算法形成混合蚁群算法是克服这些缺点的有效手段。

遗传算法(genetic algorithm，GA)以决策变量的编码作为运算对象，在优化过程中借鉴生物学中染色体和基因的概念，模拟自然界中生物和遗传进化等机理，通过个体适应度来进行概率选择操作，通过交叉变异产生新的个体，从而遗传算法具有较强的全局性。

为克服蚁群算法搜索速度慢、易陷入局部最优等缺点。

本文提出了一种新的动态蚁群遗传混合算法(Dynamic Ant Algorithm -Genetic Algorithm，DAAGA)。

《基于遗传—蚁群融合算法的聚类算法研究》篇一基于遗传-蚁群融合算法的聚类算法研究一、引言聚类算法作为数据挖掘和机器学习领域的重要技术，广泛应用于图像处理、模式识别、生物信息学等多个领域。

然而，传统的聚类算法在处理大规模、高维度的数据时，往往存在计算复杂度高、聚类效果不佳等问题。

为了解决这些问题，本文提出了一种基于遗传-蚁群融合算法的聚类算法，通过融合遗传算法和蚁群算法的优点，提高聚类的准确性和效率。

二、相关技术背景1. 遗传算法：遗传算法是一种模拟自然进化过程的优化算法，通过模拟生物进化过程中的选择、交叉、变异等操作，实现对问题空间的搜索和优化。

2. 蚁群算法：蚁群算法是一种模拟蚂蚁觅食过程中信息素传递的优化算法，通过模拟蚂蚁的信息素传递和协作行为，实现对问题的求解。

3. 聚类算法：聚类算法是一种无监督学习方法，将数据划分为若干个簇，使得同一簇内的数据相似度高，不同簇间的数据相似度低。

三、基于遗传-蚁群融合算法的聚类算法1. 算法思想本算法融合了遗传算法和蚁群算法的优点，通过遗传算法的全局搜索能力和蚁群算法的局部优化能力，实现对聚类问题的求解。

具体思想如下：（1）初始化：随机生成一定数量的聚类中心，作为初始解集。

（2）编码与解码：将聚类中心编码为染色体，通过遗传操作生成新的染色体，解码得到新的聚类中心。

（3）适应度评价：根据聚类效果评价函数，计算每个染色体的适应度。

（4）选择、交叉、变异：根据适应度选择优秀的染色体进行交叉、变异操作，生成新的解集。

（5）蚁群局部优化：在遗传算法的基础上，利用蚁群算法对聚类结果进行局部优化，提高聚类的准确性。

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，每次迭代都要计算每个染⾊体在本种群内部的优先级别，类似归⼀化参数。

收稿日期:2006-07-20;修返日期:2006-09-08 基金项目:国家自然科学基金资助项目(60473012)作者简介:刘萍(1981-),女,江苏泰兴人,硕士研究生,主要研究方向为信息安全(yzuliuping@sina .com);高飞(1980-),男,江苏南通人,硕士研究生,主要研究方向为信息安全;杨云(1957-),男,江苏扬州人,副教授,博士,主要研究方向为网络安全、分布式路由、QoS 路由.基于遗传算法和蚁群算法融合的QoS 路由算法*刘 萍,高 飞,杨 云(扬州大学计算机科学与工程系,江苏扬州225009)摘 要:面向QoS 路由问题,设计了一种基于遗传算法和蚁群算法融合的QoS 路由算法(QoS rout ing algorit hm according to t he com bination of the genetic algorithm and ant colony algorit hm,GAACO_QoS)。

利用遗传算法生成初始解,将其转换为蚁群算法所需的信息素初值,然后利用蚁群算法求取最优解。

设置遗传算法控制函数来控制遗传算法和蚁群算法融合的适当时机。

通过与遗传算法以及蚁群算法的比较,进一步说明算法的有效性。

关键词:遗传算法;蚁群算法;服务质量路由中图分类号:TP 393 文献标志码: A 文章编号:1001-3695(2007)09-0224-04QoS rou ting algorithm ba sed on th e com bina tion of genetic algor it hman d ant colony algorithmLIU Ping,GAO Fei,YAN G Yun(Dept.of Comp uter S cience &E ngineering,Yangz hou Univer sity,Yangzhou Jiangs u 225009,C hina)Abst ract :For t he QoS rout ing problem,this pa per des ig ned a QoS routing a lg orithm according t o the com bina tion of the ge-netic algorithm and a nt colony a lg orit hm (GAACO_QoS ).Ta king a dva nt ag e of g enet ic algorit hm wa s used t o produce the origi-na l res ults,t hey were t ra nsform ed int o the init ia l pherom ones v alue needed by ant colony a lg orithm ,then ant colony a lg orithm t o g et t he bes t result s.The definition of the genetic a lg orithm cont rol funct ion was to control t he a ppropriat e com bina tion oppor-t unit y of t he two algorithm s.The va lidit y of t he algorit hm w as illum inat ed when com pa red t o t he genetic algorit hm a nd the a nt colony algorit hm .Key words:genet ic a lg orit hm ;ant colony algorit hm ;QoS rout ing 随着Internet 的发展,接入Int ernet 的用户业务也趋于多样化,并具有明确的QoS 需求。

蚁群算法与遗传算法的混合算法蚁群算法（Ant Colony Optimization，ACO）和遗传算法（Genetic Algorithm，GA）都属于启发式算法的范畴，它们分别从不同的角度对问题进行建模和求解。

蚁群算法以模拟蚁群觅食行为为基础，通过信息素和启发式规则指导蚂蚁解空间；而遗传算法通过模拟进化过程，利用交叉和变异运算生成新的个体，并适应性地选择个体进行下一代的繁衍。

两者在解决问题时有各自的局限性，因此将两种算法相结合，形成混合算法，可以克服各自的缺点，实现更有效的求解。

蚁群算法具有较强的全局能力，但其速度较慢，且可能会陷入局部最优解。

而遗传算法能够在过程中较快地收敛到局部最优解，但有可能会陷入局部最优解无法跳出。

因此，将两者结合起来，可以同时利用蚁群算法的全局和遗传算法的局部特性。

混合算法的基本思想是，将蚁群算法作为全局策略，用于生成一组较优的解，然后利用遗传算法在这组解中进行局部优化，以寻找最优解。

整个混合算法的流程如下：1.初始化蚁群相关参数和遗传算法的相关参数，包括蚁群大小、信息素更新速率、遗传算法的种群大小、交叉和变异的概率等；2.使用蚁群算法生成一组初始解，并计算每个解的适应度；3.利用遗传算法从初始解中选择适应度较高的一部分个体，作为种群；4.对种群进行交叉和变异操作，生成下一代个体；5.计算下一代个体的适应度；6.如果满足停止条件（如达到指定迭代次数或找到满意解），则输出结果；否则，返回第3步，继续优化。

在混合算法中，蚁群算法和遗传算法的相互作用可以通过以下几种方式实现：1. 优选策略（Elitism）：将蚁群算法生成的一组解合并到遗传算法的种群中，在遗传算法的选择过程中保留一些蚁群算法生成的优秀个体，以避免遗传算法陷入局部最优解。

2.信息素启发式规则：将蚁群算法的信息素启发式规则应用于遗传算法的交叉和变异操作中，以指导交叉和变异过程中的方向，增加遗传算法的全局能力。

《工业控制计算机》2011年第24卷第2期*安徽财经大学信息工程学院青年教师项目（xgky2008003）；安徽财经大学校级科研项目（ACKYQ0947ZC ）融合遗传算法和蚁群算法动态网格任务调度算法研究*孙玉涛毕殿杰（安徽财经大学信息工程学院计算机科学与技术系，安徽蚌埠233041）Genetic Algorithm and Ant Colony Algorithm for Dynamic Grid Task Scheduling本文将遗传算法和蚁群算法相结合，利用遗传算法前期收敛速度快的特点，进行前期的训练；而得到的信息素作为蚁群算法的初始值，进一步进行搜索收敛，最终得到最优或次优调度方案。

结合网格任务调度的特点，本文借鉴将遗传算法和蚁群算法动态融合应用于软硬件划分的思想，选取优化的遗传算法和蚁群算法的参数设置，将问题转换到网格计算任务调度问题上来，提出融合遗传算法和蚁群算法的网格任务调度算法。

其基本思路是算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布。

算法后期采用蚁群算法，在有一定初始信息素分布的情况下，充分利用蚁群算法并行性、正反馈性、求精解效率高等特点。

其总体框架如图1所示。

图1总体框架1任务调度问题描述求解网格计算任务调度问题时，通常用有向无环图（DAG ）来描述，如图2所示。

在DAG 图中，每个子任务用一个圆圈表示，圈中分数的分子T 表示任务号，分母Q 表示计算量，而DAG 图中的箭头表示子任务之间的优先关系，C （i ，j ）表示任务T i 与T j 之间的通信量。

箭头从前驱指向后继，前驱是后继的必要条件，只有在某个任务的所有前驱都完成的条件下，该任务才能被执行。

将子任务表示成DAG 图之后，可以得到各种任务分配方案，这些分配方案的效率是不同的，需要进行优化。

如图3是根据任务划分得到的分配到三个计算结点的一种方案。

设有n 个计算结点所组成的网格系统P＝邀P 1，P 2，…，P n 妖，每个结点P j 处理能力为r 。

《基于遗传—蚁群融合算法的聚类算法研究》篇一基于遗传-蚁群融合算法的聚类算法研究一、引言随着大数据时代的到来，聚类算法在数据分析和处理中扮演着越来越重要的角色。

遗传算法和蚁群算法作为两种经典的优化算法，各自在聚类问题中表现出良好的性能。

然而，传统的聚类算法往往在处理复杂数据时存在局限性。

因此，本文提出了一种基于遗传-蚁群融合算法的聚类算法，旨在提高聚类的准确性和效率。

二、相关研究概述遗传算法是一种模拟自然进化过程的优化算法，具有较强的全局搜索能力。

蚁群算法则是一种模拟蚂蚁觅食行为的优化算法，具有较强的局部搜索能力和自适应性。

这两种算法在聚类问题中均有所应用，但各自存在局限性。

遗传-蚁群融合算法则是将这两种算法的优势结合起来，以提高聚类的效果。

三、遗传-蚁群融合算法的聚类算法设计1. 算法框架本文提出的基于遗传-蚁群融合算法的聚类算法主要包括三个步骤：初始化、遗传操作和蚁群操作。

在初始化阶段，算法随机生成初始聚类中心；在遗传操作阶段，通过遗传算法优化聚类中心；在蚁群操作阶段，利用蚁群算法优化聚类结果。

2. 遗传操作遗传操作包括选择、交叉和变异三个步骤。

在选择阶段，根据适应度函数选择优秀的个体；在交叉阶段，对选中的个体进行交叉操作，生成新的个体；在变异阶段，对个体进行随机变异，增加种群的多样性。

通过遗传操作，算法可以全局地搜索最优的聚类中心。

3. 蚁群操作蚁群操作主要利用蚁群算法的局部搜索能力和自适应性。

在蚁群操作阶段，每个蚂蚁根据当前的信息素和启发式信息选择下一个聚类中心，并通过信息素的更新机制逐步优化聚类结果。

蚁群操作可以在局部范围内搜索更优的聚类结果。

四、实验与分析为了验证本文提出的基于遗传-蚁群融合算法的聚类算法的有效性，我们进行了多组实验。

实验结果表明，该算法在处理复杂数据时具有较高的准确性和效率。

与传统的聚类算法相比，该算法在聚类效果和稳定性方面均有所提高。

此外，我们还对算法的参数进行了敏感性分析，以确定最佳参数组合。

蚁群算法与其他算法的混合大摘要自从上世纪50 年代中期创立仿生学以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划等，并成功应用于解决实际问题。

由意大利学者M.Dorigo，VManiezzo，A.Colorni 于1992 年首先提出的蚁群系统(Ant Colony System ，ACS )，是一种新颖的仿生进化算法，适用于求解复杂组合优化问题。

目前，蚁群系统己成功应用于求解旅行商问题(TSP)、二次分配问题和job-shop调度问题等，取得了很好的实验效果。

受其影响，蚁群系统的研究已经逐渐引起了更多学者和专家的关注。

虽然，该研究方法处于研究的初级阶段，但是一些研究成果已经显示出蚁群系统在求解复杂优化问题方面的优越性。

作为一种全局搜索的方法，蚁群算法具有正反馈性、并行性、分布性、自组织性等特点。

但是，蚁群算法也存在一些不足之处:例如，算法需要较长的搜索时间、容易出现早熟停滞现象等。

针对上述不足，我们在深入研究蚁群算法的同时，又对免疫算法和禁忌搜索等算法进行了一定的分析和研究，提出了几种新的用于求解旅行商问题(TSP)的蚁群改进算法。

旨在借鉴其他仿生算法的长处，利用其优点弥补蚁群算法的不足，从而提高蚁群算法的求解性能。

本文的主要内容包括：首先，针对蚁群算法中的个体蚂蚁缺乏识别问题特征信息的能力，将免疫算法中疫苗的思想引入到蚁群算法中，新算法从TSP 问题本身出发，提取出该问题的一种本质特征，将此特征信息作为疫苗注射给精英蚂蚁，使其具有“免疫”的能力，能识别该固有特征，以提高精英蚂蚁的搜索质量，从而使得整体的求解能力得以提高。

其次，因为蚁群算法容易出现早熟停滞，而禁忌搜索算法可以接受劣解，搜索时能跳出局部最优解，转向解空间的其他解，从而获得更好的全局最优解。

故将两种算法混合，用蚁群算法作全局搜索，禁忌搜索算法作局部搜索。

第40卷第9期2003年9月计算机研究与发展JOURNAL OF COM PUTER RESEARCH AND DEVELOPM EN TVol .40,No .9Sep .2003　收稿日期:2002-10-23;修回日期:2003-06-12　基金项目:国家自然科学基金(60174021);天津自然科学基金重点项目(013800711);河南科技攻关项目(0124140141)遗传算法与蚂蚁算法的融合丁建立　陈增强　袁著祉(南开大学信息技术科学学院　天津　300071)(jianliding @yahoo .com .cn )摘　要　遗传算法具有快速随机的全局搜索能力,但对于系统中的反馈信息利用却无能为力,当求解到一定范围时往往做大量无为的冗余迭代,求精确解效率低.蚂蚁算法是通过信息素的累积和更新收敛于最优路径上,具有分布式并行全局搜索能力.但初期信息素匮乏,求解速度慢.算法是将遗传算法与蚂蚁算法融合,采用遗传算法生成信息素分布,利用蚂蚁算法求精确解,优势互补.仿真表明取得了非常好的效果.关键词　遗传算法;蚂蚁算法;融合;中图法分类号　TP301;T P18On the Combination of Genetic Algorithm and Ant AlgorithmDING Jian -Li ,CHEN Zeng -Qiang ,and YUAN Zhu -Zhi(College of Information Technology and Science ,Nankai University ,Tianjin 300071)Abstract Genetic algo rithm has the ability of doing a global searching quickly and stochastically .But it can 't m ake use of enough system output information .It has to do a large redundancy repeat for the result w hen solving to certain scope .So the efficiency to solve precisio n results is reduced .Ant algorithm con -verges on the optimization path throug h inform ation pheromo ne accumulation and renew al .It has the abili -ty of parallel processing and global searching .The speed at w hich the ant algo rithm gives the solution is slow ,because there is little information pheromone on the path early .The alg orithm in this paper is based on the combination of genetic alg orithm and ant algorithm .First ,it adopts genetic algorithm to give infor -mation pheromone to distribute .Second ,it m akes use of the ant algorithm to give the precision of the solu -tion .Finally ,it develops enough advantage of the tw o algorithms .The simulation results show that very nice effects are obtained .Key words genetic algorithm ;ant algo rithm ;combination1　引 言启发式智能化方法近年来愈来愈引起了众多学者的关注和兴趣.诸如神经网络、模拟退火、禁忌搜索、遗传算法、蚂蚁算法、DNA 计算等,它们毫无争议地成为解决组合爆炸及NP 类问题的锐利工具.然而,面对各种问题的特殊性和复杂性,每一种算法都表现其自身的优势和缺陷,都会面临时间性能和优化性能的双重挑战[1].遗传算法是由美国密执安大学的John Holland教授于1975年首先提出的一类仿生型优化算法.它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上,子代是父代遗传基因在染色体上的有序排列”为基础,模拟生物界进化过程.其优点是:①具有大范围全局搜索的能力,与问题领域无关;②搜索从群体出发,具有潜在的并行性;可进行多值比较,鲁棒性强;③搜索使用评价函数启发,过程简单;④使用概率机制进行迭代,具有随机性;⑤具有可扩展性,容易与其他算法结合.其缺点是:对于系统中的反馈信息利用不够[2],当求解到一定范围时往往做大量无为的冗余迭代,求精确解效率低.蚂蚁算法(ant algorithm,AA)是近年来刚刚诞生的随机优化方法,它是一种源于大自然的新的仿生类算法.它是意大利学者M.Do rigo等最早提出[3,4]的,蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的,最初又称蚁群优化方法(ant colony optimization,ACO).由于模拟仿真中使用了人工蚂蚁的概念,因此亦称蚂蚁系统(ant sys-tem,AS).其优点是:①其原理是一种正反馈机制或称增强型学习系统,它通过信息素的不断更新达到最终收敛于最优路径上;②它是一种通用型随机优化方法,但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能;③它是一种分布式的优化方法,不仅适合目前的串行计算机,而且适合未来的并行计算机;④它是一种全局优化的方法,不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题.其缺点是:初期信息素匮乏,求解速度慢[5].本文算法是将遗传算法与蚂蚁算法的融合,采用遗传算法生成信息素分布,利用蚂蚁算法求精确解,优势互补,期望获得优化性能和时间性能的双赢.2　蚂蚁算法的优化机理及模型描述2.1　蚂蚁算法的优化机理蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径,并且能随环境的变化而变化,适应性地搜索新的路径,产生新的选择.其根本原因是蚂蚁在寻找食物源时,能在其走过的路上释放一种特殊的分泌物———信息素(pheromone,随着时间的推移该物质会逐渐挥发),后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.当一定路径上通过的蚂蚁越来越多时,其留下的信息素轨迹也越来越多,后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度.而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制.通过这种正反馈机制,蚂蚁最终可以发现最短路径.特别地,当蚂蚁巢穴与食物源之间出现障碍物时,蚂蚁不仅可以绕过障碍物,而且通过蚁群信息素轨迹在不同路径上的变化,经过一段时间的正反馈,最终收敛到最短路径上[6,7].2.2　蚂蚁圈模型蚂蚁圈模型是全局优化较好的蚂蚁算法,假如路径(i,j)在t时刻信息素轨迹强度为τij,蚂蚁k 在路径(i,j)上留下的单位长度轨迹信息素数量Δτk ij,轨迹的持久性ρ(0≤ρ<1),则轨迹强度的更新方程[6,8]为τij(t+1)=ρ·πij(t)+∑Δτk ij(t). 设Z k为第k只蚂蚁在本次循环中所走的路径的长度,则Δτk ij(t)=Q/Z k,其中Q是一个常数[5,6].如果设ηij为边路径(i,j)的能见度,一般取为1/d ij,这里d ij为路径(i,j)的长度,路径可见度的相对重要性β(β≥0),路径轨迹的相对重要性α(α≥0),U为可行顶点集,蚂蚁k在t时刻的转移概率为p k ij(t),则p k ij(t)可定义[6,8]如下p k i j(t)=[τij(t)]α[ηij]β∑l∈U[τil(t)]α[ηil]β,　j∈U,0,其他.2.3　MMAS(max-min ant system)算法MM AS算法是比利时学者Thomas Stutzle提出的[8],它对基本蚂蚁算法(AS)进行了3点改进[9]:①为了更加充分地进行寻优,各路径信息素初值设为最大值τmax;②一圈中只有最短路径的蚂蚁才进行信息素修改增加,这与AS蚂蚁圈模型调整方法相似;③为了避免算法过早收敛非全局最优解,将各路经的信息素浓度限制在[τmin,τmax]之间,超出这个范围的值被强制设为τmin或者τmax.从实验结果看,MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进.3　遗传算法与蚂蚁算法的融合(GAAA)3.1　GAAA算法的设计思想及总体框架遗传算法与蚂蚁算法的融合(genetic algorithm-ant algorithm,GAAA),其基本思想是汲取两种算法的优点,克服各自的缺陷,优势互补.在时间效率上优于蚂蚁算法,在求精解效率上优于遗传算法,是时间效率和求解效率都比较好的一种新的启发式方法.其基本思路是算法前过程采用遗传算法,充分利用遗传算法的快速性、随机性、全局收敛性,其结1352计算机研究与发展2003年果是产生有关问题的初始信息素分布.算法后过程采用蚂蚁算法,在有一定初始信息素分布的情况下,充分利用蚂蚁算法并行性、正反馈性、求精解效率高等特点.其总体框架如图1所示:图1　GA AA 算法总体框架3.2　GAAA 中遗传算法的定义与设置编码与适应值函数:结合解决问题,采用十进制实数编码,适应值函数结合目标函数而定.如TSP 问题,以城市的遍历次序作为遗传算法的编码,适应度函数取为哈密顿圈的长度的倒数.种群生成与染色体选择:利用rand 函数随机生成一定数量的十进制实数编码种群,根据适应值函数选择准备进行交配的一对染色体父串.交叉算子:采用Davis 提出的顺序交叉方法,先进行常规的双点交叉,再进行维持原有相对访问顺序的巡回路线修改.具体交叉如下:①随机在父串上选择一个交配区域,如两父串选定为old 1=12 3456 789,old 2=98 7654 321.②将old 2的交配区域加到old 1前面,将old 1的交配区域加到old 2的前面:old 1′=7654 123456789,old 2′=3456 987654321.③依次删除old 1′,old 2′中与交配区相同的数码,得到最终的两子串:new 1=765412389,new 2=345698721.变异算子:采用逆转变异方法[5],所谓“逆转”,如染色体(1—2—3—4—5—6)在区间2—3和区间5—6处发生断裂,断裂片段又以反向顺序插入,于是逆转后的染色体变为(1—2—5—4—3—6).这里的“进化”,是指逆转算子的单方向性,只有经逆转后,适应值有提高的才接受下来,否则逆转无效.3.3　GAAA 中蚂蚁算法的改进与衔接信息素的初值设置:MM AS 是把各路径信息素初值设为最大值τmax ,这里我们通过遗传算法得到了一定的路径信息素,所以把信息素的初值设置为τS =τC +τG . 这里,τC 是一个根据具体求解问题规模给定的一个信息素常数,相当于M MAS 算法中的τm in ,τG 是遗传算法求解结果转换的信息素值.信息素更新模型:采用蚂蚁圈模型进行信息素更新,即一圈中只有最短路径的蚂蚁才进行信息素修改增加.而所有路径的轨迹更新方程均采用:τij (t +1)=ρ·τij (t )+∑Δτkij (t ).4　仿真实验结果我们采用典型的NP -hard 问题30城市TSP [1]进行实验,GAAA 中遗传算法迭代次数固定为30代,蚂蚁算法中各路径信息素初值[10]τC 设为60,遗传算法求解结果转换的信息素值是经过路径加2,轨迹更新ρ=0.8,Q =1000.13539期丁建立等:遗传算法与蚂蚁算法的融合表1反映GAAA 算法优化解数据逼近过程,图2形象说明了GAAA 算法中经过遗传算法求解结果在信息素初值设置的表现.从中可以看出本文算法是一个逐步收敛的过程,从均值和分布来看,其求精确解的精度非常高.图3是应用GAAA 算法得到的最优解,和目前得到的最好解一致.图4～图7找到的解与最优解非常接近,是其他算法容易陷入局部最优的几个值,本文算法因为在遗传阶段采用随机产生的种群,因而有效地避免了陷入局部最优.表1　GAAA 算法优化解数据逼近过程GAAA 过程优化解分布最大值最小值平均值初始随机生成的一组优化解遗传算法后生成的一组优化解蚂蚁算法后生成的一组优化解130913331181111912711256140112161275129310461385130212631309134714481227128812831181128915001387146013641206121714411303961918993888938939922838834868924892816901941987926916871918949947908912926975825919989817436430431439426437433429434439426438424426425446449426424443434427452436426425448431440430150010461298.8987817912.3452424433.7图2　GAAA算法一次随机遗传变异后产生的信息素分布图4　GAAA 算法一次随机迭代求得最好结果(d =424.46)图3　GAAA 算法找到的最优路径(d +=423.74)图5　GAAA 算法一次随机迭代求得最好结果(d =424.67)1354计算机研究与发展2003年图6　GAAA算法一次随机迭代求得最好结果(d=424.69)图7　GAAA算法一次随机迭代求得最好结果(d=424.90) 表2是本文算法的实验结果,它和表3基本蚂蚁算法(AA)的实验结果相比,不仅进化代数大大减少,而且在ρ固定的情况下,可以反复迭代,不会陷入局部最优,并且求解精度也大大提高.GAAA算法和表4遗传算法(GA)与模拟退火(SA)相比,求解效率更是大大提高.表2　GAAA算法的实验结果αβρ最短路径长度GAAA进化代数遗传算法+蚂蚁算法110.8426.6030+11 120.8424.6930+10 210.8424.4630+16 220.8423.7430+13 230.8424.6730+21 330.8425.6530+19 320.8425.5230+13 520.8424.9030+9530.8426.9030+11 350.8429.7930+9550.8430.1330+10表3　基本蚂蚁算法(AA)的实验结果[5]αβρ最短路径长度蚂蚁算法进化代数220.5424.8350220.9427.0344120.5423.7342520.9430.5338520.5445.0347表4　遗传算法(GA)与模拟退火(SA)[1]GA收敛最优解平均进化代数404SA同上1018 GASA混合同上554 (并行P)S A同上10125　结 论从本文算法及实例仿真我们可以得到如下结论:(1)本文算法无论是优化性能还是时间性能,都取得了非常好的效果;(2)本文算法由于在遗传算法中使用随机生成种群,不仅加快了蚂蚁算法的速度而且避免求精确解阶段陷入局部最优;(3)遗传算法与蚂蚁算法的融合,对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验次数;(4)本文算法对TSP问题进行了仿真应用,对于其他NP问题也同样适用.参考文献1王凌.智能优化算法及其应用.北京:清华大学出版社,2001.154～159(Wang Ling.Intelligent Optimization Algorithms w ith Application (in Chinese).Beij ing:Ts inghua Univers ity Press,2001.154～159)2李敏强,徐博艺,寇纪淞.遗传算法与神经网络的结合.系统工程理论与实践,1999,19(2):65～69(Li M inqiang,Xu Boyi,Kou Jisong.On the combination of ge-netic algorithms and neural netw ork s.Systems-Engineering Theo-ry&Practice(in Chinese),1999,19(2):65～69)3M arco Dorigo,Gambardella,Luca M aria.Ant colonies for the traveling s alesman problem.Biosystems,1997,43(2):73～814M arco Dorigo,Gambardella,Luca M aria.Ant colony s ystem:A cooperative l earning approach to the traveling salesman problem.IEEE Trans on Evolutionary Computation,1997,1(1):53～6613559期丁建立等:遗传算法与蚂蚁算法的融合5吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法.计算机研究与发展,1999,36(10):1240～1245(Wu Qinghong,Zhang Jihui,Xu Xinhe.An ant colony algorithm w ith mutation features.Journal of Computer Research and Devel-opment(in Chines e),1999,36(10):1240～1245)6M arco Dorigo,E ric Bonabeau,Theraulaz Guy.An t algorithms and stigmergy.Future Generation Com puter System,2000,16(8):851～8717张素兵,刘泽民.基于蚂蚁算法的时延受限分布式多播路由研究.通信学报,2001,22(3):70～74(Zhang Subing,Liu Zemin.A distribu ted delay-bounded con-straint multicast routing algorithm based on ant-algorithm.Journal of China Institute of Communications(in C hinese),2001,22(3): 70～74)8Thomas Stutzle,Holger H Hoos et al.M AX-M IN an t s ystem.Future Generation Com puter System,2000,16(8):889～9149吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2001,24(12):1328～1333(Wu Bin,Shi Zhongzhi.An ant colony algorithm based partition algorithm for TS P.C hinese Journal of Computers(in Chinese),2001,24(12):1328～1333)10M arcus Randall,And rew Lew is.A parallel implem entation of ant colony optimization.Journal of Parallel and Distributed Comput-ing,2002,62(9):1421～1432 丁建立　男,1963年生,博士,副教授,主要研究方向为智能仿生算法、智能决策、网络优化. 陈增强　男,1964年生,教授,博士生导师,主要研究方向为智能预测控制、智能网络管理. 袁著祉　男,1937年生,教授,博士生导师,主要研究方向为自适应控制、智能控制、智能决策系统.敬告作者: 目前,本刊已被国内外多个重要检索机构所收录.一篇文章的中英文摘要是检索的重要内容,因此,中英文摘要写得如何,直接关系着文章的宣传效果.从我们所接收的稿件来看,一些文章的中英文摘要写得过于简单,没有充分概括文章的重要内容.请广大作者再投稿时,将中英文摘要写得充分些,要将研究工作的目的、实验方法、结果和最终结论等写进摘要中,形成一个完整的短文,具体要求请参考下列写作规范.编者注科技论文的中英文摘要写作规范1.摘要是报告、论文的内容不加注释和评论的简短陈述.2.报告、论文一般均应有摘要,为了国际交流,还应有外文(多用英文)摘要.3.摘要应具有独立性和自含性,即不阅读报告、论文的全文,就能获得必要的信息.摘要中有数据、有结论,是一篇完整的短文,可以独立使用,可以引用,可以用于工艺推广.摘要的内容应包含与报告、论文同等量的主要信息,供读者确定有无必要阅读全文,也供文摘等二次文献采用.摘要一般应说明研究工作的目的、实验方法、结果和最终结论等,而重点是结果和结论.4.中文摘要一般不宜超过200～300字,外文摘要不宜超过250个实词.如遇特殊需要字数可以略多(为了扩大国际影响,英文摘要尽量写长一些,可不与中文摘要一一对应.———编辑部注).5.除了实在无变通办法可用以外,摘要中不用图、表、化学结构式、非公知公用的符号和术语.6.报告、论文的摘要可以用另页置于题名页之后,学术论文的摘要一般置于题名和作者之后、正文之前.7.学位论文为了评审,学术论文为了参加学术会议,可按要求写成变异本式的摘要,不受字数规定的限制.———引自《中华人民共和国国家标准》科学技术报告、学位论文和学术论文的编写格式1356计算机研究与发展2003年。