优化算法及其在软测量技术中的应用

本章主要内容概述遗传算法微粒群算法蚁群算法第1页/共73页第一页，共74页。6.1

概述进化计算(EvolutionaryComputation)是通过模拟自然界中生物进化机制进行搜索的一种算法。◆遗传算法（GeneticAlgorithms）

◆进化策略（EvolutionStrategies）

◆进化规划（EvolutionProgramming）遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。

第2页/共73页第二页，共74页。6.1

概述群智能(SwarmIntelligence)这个概念来自对蜜蜂、蚂蚁、大雁等群居生物群体行为的观察和研究。任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置都称为群智能。群智能是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能实现模式，是对简单生物群体的智能涌现现象的具体模式研究，即简单智能的主体通过合作表现出复杂智能行为的特性。该智能模式需要以相当数目的智能个体来实现对问题的求解功能。群智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。第3页/共73页第三页，共74页。6.1

概述群智能的特点：◆分布式：能够适应当前网络环境下的工作状态◆鲁棒性：没有中心的控制与数据，个体的故障不影响整个问题的求解◆扩充性：个体的增加，系统的通信开销增加小◆简单性：个体简单，实现也比较简单第4页/共73页第四页，共74页。6.1

概述群智能的典型实现模式：◆微粒群算法（Particleswarmoptimization,PSO）：模拟鸟群运动模式◆蚁群算法（Antcolonyalgorithm）：模拟生物蚁群运动行为第5页/共73页第五页，共74页。6.2

遗传算法遗传算法的基本机理遗传算法的一般框架遗传算法的模式理论Matlab遗传算法工具箱第6页/共73页第六页，共74页。6.2.1

遗传算法的基本机理遗传与进化的系统观点：生物的所有遗传信息的都包含在其染色体中，染色体决定了生物的性状染色体是由基因及其有规律的排列所构成的，遗传进化过程发生在染色体上生物的繁殖过程是由其基因的复制过程来完成的通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代第7页/共73页第七页，共74页。6.2.1

遗传算法的基本机理遗传算法的基本机理模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。利用选择、交叉、变异等遗传算子产生新的染色体，通过不断计算各染色体的适应度值，选择最好的染色体，获得最优解。第8页/共73页第八页，共74页。6.2.1

遗传算法的基本机理遗传学和遗传算法中基本术语对照表：自然界染色体(chromosome)基因(gene)等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构第9页/共73页第九页，共74页。6.2.2

遗传算法的一般框架遗传算法的构成要素：◆染色体编码方法◆适应度函数◆遗传算子（选择、交叉、变异）◆遗传参数设置第10页/共73页第十页，共74页。6.2.2

遗传算法的一般框架编码与解码：

◆

将问题结构变换为位串形式表示的过程叫编码，相反把位串形式表示变换为原问题结构的过程叫解码

◆

GA常用的编码方法：二进制编码，实数编码，格雷码，符号编码，多参数编码等

第11页/共73页第十一页，共74页。6.2.2

遗传算法的一般框架适应度函数：

◆

一般情况下，适应度函数由目标函数变换而成，适应度函数要求为非负函数

◆若目标函数为最大化问题，则

◆若目标函数为最小化问题，则第12页/共73页第十二页，共74页。6.2.2

遗传算法的一般框架遗传算子：

◆

选择（Selection）：

-从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交叉、变异，产生新的染色体作准备。

-选择方法：适应度比例法（轮盘赌法），即按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：第13页/共73页第十三页，共74页。6.2.2

遗传算法的一般框架遗传算子：

◆

交叉（Crossover）：

-随机选择二个染色体(双亲染色体)，随机指定一点或多点，将两者部分码值进行交换，可得二个新的染色体(子辈染色体)。新的子辈染色体:A’11010001B’01011110第14页/共73页第十四页，共74页。6.2.2

遗传算法的一般框架遗传算子：

◆

变异（Mutation）：

-模拟生物在自然界环境变化，引起基因的突变。

-在染色体二进制编码中，1变成0，或0变成1-变异产生染色体的多样性，避免进化中早期成熟，陷入局部极值点，变异的概率很低。A10100110A’10110110第15页/共73页第十五页，共74页。6.2.2

遗传算法的一般框架遗传参数设置：

◆

N：群体大小，即群体中所含个体的数量，一般取20~100

◆

T：GA的终止进化代数，一般取100~500

◆

Pc：交叉概率，一般取0.4~0.99

◆

Pm：变异概率，一般取0.0001~0.1第16页/共73页第十六页，共74页。6.2.2

遗传算法的一般框架遗传算法进行问题求解的过程：

◆初始化群体

◆计算群体中每个个体的适应度值

◆按由个体适应度值所决定的某个规则选择进入下一代的个体

◆按概率Pc进行交叉操作

◆按概率Pm进行变异操作

◆若没有满足某种停止条件，就转到第2步，否则进入下一步

◆输出群体中适应度值最优的染色体作为问题的满意解或最优解第17页/共73页第十七页，共74页。第18页/共73页第十八页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：例4-1

利用遗传算法求解区间[0,31]上的二次函数y=x2的最大值。y=x2

31

XY分析：

原问题可转化为在区间[0,31]中搜索能使y取最大值的点a的问题。那么，[0,31]中的点x就是个体，函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个解空间。这样,只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。第19页/共73页第十九页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：

解：(1)

设定种群规模，编码染色体，产生初始种群。将种群规模设定为4，用5位二进制数编码染色体，取下列个体组成初始种群S1:

s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定义适应度函数：f(x)=x2

(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作，直到适应度最高的个体(即31（11111）)出现为止。第20页/共73页第二十页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：

首先计算种群S1中各个体的适应度f(si)：

f(s1)=f(13)=132=169，f(s2)=f(24)=242=576f(s3)=f(8)=82=64，f(s4)=f(19)=192=361再计算种群S1中各个体的选择概率：

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31s40.31s20.49s10.14s30.06第21页/共73页第二十一页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：在算法中赌轮选择法可用下面的子过程来模拟：①在[0,1]区间内产生一个均匀分布的随机数r。②若r≤q1，则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N)，则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率，其计算公式为：

第22页/共73页第二十二页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：

设从区间[0,1]中产生4个随机数如下：

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色体

适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第23页/共73页第二十三页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：于是，经复制得群体：

s1’

=11000（24）,s2’

=01101（13）

s3’

=11000（24）,s4’

=10011（19）设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

第24页/共73页第二十四页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：

设变异率pm=0.001，这样，群体S1中共有

5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。

于是，得到第二代种群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

第25页/共73页第二十五页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：第二代种群S2中各染色体的情况：

染色体

适应度选择概率积累概率

估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第26页/共73页第二十六页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：假设这一轮选择复制操作中，种群S2中的4个染色体都被选中，则得到群体：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉运算，让s1’与s2’，s3’与s4’

分别交换后三位基因：

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

这一轮仍然不会发生变异。

第27页/共73页第二十七页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：第三代种群S3中各染色体的情况：

染色体

适应度选择概率积累概率

估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第28页/共73页第二十八页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：设这一轮的选择复制结果为：

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

做交叉运算，让s1’与s2’，s3’与s4’

分别交换后三位基因：

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

这一轮仍然不会发生变异。

第29页/共73页第二十九页，共74页。6.2.2

遗传算法的一般框架遗传算法应用举例：第四代种群S4中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

第30页/共73页第三十页，共74页。YYy=x2

8131924

X第一代种群及其适应度y=x2

12162527

XY第二代种群及其适应度y=x2

9192428

XY第三代种群及其适应度y=x216242831

X第四代种群及其适应度第31页/共73页第三十一页，共74页。6.2.2

遗传算法的一般框架遗传算法的特点：

◆GA是对参数集合的编码而非针对参数本身进行优化

◆GA是从问题解的编码组开始而非单个解开始搜索

◆

GA利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索

◆

GA利用选择、交叉、变异等算子而不是确定性规则进行随机操作

第32页/共73页第三十二页，共74页。6.2.2

遗传算法的一般框架遗传算法的局限性：

◆遗传算法在解决某些问题时速度较慢

◆遗传算法对编码方案的依赖性较强

◆算法的鲁棒性不够好

第33页/共73页第三十三页，共74页。6.2.3

遗传算法的模式理论遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。模式是能对染色体之间的相似性进行解释的模板。设GA的个体，记集合则称为一个模式，其中＊是通配符。即模式(schema)是含有通配符(*)的一类字符串的通式表达。每个“*”可以取“1”或者“0”。第34页/共73页第三十四页，共74页。6.2.3

遗传算法的模式理论模式举例：

-模式*10101110与以下两个字符串匹配：010101110110101110

-模式*1010＊110与以下四个字符串匹配：010100110010101110110100110110101110第35页/共73页第三十五页，共74页。6.2.3

遗传算法的模式理论一个模式s的阶(order)是出现在模式中的“0”和“1”的数目，记为o(s)。

-如：模式“0****”的阶为1，模式“10*1*”的阶为3一个模式s的长度(Length)是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为。

-如：模式“01***”的长度为1，模式“0***1”的长度为3。第36页/共73页第三十六页，共74页。6.2.3

遗传算法的模式理论复制对模式的影响：

假定在给定的时间（代）t，一个特定的模式s在群体P(t)中包含有m个代表串，记为m=m(s,t)。每个串根据适应值的大小获得不同的复制概率。串i的复制概率为：

则在群体P(t+1)中，模式s的代表串的数量的期望值为

其中，表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。第37页/共73页第三十七页，共74页。6.2.3

遗传算法的模式理论复制对模式的影响：若记P(t)中所有个体的适应值的平均值为：则有：上式表明，模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。即：适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。

第38页/共73页第三十八页，共74页。6.2.3

遗传算法的模式理论复制对模式的影响：

假设模式的适应值为，其中c是一个常数，则有：

上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。复制的结果并没有生成新的模式。因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。

第39页/共73页第三十九页，共74页。6.2.3

遗传算法的模式理论交叉对模式的影响：

交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。假定模式s在交叉后不被破坏的概率为ps，则：

若交叉概率为pc，则s不被破坏的概率为：

第40页/共73页第四十页，共74页。6.2.3

遗传算法的模式理论交叉对模式的影响：

若综合考虑复制和交叉的影响，特定模式在下一代中的数量可用下式来估计：可见，对于那些高于平均适应度且具有短短定义长度的模式将更多地出现在下一代中。

第41页/共73页第四十一页，共74页。6.2.3

遗传算法的模式理论变异对模式的影响：变异算子以概率pm随机地改变个体某一位的值，只有当o(s)个确定位的值不被破坏时，模式s才不被破坏。模式s在变异后不被破坏的概率：由于Pm<<1，可近似地表示为：

第42页/共73页第四十二页，共74页。6.2.3

遗传算法的模式理论变异对模式的影响：综合考虑复制、交叉及变异操作，可得特定模式s的数量为：

第43页/共73页第四十三页，共74页。6.2.3

遗传算法的模式理论模式理论(SchemaTheorem)：

适应值在群体适应值之上的、长度较短的、低阶的模式在GA的迭代中将按指数增长方式被复制。“积木块假设”(BuildingBlockHypothesis):低阶、长度较短、高于平均适应度的模式(积木块)在遗传算子的作用下，相互结合，能生成高阶、长度较长、适应度较高的模式，并得到全局最优解。

第44页/共73页第四十四页，共74页。6.2.4

Matlab遗传算法工具箱在Matlab7.0以上版本中包含了遗传算法工具箱GADS，该工具箱可以用遗传算法求解如下带约束非线性优化问题：

第45页/共73页第四十五页，共74页。6.2.4

Matlab遗传算法工具箱GADS工具箱可通过图形界面方式和命令行方式调用。在命令行中输入：

>>gatool图形界面如图：

第46页/共73页第四十六页，共74页。6.2.4

Matlab遗传算法工具箱GADS工具箱可通过命令行或m文件调用，其核心函数为：[x,

fval,

reason,

output]=ga(fitnessfcn,

nvars,A,b,Aeq,beq,LB,UB,nonlcon,

options)函数参数说明如下：

输入参数fitnessfcn：适应度函数f(x)nvars：变量数量A,b：线性不等式约束条件下A1x≤b1的参数Aeq,beq：线性等式约束条件A2x=b2的参数LB：x的取值下限v1UB：x的取值上限v2nonlcon：非线性约束条件c1(x)≤0和c2(x)=0options:：与算法性能相关的参数输出参数x：最优值fval：最优值下的适应度函数值reason：算法停止原因output：每次迭代信息及其他算法信息第47页/共73页第四十七页，共74页。6.2.4

Matlab遗传算法工具箱影响遗传算法性能的参数由结构体options给定，可使用如下命令查看options的默认值：

>>options=gaoptimset

GADS中默认的options参数值为：

PopulationType:'doubleVector’种群数据类型InitialPopulation:[]初始种群PopInitRange:[2*1double]初始种群中个体取值范围InitialScores:[]初始适应度PopulationSize:20种群规模InitialPenalty:10初始惩罚参数EliteCount:2在每代中保留下来的个体数量PenaltyFactor:100惩罚更新参数CrossoverFraction:0.8000交叉概率PlotInterval:1绘制函数调用间隔Migrationdirection:

‘forword’变异方向CreationFcn:@gacreationuniform初始种群函数的句柄MigrationInterval:20子群中发生变异的代数间隔FitnessScalingFcn:@fitscalingrank调节适应度的函数句柄MigrationFraction:0.2000变异概率SelectionFcn:@selectionstochunif选择函数句柄Generations:100最大迭代次数CrossoverFcn:@crossoverscattered交叉函数句柄TimeLimit:Inf最大运行时间MutationFcn:@mutationgaussian变异函数句柄FitnessLimit:-Inf当适应度函数达该值时算法停止HybridFcn:[]GA终止后继续优化的函数句柄StallGenLimit:50算法停止的代数Display:‘final’显示方式StallTimeLimit:20算法停止的时间PlotFcns:[]绘制函数的句柄TolFun:1.0000e-006当适应度函数在StallGenLimit设定的代数内变化小于该值算法停止OutputFcns:[]在每代中调用的函数TolCon:1.0000e-006非线性约束的可行性Vectorized:‘off’适应度函数是否矢量化第48页/共73页第四十八页，共74页。6.2.4

Matlab遗传算法工具箱如果需要修改上述options中的参数值，例如修改PopulationSize至100，可采用如下命令：

>>options=gaoptimset(‘PopulationSize’,100)

也可通过上述命令同时修改多个参数在实际应用中，通常需要根据应用需求编写适当的适应度函数，在编写函数的时候需注意GADS是求最小值的，编写好的适应度函数需存成m文件放在同一目录下。

第49页/共73页第四十九页，共74页。6.2.4

Matlab遗传算法工具箱例：当x1∈[-3.0,12.1]，x2∈[4.1,5.8]时，求函数

f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)的极大值。解：首先编写适应度函数如下：

functionscore=my_func1(x)

score=-21.5-x(1)*sin(4*pi*x(1))-x(2)*sin(20*pi*x(2));

然后选用合适的参数调用ga函数：

opt1=gaoptimset;

opt1.PopInitRange=[[-3.04.1];[12.15.8]];

opt1.PopulationSize=1000;

opt1.MutationFcn=@mutationuniform;

[x,fval]=ga(@my_func1,2,opt1)

第50页/共73页第五十页，共74页。6.2.4

Matlab遗传算法工具箱运行结果如下：

Optimizationterminated:stallgenerationslimitexceeded.

x=

11.62885.7244

fval=

-38.8354需要注意到是：由于遗传算法是一种随机搜索算法，每次运行得到的结果很可能不同，这主要是Matlab在每次迭代时，采用rand和randn这两个随机数生成函数来随机选择样本，每次Matlab调用这两个函数时，他们的状态是不同的，因此产生的随机数也不同，从而导致最终结果也不同。

第51页/共73页第五十一页，共74页。6.3

微粒群算法微粒群算法的基本思想：PSO是J.Kennedy和R.C.Eberhart于1995年提出的一种新的优化算法，其基本思想来源于鸟群捕食过程的社会行为研究。PSO将群体中的成员描述为空间内一个没有质量、没有体积的微粒，所有微粒通过一个适应度函数来确定其在空间中的适应度。进化初期，每个微粒的位置和速度都被随机初始化，微粒在飞行过程中相互合作，根据自身和同伴的运动状态及时调整自己的速度和位置，以便在适应度较好的位置降落。第52页/共73页第五十二页，共74页。6.3

微粒群算法微粒群算法数学描述：设微粒群体规模为N，其中每个微粒在D维空间中的坐标位置可表示为Xi=(xi1,xi2,…,xiD)，微粒i的速度定义为每次迭代中微粒移动的距离，表示为Vi=(vi1,vi2,…,viD)，Pi表示微粒i所经历的最好位置，Pg为群体中所有微粒所经过的最好位置，则微粒i在第d维子空间中的飞行速度vid根据下式进行调整：微粒通过下式调整自身位置：第53页/共73页第五十三页，共74页。6.3

微粒群算法微粒群算法数学描述：

速度调整公式：第一项为微粒先前速度乘一个权值进行加速，表示微粒对当前自身速度状态的信任，依据自身的速度进行惯性运动，因此称这个权值为惯性权值第二项为微粒当前位置与自身最优位置之间的距离，为认知部分，表示微粒本身的思考，即微粒的运动来源于自己经验的部分第三项为微粒当前位置与群体最优位置之间的距离，为社会部分，表示微粒间的信息共享与相互合作，即微粒的运动中来源于群体中其他微粒经验的部分第54页/共73页第五十四页，共74页。6.3

微粒群算法微粒群算法基本流程：

(1)Initial:

随机初始化每一微粒的位置和速度。

(2)Evaluation：依据适应度函数计算每个微粒的适应度值，以作为判断每一微粒之好坏。

(3)FindthePbest：找出每一微粒到目前为止的搜寻过程中最佳解，这个最佳解称为Pbest。

(4)FindtheGbest：找出所有微粒到目前为止所搜寻到的整体最佳解，此最佳解称之为Gbest。

(5)UpdatetheVelocity：更新每一微粒的速度与位置

(6)回到步骤(2)继续执行，直到获得一个令人满意的结果或符合终止条件为止。

第55页/共73页第五十五页，共74页。6.3

微粒群算法微粒群算法基本流程：第56页/共73页第五十六页，共74页。6.3

微粒群算法PSO的参数设置：

◆种群规模:

一般取20-40◆粒子长度：由优化问题决定，就是问题解的长度◆粒子范围：由优化问题决定，每一维可设定不同的范围◆最大速度：决定粒子在一个循环中最大的移动距离，通常设为粒子的范围宽度◆学习因子：二者相等且在[0,4]之间，通常取为2◆终止条件：最大循环次数以及最小错误要求，由具体问题确定◆惯性权值：第57页/共73页第五十七页，共74页。6.3

微粒群算法PSO与GA的比较：

(1)共同之处:

两者都随机初始化种群，而且都使用适应值来评价系统，并且都根据适应值来进行一定的随机搜索，两个系统都不是保证一定找到最优解

(2)区别：

-PSO没有遗传操作如交叉、变异等，而是根据自己的速度来决定搜索

-粒子还有一个重要的特点，就是有记忆，而GA没有

-PSO的信息共享机制与GA也很不同，在GA中染色体互相共享信息，整个种群的移动是比较平均的向最优区域移动，而在PSO中只有Gbest给出信息给其他的粒子，整个搜索更新过程是跟随当前最优解的过程。第58页/共73页第五十八页，共74页。6.4

蚁群算法蚁群算法（Antcolonyalgorithm）是20世纪90年代初意大利学者M.Dorigo，V.Maniezzo，A.Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为提出来的一种新型的模拟进化算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。第59页/共73页第五十九页，共74页。6.4

蚁群算法简单的蚂蚁寻食过程：蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。第60页/共73页第六十页，共74页。6.4

蚁群算法简单的蚂蚁寻食过程：本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。第61页/共73页第六十一页，共74页。6.4

蚁群算法简单的蚂蚁寻食过程：

◆假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。

◆寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。

◆若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。

◆若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。第62页/共73页第六十二页，共74页。6.4

蚁群算法人工蚁群算法：

◆基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。

◆

人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。

◆两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。第63页/共73页第六十三页，共74页。6.4

蚁群算法蚁群算法与TSP问题：

TSP问题表示为一个N个城市的有向图G=（N,A），其中 城市之间距离目标函数为

其中为城市1,2，…n的一个排列，且有第64页/共73页第六十四页，共74页。6.4

蚁群算法蚁群算法与TSP问题：

◆TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：(1)信息素值，也称信息素痕迹。(2)可见度，即先验值。

◆信息素的更新方式有2种：一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。第65页/共73页第六十五页，共74页。6.4

蚁群算法蚁群算法与TSP问题：

◆蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。

◆蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。第66页/共73页第六十六页，共74页。6.4

蚁群算法蚁群算法步骤：

STEP0

对n个城市的TSP问题，城市间的距离矩阵为