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

《遗传算法和蚁群算法的比较》由会员分享，可在线阅读，更多相关《遗传算法和蚁群算法的比较（39页珍藏版）》请在装配图网上搜索。

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

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

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

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

5、道优化设计、通风网络的优化设计、飞机外型设计、超大规模集成电路的布线等。（4）计算机科学。遗传算法广泛应用于计算机科学的研究，如用于图像处理和自动识别、文档自动处理、VLSI设计等。（5）生物学。遗传算法起源于对生物和自然现象的模拟，现在又反过来用于生物领域的研究，如利用遗传算法进行生物信息学的研究等。（6）社会科学。遗传算法在社会科学的许多领域也有广泛应用，如人类行为规进化过程的模拟、人口迁移模型的建立等（7）经济领域。经济学领域也用到遗传算法。例如，国民经济预测模型、市场预测模型和期货贸易模型等。遗传算法与神经网络相结合正成功地被应用于从时间序列分析来进行财政预算等。1.2 遗传算法的基本

6、原理遗传算法是一种基于自然选择和群体遗传机制的搜索算法，它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即个体，若干个个体构成了群体（所有可能解）。在遗传算法开始时，总是随机地产生一些个体（即初始解）。根据预定的目标函数对每个个体进行评估，给出了一个适应度值。基于此适应度值，选择个体用来复制下一代。选择操作体现了“适者生存”的原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再结合生成新的一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐

7、步朝着更优解的方向进化。因此，遗传算法可以看成是一个由可行解组成的群体逐步进化的过程。图给出了简单遗传算法的基本过程。下面介绍遗传算法的编码及基本遗传操作过程。1.2.1 编码利用遗传算法求解问题时，首先要确定问题的目标函数和变量，然后对变量进行编码。这样做主要是因为在遗传算法中，问题的解是用数字串来表示的，而且遗传算子也是直接对串进行操作的。编码方式可以分为二进制编码和实数编码。若用二进制数表示个体，则将二进制数转化为十进制数的解码公式可以为其中，为某个个体的第段，每段段长都为，每个都是0或者1，和是第段分量的定义域的两个端点。1.2.2 遗传操作遗传操作是模拟生物基因的操作，它的任务就是根

8、据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度看，遗传操作可以使问题的解逐代的优化，逼近最优解。遗传操作包括以下三个基本遗传算子：选择、交叉、变异。选择和交叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到最接近最优解的能力。1. 选择选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体，被选择的可能性就越大，它的“子”在下一代的个数就越多。选择出来的个体被放入配对库中。目前常用的选择方法有轮赌盘方法（也称适应度比例法）、最佳个体保留法、期望值法、排序选择法、竞争法、线性标准化方法等。2. 交叉交叉是指把两

9、个父代个体的部分结构加以替换重组而生成新个体的操作，交叉的目的是为了能够在下一代产生新的个体。通过交叉操作，遗传算法的搜索能力得以飞跃性的提高。交叉是遗传算法获得新优良个体的最重要的手段。交叉操作是按照一定的交叉概率在配对库中随机地选取两个个体进行的。交叉的位置也是随机确定的。交叉概率的值一般取得很大，为0.60.9。3. 变异变异就是以很小的变异概率随机地改变群体中个体的某些基因的值。变异操作的基本过程是：产生一个之间的随机数，如果，则进行变异操作。变异操作本身是一种局部随机搜索，与选择、交叉算子结合在一起，能够避免由于选择和交叉算子而引起的某些信息的永久性丢失，保证了遗传算法的有效性，使遗

10、传算法具有局部的随机搜索能力，同时使得遗传算法能够保持群体的多样性，以防止出现未成熟收敛。变异操作是一种防止算法早熟的措施。在变异操作中，变异概率不能取值太大，如果，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也就不复存在了。1.3 基本步骤遗传算法的基本步骤如下：1）在一定编码方案下，随机产生一个初始种群；2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量，并求得个体的适应值；3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构成交配池；4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群；5）反复执行步骤24，直至满足收敛判据为

11、止。使用遗传算法需要决定的运行参数有：编码串长度、种群大小、交叉和变异概率。编码串长度优优化问题所要求的求解精度决定。种群大小表示种群中所含个体的数量，种群较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，可能找不到最优解；种群较大时，又会增加计算量，使遗传算法的运行效率降低。一般取种群数目为20100.交叉概率控制着交叉操作的频率，由于交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常应取较大值；但若过大的话，又可能破坏群体的优良模式。一般取0.40.99.变异概率也是影响新个体产生的一个因素，变异概率小，产生新个体少；变异概率太大，又会使遗传算法变成随机搜索。一般取变异概率

12、为0.00010.1.遗传算法常采用的收敛判据有：规定遗传代数：连续几次得到的最优个体的适应值没有变化或变化很小等。1.4 用MATLAB实现遗传算法MATLAB是Matwork公司的产品，是一个功能强大的数学软件，其优秀的数值计算能力使其在工业界和学术界的使用率都非常高。MATLAB还十分便于使用，它以直观、简洁并符合人们思维习惯的代码给用户提供了一个非常友好的开发环境。利用MATLAB处理矩阵运算的强大功能来编写遗传算法程序有着巨大的优势。1.4.1编码遗传算法不对优化问题的实际决策变量进行操作，所以应用遗传算法首要的问题是通过编码将决策变量表示成串结构数据。本文中我们采用最常用的二进制编

13、码方案，即用二进制数构成的符号串来表示一个个体，用下面的encoding函数来实现编码并产生初始种群。function bin_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的

14、初始种群bit_gen。编码后的实际搜索精度为scale_dec=(max_var-min_var)/(2bits-1)，该精度会在解码时用到。1.4.2解码解码后的个体构成的种群bin_gen必须经过解码，以转换成原问题空间的决策变量构成的种群var_gen，方能计算相应的适应值。我们用下面的代码实现。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

15、.bits-1);bits=cumsum(bits);bits=0 bits;for i=1:num_var bin_vari=bin_gen(:,bits(i)+1:bits(i+1); vari=sum(ones(popsize,1)*2.(size(bin_vari,2)-1:-1:0).*bin_vari,2).*scale_dec(i)+min_var(i);endvar_gen=var1,:;for i=1:popsize fitness(i)=eval(funname,(var_gen(i,:);endend解码函数的关键在于先由二进制数求得对应的十进制数D，并根据下式求得实际决

16、策变量值X：1.4.3选择选择过程是利用解码后求得的各个适应值大小，淘汰一些较差个体而选出一些比较优良的个体，以进行下一步的交叉和变异操作。选择算子的程序如下：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(ind

17、ex1);index=1:popsize;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

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

19、C在两两配对的个体编码串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)pc;cpoints=randint(pairs,1,1,bits);cpoints=cpairs.*

20、cpoints;for i=1:pairs new_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);endend1.4.5变异对于二进制的基因串而言，变异操作就是按照变异概率pm随机选择变异点mpoints，在变异点处将其位取反即可。变异算子的实现过程如下：function new_gen=mutation(old_gen,pm)mpoints=find(rand(size(old_gen)pm);new_gen=old_gen;new_gen(mpoints)=1-old

21、_gen(mpoints);1.5 应用实例上述程序已经考虑了多参数编码问题，可以用于搜索多变量函数的最优解。为简单起见，下面仅以一个单变量函数为例，来验证所编遗传算法程序的全局寻优能力。设函数为：，函数特性如图1所示。图1 函数特性示意图取种群大小popsize=40，搜索精度scale_var=0.0001，交叉概率pc=0.85，变异概率pm=0.05。图2和图3是某一次运算遗传40代后最佳个体和最佳适应值的变化情况。图2 最佳个体的变化情况图3 最佳个体适应值的增长情况由于采用了最优保存策略，所以在图3中未看到最佳个体适应值减少的现象。由图2可见：在前三代种群中适应值最大的个体解码后的

22、值为7.8681，落在函数的一个局部极值处。但是搜索并没有在此处停滞，很快就跃到了另一个更大的极值点7.8538附近。搜索继续，经过几次跳跃，我们发现在7.85附近搜索多次后，连续几次得到的最优个体的适应值变化很小，可以认为找到全局最大值。全局最大值点为7.8567，最大值为24.8554。下列程序为主函数。%Exampleclear;clc;close;popsize=40;%种群的个体个数scale_var=0.0001;%搜索精度pc=0.85;%交叉概率pm=0.05;%变异概率min_var=0;%函数定义域下界max_var=9;%函数定义域上界bin_gen,bits=encod

23、ing(min_var,max_var,scale_var,popsize);%随机产生初始群体old_gen=bin_gen;t=0;T=40;Max_f=;Best_var=;while(tT) var_gen,fitness=decoding(fun,old_gen,bits,min_var,max_var); evo_gen,best_indiv,best_var,max_fitness=selection(old_gen,fitness,var_gen); conew_gen=crossover(evo_gen,pc); munew_gen=mutation(conew_gen,pm

24、); new_gen=munew_gen;best_indiv;best_indiv; 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);xlabel(x)ylabel(f(x)title(f(x)=x+10sin(5x)+7cos(4x)figureplot(Best_var,g+,lin

25、ewidth,5);xlabel(遗传代数)ylabel(最佳个体解码值)title(最佳个体的变化情况)figureplot(Max_f,c*,linewidth,5);xlabel(遗传代数)ylabel(最佳适应值)title(最佳适应值的变化情况)定义的函数为：function f=fun(x)f=x+10*sin(5*x)+7*cos(4*x);2 蚁群算法2.1 蚁群算法起源及发展蚁群算法是一种源于大自然生物世界的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念

26、，因此，有时也称为蚂蚁系统。蚂蚁是一种古老的社会性昆虫，种类成千上万，分布遍及世界各地，其共同特征是群居生活，每一种群都有着严格的社会结构，不同蚂蚁有着不同的分工。因此，虽然蚂蚁个体的结构和行为都比较简单，但是由这些简单个体组成的群体，即“蚁群”系统却高度复杂，所能完成的任务复杂程度远远超出每个个体的能力。除了“蚁群”系统具有高度的分工协作之外，蚂蚁个体之间还存在着一种信息传递机制，这也是使得系统能够高效有序运转的重要原因。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出其巢穴至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂

27、蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物信息素，使得一定围的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称为蚂蚁的自催化行为。受到蚁群系统信息共享机制的启发，意大利学者Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该方法应用于其解旅行商问题和二次分配问题（QAP）中，引起了大家的广泛关注。之后，蚁群算法很快陆续渗透到其他问题领域中，如工件排序问题、图着色问题、车

28、辆调度问题、大规模集成电路设计、通信网络中的负载平衡问题等，蚁群算法越来越引起人们的重视。2.2 蚁群算法的原理用于优化领域的蚁群算法吸收了生物界中蚁群群体行为特征，其原理在于（1）感知小围区域状况，并判断出是否有食物或其他同伴的信息素轨迹；（2）释放自己的信息素；（3）所遗留的信息素数量会随时间而逐步减少。由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取食物，也不知发现食物后如何返回自己的巢穴，因此，它们仅仅依赖于同类散发在周围环境中的信息素来决定自己何去何从。有趣的是，尽管没有任何先验知识，但蚂蚁们还是有能力找到从巢穴到食物源的最佳路径，甚至在该路线设置障碍物之后，它们仍然能很快重

29、新找到新的最佳路线。这里，用一个形象化的图来说明蚁群算法的路径搜索原理和机制。(a) (b) (c)注：（a）是初始的距离图，d表示距离；（b）在t=0时刻，在各路径上没有信息素的遗留，蚂蚁以等概率选择路径；（c）在t=1时刻，比较短的边上信息素的遗留比较多。因此，这样的边容易被蚂蚁选择。在图（a）中，假设F是食物源，E是蚁穴。蚂蚁的目的是把食物带回蚁穴。显然，较短的路径比较长的路径有优势。假设在t=0时刻，这里有150只蚂蚁在点C（另有150只蚂蚁在点A）。并且在这一时刻任何一段路径都没有信息素的遗留。这样，每只蚂蚁都以相同的概率随机地选择它们的路径。所以，从点C和A出发点蚂蚁，按概率都将各

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

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

32、城市的TSP问题为例来说明基本蚁群算法模型。假设将只蚂蚁随机放在个城市上，表示城市和城市之间的距离，表示时刻城市和城市连线上的信息量，即路径的信息量。初始时刻，各条路径上信息量相等，设（为一个正常数），蚂蚁在运动过程中根据各条路径的信息量决定其转移方向。这里用禁忌表来记录蚂蚁当前所走过的城市，集合随着蚁群进化过程做动态调整。表示时刻蚂蚁由城市转移到城市的状态转移概率 （2-1）其中，表示蚂蚁下一步允许选择的城市集合，则，为信息启发因子，为期望启发因子，为启发函数，对于某个确定的TSP问题，是一个常数。其表达式如下：其中，表示城市和城市之间的距离，且其中，和分别是城市和城市的坐标。为了避免路径上

33、信息素的无限累计，导致某路径上残留的信息素过多而淹没启发信息，在每只蚂蚁走完一步或者一个循环结束后，要对路径上的信息素进行更新处理。由此，在时刻，路径上的信息量可按如下规则调整 （2-2） （2-3）其中，是信息素挥发系数，则是信息素残留因子，且。表示本次循环中路径上信息素增量，初始时刻信息素的增量为0，即。为第只蚂蚁在本次循环中留在路径上的信息素。这里，根据信息素不同的更新策略，即的不同求法将蚁群算法模型分为以下三种：Ant-Cycle模型、Ant-Auantity模型和Ant-Density模型（1）Ant-Cycle模型 （2-4）（2）Ant-Quantity模型 （2-5）（3）An

34、t-Density模型 （2-6）以上各式中，均表示信息素强度，是一个常数。在这三个模型中，Ant-Quantity模型和Ant-Density模型是当蚂蚁走完一步后更新其所走路径上的信息素，是局部信息素更新。而Ant-Cycle模型则是蚂蚁完成一个循环后更新所有路径上的信息素，利用的是整体信息素更新。我们通常采用Ant-Cycle模型作为蚂蚁算法的基本模型。2.4 基本蚁群算法实现过程以Ant-Cycle模型为例来说明基本蚁群算法的具体实现步骤：Step1（初始化）设定算法迭代次数，设置最大循环次数，设置路径初始时刻的信息量（为常数），信息素，且初始时路径上的信息素增量为0，即。Step2算

35、法的迭代过程While(NCNCmax)for i=1:n-1（确保遍历所有的城市） for k=1:m（对m只蚂蚁进行循环） for j=1:n（对n个城市进行循环） 蚂蚁k根据公式（2-1）选择转移到的下一个城市j，并将城市j置入蚂蚁k的禁忌表tabuk中 end（结束对城市的循环） end（结束对蚂蚁的循环） end（结束对i的循环）计算所有蚂蚁求得的路径长度，根据公式（2-2）、（2-3）和（2-4）更新路径（i,j）上的信息素； NC=NC+1endStep3结束算法，输出结果。2.5 用于连续函数优化的蚁群算法2.5.1 一元连续函数优化对于任何一个连续函数优化问题，都可以通过一定

36、的变换而成为一个在0,1上的函数最小化问题，其中。加上一个常数以使函数值大于0.对于端点值，可以通过直接与除去端点计算出的最小值比较的方法确定是否为最小，因此下面不考虑端点值。设问题要求自变量精确到小数点后位，则自变量可以用个十进制数来近似表示，就可以构造如下个“城市”。这些城市分为层。其中首尾两层分别仅含一个城市：一个为起始城市，一个为终止城市。中间层，从左往右分别表示自变量的十分位、百分位这些城市中，只有与层（）之间的各个城市有连接通路。记层中代表十进制数的城市与层中代表十进制数的城市之间的连接上残留的信息量为。蚂蚁在一次循环中的第步所在的城市用表示。设蚂蚁总数为。首先用一个较小的值初始化

37、所有的。让每只蚂蚁的第一步为0，即令。然后，就为每一只蚂蚁选择路径。若蚂蚁当前所在的城市为，根据如下公式选择每只蚂蚁下一步应该到达的城市： （2-7）其中，是随机数；是一个上的常数，用于确定伪随机选择的概率；表示用伪随机选择来确定下一步要走的城市，也就是根据下式选择下一层中每一个城市的概率，然后按此概率用遗传算法中的转盘式选择法确定要选择的城市： （2-8）其中，表示从当前城市转移到下一层的城市的概率。由于本算法中仅允许蚂蚁由上一层城市向下一层转移，所以这个公式与普通蚁群算法的转移概率计算公式有所不同。当每只蚂蚁按上面的公式到达了层时，都将转移到层的唯一的城市0.蚂蚁在城市上建立路径的过程中，

38、要不断地在经过的路径上按公式（2-9）减弱上面残留的信息，这样可以减少下一只蚂蚁选择同样路径的概率，除非经过多次循环后已确定一条极优的路径。这个过程叫做残留信息的局部更新。 （2-9）其中，为常数，表示路径上残留信息减弱的速度。当所有蚂蚁都按上面的步骤完成了一次循环。这时就对路径上的信息进行全局更新。首先对蚂蚁选择的路径解码，计算出蚂蚁对应的自变量值： （2-10）计算每只蚂蚁对应的函数值，并选择出函数值最小的蚂蚁： （2-11）对这只最优蚂蚁经过的路径按下式做全局更新： （2-12）其中，为上的常数。至此就完成了一个循环。反复进行上面的步骤直到达到指定的循环次数或得到的解在一定循环次数后没有

39、改进。文中提出的求解一元连续函数优化问题的蚁群算法具体描述如下：1）初始化；2）将所有蚂蚁置于初始城市；3）对所有的到层城市执行步骤4）8）；4）对每只蚂蚁执行步骤5）6）；5）根据公式（2-7）和（2-8）选择蚂蚁在第层应该到达的城市；6）每只蚂蚁选择城市后都立即按公式（2-9）执行局部更新规则；7）根据公式（2-10）（2-12）评选出最优蚂蚁并执行全局更新规则；8）判断是否满足终止条件，满足则输出结果结束计算。2.5.2 多元连续函数优化对于多元连续函数的优化问题，设自变量由个分量组成，并要求自变量的每一个分量都精确到小数点后位，则可构造一副由层城市组成，且第层由1个标号为0的城市组成，

40、其余层都由标号为0到9的10个城市组成。第到层表示自变量的第个分量。其余层都是辅助层。解码时，就对各分量对应的层分别解码。采用这种方法，每个自变量分量的最后一位与下一个分量的第一位之间都有辅助层隔开，因此前面一个分量的末位就不会影响后面一个分量首位。除了这一点以外，其余部分都与一元连续函数的优化方法相同，这里就不再详细介绍了。2.5.3 应用实例为了与遗传算法作比较，下面取与1.5中一样的函数为：。采用的参数如下：，运行循环次数为：50.2.5.3.1算法具体代码描述具体分成两部分：调用函数部分和主函数部分。（一）调用函数部分转移规则子函数%5) 根据公式(1)和(2)选择蚂蚁n在第k层应该到

41、达的城市;Tau 任意两个城市之间的信息素，三个维度，第一维表示第几层，第二维表示Q0 是一个常数，主要是作为轮盘赌法的临界点k: 代表目前进展到第几层（1d+2）a： 第k-1层的节点下标d： 代表小数位数T: 每只蚂蚁的路径矩阵n: 第n只蚂蚁%function b=select_k_city(Tau,Q0,n,k,T)a=T(n,k-1)+1;%第n只蚂蚁第k-1层的所在城市编码（注意：城市编码从110）q=rand;num=100;%轮盘赌次数P=;Select=;if qQ0 b=find(Tau(k,a,:)=max(Tau(k,a,:); else P=Tau(k,a,:)/su

42、m(Tau(k,a,:); Select=Roulette(P,num); row,col,len=size(Tau); for i=1:len Ps(i)=(sum(Select=i)/num); end b=find(Ps=max(Ps);end轮盘赌法子函数%轮盘赌法程序%function Select=Roulette(P,num)m = length(P);Select = zeros(1,num);r = rand(1,num);for i=1:num sumP = 0; j = ceil(m*rand); %产生1m之间的随机整数 while sumP r(i) sumP = s

43、umP + P(mod(j-1,m)+1); j = j+1; end Select(i) = mod(j-2,m)+1;end局部更新规则子函数%6) 每只蚂蚁选择城市后都立即按公式(3) 执行局部更新规则;需要输入rou,tao0,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)*Tau(k

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

45、(i); F=F f;endf_min=min(F);idx=find(F=f_min);var_min=X(idx(1);%蚂蚁经过路径全局性更新for k=2:d+1 i=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定义连续函数子函数function myvalue=myfunction(x)y=8*x+1;myvalue=-(y+10*sin(5*y)+7*cos(4*y)+30;（二）主函数部分主函数%test_lianxu_function%第一层和最后一层只有0%中间

46、层都是0-9 len%T蚂蚁的路径矩阵，起始点是第一层的0，终点是第d+2层的0%Tau全部d+2层的信息素矩阵，代表每一层上每一节点的经过概率% Rho信息素蒸发系数，取值01之间，推荐取值0.70.95% N蚁群规模len=10;tau=0.01;d=10;Tau=ones(d+2,len,len);Tau=Tau*tau;%所有蚂蚁共用Rho=0.8;N=20;T=zeros(N,d+2);%N只蚂蚁，d+2层，赋予初始值为0，也就是说所有蚂蚁第一次的都从第一个城市出发Q0=0.8;iteration=50;alpha=0.8;F_min=;Var_min=;for i=1:iterat

47、ion%迭代次数，迭代1000次，也就是所有蚂蚁走过1000遍 for j=2:d+1%层数，从初始点第一层0出发，到最后一层的0结束 for k=1:N%蚂蚁编码 b=select_k_city(Tau,Q0,k,j,T); T(k,j)=b(1)-1;%T数组保存的是第k蚂蚁第j层的具体数值，应该为城市编号减1 Tau=update_tao(Tau,Rho,tau,T,j,k); end end Tau,f_min,var_min=update_all_tao(Tau,N,alpha,d,T); F_min(i)=f_min; Var_min(i)=var_min;enddisp(最大值为

48、： num2str(30-f_min) )disp(全局最大值点为： num2str(8*var_min+1) )figureplot(8*Var_min+1,g+,linewidth,5);xlabel(迭代次数)ylabel(最佳个体值)title(最佳个体的变化情况)figureplot(30-F_min,c*,linewidth,5);xlabel(迭代次数)ylabel(最佳适应值)title(最佳适应值的变化情况)2.5.3.2结果结果如下：最大值为：24.8554，全局最大值点为：7.8567。图4和图5分别显示了最佳个体和最佳适应值随循环次数的变化情况。图4 最佳个体的变化情况

49、图5 最佳适应值的变化情况3遗传算法、蚁群算法的特点与比较3.1遗传算法的特点（1）遗传算法是以决策变量的编码作为运算对象。在优化过程中借鉴生物学中染色体和基因等概念，模拟自然界中生物的遗传和进化等机理，应用遗传操作，求解无数值概念或很难有数值概念的优化问题；（2）遗传算法直接以目标函数作为搜索信息。它仅使用由目标函数变换来的适应度函数值就可确定进一步搜索的方向和围，而不需要目标函数的导数值等信息；（3）遗传算法同时在多点进行信息搜索，具有天生的并行性，由多个个体组成一个初始群体开始搜索，对群体进行选择、交叉、变异等运算，产生出新一代的群体，继续搜索；（4）遗传算法使用概率搜索技术。它属于一种

50、自适应概率搜索技术，其选择、交叉、变异等运算都是以一定的概率进行的，增加了其搜索过程的灵活性。实践和理论证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。除上述特点之外，遗传算法还有许多问题需要解决，如算法本身的参数优化问题；如何避免过早收敛；如何改进操作手段或引入新的操作来提高算法的效率；遗传算法与其他优化算法的结合问题等。3.2蚁群算法的特点（1）蚁群算法具有很强的发现较好解的能力。由于算法本身采用正反馈原理，加快了进化过程，且不易陷入局部最优解；（2）蚁群算法具有很强的并行性，个体之间不断进行信息交流和传递，有利于发现较好解。单个个体容易收敛于局部最优，多个个体通过合作，可很快收敛于解空间的某一子集，有利于对解空间的进一步探索，从而发现较好解。存在的问题是该算法本身很复杂，一般需要较长的搜索时间；容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。39 / 39