计算群体智能

计算群体智能第一页，共一百零二页，编辑于2023年，星期一1、优化方法遗传算法概述传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法

GA、漫步法（RandomWalk）、模拟退火法

第二页，共一百零二页，编辑于2023年，星期一2、遗传算法优点

遗传算法（GA）模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。

第三页，共一百零二页，编辑于2023年，星期一遗传算法基本原理1、基本思想

模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。2、遗传算法的基本运算⑴选择运算⑵交换操作⑶变异第四页，共一百零二页，编辑于2023年，星期一选择运算

从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）某染色体被选的概率：Pcxi为种群中第i个染色体，f(xi)为第i个染色体的适应度值。第五页，共一百零二页，编辑于2023年，星期一具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。第六页，共一百零二页，编辑于2023年，星期一举例：

⒈具有6个染色体的二进制编码、适应度值、Pc累计值。

染色体的适应度和所占的比例用转轮方法进行选择第七页，共一百零二页，编辑于2023年，星期一染色体被选的概率染色体编号12345678910适应度8217721211737被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计8

10

2734364859666976被选的染色体个数随机数2349761312757所选染色体号码37103137第八页，共一百零二页，编辑于2023年，星期一交换操作

方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A’11010001

B’01011110第九页，共一百零二页，编辑于2023年，星期一变异模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.第十页，共一百零二页，编辑于2023年，星期一GA流程第十一页，共一百零二页，编辑于2023年，星期一简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0<G<1③选择方法:转轮法,精英选择法,竞争法.④交换率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%第十二页，共一百零二页，编辑于2023年，星期一实例1、产生初始种群00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）1110010110100101101111000000011001110100000101001（12）（5）（19）（10）（14）2、计算适应度第十三页，共一百零二页，编辑于2023年，星期一3、选择个体染色体适应度选择概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.0869570.05434858＋5＋2＋10＋7＋12＋5＋19＋10＋140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第十四页，共一百零二页，编辑于2023年，星期一3、选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第十五页，共一百零二页，编辑于2023年，星期一3、选择在0～1之间产生一个随机数：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰第十六页，共一百零二页，编辑于2023年，星期一4、交叉000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011000001110010110110000000110011101000001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011第十七页，共一百零二页，编辑于2023年，星期一5、变异0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011第十八页，共一百零二页，编辑于2023年，星期一6、至下一代，适应度计算→选择→交叉→变异，直至满足终止条件。第十九页，共一百零二页，编辑于2023年，星期一遗传算法的应用及一些问题1、遗传算法的应用领域（1）组合优化（2）函数优化（3）自动控制（4）生产调度（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘2、遗传算法在应用中的一些问题1）知识的编码

二进制和十进制的比较：二进制有更多图式和更大的搜索范围；十进制更接近于实际操作。第二十页，共一百零二页，编辑于2023年，星期一

2）适应度函数

适应度函数值必须非负，根据情况做适当的处理。

第二十一页，共一百零二页，编辑于2023年，星期一如图第二十二页，共一百零二页，编辑于2023年，星期一3）全局最优和收敛性。

根据图式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。举例：3位欺骗函数第二十三页，共一百零二页，编辑于2023年，星期一4.2粒子群算法第二十四页，共一百零二页，编辑于2023年，星期一

粒子群优化算法（PSO）是一种进化计算技术（evolutionarycomputation）,由Eberhart博士和kennedy博士于1995年提出(KennedyJ，EberhartR．

Particleswarmoptimization．ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks．1995．1942~1948.)。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解．

PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

第二十五页，共一百零二页，编辑于2023年，星期一设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。第二十六页，共一百零二页，编辑于2023年，星期一

抽象：鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)．每个粒子都有一个由目标函数决定的适应值(fitnessvalue)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi．这个可以看作是粒子自己的飞行经验．除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)．这个可以看作是粒子同伴的经验．粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

第二十七页，共一百零二页，编辑于2023年，星期一PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数。第二十八页，共一百零二页，编辑于2023年，星期一Vi

是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi是粒子的当前位置。c1和c2是学习因子，通常取c1＝c2＝2在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的Vmax，那么这一维的速度就被限定为Vmax。（Vmax

>0）从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。第二十九页，共一百零二页，编辑于2023年，星期一1998年shi等人在进化计算的国际会议上发表了一篇论文《Amodifiedparticleswarmoptimizer》对前面的公式(1)进行了修正。引入惯性权重因子。（3）式非负，称为惯性因子。公式(2)和(3)被视为标准pso算法。第三十页，共一百零二页，编辑于2023年，星期一标准PSO算法的流程：Step1:初始化一群微粒(群体规模为m)，包括随机位置和速度；Step2:评价每个微粒的适应度；Step3:对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest;Step4:对每个微粒，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest;Step5:根据(2)、(3)式调整微粒速度和位置；Step6：未达到结束条件则转Step2。迭代终止条件根据具体问题一般选最大迭代次数或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。第三十一页，共一百零二页，编辑于2023年，星期一方程(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置，当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only):被称为全局PSO算法.粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题比标准PSO更易陷入局部最优。当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。第三十二页，共一百零二页，编辑于2023年，星期一参数有：群体规模m，惯性因子，学习因子c1和c2最大速度Vmax，迭代次数Gk。群体规模m一般取20～40，对较难或特定类别的问题可以取到100～200。最大速度Vmax决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点;如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。参数分析第三十三页，共一百零二页，编辑于2023年，星期一权重因子：包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。C1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。

如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得w的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。第三十四页，共一百零二页，编辑于2023年，星期一基本PSO是用于实值连续空间，然而许多实际问题是组合优化问题，因而提出离散形式的PSO。速度和位置更新式为：thenelse其中：为sigmoid函数离散二进制PSO第三十五页，共一百零二页，编辑于2023年，星期一4.3模拟退火算法

第三十六页，共一百零二页，编辑于2023年，星期一4.3.1模拟退火算法及模型

算法的提出

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。4.3.1.1物理退火过程第三十七页，共一百零二页，编辑于2023年，星期一物理退火过程

什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。第三十八页，共一百零二页，编辑于2023年，星期一物理退火过程

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。第三十九页，共一百零二页，编辑于2023年，星期一数学表述

在温度T，分子停留在状态r满足Boltzmann概率分布第四十页，共一百零二页，编辑于2023年，星期一数学表述在同一个温度T，选定两个能量E1<E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。<1>0第四十一页，共一百零二页，编辑于2023年，星期一数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。能量最低状态非能量最低状态第四十二页，共一百零二页，编辑于2023年，星期一Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。第四十三页，共一百零二页，编辑于2023年，星期一若在温度T，当前状态i→新状态j

若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j

为当前状态；若不成立则保留状态i

为当前状态。第四十四页，共一百零二页，编辑于2023年，星期一p=exp[-(Ej-Ei)/kBT]

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。第四十五页，共一百零二页，编辑于2023年，星期一相似性比较

组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量第四十六页，共一百零二页，编辑于2023年，星期一基本步骤

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。第四十七页，共一百零二页，编辑于2023年，星期一影响优化结果的主要因素

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。三函数两准则初始温度第四十八页，共一百零二页，编辑于2023年，星期一4.3.2模拟退火算法关键参数和操作的设计原则

产生的候选解应遍布全部解空间方法

在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生4.3.2.1状态产生函数第四十九页，共一百零二页，编辑于2023年，星期一原则

(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；

(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；

(3)当温度趋于零时，只能接受目标函数下降的解。方法

具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]4.3.2.2状态接受函数第五十页，共一百零二页，编辑于2023年，星期一收敛性分析

通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明

初温越大，获得高质量解的机率越大，但花费较多的计算时间；4.3.2.3初温第五十一页，共一百零二页，编辑于2023年，星期一方法

（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。第五十二页，共一百零二页，编辑于2023年，星期一时齐算法的温度下降函数

（1），α越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。4.3.2.4温度更新函数第五十三页，共一百零二页，编辑于2023年，星期一非时齐模拟退火算法

每个温度下只产生一个或少量候选解时齐算法——常用的Metropolis抽样稳定准则

（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。4.3.2.5内循环终止准则第五十四页，共一百零二页，编辑于2023年，星期一常用方法

（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。4.3.2.6外循环终止准则第五十五页，共一百零二页，编辑于2023年，星期一4.3.3模拟退火算法的改进模拟退火算法的优点

质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点

由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。4.3.3.1模拟退火算法的优缺点第五十六页，共一百零二页，编辑于2023年，星期一改进的可行方案

（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。4.3.3.2改进内容第五十七页，共一百零二页，编辑于2023年，星期一改进的方式

（1）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆“Bestsofar”状态）；（3）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；（5）结合其它搜索机制的算法；（6）上述各方法的综合。第五十八页，共一百零二页，编辑于2023年，星期一4.3.4模拟退火算法的实现与应用算法流程

30城市TSP问题（d*=423.741byDBFogel）

第五十九页，共一百零二页，编辑于2023年，星期一初始温度的计算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

第六十页，共一百零二页，编辑于2023年，星期一状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。283591467283591467283591467281593467283419567235981467第六十一页，共一百零二页，编辑于2023年，星期一参数设定

截止温度tf=0.01;

退温系数alpha=0.90;

内循环次数L=200*CityNum;第六十二页，共一百零二页，编辑于2023年，星期一运行过程

第六十三页，共一百零二页，编辑于2023年，星期一运行过程

第六十四页，共一百零二页，编辑于2023年，星期一运行过程

第六十五页，共一百零二页，编辑于2023年，星期一运行过程

第六十六页，共一百零二页，编辑于2023年，星期一运行过程

第六十七页，共一百零二页，编辑于2023年，星期一运行结果

第六十八页，共一百零二页，编辑于2023年，星期一4.4蚁群算法

第六十九页，共一百零二页，编辑于2023年，星期一4.4.1蚁群优化算法起源20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——

蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法．第七十页，共一百零二页，编辑于2023年，星期一4.4.2蚁群优化算法应用领域这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。第七十一页，共一百零二页，编辑于2023年，星期一4.4.3蚁群优化算法研究现状90年代Dorigo最早提出了蚁群优化算法---蚂蚁系统（AntSystem,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。第七十二页，共一百零二页，编辑于2023年，星期一4.4.4蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。第七十三页，共一百零二页，编辑于2023年，星期一4.4.4.1简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。第七十四页，共一百零二页，编辑于2023年，星期一本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。第七十五页，共一百零二页，编辑于2023年，星期一假设蚂蚁每经过一处所留下的信息素为一个单位，则经过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路线。第七十六页，共一百零二页，编辑于2023年，星期一4.4.4.2自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。第七十七页，共一百零二页，编辑于2023年，星期一下面以TSP问题为例说明基本蚁群算法模型。TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中，，为城市1,2，…n的一个排列，。第七十八页，共一百零二页，编辑于2023年，星期一其中： 表示边（i，j）上的信息素浓度； 是启发信息，d是城市i和j之间的距离；

α和β反映了信息素与启发信息的相对重要性； 表示蚂蚁k已经访问过的城市列表。当所有蚂蚁完成周游后，按以下公式进行信息素更新。首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:第七十九页，共一百零二页，编辑于2023年，星期一其中：ρ为小于1的常数，表示信息的持久性。其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。第八十页，共一百零二页，编辑于2023年，星期一求解TSP算法步骤⑴初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中;⑵迭代过程k=1whilek=<ItCountdo(执行迭代)fori=1tomdo(对m只蚂蚁循环)forj=1ton-1do(对n个城市循环)

根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j;

将j置入禁忌表,蚂蚁转移到j;

endforendfor计算每只蚂蚁的路径长度;根据式(2)更新所有蚂蚁路径上的信息量;k=k+1;endwhile⑶输出结果,结束算法.第八十一页，共一百零二页，编辑于2023年，星期一蚁群的规模和停止规则一、蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件

1给定一个外循环的最大数目；

2当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。第八十二页，共一百零二页，编辑于2023年，星期一蚂蚁算法的缺点蚂蚁算法的缺点：1）收敛速度慢2）易于陷入局部最优第八十三页，共一百零二页，编辑于2023年，星期一4.5人工免疫算法

第八十四页，共一百零二页，编辑于2023年，星期一4.5.1免疫算法的生物学基础免疫系统是哺乳动物抵御外来有害物质侵害的防御系统，动物一生始终处于复杂多变的、充满伤害的自然环境中，能够平安无事、进行正常的生命活动，免疫系统在其中起着重要的作用。免疫是生物体的特异性生理反应,由具有免疫功能的器官、组织、细胞、免疫效应分子及基因等组成。免疫系统通过分布在全身的不同种类的淋巴细胞识别和清除侵入生物体的抗原性异物。当生物系统受到外界病毒侵害时,便激活自身的免疫系统,其目标是尽可能保证整个生物系统的基本生理功能得到正常运转。第八十五页，共一百零二页，编辑于2023年，星期一4.5.2免疫算法的起源在生物自然界中，免疫现象普遍存在，并对物种的生存与繁衍

发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物免疫主要有两种类型： 特异性免疫反应（SpecificImmunity） 非特异性免疫反应（NonspecificImmunity）；生物免疫系统是通过自我识别、相互刺激与制约而构成了一个

动态平衡的网络结构

。第八十六页，共一百零二页，编辑于2023年，星期一4.5.3免疫算法的生物免疫机制第八十七页，共一百零二页，编辑于2023年，星期一4.5.4免疫算法的基本概念 抗原：在生命科学中，是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。在我们的算法中，是指所有可能错误的基因，即非最佳个体的基因。抗体：在生命科学中，是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。第八十八页，共一百零二页，编辑于2023年，星期一免疫疫苗：根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。免疫调节：在免疫反应过程中，大量的抗体的产生降低了抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同时产生的抗体之间也存在着相互刺激和抑制的关系，这种抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫反应维持一定的强度，保证机体的免疫平衡。第八十九页，共一百零二页，编辑于2023年，星期一免疫记忆：指免疫系统将能与抗原发生反应的抗体作为记忆细胞保存记忆下来，当同类抗原再次侵入时，相应的记忆细胞被激活而产生大量的抗体，缩短免疫反应时间。抗原识别：通过表达在抗原表面的表位和抗体分子表面的对位的化学基进行相互匹配选择完成识别，这种匹配过程也是一个不断对抗原学习的过程，最终能选择产生最适当的抗体与抗原结合而排除抗原。第九十页，共一百零二页，编辑于2023年，星期一4.5.5