遗传算法和蚁群算法地比较

1、全局优化报告遗传算法和蚁群算法的比较姓名：玄玄学号：3112054023班级：硕20411 遗传算法1.1 遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。 20 世纪60年代初期，Holla nd教授开始认识到生物的自然遗传现象与人工自 适应系统行为的相似性。 他认为不仅要研究自适应系统自身， 也要研 究与之相关的环境。因此，他提出在研究和设计人工自适应系统时， 可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。 1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一 词。到 70 年代初， Holland 教授提出了“模式定理” ，一般认为是遗

2、传算法的基本定理，从而奠定了遗传算法的基本理论。 1975 年， Holla nd出版了著名的自然系统和人工系统的自适应性，这是第一 本系统论述遗传算法的专著。因此，也有人把 1975 年作为遗传算法 的诞生年。1985 年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holla nd的学生Goldberg出 版了搜索、优化和机器学习中的遗传算法 ，总结了遗传算法研究 的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时 期的遗传算法从古典时期发展了现代阶段， 这本书则奠定了现代遗传 算法的基础。遗传算法是建立在达尔文的生物进化论和孟德尔的遗传

3、学说基 础上的算法。 在进化论中， 每一个物种在不断发展的过程中都是越来 越适应环境， 物种每个个体的基本特征被后代所继承， 但后代又不完 全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就 将被淘汰。 在遗传学中认为， 遗传是作为一种指令遗传码封装在每个 细胞中，并以基因的形式包含在染色体中， 每个基因有特殊的位置并 控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。 基因杂交和基因突变可能产生对环境适应性强的后代， 通过优胜劣汰 的自然选择， 适应值高的基因结构就保存下来。 遗传算法就是模仿了 生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过 程中，遗传算法

4、从一个初始变量群体开始， 一代一代地寻找问题的最 优解，直到满足收敛判据或预先假定的迭代次数为止。遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科， 并且几乎在所有的科学和工程问题中都具有应用前景。 一些典型的应 用领域如下：（1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解； 而遗传算法可以 克服这一缺点，找到全局最优解。（2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划 问题属于 NP 难问题，很难找到有效的求解方法；而遗传算法即特别 适合解决这一类问题， 能够在可以接受的计算时间求得满意的近似最 优解，如著名的旅行商问

5、题、 装箱问题等都可以用遗传算法得到满意 的解。（3）工程应用方面。工程方法的应用是遗传算法的一个主要应用领 域，如管道优化设计、通风网络的优化设计、飞机外型设计、超大规 模集成电路的布线等。（4）计算机科学。遗传算法广泛应用于计算机科学的研究，如用于图像处理和自动识别、文档自动处理、 VLSI设计等。（5）生物学。遗传算法起源于对生物和自然现象的模拟，现在又反 过来用于生物领域的研究，如利用遗传算法进行生物信息学的研究 等。（ 6）社会科学。遗传算法在社会科学的许多领域也有广泛应用，如 人类行为规进化过程的模拟、人口迁移模型的建立等 （7）经济领域。经济学领域也用到遗传算法。例如，国民经济预

6、测模型、市场预测模型和期货贸易模型等。 遗传算法与神经网络相结合 正成功地被应用于从时间序列分析来进行财政预算等。1.2 遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机制的搜索算法， 它模 拟了自然选择和自然遗传过程中的繁殖、 杂交和突变现象。 在利用遗 传算法求解问题时， 问题的每个可能的解都被编码成一个 “染色体”， 即个体，若干个个体构成了群体（所有可能解） 。在遗传算法开始时， 总是随机地产生一些个体（即初始解） 。根据预定的目标函数对每个 个体进行评估，给出了一个适应度值。基于此适应度值，选择个体用 来复制下一代。选择操作体现了“适者生存”的原理， “好”的个体 被选择用来

7、复制，而“坏”的个体则被淘汰。然后选择出来的个体经 过交叉和变异算子进行再结合生成新的一代。 这一群新个体由于继承 了上一代的一些优良性状， 因而在性能上要优于上一代， 这样逐步朝 着更优解的方向进化。 因此， 遗传算法可以看成是一个由可行解组成 的群体逐步进化的过程。 图给出了简单遗传算法的基本过程。 下面介 绍遗传算法的编码及基本遗传操作过程。编码利用遗传算法求解问题时，首先要确定问题的目标函数和变量， 然后对变量进行编码。 这样做主要是因为在遗传算法中， 问题的解是 用数字串来表示的， 而且遗传算子也是直接对串进行操作的。 编码方 式可以分为二进制编码和实数编码。 若用二进制数表示个体，

8、 则将二 进制数转化为十进制数的解码公式可以为F（bii,bi2,., bi ） Ri i bj 2211 j i其中，（bi，bi2,，bH ）为某个个体的第i段，每段段长都为I ,每个bik 都是0或者1, T和R是第i段分量Xi的定义域的两个端点。遗传操作遗传操作是模拟生物基因的操作，它的任务就是根据个体的适应 度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索 的角度看，遗传操作可以使问题的解逐代的优化，逼近最优解。遗传 操作包括以下三个基本遗传算子：选择、交叉、变异。选择和交叉基 本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到最 接近最优解的能力。1. 选择选择

9、是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体，被选择的可能性就越 大，它的“子”在下一代的个数就越多。选择出来的个体被放入配对 库中。目前常用的选择方法有轮赌盘方法（也称适应度比例法）、最佳 个体保留法、期望值法、排序选择法、竞争法、线性标准化方法等。2. 交叉交叉是指把两个父代个体的部分结构加以替换重组而生成新个 体的操作， 交叉的目的是为了能够在下一代产生新的个体。 通过交叉 操作，遗传算法的搜索能力得以飞跃性的提高。 交叉是遗传算法获得 新优良个体的最重要的手段。交叉操作是按照一定的交叉概率 Pc 在配对库中随机地选取两个 个体进行的。 交

10、叉的位置也是随机确定的。 交叉概率 Pc 的值一般取得 很大，为 0.60.9。3. 变异变异就是以很小的变异概率 Pm 随机地改变群体中个体的某些基 因的值。变异操作的基本过程是：产生一个 0,1之间的随机数 rand ， 如果 rand Pm ，则进行变异操作。变异操作本身是一种局部随机搜索， 与选择、交叉算子结合在一 起，能够避免由于选择和交叉算子而引起的某些信息的永久性丢失， 保证了遗传算法的有效性， 使遗传算法具有局部的随机搜索能力， 同 时使得遗传算法能够保持群体的多样性， 以防止出现未成熟收敛。 变 异操作是一种防止算法早熟的措施。 在变异操作中， 变异概率不能取 值太大，如果

11、Pm 0. 5 ，遗传算法就退化为随机搜索，而遗传算法的 一些重要的数学特性和搜索能力也就不复存在了。1.3 基本步骤遗传算法的基本步骤如下：1）在一定编码方案下，随机产生一个初始种群；2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量， 并求得个体的适应值；3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构 成交配池；4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形 成新一代的种群；5）反复执行步骤24，直至满足收敛判据为止。使用遗传算法需要决定的运行参数有：编码串长度、种群大小、 交叉和变异概率。编码串长度优优化问题所要求的求解精度决定。种群大小表示种群中所

12、含个体的数量，种群较小时，可提高遗传算法的 运算速度，但却降低了群体的多样性，可能找不到最优解；种群较大 时，又会增加计算量，使遗传算法的运行效率降低。一般取种群数目 为20100交叉概率控制着交叉操作的频率，由于交叉操作是遗传算 法中产生新个体的主要方法，所以交叉概率通常应取较大值；但若过 大的话，又可能破坏群体的优良模式。一般取0.40.99变异概率也是影响新个体产生的一个因素，变异概率小，产生新个体少；变异概 率太大，又会使遗传算法变成随机搜索。一般取变异概率为0.0001 0.1.遗传算法常采用的收敛判据有：规定遗传代数：连续几次得到的 最优个体的适应值没有变化或变化很小等。1.4用M

13、ATLAB实现遗传算法MATLAB是Matwork公司的产品，是一个功能强大的数学软件， 其优秀的数值计算能力使其在工业界和学术界的使用率都非常高。 MATLAB还十分便于使用，它以直观、简洁并符合人们思维习惯的代 码给用户提供了一个非常友好的开发环境。 利用MATLAB处理矩阵运 算的强大功能来编写遗传算法程序有着巨大的优势。编码遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法首要的问题是通过编码将决策变量表示成串结构数据。本文中我们采用最常用的二进制编码方案，即用二进制数构成的符号串来表示 一个个体，用下面的encoding函数来实现编码并产生初始种群。function bin

14、_gen,bits=encoding(min_var,max_var,scale_var,popsize)bits=ceil(log2(max_var-min_var)./scale_var); bin_gen=round(rand(popsize,sum(bits);end在上面的代码中，首先根据各决策变量的下界(min_var)、上界(max_var)及其搜索精度scale_var来确定表示各决策变量的二进制串的长度bits，然后随机产生一个种群大小为popsize的初始种群bit_gen 。 编码后的实际搜索精度为scale_dec=(max_var-min_var)/(2Abits-1

15、)该精度会在解码时用到。142解码解码后的个体构成的种群bin_gen必须经过解码，以转换成原问题空 间的决策变量构成的种群 var_ge n,方能计算相应的适应值。我们用 下面的代码实现。function var_gen,fitness=decoding(funname,bin_gen,bits,min_var,max_var) num_var=length(bits);popsize=size(bin_gen,1);scale_dec=(max_var-min_var)./(2.Abits-1);bits=cumsum(bits);bits=0 bits;for i=1:num_varbi

16、n_vari=bin_gen(:,bits(i)+1:bits(i+1);vari=sum(ones(popsize,1)*2.A(size(bin_vari,2)-1:-1:0).*bin_vari,2).*scale_dec(i)+min_var(i); endvar_gen=var1,:;for i=1:popsizefit ness(i)=eval(f unn ame,'(var_ge n( i,:)');endend解码函数的关键在于先由二进制数求得对应的十进制数D，并根据下式求得实际决策变量值X：X D scale dec min var143选择选择过程是利用解码

17、后求得的各个适应值大小，淘汰一些较差个体而选出一些比较优良的个体，以进行下一步的交叉和变异操作。 选择算子的程序如下：function evo_gen,best_indiv,best_var,max_fitness=selection(old_gen,fitness,var_gen)popsize=length(fitness);max_fitness,index1=max(fitness);min_fitness,index2=min(fitness);best_indiv=old_gen(index1,:);best_var=var_gen(index1);index=1:popsize;

18、index(index1)=0;index(index2)=0;index=nonzeros(index);evo_gen=old_gen(index,:);evo_fitness=fitness(index);evo_popsize=length(index);ps=evo_fitness/sum(evo_fitness);pscum=transpose(cumsum(ps);r=rand(1,evo_popsize); selected=sum(pscum*ones(1,evo_popsize)<ones(evo_popsize,1)*r)+1; evo_gen=evo_gen(se

19、lected,:);end在该算子中，采用了最优保存策略和比例选择法相结合的思路， 即首 先找出当前群体中适应值最高和最低的个体，将最佳个体best_i ndiv保存并用其替换掉最差个体。为保证当前最佳个体不被交叉、变异操作所破坏，允许其不参与交叉和变异而直接进入下一代。然后将剩下 的个体evo_gen按比例选择法进行操作。所谓比例选择法，也叫赌轮 算法，是指个体被选中的概率与该个体的适应值大小成正比。将这两种方法想结合的目的是：在遗传操作中，不仅能不断提高群体的平均 适应值，而且能保证最佳个体的适应值不减小。144交叉下面采用单点交叉的方法来实现交叉算子，即按选择概率PC在两两配对的个体编码

20、串cpairs中随机设置一个交叉点cpoints,然后在该点 相互交换两个配对个体的部分基因，从而形成两个新的个体。交叉算子的程序如下：function new_gen=crossover(old_gen,pc)nouse,mating=sort(rand(size(old_gen,1),1);mat_gen=old_gen(mating,:);pairs=size(mat_gen,1)/2;bits=size(mat_gen,2);cpairs=rand(pairs,1)vpc;cpoints=randint(pairs,1,1,bits);cpoints=cpairs.*cpoints;f

21、or i=1:pairsnew_gen(2*i-1 2*i,:)=mat_gen(2*i-1 2*i,1:cpoints(i) mat_gen(2*i 2*i-1,cpoints(i)+1:bits);145变异 对于二进制的基因串而言，变异操作就是按照变异概率 pm随机选择变异点mpoints，在变异点处将其位取反即可。变异算子的实现过程如下：function new_gen=mutation(old_gen,pm) mpoints=find(rand(size(old_gen)vpm); new_gen=old_gen; new_gen(mpoints)=1-old_gen(mpoints

22、);1.5应用实例上述程序已经考虑了多参数编码问题，可以用于搜索多变量函数的最优解。为简单起见，下面仅以一个单变量函数为例，来验证所编遗传算法程序的全局寻优能力。设函数为：y 10 sin( 5x)7 cos( 4x) x, x 1,9，函数特性如图 1 所示。图1函数特性示意图取种群大小popsize=40,搜索精度scale_var=0.0001,交叉概率pc=0.85,变异概率pm=0.05。图2和图3是某一次运算遗传40代后 最佳个体和最佳适应值的变化情况。5忑藝绘4-妙醞图2最佳个体的变化情况最住适应值的变化情况24.86511:1124 6624 355 -852424.64 -_

23、24 835 -24.03J1LL110610152025303540遗传代数图3最佳个体适应值的增长情况由于采用了最优保存策略，所以在图3中未看到最佳个体适应值减少 的现象。由图2可见：在前三代种群中适应值最大的个体解码后的值 为7.8681,落在函数的一个局部极值处。但是搜索并没有在此处停滞, 很快就跃到了另一个更大的极值点7.8538附近。搜索继续，经过几次跳跃，我们发现在7.85附近搜索多次后，连续几次得到的最优个 体的适应值变化很小，可以认为找到全局最大值。全局最大值点为 7.8567，最大值为24.8554。下列程序为主函数。%Exampleclear;clc;close;pops

24、ize=40;%种群的个体个数scale_var=0.0001;%搜索精度pc=0.85;%交叉概率pm=0.05;%变异概率min_var=0;%函数定义域下界max_var=9;%函数定义域上界bin_gen,bits=encoding(min_var,max_var,scale_var,popsize);% 随机产生初始群体old_gen=bin_gen;t=0;T=40;Max_f=;Best_var=;while(t<T)var_gen,fitness=decoding('fun',old_gen,bits,min_var,max_var);evo_gen,be

25、st_indiv,best_var,max_fitness=selection(old_gen,fitness,var_gen); conew_gen=crossover(evo_gen,pc);old_gen=new_gen;Best_var=Best_var,best_var;Max_f=Max_f,max_fitness;t=t+1;enddisp('最大值为：'num2str(max_fitness)disp('全局最大值点为：'num2str(best_var) figureezplot('fun',min_var,max_var);x

26、label('x')ylabel('f(x)')title('f(x)=x+10sin(5x)+7cos(4x)')figureplot(Best_var,'g+','linewidth',5);xlabel('遗传代数')ylabel('最佳个体解码值')title('最佳个体的变化情况')figureplot(Max_f,'c*','linewidth',5);xlabel('遗传代数')ylabel('最佳

27、适应值')title('最佳适应值的变化情况')定义的函数为:function f=fun(x) f=x+10*sin(5*x)+7*cos(4*x);2蚁群算法2.1蚁群算法起源及发展蚁群算法是一种源于大自然生物世界的仿生类算法， 作为通用型 随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性， 通过其在的搜 索机制，在一系列困难的组合优化问题求解中取得了成效。 由于在模 拟仿真中使用的是人工蚂蚁概念，因此，有时也称为蚂蚁系统。蚂蚁是一种古老的社会性昆虫，种类成千上万，分布遍及世界各 地，其共同特征是群居生活，每一种群都有着严格的社会结构，不同 蚂蚁有着不同的分工。因此，

28、虽然蚂蚁个体的结构和行为都比较简单， 但是由这些简单个体组成的群体，即“蚁群”系统却高度复杂，所能 完成的任务复杂程度远远超出每个个体的能力。除了“蚁群”系统具 有高度的分工协作之外，蚂蚁个体之间还存在着一种信息传递机制， 这也是使得系统能够高效有序运转的重要原因。据昆虫学家的观察和 研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出其巢 穴至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新 的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走 过的路径上释放一种蚂蚁特有的分泌物信息素， 使得一定围的其 他蚂蚁能够察觉到并由此影响它们以后的行为。 当一些路径上通过的 蚂蚁

29、越来越多时， 其留下的信息素轨迹也越来越多， 以致信息素强度 增大（随时间的推移会逐渐减弱） ，后来蚂蚁选择该路径的概率也越 高，从而更增加了该路径的信息素强度， 这种选择过程被称为蚂蚁的 自催化行为。受到蚁群系统信息共享机制的启发，意大利学者 Dorigo 于 1992 年在他的博士论文中首次系统提出了蚁群算法， 并成功地将该方法应 用于其解旅行商问题和二次分配问题（QAP）中，引起了大家的广泛 关注。之后，蚁群算法很快陆续渗透到其他问题领域中，如工件排序 问题、图着色问题、车辆调度问题、大规模集成电路设计、通信网络 中的负载平衡问题等，蚁群算法越来越引起人们的重视。2.2 蚁群算法的原理用

30、于优化领域的蚁群算法吸收了生物界中蚁群群体行为特征， 其 原理在于（ 1）感知小围区域状况，并判断出是否有食物或其他同伴的信 息素轨迹；（ 2）释放自己的信息素；（3）所遗留的信息素数量会随时间而逐步减少由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取 食物，也不知发现食物后如何返回自己的巢穴，因此，它们仅仅依赖 于同类散发在周围环境中的信息素来决定自己何去何从。有趣的是， 尽管没有任何先验知识，但蚂蚁们还是有能力找到从巢穴到食物源的 最佳路径，甚至在该路线设置障碍物之后，它们仍然能很快重新找到 新的最佳路线。这里，用一个形象化的图来说明蚁群算法的路径搜索 原理和机制。(a)(b)(c

31、)注：（a）是初始的距离图，d表示距离；（b）在t=0时刻，在各路径上没有信息素的遗留, 蚂蚁以等概率选择路径；（c）在t=1时刻，比较短的边上信息素的遗留比较多。因此，这样 的边容易被蚂蚁选择。在图（a）中，假设F是食物源，E是蚁穴。蚂蚁的目的是把食物带回蚁穴。显然，较短的路径比较长的路径有优势。假设在t=0时刻，这里有150只蚂蚁在点C （另有150只蚂蚁在点A）。并且在这一时刻任何一段路径都没有信息素的遗留。 这样，每只蚂蚁都以相同的 概率随机地选择它们的路径。所以，从点C和A出发点蚂蚁，按概率 都将各有75只走向D,另外75只走向B （图（b）。当t=1时，又有 150只蚂蚁从F走向C

32、,此时在C到D的路径上遗留了先前从 C经D 到A的75只蚂蚁所遗留的信息素，而在 C到B的路径上则遗留了先 前从C经B到A的75只蚂蚁以及从A经B到C的75只蚂蚁所遗留 的信息素。蚂蚁在选择路径的时候依据各路径所遗留信息素的浓度来 进行选择，因此，按概率将有 100 只蚂蚁朝点 B 走，有 50 只蚂蚁朝 点D走。由E点到A点也是相同的情况（图（c）。这一过程反复进 行，最终所有点蚂蚁都将选择到这条最短路径，即CBA这条边。蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路 径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的 选择。其根本原因是蚂蚁在寻找食物源时， 能在其走过的路

33、上释放信 息素，随着时间的推移该物质会逐渐挥发， 后来的蚂蚁选择该路径的 概率与当时这条路径上该物质的强度成正比， 当一定路径上通过的蚂 蚁越来越多时， 其留下的信息素轨迹也越来越多， 后来蚂蚁选择该路 径的概率也越高， 从而更增加了该路径的信息素强度。 而强度大的信 息素会吸引更多的蚂蚁， 从而形成一种正反馈机制。 通过这种正反馈 机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之 间出现障碍物时， 蚂蚁不仅可以绕过障碍物， 而且通过蚁群信息素轨 迹在不同路径上的变化， 经过一段时间的正反馈， 最终收敛到最短路 径上。2.3基本蚁群算法数学模型为了便于理解，现用求解平面上n个城市的

34、TSP问题为例来说明基本蚁群算法模型。假设将m只蚂蚁随机放在n个城市上，dj表示城市i和城市j之 间的距离，j (t)表示t时刻城市i和城市j连线上的信息量，即路径 (i,j)的信息量。初始时刻，各条路径上信息量相等，设j(0) C( C 为一个正常数)，蚂蚁k(k 1,2,., m)在运动过程中根据各条路径的 信息量决定其转移方向。这里用禁忌表 tabu k(k1,2,., m)来记录蚂蚁k当前所走过的城市，集合tabu k随着蚁群进化过程做动态调整。 pj(t)表示t时刻蚂蚁k由城市i转移到城市j的状态转移概率pj(t)j (t ) ij (t ) is(t ) is (t )s allo

35、wed kallowed k(2-1)0,否则其中，allowed k表示蚂蚁k下一步允许选择的城市集合，则 allowed k C tabuj ,为信息启发因子， 为期望启发因子，j (t ) 为启发函数，对于某个确定的 TSP问题，j (t)是一个常数。其表达 式如下：ij(t)Jdij其中，dj表示城市i和城市j之间的距离，且dij 以 Xj)2(yi yj )2其中，(Xi , yi )和(Xj,yj)分别是城市i和城市j的坐标为了避免路径上信息素的无限累计，导致某路径上残留的信息素 过多而淹没启发信息，在每只蚂蚁走完一步或者一个循环结束后， 要 对路径上的信息素进行更新处理。由此，在

36、 t 1时刻，路径(i,j )上 的信息量可按如下规则调整j(t 1)(1)j(t)j(t)(2-2)m(2-3)(t)ik (t)i 1其中， 是信息素挥发系数，则1是信息素残留因子，且 (0,1)ij (t )表示本次循环中路径(i , j )上信息素增量，初始时刻信息素的增 量为0,即0 (0)0。 ik(t)为第k只蚂蚁在本次循环中留在路径(i , j )上的信息素。这里，根据信息素不同的更新策略，即ik (t)的不同求法将蚁群算法模型分为以下三种：An t-Cycle模型、An t-Aua ntity模型和An t-De nsity 模型(1) Ant-Cycle模型ik(t)若第k

37、只蚂蚁在t和t1之间经过(i ,j )(2-4)0,否则(2) Ant-Quantity 模型j(t)dj若第k只蚂蚁在t和t1之间经过(i , j )(2-5)0,否则(3) Ant-Density 模型j(t)(2-6)Q,若第k只蚂蚁在t和t 1之间经过(i , j )0,否则以上各式中，Q均表示信息素强度，是一个常数。在这三个模型中，Ant-Quantity模型和Ant-Density模型是当蚂蚁走完一步后更新其所走 路径上的信息素，是局部信息素更新。而Ant-Cycle模型则是蚂蚁完成一个循环后更新所有路径上的信息素，利用的是整体信息素更新。 我们通常采用Ant-Cycle模型作为蚂

38、蚁算法的基本模型。2.4基本蚁群算法实现过程以Ant-Cycle模型为例来说明基本蚁群算法的具体实现步骤：Step1 (初始化)设定算法迭代次数NC 0，设置最大循环次数NCmax， 设置路径(i , j )初始时刻的信息量j (0) C (C为常数)，信息素Q， 且初始时路径(i ,j )上的信息素增量为0,即j (0)0。Step2算法的迭代过程While(NCvNGax)for i=1: n-1 (确保遍历所有的城市)for k=1:m （对m只蚂蚁进行循环）for j=1: n （对n个城市进行循环）蚂蚁k根据公式（2-1）选择转移到的下一个城市j,并将城市 j 置入蚂蚁 k 的禁忌表

39、 tabuk 中end （结束对城市的循环）end （结束对蚂蚁的循环）end （结束对i的循环）计算所有蚂蚁求得的路径长度， 根据公式（2-2）、（2-3）和（2-4）更新路径（i,j）上的信息素；NC=NC+1endStep3 结束算法，输出结果。2.5 用于连续函数优化的蚁群算法一元连续函数优化对于任何一个连续函数优化问题， 都可以通过一定的变换而成为一个在0,1上的函数最小化问题min f（x） C，其中x 0,1。加上一个常数C以使函数值大于0对于端点值，可以通过直接与除去端点计算出的最小值比较的方法确定是否为最小，因此下面不考虑端点值设问题要求自变量精确到小数点后 d位，则自变量x

40、可以用d个 十进制数来近似表示，就可以构造如下 d 10 2个“城市”。这些城 市分为 d 2层。其中首尾两层分别仅含一个城市：一个为起始城市， 一个为终止城市。中间 d 层，从左往右分别表示自变量的十分位、百 分位这些城市中，只有k 1与k层(k 2,d 2)之间的各个城市有连接通路。记k 1层中代表十进制数a的城市与k层中代表 十进制数b的城市之间的连接上残留的信息量为 点。蚂蚁n在一次循 环中的第m步所在的城市用T( n, m)表示。设蚂蚁总数为N0。首先用一个较小的值 0初始化所有的 akb 。让每只蚂蚁的第一步为 0,即令T(n,1)qn 1,2,.,N°)。然后，就为每一

41、只蚂蚁选择路径。若蚂蚁n当前所在的城市为T( n, k 1)a，根据如下公式选择每只蚂蚁下一步应该到达的城市：T(n, k)arg max akb, 如果 qQ0Sr , 否则2-7)其中，q是随机数；Q是一个0,1上的常数，用于确定伪随机选择的 概率； Sr 表示用伪随机选择来确定下一步要走的城市，也就是根据下式选择下一层中每一个城市的概率， 然后按此概率用遗传算法中的转 盘式选择法确定要选择的城市：p(a, b)9akb /(kax2-8)其中，p(a, b)表示从当前城市a转移到下一层的城市b的概率。由于本 算法中仅允许蚂蚁由上一层城市向下一层转移， 所以这个公式与普通 蚁群算法的转移概

42、率计算公式有所不同。当每只蚂蚁按上面的公式到达了 d 1层时，都将转移到 d 2 层 的唯一的城市 0.蚂蚁在城市上建立路径的过程中， 要不断地在经过的路径上按公 式(2-9)减弱上面残留的信息，这样可以减少下一只蚂蚁选择同样 路径的概率， 除非经过多次循环后已确定一条极优的路径。 这个过程 叫做残留信息的局部更新。kT(n,k 1),T( n,k)(1kT(n,k 1), T(n,k)2-9)其中，( 0,1)为常数，表示路径上残留信息减弱的速度当所有蚂蚁都按上面的步骤完成了一次循环。 这时就对路径上的 信息进行全局更新。首先对蚂蚁选择的路径解码，计算出蚂蚁 n 对应 的自变量值：d12-1

43、0)x(n)T(n,k) 101 kk2计算每只蚂蚁对应的函数值，并选择出函数值最小的蚂蚁：nminarg minf (x(n)2-11)对这只最优蚂蚁经过的路径按下式做全局更新：ij（1 a）ijf（n min） 1（2-12）其中，iT（nmin，k 1）, jT（nmin，k）, k 2, d 2,为（0,1）上的常数。至此就完成了一个循环。反复进行上面的步骤直到达到指定的循环次数或得到的解在一定循环次数后没有改进。文中提出的求解一元连续函数优化问题的蚁群算法具体描述如下：1）初始化；2）将所有蚂蚁置于初始城市；3）对所有的k 1到k层城市执行步骤4）8）;4）对每只蚂蚁执行步骤5）6）

44、;5）根据公式（2-7）和（2-8）选择蚂蚁在第k层应该到达的城市；6）每只蚂蚁选择城市后都立即按公式（2-9）执行局部更新规则；7）根据公式（2-10）（2-12）评选出最优蚂蚁并执行全局更新规则;8）判断是否满足终止条件，满足则输出结果结束计算。多元连续函数优化对于多元连续函数的优化问题， 设自变量由 nx 个分量组成， 并要 求自变量的每一个分量都精确到小数点后 d 位，则可构造一副由nx dnx1层城市组成，且第 1,d2,2d3, nx dnx1层由 1个标号为 0的城市组成，其余层都由标号为 0到9的 10个城 市组成。第(k 1) (d 1)2到k (d 1)层(k1,2,.,

45、nx)表示自变量的第 k 个分量。其余层都是辅助层。解码时，就对各分量对应的层 分别解码。采用这种方法，每个自变量分量的最后一位与下一个分量的第一 位之间都有辅助层隔开， 因此前面一个分量的末位就不会影响后面一 个分量首位。除了这一点以外，其余部分都与一元连续函数的优化方法相同， 这里就不再详细介绍了。应用实例为了与遗传算法作比较，下面取与 1.5 中一样的函数为： y 10sin( 5x) 7 cos( 4x ) x,x 1,9 。采用的参数如下：0.8，0. 8，Q0 0. 8，0.01，d 10， N0 20，运行循环次数为：50.算法具体代码描述 具体分成两部分：调用函数部分和主函数部

46、分。(一)调用函数部分 转移规则子函数%5)根据公式(1)和(2)选择蚂蚁n在第k层应该到达的城市；Tau任意两个城市之间的信息素，三个维度，第一维表示第几层，第二维表示Q0是一个常数，主要是作为轮盘赌法的临界点k:代表目前进展到第几层(1d+2)a： 第k-1层的节点下标d:代表小数位数T:每只蚂蚁的路径矩阵n:第n只蚂蚁%function b=select_k_city(Tau,QO,n,k,T)a=T(n,k-1)+1;%第n只蚂蚁第k-1层的所在城市编码(注意：城市编码从110)q=rand;num=100;%轮盘赌次数P=【;Select=;if q<Q0b=find(Tau(

47、k,a,:)=max(Tau(k,a,:);elseP=Tau(k,a,:)/sum(Tau(k,a,:);Select=Roulette(P,num);for i=1:lenPs(i)=(sum(Select=i)/num);endb=find(Ps=max(Ps);end轮盘赌法子函数%轮盘赌法程序%function Select=Roulette(P,num)m = length(P);Select = zeros(1,num);r = rand(1,num);for i=1:numsumP = 0;j = ceil(m*rand); %产生1m之间的随机整数 while sumP &l

48、t; r(i)sumP = sumP + P(mod(j-1,m)+1);j =j+1;endSelect(i) = mod(j-2,m)+1;end局部更新规则子函数6)每只蚂蚁选择城市后都立即按公式(3)执行局部更新规则；需要输入 rou,taoO,T,Tau%k 第k层%Tau两层之间的信息素%Rho 比例%tao0剩余信息素0.01%T每一只蚂蚁下一步到达的城市.第一维是第几只蚂蚁、第二位是目前是第几步%n第几只蚂蚁function Tau=update_tao(Tau,Rho,tao0,T,k,n)i=T(n,k)+1;j=T(n,k-1)+1;Tau(k,j,i)=(1-Rho)*

49、Tau(k,j,i)+Rho*tao0;全局更新规则子函数%test7%7)根据公式(4)(6)评选出最优蚂蚁并执行全局更新规则；%共有n只蚂蚁%tau层与层之间的信息素d是小数点后精确到d位%X所有蚂蚁的具体数值数组%idx最小的蚂蚁编码，也就是数组下标%alpha是一常量X=zeros(N,1);forj=1:Nfor i=2:d+1X(j)=X(j)+T(j,i)*(10A(1-i)；endend%选择出蚂蚁的最小值F=；for i=1:Nf=myfunction(X(i);F=F f；endf_min=min(F);idx=find(F=f_min);var_min=X(idx(1);

50、%蚂蚁经过路径全局性更新for k=2:d+1i=T(idx,k-1)+1;j=T(idx,k)+1;Tau(k,i,j)=(1-alpha)*Tau(k,i,j)+alpha*(1./f_min);end定义连续函数子函数y=8*x+1;myvalue=-(y+10*sin(5*y)+7*cos(4*y)+30;(二)主函数部分主函数%test_lianxuunction%第一层和最后一层只有0%中间层都是0-9 len%T蚂蚁的路径矩阵，起始点是第一层的0,终点是第d+2层的0%Tau全部d+2层的信息素矩阵，代表每一层上每一节点的经过概率% Rho信息素蒸发系数，取值 01之间，推荐取值0.