人工智能第三章遗传算法、蚁群算法、粒子群算法课件

第三章遗传算法、蚁群算法与粒子群算法4/2/202313.1遗传算法4/2/20232生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。4/2/20233遗传算法是模拟生物在自然环境力的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在—系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。4/2/20235一、遗传算法概要

式中，为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。对于一个求函数最大值的优化问题(求函数最小值也类同)，—般可描述为下述数学规划模型：满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。4/2/20236U基本空间R可行解集合X可行解4/2/20237求最优解或近似最优解的方法(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每—个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。4/2/20239(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到—种较好的平衡。而遗传算法为解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。4/2/202310遗传算法中，将n维决策向量用n个记号Xi(n＝l，2，，n)所组成的符号串X来表示：把每一个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。

—般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和l这两个整数组成的。相应的染色体就可表示为一个二进制符号串。4/2/202311生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第t代群体记做P(t)，经过一代遗传和进化后，得到第t+l代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。生物的进化过程主要是通过染色体之间的交叉和变异来完成的，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(geneticoperators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。4/2/202313选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每对个体，以某个概率(称为交叉概率，crossoverrate)交换它们之间的部分染色体。变异(mutation)：对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutationrate)改变某一个或某一些基因座上的基因值为其他的等位基因。4/2/202314二、遗传算法的运算过程

使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下所述：步骤一：初始化。设置进化代数计数器t0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。步骤二：个体评价。计算群体P(t)中各个个体的适应度。步骤三：选择运算。将选择算子作用于群体。4/2/202315三、遗传算法的特点(1)遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。4/2/202317(2)遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。这个特性对很多目标函数无法或是很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。4/2/202318(3)遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间个的一个初始点开始最优解的这代搜索过程，单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时其至使搜索过程陷入局部最优解而停滞不前。遗传算法从很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从—个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。4/2/202319四、遗传算法的发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在上世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后，美国密执安大学的Ho11and教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。4/2/2023211、J．H．Holland60年代，Ho11and提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。70年代初，Ho11and教授提出了遗传算法的基本定理——模式定理(schemaTheorem)，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。1975年，Ho11and出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性(Adaptationinnaturalandartificialsystem)》。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统——分类器系统(C1assifiersystem，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。4/2/2023222、J．D．Bagley1967年，Ho11and的学生Bagley在其博士论文中首次提出“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法相类似。他还敏锐地意识到在遗传算法执行的不向阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。

4/2/2023235、L．Davis1991年，Davis编辑出版了《遗传算法手册(HandbookofGeneticAlgorithms)》—书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到了重要的指导作用。6．J．R．Koza1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(GeneticProgramming，简称GP)的概念。他将一段LISP语言程序作为个体的基因型，把问题的解编码作为一棵树，基于遗传和进化的概念，对由树组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。

4/2/202325五、遗传算法的应用

(1)函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。4/2/202326(4)自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工种经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。4/2/202329(5)机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。4/2/202330(6)图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、持征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使机器视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。4/2/202331人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。

(7)人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自织织能力和自学习能力是人工生命的两大主要特征。4/2/202332(8)遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。4/2/202333(9)机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。4/2/2023343.2基本遗传算法4/2/202335一、基本遗传算法的构成要素基于对自然界中生物遗传与进化机理的模仿，针对不向的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。4/2/202336基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法(SimpleGeneticAlgorithms，简称SGA)。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。4/2/2023371、染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成，如：X＝1101101就可表示一个个体，该个体的染色体长度是n＝18。4/2/2023382、个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要领先确定好当目标函数值为负数时的处理方法。4/2/2023393、遗传算子选择运算使用比例选则算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子或均匀变异算子。4/2/2023404、基本遗传算法的运行参数基本遗传算法有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为201000T：遗传运算的终止进化代数，一般取为100500Pc：交叉概率，—般取为0.40.99。Pm：变异概率，一般取为0.00010.1这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。4/2/202341在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。一般来说，选择较大数目的初始种群可以同时处理更多的解，因而容易找到全局的最优解，其缺点使增加了每次迭代所需要的时间。交叉概率的选择决定了交叉操作的频率。频率越高，可以越快收敛到最有希望的最优解区域；但是太高的频率也可能导致收敛于一个解。变异概率通常只取较小的数值。若选取高的变异率，一方面可以增加样本的多样性，另一方面可能引起不稳定。但是若选取太小的变异概率，则可能难于找到全局的最优解。4/2/202342ProcedureSGAbegin initializeP(0); t=0; while(tT)do fori=1toMdo EvaluatefitnessofP(t); endfor 二、基本遗传算法的伪代码描述4/2/202343 fori=1toMdo SelectoperationofP(t); endfor fori=1toM/2do CrossoveroperationofP(t); endfor fori=1toMdo MutationoperationofP(t); endfor 4/2/202344 fori=1toMdo P(t+1)=P(t); endfort=t+1; endwhileend4/2/202345三、基本遗传算法的实现

1、个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。4/2/202346对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：

minf(X)＝max(－f(X))当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(x)就等于相应的目标函数值f(X)，即：F(X)＝f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。上面两式保证不了所有情况下个体的适应度都是非负数这个要求。所以必须寻求出一种通用且有效的由目标函数值到个体适应度之间的转换关系，由它来保证个体适应度总取非负值。4/2/202347为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值f(X)变换为个体的适应度F(x)。式中，Cmin为一个适当地相对比较小的数，它可以用下面几种方法之一来选择：

方法一：对于求目标函数最大值的优化问题，变换方法为：预先指定的一个较小的数。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。4/2/202348方法二：对于求目标函数最小值的优化问题，变换方法为：

式中，Cmax为一个适当地相对比较大的数，它可以用下面几种方法之一来选择：预先指定的—个较大的数。进化到当前代为止的最大目标函数值。前代或最近几代群体中的最大目标函数值。4/2/2023492、比例选择算子选择算子或复制算子的作用是从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。最常用和最基本的选择算子是比例选择算子。比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulettewheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。所谓比例选择算了，是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。4/2/202350如图所示为一赌盘示意图。整个赌盘被分为大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。虽然赌盘的指针具体停止在哪一个扇面是无法预测的，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比：圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。与此类似，在遗传算法中，整个群体被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。4/2/202351金银铜铁10％20％30％40％4/2/202352比例选择算子的具体执行过程是：(1)先计算出群体中所有个体的适应度的总和。(2)其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率。(3)最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数。4/2/2023533、单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。算子的具体执行过程如下：(1)对群体中的个体进行两两随机配对。若群体的大小为M，则共有[M/2]对相互配对的个体组。其中[x]表示不大于x的最大整数。(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为n，则共有(n-1)个可能的交叉点位置。(3)对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。4/2/202354单点交叉示意如下所示：

A：1011011100A’：1011011111B：0001110011B’；0001110000单点交叉交叉点4/2/2023554、基本位变异算子

对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为l，则变异操作将其变为0。A：10l0101010A’：10l0001010基本位变异

变异点

(1)对个体的每一个基因座，依变异概率pm指定其为变异点。(2)对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。4/2/202356四、基本遗传算法应用举例1、遗传算法的应用步骤第一步：确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值)及其数学描述形式或量化方法。第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。第四步：确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法。4/2/202357若参数a的变化范围为[amin，amax]，用m位二进制数b来表示，则二者之间满足：第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、pc、pm等参数。4/2/2023582、遗传算法的手工模拟计算示例

例：求下述二元函数的最大值：4/2/202359(1)个体编码遗传算法的运算对象是表示个体的符号串，所以必须把变量xl、x2编码为一种符号串。该例题中，xl和x2取0—7之间的整数，可分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了个体的基因型，表示一个可行解。例如，基因型X=10l110所对应的表现型是：X＝[5，6]T。个体的表现型和基因型之间可通过编码和解码程序相互转换。4/2/202360(2)初始群体的产生遗传算法是对群体进行的进化操作，需要给其准备一些表示起始搜索点的初姑群体数据。本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。一个随机产生的初始群体如表中第1栏所示。4/2/202361(3)适应度计算遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。为计算函数的目标值，需先对个体基因型X进行解码。表中第2、3栏所示为初始群体中各个个体的解码结果，第4栏所示为各个个体所对应的目标函数值，它也是个体的适应度，第4栏中还给出了群体中适应度的最大值和平均值。4/2/202362个体1P(0)2x13x24fi(x1,x2)101110135342101011533430111003425411100171504/2/202363(4)选择运算选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下—代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。本例中，采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：先计算出群体中所有个体的适应度的总和；其次计算出每个个体的相对适应度的大小，如表中第5栏所示，它即为每个个体被遗传到下一代群体中的概率，每个概率值组成一个区域，全部概率值之代为l。最后产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。如表中第6、7栏所示为一随机产生的选样结果。4/2/202364个体56选择次数7选择结果10.24101110120.241111001303521110014/2/202365(5)交叉运算交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：先对群体进行随机配对，表中第8栏所示为一种随机配对情况；其次随机设置交叉点位置，如表第9栏所示为一随机产生的交叉点位置，其中的数字表示交叉点设置在该基因座之后；最后再相互交换配对染色体之间的部分基因。表中第10栏所示为交叉运算的结果。4/2/202366个体8配对情况9交叉点10交叉结果11变异点12变异结果11－23－42401100140111012111101511111131010012111001411101161110104/2/202367例如，若第3号和第4号个体在第4个基因座之后进行交叉运算，则可得到两个新的个体：

第3号个体：101011第4号个体：111001101001111011交叉操作可以看出，其中新产生的个体“111011”的适应度较原来两个个体的适应度都要高。4/2/202368(6)变异运算变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：首先确定出各个个体的基因变异位置，如表中第11栏所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；然后依照某—概率将变异点的原有基因值取反。表中第12栏所示为变异运算结果。4/2/202369例如，若第3号个体的第2个基因座需要进行变异运算，则可产生出—个新的个体：

第3号个体：101001111001第二位变异对群体P(t)进行—轮选择、交叉、变异运算之后可得到新一代的群体P(t+1)。如表第13栏所示。表中第14、15、16、17栏还分别表示出了新群体的解码值、适应度和相对适应度，并给出了适应度的最大值和平均值等。从表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。4/2/202370个体13P(1)14x115x216fi(x1,x2)17101110135340.14211111177980.42311100171500.21411101072530.23需要说明的是，表中第1、6、8、9、11栏的数据是随机产生的。这里为了更好地说明问题，特意选择了一些较好的数值以便能够得到较好的结果。在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。4/2/2023713、基本遗传算法在函数优化中的应用

该函数有两个局部极大值，分别是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者为全局最大值。下面介绍求解该问题的遗传算法的构造过程。第一步：确定决策变量和约束条件。第二步：建立优化模型。例：Rosenbrock函数的全局最大值计算。4/2/202372用长度为l0位的二进制编码串来分别表示二个决策变量x1，x2。10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1，x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。第三步：确定编码方法。从离散点－2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1，x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法．解空间和遗传算法的搜索空间具有一一对应的关系。例如X：000011011l1101110001就表示一个个体的基因型，其中前l0位表示x1，后10为表示x2。4/2/202373第四步：确定解码方法。

解码时需先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。例如，对于前述个体X：000011011l1101110001它由这样的两个代码所组成：y1＝55y2＝881经解码处理后，可得到：x1=－1.828x2=1.476依据前述个体编码方法和对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：4/2/202374第五步：确定个体评价方法。第六步：设计遗传算子。可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，即有：F(X)=f(x1，x2)选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。4/2/202375第七步：确定遗传算法的运行参数。对于本例，设定基本遗传算法的运行参数如下：群体大小：M＝80终止代数：T＝200交叉概率：pc＝0.6变异概率：pm＝0.001通过上述七个步骤就可构成用于Rosenbrock函数优化计算的基本遗传算法。4/2/2023761、自适应变异如果双亲的基因非常相近，所产生的后代相对于双亲也必然比较接近。这样所期待的性能改善也必然较小。类似于“近亲繁殖”。所以基因模式的单一性不仅减慢进化历程，而且可能导致进化停滞，过早地收敛于局部的极值解。DarrelWnitly提出了一种如下的自适应变异的方法：在交叉前，以海明(Hamming)距离测定双亲基因码的差异，根据测定值决定后代的变异概率pm。若双亲的差异较小，则选取较大的变异概率。当群体中的个体过于趋于一致时，通过变异的增加来提高群体的多样性，即增强了算法维持全局搜索的能力；反之，当群体已具备较强的多样性时，减小变异率，从而不破坏优良的个体。五、遗传算法的改进4/2/2023772、部分替代法设PG为上一代进化到下一代时被替换的个体的比例，则按此比例，部分个体被新的个体所取代，而其他部分的个体则直接进入下一代。PG越大，进化得越快，但算法的稳定性和收敛性将受到影响；而PG越小，算法的稳定性越好，但进化速度将变慢。可见，应该寻求运行速度与稳定性、收敛性之间的谐调平衡。4/2/2023783、优秀个体保护法这种方法对于每代中一定数量的最优个体，使之直接进入下一代。这样可以防止优秀个体由于复制、交叉或变异中的偶然因素而被破坏掉。这是增强算法稳定性和收敛性的有效方法。但同时也可能使遗传算法陷入局部的极值范围。4/2/2023794、分布式遗传算法该方法将一个总的群体分为若干个子群，各子群将具有略微不同的基因模式，它们各自的遗传过程具有相对的独立性和封闭性，因而进化的方向也略有差异，从而保证了搜索的充分性及收敛结果的全局最优性。另一方面，在各子群之间又以一定的比例定期地进行优良个体的迁移，即每个子群将其中最优的几个个体轮流送到其他子群中。这样做的目的是期望使各子群能共享优良的基因模式以防止某些子群向局部最优方向收敛。分布式遗传算法模拟了生物进化过程中的基因隔离和基因迁移，即各子群之间有相关的封闭性，又有必要的交流和沟通。研究表明，在总的种群个数相同的情况下，分布式遗传算法可以得到比单一种群遗传算法更好的效果。4/2/202380运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及MathWorks公司推出的GADS。GADS这个是Matlab7.0版本自带的工具箱，全名叫GeneticAlgorithmandDirectSearchToolbox。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。另一方面它还提供了一个图形用户界面的工具，名为gatool，有了这个工具就可以不必输入繁琐的命令行参数，能方便而且直观的观察算法的运行过程。MATLAB下遗传算法工具箱4/2/2023813.3蚁群算法4/2/202382蚁群算法是最近几年才提出的一种新型的模拟进化算法，由意大利学者ColorniA、DorigoM和ManiezzoV于1992年首先提出，用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的困难问题。已经用该方法解决了旅行商问题、指派问题、调度问题等，取得了一系列较好的实验结果。4/2/202383像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径。虽然单只蚂蚁的行为极其简单，但由这样的单个简单个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能适应环境的变化，如：在蚂蚁运动路线上突然出现障碍物时，蚂蚁能够很快重新找到最优路径。人们经过大量的研究发现，蚂蚁个体间通过一种称之为信息素(pheromone)的物质进行信息传递，从而能够相互协作，完成复杂的任务。蚂蚁之所以表现出复杂有序的行为，个体之间的信息交流和相互协作起着重要的作用。蚂蚁觅食的生物学基础4/2/202384蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。4/2/202385蚁群系统示意图食物蚁巢ADBC障碍物1112214/2/202386假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源，分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。在t=0时刻，20只蚂蚁从巢穴出发移动到A，它们以相同的概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，10只走右侧。t=4时刻，第一组到达食物源的蚂蚁将折回，此时第二组的蚂蚁到达CD中点处。t=5时刻，两组蚂蚁将在D点相遇。此时BD上的信息素和CD上的相同，因为各有10只蚂蚁选择了相应的道路，从而有5只返回的蚂蚁将选择BD，而另5只将选择CD，第二组蚂蚁继续向食物方向移动。4/2/202387t=8时刻，前5只蚂蚁将返回巢穴，此时在AC中点处、CD中点处以及B点上各有5只蚂蚁。t=9时刻，前5只蚂蚁又回到A点，并且再次面对往左还是往右的选择。这时，AB上的轨迹数是20而AC上是15，因此将有较为多数的蚂蚁选择往左，从而增强了该路线上的信息素。随着该过程的继续，两条道路上的信息素的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线有更多的机会被选择。4/2/202388蚁群算法是一种随机搜索算法，与其他模型进化算法一样，通过候选解组成的群体的进化来寻求最优解。该过程包括两个阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期产生性能更好的解。作为与遗传算法同属一类的通用型随机优化算法，蚁群算法不需要任何先验知识，最初只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得更有规律，并逐渐逼近直至最终达到全局最优解。4/2/202389蚁群算法对搜索空间的“了解”机制（1）、蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会再被选择，由此在蚁群算法中建立禁忌列表来进行模拟。（2）、蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种叫信息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成为蚂蚁之间通信的媒介。4/2/202390（3）、蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度。而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发。模拟这种现象即可利用群体智能建立路径选择机制，使蚁群算法的搜索向最优解推进。蚁群算法所利用的搜索机制呈现出一种自催化或正反馈的特征，可将蚁群算法模型理解成增强型学习系统。4/2/202391旅行商问题旅行商问题即TSP问题(TravelingSalesmanProblem)指给定n座城市和两两城市之间的距离，要求确定一条经过各个城市当且仅当一次的最短路线。其图论描述为：给定图G=(V,A)，其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路。4/2/202392蚁群算法应用于旅行商问题的基本算法（1）它根据以城市距离和连接边上的信息素轨迹强度的数量为变量的概率函数选择下一个城市。（2）规定蚂蚁走合法路线，除非周游完成，不允许转到已访问的城市，由禁忌表控制（设tabuk表示第k只蚂蚁的禁忌表，tabuk(s)表示禁忌表中的第s个元素。）（3）它完成周游后，蚂蚁在它每一条访问的边上留下信息素。每只蚂蚁所具有的特征4/2/202393bi(t)(i=1,2,,n)：在t时刻城市i的蚂蚁数算法中的基本符号：全部蚂蚁数dij：两城市之间的距离ij

：路径(i，j)上的能见度，反映城市i到城市j的启发程度，一般取=1/dijij(t)：t时刻路径(i,j)上的信息素轨迹强度初始时刻，各条路径上的信息量相等，设ij(0)＝C。n：城市数目4/2/202394蚂蚁k(k=1,2,,m)在运动过程中，根据各条路径上积累的信息素轨迹强度和启发式信息决定转移方向。表示在t时刻蚂蚁k由位置i转移到位置j的概率，也就是其选择策略。allowedk={0,1,,n-1}-tabuk：表示蚂蚁k下一步允许选择的城市。4/2/202395tabuk(k=1,2,,m)：与实际蚁群不同，人工蚁群系统具有记忆功能，用tabuk记录蚂蚁k当前所走过的城市，集合tabuk随着进化过程做动态调整。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径就是问题的一个解。之后，禁忌表被清空，该蚂蚁又可以自由选择，开始下一个循环。和：表示信息素强度的相对重要性，表示能见度的相对重要性。分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性：如果

=0，则是传统的贪心算法，如果

=0，则是纯粹的正反馈的启发式算法。4/2/202396经过n个时刻(n即为城市数目)，蚂蚁完成一次循环，各路径上的信息量要根据以下公式做调整：：第k只蚂蚁在本次循环中留在路径ij上的信息量：本次循环中路径ij上的信息量增量：表示轨迹的持久性，(1－)称为信息的挥发系数，表示信息消逝程度，随时间推移，以前留下的信息逐渐消失。通常设置系数0<<1来避免路径上信息素的无限累加。4/2/202397信息素修改ant-cyclealgorithm（蚁环算法）蚁环算法利用的是整体信息，在求解TSP问题时，性能较好。该算法的特点是行走的路径越短，对应保存的信息素的值就越大。4/2/202398ant-quantityalgorithm（蚁量算法）ant-densityalgorithm（蚁密算法）后两种模型利用的是局部信息。信息浓度会因为城市距离的减小而增大。4/2/202399在线和离线信息素修改信息素的更新可分为离线和在线两种方式。离线方式，也称为同步更新方式，其主要思想是在若干只蚂蚁完成n个城市的访问后，统一对残留信息进行更新处理。信息素在线更新，也称为异步更新，蚂蚁每行一步，马上回溯并且更新行走路线上的信息素。4/2/2023100对于离线方式的信息素更新，进一步可以细分为单蚂蚁离线更新和蚁群离线更新两种方式。蚁群更新是在蚁群中的m只蚂蚁全部完成n个城市的访问后，统一对残留信息进行更新处理。蚁群中蚂蚁的先后出行顺序没有相关性，前面出行的蚂蚁不影响后面出行的蚂蚁的行为，但每次循环需要记录m只蚂蚁的行走路径，以便最后比较选择最好的路径。单蚂蚁更新是在第s只蚂蚁完成对所有n个城市的访问后，进行路径回溯，更新行走路径上的信息素，同时释放分配给它的资源。记忆信息相对较少。信息量记忆更小的是信息素的在线更新方式。蚂蚁每行一步，马上回溯并且更新行走路径上的信息素。4/2/2023101蚂蚁系统参数的选择到目前还没有研究出蚂蚁算法模型的数学分析方法使之能够在每个情况下都能生成最优的参数设置，实际的应用中需要逐步试凑得到最优参数组合。可以使用以下三步走的原则:蚂蚁系统需要确定的参数有：m，Q、C、、、。2)参数粗调，即调整取值范围较大的信息素启发因子

、期望因子以及信息素强度Q等参数，以得到最好的解。3)参数细调，即调整取值范围较小的信息素挥发因子P。以上步骤反复进行，自到最终确定出一组较好的组合参数。1)确定蚂蚁数目：如下公式大致确定蚂蚁个数4/2/2023102终止条件有三类：第一类为一个给定的外循环最大数目，表明已经有足够的蚂蚁工作；第二类为当前最优解连续K次相同而停止的规则，其中K是一个给定的整数，表示算法已收敛，不需要再继续；第三类为目标控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。终止条件4/2/2023103TSP问题的蚁群算法基本步骤（1）t0（t为迭代步数或搜索次数）；参数初始化。（2）假设有m只蚂蚁在工作，将各蚂蚁的初始出发点置于当前解集中；对每只蚂蚁k，按概率移至下一个顶点j；将顶点j置于当前解集，直至每只蚂蚁完成任务，完成内循环，即每只蚂蚁独立完成一个解。（3）计算各蚂蚁的路径长度Lk；记录当前最好解。（4）修改信息素。（5）tt+1。（6）若t<预定的迭代次数，且无退化行为（即找到的都是相同的解），则转步骤2。（7）输出目前最好解。4/2/2023104蚁群算法流程4/2/2023105蚁周系统应用于TSP问题仿真指导蚁周系统搜索过程的反馈信息是全局信息，即蚂蚁释放的信息素的量正比于所生成解的优劣度。蚂蚁生成的路径越短，它在这条路径上贡献的信息素量就越多，蚁周系统模型的性能远好于其它两种模型。以20城市的TSP问题为例，对蚁周系统进行仿真，先做如下规定：x,y是两个向量，来表示20城市的横纵坐标，向量元素的顺序就表示了城市的位置序号，并且规定要求的距离为欧几里德距离。即第i，j个城市之间的距离为：4/2/2023106蚁周模型的参数的选择如下：m=20；Q=10；nc

=500；

=1;=5；=0.7。最优路径在121次循环中找到，最优距离f=25.6396。依次经过各个城市的顺序：8－4－3－12－2－9－15－10－19－7－18－16－5－13－20－6－17－1－14－11－8。20城市问题即求：，当且仅当每个城市经过一次。x=[5.294，4.286，4.719，4.185，0.915，4.771，1.524，3.447，3.718，2.649，4.439，4.660，1.232，5.036，2.710，1.072，5.855，0.194，1.762，2.862]y=[1.558，3.622，2.774，2.230，3.821，6.041，2.871，2.111，3.665，2.556，1.194，2.949，6.440，0.244，3.140，3.454，6.203，1.862，2.693，6.097]4/2/2023107最短路径示意图4/2/2023108在初始阶段，信息素的轨迹量被均匀的分布在各条边上，搜索只能由能见度指导，随后较优的路经上信息素得到增强，而较差的路径边上的信息素被完全挥发掉。结果最差路经上的边被从图上删除，从而使得搜索空间变小，最后蚂蚁收敛到同一路径上。4/2/2023109tsp_30=[

87，7；91，38；83，46；71，44；64，60； 68，58；83，69；87，76；74，78；71，71； 58，69；54，62；51，67；37，84；41，94； 2，99；7，64；22，60；25，62；18，54； 4，50；13，40；18，40；24，42；25，38； 41，26；45，21；44，35；58，35；62，32]30个城市的TSP问题Oliver30数据4/2/2023110改进及扩展的离散蚁群算法离散蚁群算法在求解TSP问题上的出色表现，使得它足以与许多同类智能算法如GA,SA等相媲美，并发展出许多改进的离散蚁群算法，如最优解保留策略蚂蚁系统(AntSystemwithElitist，蚁群系统(AntColonySystem,ACS)，最大最小蚁群系统(MAX-MINAntSystem,MMAS)，自适应蚁群算法(AdaptiveAntColonyAlgorithm,AACA)等。这些算法从信息素更新和最优解信息的利用上对算法进行改进，提高了算法性能。另一方面通过嵌入局部确定性搜索算法，如2-opt去交叉技术等，提高了算法的收敛速度。4/2/2023111蚁群算法在参数寻优中的应用由于蚁群算法应用于离散优化问题所表现出的优异性能，很自然地让人想到把蚁群算法扩展到连续优化问题。由于离散优化问题和连续优化问题性质的不同，导致在信息素分布方式上的差异，解决离散优化问题的蚁群算法并不能自接用于求解连续优化问题。一种解决办法是，将各蚂蚁本身视为顶点，信息素直接分布在解空间内各蚂蚁所在的位置上。另一种办法是，把解的各个分量离散成固定长度的区间，将各分量子区间视为顶点，信息素分布在各层分量的子区间上，具有代表性的是CACA算法。4/2/2023112不失一般性，定义连续函数优化问题为：在连续函数优化问题，目标函数f为任意非线性函数，设计变量，约束条件构成Rn上的一个n维区域。4/2/2023113蚂蚁路经和节点的生成蚁群算法所搜索出的路径代表了寻优参数的值，它是通过蚁群系统中的节点来实现的。信息素也便遗留在最优蚂蚁所走过的节点上，并且根据目标函数值来更新信息素物质的浓度，目标函数中包含最优蚂蚁所走过的所有节点。而每个参数可以用若干个十进制有效数位表示，每个有效位可以用节点来表示。但是要根据实际情况来确定各个参数小数点前后的位数。连续优化问题算法一4/2/2023114假设参数a取1位整数，4位小数；参数b取3位整数，2位小数；参数c取2位整数，3位小数。a=4.5396；b=250.53；c=45.636。路径和节点图4/2/2023115假设每只蚂蚁从i-1列上任意节点爬行到第i列上的任意节点所用时间相等，与节点的距离无关。这样，所有蚂蚁从第0列出发，最终爬到最后一列(第N列)，完成一次循环。假设在第t次循环中，第k只蚂蚁从第i-1列某个节点向下一列(即第i列)的第j个节点(i,j)爬行的转移概率Pij由下式确定：转移概率4/2/2023116在第一次循环中，jopt(i)为初始值对应于如图上的10个节点的值，在以后的循环中，jopt(i)为上一次循环产生的一组最优参数对应于图的10个节点。能见度指标（启发信息）4/2/2023117信息素更新4/2/2023118连续优化问题算法二首先可根据问题的性质估计一下最优解的范围，估计出各变量的取值范围：。在各变量区域内打网格，空间的网格点上对应于一个状态，人工蚂蚁在各个空间网格点之间移动，根据各网格点的目标函数值，留下不同的信息量，以此影响下一批人工蚂蚁的移动方向。循环一段时间后，目标函数值小的网格点信息量比较大。根据信息量，找出信息量大的空间网格点，缩小变量范围，在此点附近进行人工蚂蚁移动。重复上述过程，直到网格的间距小于预先给定的精度，算法终止。4/2/2023119状态空间解的表示0123N0123N0123N0123N第一级第二级第三级第n级4/2/2023120假设各变量分成N等分，n个决策变量变成n级决策问题，每一级有N+1个节点。共有(N+1)n个节点。从第1级到第n级之间连接到一起，组成空间的一个解。如图所示的状态为(3,2,1,,1)，其对应的解为：4/2/2023121蚂蚁确定第i个分量在第j个节点的概率为：转移概率该算法没有定义启发式信息。4/2/2023122信息素更新ij表示第i级第j个区间的吸引强度；表示强度的持久性系数，一般取为0.5~0.9；4/2/2023123算法步骤步骤1估计出各变量的取值范围：步骤2对各变量N等份：步骤3若max(h1,h2,hn)<，则算法终止，最优解为：否则转步骤4。步骤4初始化：给信息素矩阵赋一个相同的常数值；给定Q和的数值；将m只蚂蚁随机地分配到第一个分量的N个子区间；t0(t为循环次数)。4/2/2023124步骤5设置变量计数i=1(i=1,2,n，n为变量总数)步骤6设置变量计数ii+1步骤7每只蚂蚁k(k=1,2,m，m为蚂蚁总数)根据概率pij选择第i个分量所在节点j步骤8当m只蚂蚁选择完分量i以后，返回步骤6，开始选择下一个分量(下一级)，直到所有蚂蚁完成一次周游为止。步骤9计算所有蚂蚁的适应度函数值fk。4/2/2023125步骤10进行全局信息素更新：4/2/2023126步骤11

tt+1(t为循环次数)，若迭代次数小于规定的最大循环次数，转步骤5；否则，找出ij矩阵中每列最大的元素对应的行(m1,m2,,mn)，缩小变量的取值范围：转步骤2。4/2/2023127连续优化问题算法三：CACA算法该算法通过把各维变量离散化，在算法的每一次迭代中，先根据蚁群优化原理求出最优解所在的区域，然后在各区域中运用遗传算法确定解的具体值。参考文献：1、陈峻，沈洁，秦玲.蚁群算法求解连续空间优化问题的一种方法.软件学报，2002年，13(12)：2317－23232、王晗.基于蚁群算法的制动器参数优化设计.吉林大学工学硕士学位论文.2007年4/2/2023128选取一定长度，将可行域在各维分量上离散成若干等长度的子区间。为了确定解的具体值，可在各个子区间已有的取值中保存若干几个适应度较好的解的分量作为候选组。然后使用遗传算法中的选择、交叉、变异等操作，在候选组中确定解的相应分量的值。对子区间候选组内各分量值的选择，相当于对问题的局部寻优。4/2/2023129单蚁在n维连续空间中路径选择图问题映射4/2/2023130参数的数据结构及初始化1)子区间初始化子区间初始化包括子区间范围的初始化和各子区间内候选组的初始化。选取一定长度，设ki=[(ui-li)/]，将可行域在第i维上离散成ki个子区间，i=1,2,,n。由于各维分量的子区间的个数不一致，因此，定义一个二维的链表数组C，以Cij表示第i维的第j个子区间，需要对各子区间Cij的上下边界Lij、Uij及候选组进行初始化。各候选组一般先初始化为空，在需要的时候根据遗传操作生成相应的候选值。4/2/2023131对规模为m的蚁群，设计变量维数为n的问题，定义一个nxm的矩阵AC，用以记录蚁群各维分量上的值。2)蚁群初始化AC一般先随机初始化为约束域内某些值，并根据各子区间边界，计算各分量所属子区间。4/2/2023132在CACA中，子区间之间的连线对应蚂蚁的寻优路径，信息素分布在各维分量的各个子区间上。记t时刻第i分量的第了个子区间j上的信息素为ij(t)。与子区间的初始化类似，也用一个二维链表来实现。根据初始蚁群各分量所属的子区间，对相应的进行初始化。3)信息素初始化4/2/2023133选择概率计算CACA中没有定义启发信息，直接根据信息素决定转移概率的大小。同时，为更好地利用最优解的信息，利用下式来选择第i分量值所在的子区间号j：q：(0,1)之间的随机数；q0：状态转移概率4/2/2023134q0是一个确定选取最佳解分量值所在的子区间的概率，例如可取q0＝0.8，信息量最大的子区间以高概率0.8被选中，其余的子区间以0.2的概率参与选择。argmax{ij|1jki}表示分量i的信息量最大的子区间号。4/2/2023135信息素更新(局部和全局更新)1)信息素局部更新由于算法中以q0的概率选择ki个子区间中信息量最大的子区间，因此信息量最大的那个子区间常常被选中，这就使得新一代解的该分量值集中在这个子区间，容易发生停滞现象。为了避免这种现象，算法对所选的子区间的信息量进行局部更新，对被选中的子区间立即适当地减少其信息量，使其他蚂蚁选中该子区间的概率降低。4/2/2023136更新后的信息量是原来的信息量和有关第i个分量各子区间的最小信息量的凸组合，当信息量最大的子区间被多次选中之后，信息量减少到ki个子区间的信息量的平均水平，从而蚂蚁选择其他子区间的概率增加，增加了所建立解的多样性，同时也有效减少了停滞现象的发生.设第k个个体的第i个分量选中第j个子区间，则按下式局部更新子区间j的信息量：4/2/20231372)信息素全局更新全局更新发生在所有蚂蚁完成路径选择，即得到各自解之后，按下式进行更新计算：4/2/2023138局部优化在确定某分量所在区间后，用遗传算法相关操作对该子区间内候选组内的值进行选择，以实现对问题的局部优化。设gij表示第i分量候选组j中候选值的个数，根据不同的gij值，对候选组进行选择、交叉、变异等遗传操作。1)若gij＝0，则在[LijUij]内产生一个随机数作为解的分量，跳过选择、交叉、变异等操作；2)若gij＝1，则跳过选择、交叉操作，自接对这个候选值进行变异操作，以变异后的值作为该分量的值；3)若gij＝2，即候选组里有两个候选值，则跳过选择操作，直接对这两个候选值进行交叉、变异等操作;4)

否则，选择两个分量后进行交叉、变异操作。4/2/2023139在选择操作中，根据候选组里各候选值的适应度的大小，用“赌轮”的方法选取两个值。1)选择2)交叉在交叉操作中，设进行交叉的两个值为xi(1)和xi(2)，对它们的交叉过程按下式进行(交叉后只产生一个新的个体，而且可以保证遗传操作的结果仍然在子区间中)：4/2/20231403)变异变异按如下公式进行，设对候选值xi进行变异：可以保证遗传操作的结果仍然在子区间中。4/2/2023141候选组更新为避免子区间内候选值的个数gij无限制增大，在所有蚂蚁构造完各自的解后，需对各子区间的候选组进行更新。即选取蚁群中适应度最好的num个解，将其分量插入相应的子区间的候选组中，并淘汰较差者。一般取num=[m/3]。4/2/2023142与离散蚁群算法相同，可以限定最大迭代次数作为迭代终止条件。注意到适应度计算式中以fmax－fmin作为分母，因此，同时限定fmax－fmin

，即蚁群中各蚂蚁的目标函数趋同的时候，终止迭代过程。迭代终止条件4/2/2023143算法框架(1)初始化随机产生M个初始解，计算这M个初始解的适应度，由这M个初始解的各个分量计算出其所属的子区间，产生各个子区间上的相应分量的候选组，并将候选组中的值按它们所在解的适应度排序，根据适应度计算各分量各个子区间上(即各条边上)的信息量。4/2/2023144whilenot结束条件do{fork=1tomdo(对m个蚂蚁循环){

fori=1tondo(对n个分量循环){根据q0和概率确定第i个分量的值在第j个子区间;修改第j个子区间的信息量ij(t);（局部更新）在第j个子区间候选组里生成第i个分量的的值;（局部优化）}(fori=1ton循环)计算蚂蚁k的适应度函数值Fk，从而计算;}(fork=1tom循环)修改各条边上的信息量;（全局更新）候选组更新；}(while循环)(2)迭代过程4/2/20231453.4粒子群算法4/2/2023146粒子群算法的研究背景粒子群算法(ParticleSwarmOptimization，简称PSO)，是一种基于群体智能的进化计算方法。PSO由Kennedy和Eberhart博士于1995年提出。PSO一经提出，由于算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。目前PSO算法已被“国际进化计算会议”(IEEEInternationalConferencesonEvolutionaryComputation,CEC)列为一个讨论的专题。4/2/2023147PSO的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群算法的基本原理4/2/2023148PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。“群”(Swarm)的概念来自于人工生命，满足人工生命的五个基本原则。因此PSO算法也可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体中的信息共享机制，这是推动算法的主要机制。4/2/2023149粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitnessvalue)，这个适应值用于评价粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位置(particlebest，记为pbest)和当前的位置，pbest就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(globalbest，记为gbest)，gbest是在pbest中的最好值，即是全局最优解，这个可以看作是整个群体的经验。4/2/2023150每个粒子使用下列信息改变自己的当前位置：(1)当前位置；(2)当前速度；(3)当前位置与自己最好位置之间的距离；(4)当前位置与群体最好位置之间的距离。4/2/2023151用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：一