ch2智能优化算法-研究生

第二章智能优化算法第二章智能优化算法概述进化计算及其应用模拟退火算法及其应用群智能算法及其应用3参考教材王凌,?智能优化算法及其应用?,清华大学出版社,施普林格出版社,2001年10月第1版.王小玉,?遗传算法—理论、应用与软件实现?,西安交通大学出版社,2002年1月第1版王耀南,?智能信息处理技术?,高等教育出版社,2003年8月第1版.42.1概述一、最优化问题分类可分为函数优化问题和组合优化问题两大类。函数优化问题：最小化和最大化优化对象：一定区间S内的连续变量最小化问题的一般描述：求Xmin

S使f(Xmin)在S上全局最小符号化表示为：

X

S:f(Xmin)

f(X)S为Rn上的有界子集，即变量的定义域f:S→R为n维实值函数52.1概述一、最优化问题分类函数优化问题最大化问题的一般描述：求Xmax

S使f(Xmax)在S上全局最大符号化表示为：

X

S:f(Xmax)

f(X)S为Rn上的有界子集，即变量的定义域f:S→R为n维实值函数82.1概述经典算法如：线性规划、动态规划、整数规划、分枝定界等运筹学中的传统算法。算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用。构造型算法用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。调度中的典型构造型算法有：Johnson法、Palmer法、基于枚举树的分区法等。92.1概述改进型算法，或称邻域搜索算法从任一解出发，通过对其邻域的不断搜索和当前解的替换来实现优化。根据搜索行为，可分为局部搜索法和指导性搜索法〔如SA、GA〕。基于系统动态演化的方法将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络、蚁群算法、混沌搜索等。混合型算法上述各算法从结构或操作上混合而产生的各类算法。2.2进化算法及其应用2.2.1进化算法简介2.2.2遗传算法与生物进化学说2.2.3遗传算法的计算机实现2.2.4遗传算法解决TSP问题2.2.5遗传算法的特点10产生背景主要特点理论根底分类说明2.2.1进化算法简介一、产生背景对自身的大脑信息处理机制进行模拟----人工神经网络理论对自身模糊性的思维方式进行类比----模糊系统对自然界中动植物的免疫机理进行模拟----免疫系统对自身进化这一更为宏观的过程学习----进化算法(EvolutionaryComputation，EC)2.2.1进化算法简介进化算法是一种模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术。优胜劣汰，适者生存进化规则繁殖、变异、竞争、选择指导思想进化算法是建立在模拟生物进化过程的根底上而产生的一种随机搜索优化技术2.2.1进化算法简介2.2.1进化算法简介二、主要特点在算法中主要表现为全局搜索方式，表达在下面几个方面有指导搜索：依据是每个个体的适应度值自适应搜索：通过进化操作改进群体性能渐进式寻优：每代进化的结果都优于上一代并行式搜索：对每一代群体所有个体同时进行黑箱式结构：只要研究输入和输出而不需考虑过程全局最优解：在整个搜索区域的各个局部同时进行内在学习型：学习是一种有保存的行为稳健性强：不同的条件和环境下算法适用和有效性2.2.1进化算法简介三、理论根底进化计算是模拟生物进化理论而形成的一种全局优化自适应概率搜索的算法理论。具有深厚的生物学理论根底：遗传：父代利用遗传基因将自身的基因信息交付给下一代〔子代〕，属性特征相同或相近。变异：子代和父代，以及子代各个体之间存在着一定的差异，在进化过程中是随机发生的。生存斗争和适者生存：适应性变异较强的个体被保存下来，而适应性变异较弱的个体那么被淘汰。2.2.1进化算法简介四、分类说明从进化的过程性质进行区分，与进化算法相关的算法可细分为：遗传算法：最具代表性也是最根本的进化策略：侧重于数值分析进化规划：介于数值分析与人工智能之间遗传规划：偏向以程式表现人工智能行为进化动力学：偏向进化的自组织和系统动力学特性分类系统：适应动态环境学习动态模拟系统：用以观察复杂系统交互元胞自动机：研究人工生命蚁群系统：模拟蚂蚁群体行为172.2.2遗传算法与生物进化学说1885年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面：

遗传 变异 生存斗争和适者生存182.2.2遗传算法与生物进化学说20世纪20年代，一些学者用统计生物学和种群遗传学的成就重新解释达尔文自然选择理论，形成现代综合进化论。种群遗传学认为：在一定地域中一个物种的全体成员构成一个种群；生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。192.2.2遗传算法与生物进化学说GA中与生物学相关的概念与术语：个体种群适应度选择交叉变异优化问题中的描述：解解集/解空间评价函数/目标函数/寻优函数产生新解的方法2.2.3遗传算法的计算机实现 20世纪60年代中期，J.Holland在前人工作根底上，提出位串编码技术。这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。 随后，Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了开创性著作“AdaptationinNaturalandArtificalSystem〞。 以后更是将算法进行了推广，并应用到优化以及学习中，正式将其命名为遗传算法(GeneticAlgorithms，简称GA)。21遗传算法根本思路：计算开始时，随机初始化一定数目的个体〔即种群〕，并计算每个个体的适应度值，产生第一代〔初始代〕。如果不满足优化准那么，开始新一代的计算：按照适应度值选择个体，产生下一代；父代按一定概率进行交叉操作，产生子代；所有的子代按一定概率变异，形成新的一代。计算新子代的适应度值。这一过程循环执行，直到满足优化准那么为止。2.2.3遗传算法的计算机实现22遗传算法根本流程2.2.3遗传算法的计算机实现23需要解决的问题：种群适应度函数复制〔选择〕交叉变异编码：首先需要解决的问题遗传操作242.2.3遗传算法的计算机实现什么是编码？解题过程中，每个具体的解就对应一个个体。简单来说，编码就是将问题的解用一种码来表示，从而将问题的解(状态)空间与GA的码空间相对应。252.2.3遗传算法的计算机实现编码的意义：编码方案很大程度上决定了如何进行群体的遗传运算及其运算效率。一个好的编码方案，可以使遗传运算简单地实现和执行。否那么，可能使运算难以实现。编码是应用GA时要解决的首要问题，也是设计GA的一个关键步骤，选择或设计一种适宜的编码方案对算法的性能和效率意义重大。262.2.3遗传算法的计算机实现例：考虑一元函数求最大值的优化问题272.2.3遗传算法的计算机实现f(x)在区间[-1,2]可微，先用微分法求取f(x)的最大值。上式的解有无穷多个：

i是一种接近于0的实数递减序列。i为奇数时，xi对应局部极大值点；i为偶数时，xi对应局部极小点。x19是区间[-1,2]内的最大点。282.2.3遗传算法的计算机实现步骤1：编码

已有的编码方案：二进制编码、Delta编码、格雷码编码、实数编码、自然数编码、符号编码、动态变量编码、链表编码、矩阵编码、树型编码、量子比特编码……292.2.3遗传算法的计算机实现步骤1：编码

最常用的编码方法：二进制编码使用二值编码符号集{0,1}。每个个体是一个二进制符号串，串长与求解精度有关。根据模式理论，采用二进制编码算法处理的模式最多，几乎任何问题都可以用二进制编码来表达。因此，二进制编码应用是最早和最广泛的，它是GA中最常用的一种编码方案。302.2.3遗传算法的计算机实现设：求解精度为6位小数因为，采用二进制编码方法，不能表示小数和负数所以，将闭区间[-1,2]改为：[0,3

106]又因为：3

106=(1011011100011011000000)2 2097152=221<3×106<222=4194304所以，编码的二进制串长至少需要22位

312.2.3遗传算法的计算机实现穷尽编码：二进制串(0000000000000000000000) 表示区间端点值-1

二进制串 表示区间端点值2

不穷尽编码？322.2.3遗传算法的计算机实现将一个二进制串〔b21b20…b0〕转化为区间[-1,2]内对应的实数，需要采用以下步骤：将二进制数转化为十进制数x’将x’转化为区间[-1，2]内的实数x332.2.3遗传算法的计算机实现步骤1：编码二进制编码的主要优点：编码、解码操作简单易行选择、交叉和变异等遗传操作便于实现符合最小符号集编码原那么便于利用模式定理对算法进行理论分析。342.2.3遗传算法的计算机实现步骤2：产生初始种群产生一定数目的个体组成种群初始个体的产生方法：随机法、启发法。种群规模是影响算法优化性能和效率的因素之一。种群规模是指种群中个体数目。种群太小，不能提供足够的采样点，导致算法性能很差，甚至得不到问题的可行解。种群太大，尽管可增加优化信息以阻止早熟收敛的发生，但会增加计算量，使收敛时间太长。352.2.3遗传算法的计算机实现步骤3：计算适应度遗传算法在进化搜索中根本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。一般，适应度函数是由目标函数变换而成。假设目标函数为最大化问题：Fit(x)=f(x)假设目标函数为最小化问题：Fit(x)=-f(x)本例的目标函数在定义域内均大于0，而且求函数最大值，可直接引用目标函数作为适应度函数：f(s)=f(x)，式中，二进制串s对应变量x的值。362.2.3遗传算法的计算机实现设某个个体的二进制为：s372.2.3遗传算法的计算机实现设有三个个体的二进制为：s1s2s3分别对应于变量：x1=0.637197、x2=-0.958973、x3=1.627888个体的适应度为：f(s1)=f(x1)=2.586345、f(s2)=f(x2)=1.078878f(s3)=f(x3)=3.250650三个个体中s3的适应度最大，因此，s3为最正确个体。38步骤4：选择选择操作决定从父代种群中选取哪些个体遗传到下一代种群中，它以个体的适应度值为评价指标，对种群中个体进行优胜劣汰。最常用的算子：比例选择算子〔选择的蒙特卡罗法〕根本思想：每个个体被选中的概率与其适应度值成正比。设种群规模为M，个体i的适应度值为fi，那么个体i被选中的概率Pi为：2.2.3遗传算法的计算机实现39当Pi给定后，产生[0,1]区间内的均匀随机数来决定哪个个体参加交叉操作。即：用赌轮方式决定个体的选择份数。个体i1234567适应度值fi1.3640.8680.3723.3481.7361.243.348

fi=12.4选择概率Pi0.110.070.030.270.140.100.27

Pi=fi/fi

2.2.3遗传算法的计算机实现402.1遗传算法及其应用41经选择产生的交叉种群由以下个体组成：1,2,3,5,6,9,……2.2.3遗传算法的计算机实现个体i1234567891011适应度fi2.01.81.61.41.21.00.80.60.40.20.1

fi=11.1选择概率0.180.160.140.130.110.090.070.050.040.020.01fi/

fi累积概率0.180.340.480.610.720.810.880.930.970.991.00轮数1234567891011随机数0.810.320.960.010.650.42……………42步骤5：交叉在选择操作根底上，根据交叉概率pc进行交叉操作：把两个父个体的局部结构进行替换重组，生成新个体。对应于二进制编码，常用的交叉算子是：单点交叉。交叉点的范围为：[1，N-1]，N为二进制串的串长。交叉操作时，个体以该点为分界相互交换变量。2.2.3遗传算法的计算机实现43设经过选择操作，得到两个个体：

s2s3=(11100|

)随机选择一个交叉点，交叉后产生新的子个体：

s2’=(00000|)s3f(s2’)=f(-0.998113)=1.940865、f(s3’)=f(1.666028)=3.4592452.2.3遗传算法的计算机实现44pc控制交叉操作频率，使局部被选择的个体进行交叉操作pc太大，个体更新过快，高适应度值的个体很快被破坏。pc太小，很少进行交叉操作，使搜索停滞不前。本例中，交叉概率取为：pc=0.82.2.3遗传算法的计算机实现45步骤6：变异基于二进制编码的GA中，变异是指将被选中个体的某一位进行翻转操作，即：将1换为0，将0换为1。设以一小概率选择了第5位变异：s3=(1110000000s3’=(11101f(s3’)=f(1.721638)=0.917743f(s3)=3.250650假设选择第10位变异，产生的新个体为：s3’’=(1110100001f(s3’’)=f(1.630818)=3.343555f(s3)=3.2506502.2.3遗传算法的计算机实现46不是所有被选择的个体，都要进行变异操作。变异概率是加大种群多样性的重要因素。概率太小很难产生新个体。概率太大会使GA成为随机搜索。基于二进制编码的GA中，通常一个较低的变异率足以防止整个种群中任一位置的基因一直保持不变。本例中，变异概率取为：pm=0.01

2.2.3遗传算法的计算机实现47步骤7：算法的终止判断最常用的终止条件：事先给定一个最大进化步数；判断最正确优化值是否连续假设干步没有明显变化。2.2.3遗传算法的计算机实现482.2.4遗传算法求解TSP问题编码最常用策略：路径编码直接采用城市在路径中的位置来构造用于优化的状态。例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3路径编码：(541798623)49502.2.4遗传算法求解TSP问题512.2.5遗传算法的特点GA是一种通用的优化算法，它的优点有：编码技术和遗传操作比较简单；优化不受限制性条件的约束；隐含并行性和全局解空间搜索。随着计算机技术的开展，GA愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功应用。522.3模拟退火算法及其应用模拟退火算法〔SimulatedAnnealing，SA)是一种通用的优化算法。已在：生产调度、控制工程、机器学习、神经网络、图像处理等工程领域中得到了广泛应用。2.3.1模拟退火算法与物理退火过程2.3.2模拟退火算法的计算机实现2.3.3模拟退火算法解决TSP问题2.3.4模拟退火算法的特点532.3.1SA算法与物理退火过程SA算法是基于MenteCarlo迭代求解策略的一种随机寻优算法，其出发点是：基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。54物理退火过程由以下三局部组成：加温过程增强粒子热运动，使其偏离平衡位置。当温度足够高时，固体熔解为液体，消除系统可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。等温过程对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总朝自由能减少的方向进行，当自由能到达最小时，系统到达平衡态。冷却过程使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。2.3.1SA算法与物理退火过程55为了模拟固体在恒定温度下到达热平衡的过程，可采用MonteCarlo方法，该方法简单，但必须大量采样才能得到较精确结果，计算量很大。考虑到物理系统倾向于能量较低的状态，而热运动又阻碍它准确落到最低态，采样时着重取那些有重要奉献的状态那么可较快到达较好的结果。1953年，Metropolis等据此提出了重要性采样法〔也称为Metropolis准那么〕，即以概率接受新状态。2.3.1SA算法与物理退火过程56Metropolis准那么：在温度t，由当前状态i产生新状态j，两者的能量分别为Ci和Cj，假设Cj<Ci，那么接受新状态j为当前状态；否那么，假设概率pr=exp[-(Cj-Ci)/(kt)]大于[0,1)区间内的随机数，仍接受新状态j为当前状态;假设不成立，那么保存状态i为当前状态。其中，k为Boltzmann常数。2.3.1SA算法与物理退火过程57SA算法的根本思路：由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。2.3.1SA算法与物理退火过程581953年，Metropolis等提出SA思想。1983年，Kirkpatrick〔柯克帕特里克〕等将其用于组合优化，目的在于：为具有NP复杂性的问题提供有效的近似求解算法；克服优化过程陷入局部极小；克服初值依赖性。2.3.1SA算法与物理退火过程

模拟退火算法流程图5960需要解决的问题：状态产生函数状态接受函数温度更新函数〔退温函数〕内循环终止准那么〔抽样稳定准那么〕外循环终止准那么〔退火结束准那么〕初温编码能量函数2.3.2模拟退火算法的计算机实现退火历程三函数二准那么61例：考虑一元函数求最大值的优化问题2.3.2模拟退火算法的计算机实现62步骤1：确定编码方式和能量函数〔目标函数〕最常用的编码方案：实数编码，以实数来表示求解状态。s=1.8函数优化问题中，能量函数由待优化函数变换而成。假设目标函数为最大化问题：C(s)=-f(s)假设目标函数为最小化问题：C(s)=f(s)2.3.2模拟退火算法的计算机实现注意：与遗传算法适应度函数设计的区别63步骤2：确定初温实验说明，初温t0越大，获得高质量解的几率越大，但计算时间增加。初温确实定应折衷考虑优化质量和效率。常用确实定初温的方法包括：均匀抽样一组状态，以各状态目标值的方差为初温。随机产生一组状态，确定两两状态间的最大目标值差|∆max|，计算初温，t0=-∆max/lnpr初始接受概率pr理论上接近于1。设为某个较大的常数。2.3.2模拟退火算法的计算机实现64步骤3：确定初始状态〔初始解〕理论上，初始状态可以随机取。为了提高优化效率，可采用启发式算法快速得到一个解，并以此为SA的初始状态。2.3.2模拟退火算法的计算机实现65步骤4：状态产生函数〔新解产生函数〕设计的出发点是尽可能保证产生的候选解遍布全部解空间。最常用的状态产生函数：snew=sold+为扰动幅度参数，为随机扰动变量。随机扰动可服从柯西分布、高斯分布、均匀分布。2.3.2模拟退火算法的计算机实现66柯西分布：a为尺度参数高斯分布：

为方差，均值为0均匀分布：2.3.2模拟退火算法的计算机实现67步骤5：状态接受函数该函数的引入是SA算法实现全局搜索的最关键因素，一般以概率方式给出。最常用的状态接受函数：min{1,exp[-(C(sj)-C(si))/tk]}random[0,1]?设计状态接受函数，应该遵循以下原那么：固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率；随温度下降，接受使目标函数值上升解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。2.3.2模拟退火算法的计算机实现68步骤6：内循环终止准那么或称Metropolis抽样稳定准那么

常用的抽样稳定准那么包括：检验目标函数的均值是否稳定；连续假设干步的目标值变化较小；按一定的步数抽样。2.3.2模拟退火算法的计算机实现69步骤7：退温函数用于在外循环中修改温度值。最常用的是指数退温函数：

tk+1=

tk

为退温速率，0<

<l，

大小可以不断变化。2.3.2模拟退火算法的计算机实现70步骤8：外循环终止准那么〔算法终止准那么〕用于决定算法何时结束。设置温度终值te是一种简单的方法，SA算法的收敛性理论中要求te趋于零，这显然不实际。通常的做法包括：设置终止温度的阈值；设置外循环迭代次数；算法搜索到的最优值连续假设干步保持不变；检验系统熵是否稳定。2.3.2模拟退火算法的计算机实现712.3.3模拟退火算法求解TSP问题模拟退火算法编码最常用策略：路径编码直接采用城市在路径中的位置来构造用于优化的状态。例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3路径编码：(541798623)72状态产生函数对于基于路径编码的SA状态产生函数操作，可设计为：互换操作逆序操作插入操作例：状态为(541798623)，两随机位置为2，6互换操作结果：(581794623)逆序操作结果：(589714623)插入操作结果：(584179623)2.3.3模拟退火算法求解TSP问题73SA通过概率判断来接受新状态，在局部极小解处有时机跳出，并最终趋于全局最优。理论上，初温充分高、降温足够慢、每一温度下抽样足够长、最终温度趋于零时，算法以概率1收敛到全局最优解。SA的参数选择是一个难题，通常只能依据一定的启发式准那么或大量的实验加以选取。2.3.4模拟退火算法的特点2.4群智能算法及其应用2.4.1群智能算法概述2.4.2蚁群算法及应用2.4.3粒子群算法及应用2.4.4鱼群算法及应用2.4.5鸟群算法应用2.4.6猫群算法及应用742.4.1群智能算法概述一、生物群体的启示二、群智能的概念三、群智能的意义和开展前景四、群智能算法与进化计算的异同五、群智能算法的分类2.4.1群智能算法概述一、生物群体的启示鸟群通过协作进行捕食；鱼聚集成群可以有效的逃避捕食者；房间偏僻角落里的蛋糕总会先被蚂蚁发现；头脑简单的蜜蜂却能构造出世界上最完美的建筑物。76一、生物群体的启示生物群中的每个个体只有简单的信息处理能力和行为能力鸟群：飞行，捕食，避碰……昆虫：爬行，觅食，产生信息素……群体中各个个体之间可以进行信息交互。鸟群：视觉，听觉，磁场……昆虫：感知信息素……群体的能力要远远超出个体能力的简单叠加。信息感知能力、分工协作能力、适应生存能力2.4.1群智能算法概述772.4.1群智能算法的概述二、群智能〔SwarmIntelligence,SI〕的概念概念 把群居昆虫的集体行为称作“群智能〞〔“群体智能〞、“群集智能〞、“集群智能〞等〕特点 个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂〔智能〕的行为特征。1.群智能概念的开展过程分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。——byBeni(贝尼)，Hackwood(哈克伍德)任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。——byBonabeau(博纳博)、Dorigo(杜里戈)&Theraula无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。 ——byBonabeau2.4.1群智能算法概述792.定义SI的五条根本原那么〔byMarkMillonas1994)ProximityPrinciple:群内个体具有能执行简单的时间或空间上的评估和计算的能力。QualityPrinciple:群内个体能对环境(包括群内其它个体)的关键性因素的变化做出响应。PrincipleofDiverseResponse:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。2.4.1群智能算法概述802.定义SI的五条根本原那么〔byMarkMillonas1994)StabilityPrinciple:不是每次环境的变化都会导致整个群体的行为模式的改变。AdaptabilityPrinciple:环境所发生的变化中，假设出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。2.4.1群智能算法概述81三、SI的意义和开展前景 群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但与梯度法及传统的演化算法相比，主要优点为：无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性。以非直接的信息交流方式确保了系统的扩展性。并行分布式算法模型，可充分利用多处理器。对问题定义的连续性无特殊要求。2.4.1群智能算法概述灵活性：群体可以适应随时变化的环境；自我组织：活动既不受中央控制，也不受局部监管。易于实现算法中仅涉及各种根本的数学操作。数据处理过程对CPU和内存的要求不高。只需要目标函数的输出值，不需要它的梯度信息。2.4.1群智能算法概述在没有集中控制且不提供全局模型的前提下，群智能的思路为寻找复杂的分布式问题求解方案提供了根底。已完成的群智能理论和应用方法研究证明群智能方法能够有效解决大多数全局优化问题群智能潜在的并行性和分布式特点为处理大量的、以数据库形式存在的数据提供了技术保证。2.4.1群智能算法概述无论从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是有重要学术意义和现实价值。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。作为一种新兴的演化计算技术，群智能已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。2.4.1群智能算法概述四、群智能算法与进化计算的异同SI与EC的相同点都研究个体与群体的关系都存在个体之间的信息传递都是为了解决实际问题，而非单纯的模拟自然现象都属于随机搜索算法SI与EC的不同点SI模拟的是个体之间的协同作用EC模拟的是适者生存的自然选择机制。2.4.1群智能算法的概述2.4.1群智能算法的概述五、群智能算法的分类广义的群智能算法包括：粒子群算法：模拟鸟群觅食行为蚁群算法：模拟蚁群觅食行为鱼群算法：模拟鱼群的觅食、聚群及追尾行为免疫算法：模拟生物免疫系统工作机理细菌觅食算法：模拟大肠杆菌觅食行为混合算法：多种群智能算法的结合一、蚁群算法起源二、蚁群算法的原理分析三、蚁群算法与TSP问题2.4.2蚁群算法及应用2.4.2蚁群算法及应用一、蚁群算法起源1992年，意大利学者Dorigo从生物进化的机制中受到启发，在其博士论文中提出蚂蚁系统(AntSystem)，模拟自然界蚂蚁搜索路径的行为。随后，Dorigo等人进一步将蚂蚁算法开展为一种通用的优化技术----蚁群优化(AntColonyOptimization,ACO)。从Dorigo在90年代最早提出AS，并将其应用于解决TSP问题开始，根本的蚁群算法得到了不断的开展和完善，并在其他许多实际优化问题求解中进一步得到了验证。蚂蚁从A点出发，速度相同，食物在D点。可随机选择的路线：ABD或ACD。设初始时每条路线分配一只蚂蚁，每单位时间行走一步上图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。2.4.2蚁群算法及应用简化的蚂蚁寻食过程：本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A走ACD的蚂蚁刚好走到D点。2.4.2蚁群算法及应用简化的蚂蚁寻食过程：简化的蚂蚁寻食过程：设蚂蚁每经过一处所留下的信息素为一个单位。36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物。ABD的路线往返了2趟，每一处的信息素为4个单位ACD的路线往返了1趟，每一处的信息素为2个单位信息素比值为2:1按信息素指导，蚁群在ABD路线上增派一只蚂蚁(共2只)，ACD路线上仍然是一只蚂蚁。2.4.2蚁群算法及应用简化的蚂蚁寻食过程：72个时间单位后，两条线路上的信息素单位积累为12和4，比值为3:1。假设按以上规那么继续，蚁群在ABD路线上再增派一只蚂蚁(共3只)，ACD路线上仍然是一只蚂蚁。再36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。假设继续进行，按信息素指导，最终所有蚂蚁会放弃ACD路线，都选择ABD路线，这就是正反响效应。2.4.2蚁群算法及应用 最初提出的AS有三种版本：Ant-density、Ant-quantity、Ant-cycle前两种算法中，蚂蚁在两个位置节点间每移动一次后即更新信息素。Ant-cycle中，所有蚂蚁都完成了自己的行程后，才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。2.4.2蚁群算法及应用与其它各种通用的启发式算法相比，在不大于75城市的TSP中，AS的求解能力比较理想。但是当问题规模扩展时，AS的解题能力大幅度下降。AS改进版共同点：增强蚂蚁搜索过程中对最优解的探索能力差异：搜索控制策略2.4.2蚁群算法及应用其后的ACO研究工作主要都集中在AS性能的改进方面。较较早的一种改进是精英策略(ElitistStrategy)，其思想是：在算法开始后，对所有已发现的最好路径给予额外增强，并将随后与之对应的行程记为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英〞，从而增大较好行程的选择时机。这种改进型算法能以更快的速度获得更好的解。但是假设选择的精英过多，那么算法会由于较早收敛于局部次优解，而导致搜索的过早停滞。2.4.2蚁群算法及应用蚁群算法能够用于解决大多数优化问题或者能够被转化为优化求解的问题，是一种有开展前景的算法。目前，其应用领域已扩展到多目标优化数据分类数据聚类模式识别生物系统建模流程规划信号处理机器人控制决策支持仿真和系统辩识2.4.2蚁群算法及应用二、蚁群算法的原理蚂蚁寻食过程：寻找路径时，在路径上释放出一种特殊的信息素。碰到没有走过的路口，随机挑选一条路径，并释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率相对较大。正反响：最优路径上激素浓度越来越大，其它路径上激素浓度随时间的流逝而消减。最终整个蚁群找出最优路径。2.4.2蚁群算法及应用2.4.2蚁群算法及应用自然蚁群与人工蚁群算法：人工蚁群中把具有简单功能的工作单元看作蚂蚁。相似处：优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。区别：人工蚁群能记忆已访问过的节点，在选择下条路径时是按一定算法规律有意识地寻找最短路径。如，TSP问题中可预先知道当前城市到下一个目的地的距离。2.4.2蚁群算法及应用三、蚁群算法与TSP问题初始的蚁群算法是基于图的蚁群算法(graph-basedantsystem，GBAS)，2000年由Gutjahr(古特雅尔)在FutureGenerationComputingSystems提出。TSP问题表示为N个城市的有向图：G=(N,A)目标函数w=(i1,i2,…,in)为城市1,2,…,n的一个排列(dij)n

n为城市间距离矩阵设m只蚂蚁在图的相邻节点间移动，协作异步地得到解。蚂蚁计算出下一步所有可达节点的一步转移概率，并按此概率实现一步移动，依此往复。一步转移概率由图中每条边上的两类参数决定：信息素值、可见度(即先验值)。信息素的更新有2种方式：挥发——所有路径上信息素以一定比率减少增强——给评价值“好〞(有蚂蚁走过)的边增加信息素2.4.2蚁群算法及应用STEP0

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

n给TSP图中的每一条弧(i,j)赋信息素初值：

ij(0)=1/|A||A|：表示图中弧(i,j)的数目，即矩阵(dij)n

n中不为零的数；设有m只蚂蚁工作，都从同一城市i0出发当前最好解是：w*=(1,2,…,n)目标函数：2.4.2蚁群算法及应用STEP1(外循环)假设满足算法停止规那么，停止计算，输出计算得到的最好解给定外循环的最大数目，说明有足够的蚂蚁工作；当前最优解连续K次相同而停止，K是给定的整数，表示算法已收敛；给定优化问题的下界和误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。否那么使蚂蚁s(1sm)从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集。2.4.2蚁群算法及应用STEP2(内循环)按蚂蚁1sm的顺序分别计算在城市i，假设L(s)=N或{l|(i,l)A,lL(s)}=，完成蚂蚁s的计算。否那么，假设T={l|(i,l)A,lL(s)}-{i0}，以概率 到达j，L(s)=L(s){j}，il=j假设L(s)N且T=，那么到达i0， L(s)=L(s){i0}，il=i0 重复STEP22.4.2蚁群算法及