第三章求解优化问题的智能算法

第三章求解优化问题的智能算法9/10/20231第1页，课件共209页，创作于2023年2月3.1概述9/10/20232第2页，课件共209页，创作于2023年2月最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。解决最优化问题的方法称为最优化方法。它具有高度应用性和技术性的特点。最优化问题可以追溯到十分古老的极值问题，在17世纪，伟大科学家Newton发明微积分的时候，已经提出了极值问题，后来又出现了Lagrange乘子法，Cauchy则利用最速下降法求解无约束极小化问题。然而，直到1947年Dantzig提出求解一般线性规划问题的单纯形法之后，它才成为一门独立的学科。3.1概述——最优化方法的研究起源和意义

1/29/10/20233第3页，课件共209页，创作于2023年2月随着近代科学技术发展的需要，特别是由于计算机技术的飞速发展，促进了最优化方法的迅速发展，并很快渗透到各个领域。20世纪70年代，最优化方法这门应用技术科学又开始产生出最优设计、最优控制与最优管理等分支。到20世纪80年代，最优化技术又在这些分支中发展出了新的更细的分支，比如，工程技术领域的机械优化设计、建筑结构优化设计以及化工石油领域的优化设计等。3.1概述——最优化方法的研究起源和意义

2/29/10/20234第4页，课件共209页，创作于2023年2月求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。9/10/20235第5页，课件共209页，创作于2023年2月转化为最小化问题。3.1概述——最优化问题的数学描述9/10/20236第6页，课件共209页，创作于2023年2月(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。3.1概述——求最优解或近似最优解的方法1/29/10/20237第7页，课件共209页，创作于2023年2月(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到—种较好的平衡。3.1概述——求最优解或近似最优解的方法2/29/10/20238第8页，课件共209页，创作于2023年2月以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：3.1概述——求解最优化问题的传统方法9/10/20239第9页，课件共209页，创作于2023年2月3.1概述——求解最优化问题的传统方法——最速下降法9/10/202310第10页，课件共209页，创作于2023年2月3.1概述——求解最优化问题的传统方法——牛顿法9/10/202311第11页，课件共209页，创作于2023年2月3.1概述——求解最优化问题的传统方法——共轭方向法9/10/202312第12页，课件共209页，创作于2023年2月对目标函数和约束函数表达的要求必须更为宽松计算的效率比理论上的最优性更重要算法随时终止能够随时得到较好的解对优化模型中数据的质量要求更为宽松实际生活中对最优化方法性能的需求促进了最优化方法的发展，最优化逐步走出“象牙塔”，面向实际需要，完成了从“方法定向”到“问题定向”的转换。3.1概述——对最优化提出的新的需求9/10/202313第13页，课件共209页，创作于2023年2月1975年，Holland提出遗传算法(GeneticAlgorithm)。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出了模拟退火(SimulatedAnnealing)算法。这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程，按玻兹曼(Boltzmann)方程计算状态间的转移概率来引导搜索，从而使算法具有很好的全局搜索能力。3.1概述——新的优化方法不断出现1/29/10/202314第14页，课件共209页，创作于2023年2月20世纪90年代初，Dorigo等提出蚁群优化算法(AntColonyOptimization)算法。这种算法借鉴蚁群群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。1995年，Kenedy和Eberhart提出粒子群优化(ParticleSwarmOptimization)算法。这种方法模仿鸟类和鱼类群体觅食迁移中，个体与群体协调一致的机理，通过群体最优方向、个体最优方向和惯性方向的协调来求解实数优化问题。1999年，Linhares提出了捕食搜索(PredatorySearch)算法。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阈值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述——新的优化方法不断出现2/29/10/202315第15页，课件共209页，创作于2023年2月不以达到某个最优性条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率；对目标函数和约束函数的要求十分宽松；算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；多数算法含有一个多个体的群体，寻优过程实际上就是种群的进化过程；理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。3.1概述——新的算法的一些共同特点9/10/202316第16页，课件共209页，创作于2023年2月由于算法理论薄弱，最早被称为“现代启发式(ModernHeuristics)”或“高级启发式(AdvancedHeuristics)”；从其人工智能的特点，被称为“智能计算(IntelligentComputation)”或“智能优化算法(IntelligentOptimizationAlgorithms)”；从不以精确解为目标的特点，又被归到“软计算(SoftComputing)”方法中；从种群进化的特点看，它们又可以称为“进化计算(EvolutionaryCompuation)”；从模仿自然规律的特点出发，又有人将它们称为“自然计算(NaturalComputing)”。3.1概述——新的优化方法的不同名称9/10/202317第17页，课件共209页，创作于2023年2月应用智能优化算法解决各类问题是重点；算法改进有很大的创新空间；多种算法结合的混合算法是一条捷径；不提倡刻意去追求理论成果；算法性能的测算是一项要下真功夫的工作；选择测试例题的一般规律：网上题库中的例题→文献中的例题→随机产生的例题→实际应用问题→自己编的例题；算法性能测试的主要指标：达优率(解的目标平均值和最优解的目标值的比，所有解的目标值的标准差等)，计算速度，计算大规模问题的能力；创造出新算法3.1概述——怎样学习研究智能优化方法9/10/202318第18页，课件共209页，创作于2023年2月3.2遗传算法9/10/202319第19页，课件共209页，创作于2023年2月生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法——概要9/10/202320第20页，课件共209页，创作于2023年2月虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生物的性状。(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的：(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。3.2遗传算法——概要9/10/202321第21页，课件共209页，创作于2023年2月遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。3.2遗传算法——概要9/10/202322第22页，课件共209页，创作于2023年2月式中，为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可描述为下述数学规划模型：满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。3.2遗传算法——概要9/10/202323第23页，课件共209页，创作于2023年2月U基本空间R可行解集合X可行解3.2遗传算法——概要9/10/202324第24页，课件共209页，创作于2023年2月对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。3.2遗传算法——概要9/10/202325第25页，课件共209页，创作于2023年2月遗传算法中，将n维决策向量用n个记号xi(n=l，2，

，n)所组成的符号串X来表示：把每一个xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。

—般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的。相应的染色体就可表示为一个二进制符号串。3.2遗传算法——概要9/10/202326第26页，课件共209页，创作于2023年2月这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。染色休X也称为个体X。对于每一个个体X，要按照一定的规则确定出其适应度；个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。通过编码和解码，使得问题的解空间和搜索空间一一对应。3.2遗传算法——概要9/10/202327第27页，课件共209页，创作于2023年2月生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第t代群体记做P(t)，经过一代遗传和进化后，得到第t+l代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的，与此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(geneticoperators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。3.2遗传算法——概要9/10/202328第28页，课件共209页，创作于2023年2月选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每对个体，以某个概率(称为交叉概率，crossoverrate)交换它们之间的部分染色体。变异(mutation)：对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutationrate)改变某一个或某一些基因座上的基因值为其他的等位基因。3.2遗传算法——概要9/10/202329第29页，课件共209页，创作于2023年2月使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下所述：步骤一：初始化。设置进化代数计数器t

0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。步骤二：个体评价。计算群体P(t)中各个个体的适应度。步骤三：选择运算。将选择算子作用于群体。3.2遗传算法——运算过程9/10/202330第30页，课件共209页，创作于2023年2月步骤四：交叉运算。将交叉算子作用于群体。步骤五：变异运算。将变异算于作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。若t

T，则：t

t+1，转到步骤二。若t＞T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。3.2遗传算法——运算过程9/10/202331第31页，课件共209页，创作于2023年2月基于对自然界中生物遗传与进化机理的模仿，针对不向的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。3.2遗传算法——基本遗传算法的实现9/10/202332第32页，课件共209页，创作于2023年2月基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法(SimpleGeneticAlgorithms，简称SGA)。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。基本遗传算法使用比例选择算子、单点交叉算子和基本位变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。3.2遗传算法——基本遗传算法的实现9/10/202333第33页，课件共209页，创作于2023年2月用二进制编码来离散自变量，码长根据离散精度来确定。例如当自变量a的变化区间为[amin，amax]

，当离散精度为

时，码长m的计算公式为：相应的解码公式为：3.2遗传算法——基本遗传算法的实现——编码和解码9/10/202334第34页，课件共209页，创作于2023年2月在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。3.2遗传算法——基本遗传算法的实现—适应度评价1/49/10/202335第35页，课件共209页，创作于2023年2月对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：

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

方法一：对于求目标函数最大值的优化问题，变换方法为：预先指定的一个较小的数。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。3.2遗传算法——基本遗传算法的实现—适应度评价3/49/10/202337第37页，课件共209页，创作于2023年2月方法二：对于求目标函数最小值的优化问题，变换方法为：

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

A：1011011100A’：1011011111B：0001110011B’；0001110000单点交叉交叉点3.2遗传算法——基本遗传算法的实现—单点交叉算子2/29/10/202344第44页，课件共209页，创作于2023年2月对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为l，则变异操作将其变为0。A：10l0101010A’：10l0001010基本位变异

变异点

(1)对个体的每一个基因座，依变异概率pm指定其为变异点。(2)对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。3.2遗传算法——基本遗传算法的实现—基本位变异算子9/10/202345第45页，课件共209页，创作于2023年2月基本遗传算法有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20

1000T：遗传运算的终止进化代数，一般取为100

500Pc：交叉概率，—般取为0.4

0.99。Pm：变异概率，一般取为0.0001

0.1这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。3.2遗传算法——遗传算法的运行参数

1/29/10/202346第46页，课件共209页，创作于2023年2月在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。一般来说，选择较大数目的初始种群可以同时处理更多的解，因而容易找到全局的最优解，其缺点使增加了每次迭代所需要的时间。交叉概率的选择决定了交叉操作的频率。频率越高，可以越快收敛到最有希望的最优解区域；但是太高的频率也可能导致收敛于一个解。变异概率通常只取较小的数值。若选取高的变异率，一方面可以增加样本的多样性，另一方面可能引起不稳定。但是若选取太小的变异概率，则可能难于找到全局的最优解。3.2遗传算法——遗传算法的运行参数

2/29/10/202347第47页，课件共209页，创作于2023年2月该函数有两个局部极大值，分别是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者为全局最大值。首先确定决策变量和约束条件，确定优化模型例：Rosenbrock函数的全局最大值计算。3.2遗传算法——在函数优化中的应用—确定优化模型9/10/202348第48页，课件共209页，创作于2023年2月用长度为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就表示一个个体的基因型，其中前10位表示x1，后10为表示x2。3.2遗传算法——在函数优化中的应用—确定编码方法9/10/202349第49页，课件共209页，创作于2023年2月解码时需先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。例如，对于前述个体X：000011011l1101110001它由这样的两个代码所组成：y1＝55y2＝881经解码处理后，可得到：x1=－1.828x2=1.476依据前述个体编码方法和对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：3.2遗传算法——在函数优化中的应用—确定解码方法9/10/202350第50页，课件共209页，创作于2023年2月第六步：设计遗传算子。可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，即有：F(X)=f(x1，x2)选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。3.2遗传算法——在函数优化中的应用—确定个体评价方法9/10/202351第51页，课件共209页，创作于2023年2月对于本例，设定基本遗传算法的运行参数如下：群体大小：M＝80终止代数：T＝200交叉概率：pc＝0.6变异概率：pm＝0.001通过上述七个步骤就可构成用于Rosenbrock函数优化计算的基本遗传算法。3.2遗传算法——在函数优化中的应用—确定运行参数9/10/202352第52页，课件共209页，创作于2023年2月myGA.mfunction[xv,fv]=myGA(fitness,a,b,NP,NG,Pc,Pm,eps)functionresult=Initial(length)functiony=Dec(a,b,x,L)myGA2.m3.2遗传算法——在函数优化中的应用—程序9/10/202353第53页，课件共209页，创作于2023年2月传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。3.2遗传算法——特点—以决策变量的编码作为运算对象9/10/202354第54页，课件共209页，创作于2023年2月传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。这个特性对很多目标函数无法或是很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。3.2遗传算法——特点—直接以目标函数值作为搜索信息9/10/202355第55页，课件共209页，创作于2023年2月传统的优化算法往往是从解空间个的一个初始点开始最优解的这代搜索过程，单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时其至使搜索过程陷入局部最优解而停滞不前。遗传算法从很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。3.2遗传算法——特点—同时使用多个搜索点的搜索信息9/10/202356第56页，课件共209页，创作于2023年2月传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体，实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。当然，交叉概率和变异概率等参数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。而另一方面，与其他一些算法相比遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能地低。3.2遗传算法——特点—使用概率搜索技术9/10/202357第57页，课件共209页，创作于2023年2月约束优化(ConstrainedOptimization)是处理具有等式和(或)不等式约束的目标函数问题，其一般形式可以表示为：可记约束集（可行集）为：用于操作染色体的遗传算法常会产生不可行的染色体的问题。3.2遗传算法——约束的处理1/39/10/202358第58页，课件共209页，创作于2023年2月——拒绝策略：抛弃进化过程中产生的所有不可行解。这是遗传算法处理约束问题的最简单也是效率最低的方法。——修复策略：在进化过程中获得不可行解后，将其修复为可行解。对于很多组合优化问题创建修复过程相对容易，但可能导致失去种群的多样性。——惩罚策略：对约束进行处理的最一般的方式，是通过对不可行解的惩罚来将约束问题转化为无约束问题。任何对于约束的违反都要在目标函数中添加惩罚项。需要设计合适的惩罚函数，不合适的惩罚函数会掩盖目标函数的优化。3.2遗传算法——约束的处理2/39/10/202359第59页，课件共209页，创作于2023年2月——特殊的编码和遗传策略：使用特殊的编码策略，在编码时就充分考虑约束问题，在编码时产生的都是符合约束的染色体。为了使染色体在遗传操作后仍然保持可行性，也有使用特殊的遗传策略，使遗传操作后染色体仍然保持可行。3.2遗传算法——约束的处理3/39/10/202360第60页，课件共209页，创作于2023年2月现实的生产和生活中人们常常遇到存在的目标超过一个，并且需要同时处理的情况，而这些不同的目标又往往是相互冲突的，这就是多目标优化(MultiobjectiveOptimization)问题。具有p个目标的多目标问题的一般形式为：3.2遗传算法——多目标的处理1/49/10/202361第61页，课件共209页，创作于2023年2月在大多数情况下，各个目标函数间可能是冲突的。这就使得多目标优化问题不存在唯一的全局最优解，使所有目标函数同时最优。但是，可以存在这样的解：对一个或几个目标函数不可能进一步优化，而对其他目标函数不至于劣化，这样的解称之为非劣最优解，也称有效解，或Pareto最优解。遗传算法种群进化特征使其适合于这样的问题。处理多目标问题时，遗传算法遇到的一个主要问题是如何根据多个目标函数值来确定个体的适应值，即适应值分配机制。3.2遗传算法——多目标的处理2/49/10/202362第62页，课件共209页，创作于2023年2月——向量评价方法：采用向量形式评价的适应值度量来产生下一代，而不是使用标量适应值度量方式来评价染色体。对于有p个目标的给定问题，每代中的选择过程是一个循环，它重复p次，每次循环依次使用一个目标，选出下一代中的一部分个体。——权重和方法：为每个目标函数分配权重并将权重目标组合为单一目标函数。权重的调整方法包括：固定权重方法、随机权重方法、适用性权重方法。3.2遗传算法——多目标的处理3/49/10/202363第63页，课件共209页，创作于2023年2月——基于Pareto的方法：有两种基于Pareto的方法：Pareto排序和Pareto竞争。——妥协方法：通过某种距离的度量来确定与理想解最近的解。——目标规划方法：采用基于排序的适应值分配方法来判断个体的价值。具体过程为：根据第一优先目标进行种群排序，如果某些个体具有相同的目标值，根据第二优先目标进行排序，如此进行下去。如果各个目标上各个个体均相同，则随机对其进行排序。然后采用从最好到最差的指数插值进行个体的适应值分配。3.2遗传算法——多目标的处理4/49/10/202364第64页，课件共209页，创作于2023年2月GADS这个是Matlab7.0版本自带的工具箱，全名叫GeneticAlgorithmandDirectSearchToolbox。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。它还提供了一个图形用户界面的工具，名为“GeneticAlgorithmTool”，有了这个工具就可以不必输入繁琐的命令行参数，能方便而且直观的观察算法的运行过程。在命令行里输入“gatool”，就可以进入该图形用户界面。3.2遗传算法——MATLAB遗传算法工具箱9/10/202365第65页，课件共209页，创作于2023年2月[xfval]=ga(@fitnessfun,nvars,options)Where@fitnessfunisahandletothefitnessfunction.nvarsisthenumberofindependentvariablesforthefitnessfunction.optionsisastructurecontainingoptionsforthegeneticalgorithm.Ifyoudonotpassinthisargument,gausesitsdefaultoptions.Theresultsaregivenby:x—Pointatwhichthefinalvalueisattainedfval—Finalvalueofthefitnessfunction3.2遗传算法——MATLAB遗传算法工具箱—命令行函数9/10/202366第66页，课件共209页，创作于2023年2月3.2遗传算法——MATLAB遗传算法工具箱—图形用户界面9/10/202367第67页，课件共209页，创作于2023年2月求下列函数的最小值：建立适应函数FitFun.m文件：functiony=FitFun(x)y=0.01;fori=1:5y=y+1/(i+(x(i)-1)^2);endy=1/y3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202368第68页，课件共209页，创作于2023年2月适应度函数的文件名待寻优变量的个数变量的下边界和上边界3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202369第69页，课件共209页，创作于2023年2月寻优结果优化参数迭代次数3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202370第70页，课件共209页，创作于2023年2月该例题的理论最小值为0.436，且在(x1,x2,x3,x4,x5)=(1,1,1,1,1)时取到。从结果的比较可以看出，遗传算法求出的结果精度是很高的。3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202371第71页，课件共209页，创作于2023年2月建立适应函数FitFun.m文件：functiony=FitFun(x)y=x(1)^2+2*x(2)^2-4*x(1)-8*x(2)+15;建立非线性约束函数NonCon.m文件：function[c,ceq]=NonCon(x)c=x(1)^2+x(2)^2-9;ceq=[];3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202372第72页，课件共209页，创作于2023年2月非线性约束函数Nonlinearconstraintfunctiondefinesthenonlinearconstraints.Specifythefunctionasananonymousfunctionorasafunctionhandleoftheform@nonlcon,wherenonlcon.misanM-filethatreturnsthevectorscandceq.Thenonlinearequalitiesareoftheformceq=0,andthenonlinearinequalitiesareoftheformc

0.线性等式和不等式约束3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202373第73页，课件共209页，创作于2023年2月此例题的理论最小值为3，在(x1,x2)=(2,2)时取得。从结果可以看出，结果精度是很高的。3.2遗传算法——MATLAB遗传算法工具箱—应用实例9/10/202374第74页，课件共209页，创作于2023年2月如果双亲的基因非常相近，所产生的后代相对于双亲也必然比较接近。这样所期待的性能改善也必然较小。类似于“近亲繁殖”。所以基因模式的单一性不仅减慢进化历程，而且可能导致进化停滞，过早地收敛于局部的极值解。Srinvivas等提出一种自适应遗传算法，交叉概率和变异概率能够随适应度自动改变。当种群各个个体适应度趋于一致或者趋于局部最优时，使交叉概率和变异概率二者增加，而当群体适应度比较分散时，使交叉概率和变异概率减少。同时，对于适应值高于群体平均适应值的个体，对应于较低的交叉概率和变异概率，使该个体得以保护进入下一代；而低于平均适应值的个体，相对于较高的交叉概率和变异概率，使该个体被淘汰。3.2遗传算法——改进—自适应遗传算法9/10/202375第75页，课件共209页，创作于2023年2月因此，自适应遗传算法能够提供相对某个解的最佳交叉概率和变异概率。自适应遗传算法中交叉概率和变异概率的计算公式为：3.2遗传算法——改进—自适应遗传算法9/10/202376第76页，课件共209页，创作于2023年2月设PG为上一代进化到下一代时被替换的个体的比例，则按此比例，部分个体被新的个体所取代，而其他部分的个体则直接进入下一代。PG越大，进化得越快，但算法的稳定性和收敛性将受到影响；而PG越小，算法的稳定性越好，但进化速度将变慢。可见，应该寻求运行速度与稳定性、收敛性之间的协调平衡。3.2遗传算法——改进—部分替代法9/10/202377第77页，课件共209页，创作于2023年2月这种方法对于每代中一定数量的最优个体，使之直接进入下一代。这样可以防止优秀个体由于复制、交叉或变异中的偶然因素而被破坏掉。这是增强算法稳定性和收敛性的有效方法。但同时也可能使遗传算法陷入局部的极值范围。3.2遗传算法——改进—优秀个体保护法9/10/202378第78页，课件共209页，创作于2023年2月该方法将一个总的群体分为若干个子群，各子群将具有略微不同的基因模式，它们各自的遗传过程具有相对的独立性和封闭性，因而进化的方向也略有差异，从而保证了搜索的充分性及收敛结果的全局最优性。另一方面，在各子群之间又以一定的比例定期地进行优良个体的迁移，即每个子群将其中最优的几个个体轮流送到其他子群中。这样做的目的是期望使各子群能共享优良的基因模式以防止某些子群向局部最优方向收敛。分布式遗传算法模拟了生物进化过程中的基因隔离和基因迁移，即各子群之间有相关的封闭性，又有必要的交流和沟通。研究表明，在总的种群个数相同的情况下，分布式遗传算法可以得到比单一种群遗传算法更好的效果。3.2遗传算法——改进—分布式遗传算法9/10/202379第79页，课件共209页，创作于2023年2月其它改进——顺序选择遗传算法——适应值函数标定的遗传算法——大变异遗传算法——双切点交叉遗传算法——多变异位自适应遗传算法3.2遗传算法——改进9/10/202380第80页，课件共209页，创作于2023年2月3.3蚁群算法9/10/202381第81页，课件共209页，创作于2023年2月群智能(swarmintelligence,SI)的概念首次由Beni和Wang在研究元胞机器人系统中提出，由无智能的机器人组成的系统呈现集体智能行为。但当时他们对于“群体”和“智能”的定义较为特定，即仅针对机器人系统及它们所具备的智能。之后，机器人专家研究采用机器人群体完成特定任务，但进展缓慢。而生物学家及仿生算法专家等在群智能领域却取得较大的进展，相继提出了两类典型的群智能优化算法，即Dorig等于1991年提出的蚁群优化算法(antcolonyoptimization，ACO)，和Kennedy等于1995年提出的粒子群优化算法(particleswarmoptimization，PSO)。3.3蚁群算法——群智能优化算法9/10/202382第82页，课件共209页，创作于2023年2月1999年，Bonabeau等在著作《SwarmIntelligence:FromNaturaltoArtificialSystems》中对群智能进行了详细的论述，并定义为：任何一种基于社会生物群体行为机制设计出的算法或分布式问题求解的策略均属于群智能。之后，Bonabeau将群智能的定义进一步推广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。2001年，Kennedy等在著作《SwarmIntelligence》中对群智能的理论与方法进行了总结，并介绍了粒子群优化算法。他们不反对Bonabeau关于群智能定义的基本思想，但反对定义中的“主体”一词，认为“主体”所带有的自治性和特殊性是许多群体的个体所不具备和拥有的，这将大大限制群智能的定义范围。他们认为暂时无法给出群智能合适的定义。3.3蚁群算法——群智能优化算法9/10/202383第83页，课件共209页，创作于2023年2月至目前为止，虽然学术界对群智能的定义仍存在争议，且其理论本身还不成熟，但是群智能具备处理复杂系统的独特优势，吸引了越来越多的专家学者投身于群智能理论与应用的研究。随着研究的进展，对群智能的理解与认识亦逐渐深入，应用领域不断拓宽。2003年IEEE第一届国际群智能研讨会在美国印第安纳州首府首次召开，且每年举办一次群智能国际研讨会。2007年9月，Dorigo与Birattari在学术百科全书网站发表了一篇“SwarmIntelligence”论文，并对群智能给出了定义：群智能是一门采用分散控制和自组织理论协调处理由多个个体组成的自然和人工系统的学科；特别的，群智能学科主要研究由个体之间以及个体与环境之间的局部相互作用而产生的集体行为。同年，由Springer出版社出版的杂志《SwarmIntelligence》创刊，由Dorigo任主编。3.3蚁群算法——群智能优化算法9/10/202384第84页，课件共209页，创作于2023年2月研究蚁群的觅食行为后发现，由仅具备简单行为的蚂蚁组成的群体通过信息素的释放与跟随，实现正反馈和分布式协作，突现出复杂的群体智能行为，即蚁群能找到蚁穴与食物源之间的最短路径。受此启发，Dorig等于1991年首次提出了蚁群优化算法，此为一种基于种群的元启发式(metaheuristics)算法，已广泛地用于组合优化问题的求解，如旅行商问题、顺序排列问题、调度问题、网络路由问题、集合覆盖问题等。3.3蚁群算法——概述9/10/202385第85页，课件共209页，创作于2023年2月像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径。虽然单只蚂蚁的行为极其简单，但由这样的单个简单个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能适应环境的变化，如：在蚂蚁运动路线上突然出现障碍物时，蚂蚁能够很快重新找到最优路径。人们经过大量的研究发现，蚂蚁个体间通过一种称之为信息素(pheromone)的物质进行信息传递，从而能够相互协作，完成复杂的任务。蚂蚁之所以表现出复杂有序的行为，个体之间的信息交流和相互协作起着重要的作用。3.3蚁群算法——概述——蚂蚁觅食的生物学基础9/10/202386第86页，课件共209页，创作于2023年2月蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后者选择该路径的概率越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。3.3蚁群算法——概述——蚂蚁觅食的生物学基础9/10/202387第87页，课件共209页，创作于2023年2月食物蚁巢ADBC障碍物1112213.3蚁群算法——概述——蚁群系统示意图9/10/202388第88页，课件共209页，创作于2023年2月假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源，分别具有长度4和6。蚂蚁在单位时间内可移动一个单位长度的距离。开始时所有道路上都未留有任何信息素。在t=0时刻，20只蚂蚁从巢穴出发移动到A，它们以相同的概率选择左侧或右侧道路，因此平均有10只蚂蚁走左侧，10只走右侧。t=4时刻，第一组到达食物源的蚂蚁将折回，此时第二组的蚂蚁到达CD中点处。t=5时刻，两组蚂蚁将在D点相遇。此时BD上的信息素和CD上的相同，因为各有10只蚂蚁选择了相应的道路，从而有5只返回的蚂蚁将选择BD，而另5只将选择CD，第二组蚂蚁继续向食物方向移动。3.3蚁群算法——概述——蚁群系统示意图9/10/202389第89页，课件共209页，创作于2023年2月t=8时刻，前5只蚂蚁将返回巢穴，此时在AC中点处、CD中点处以及B点上各有5只蚂蚁。t=9时刻，前5只蚂蚁又回到A点，并且再次面对往左还是往右的选择。这时，AB上的轨迹数是20而AC上是15，因此将有较为多数的蚂蚁选择往左，从而增强了该路线上的信息素。随着该过程的继续，两条道路上的信息素的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相同的时间区间内，短的路线有更多的机会被选择。3.3蚁群算法——蚁群系统示意图9/10/202390第90页，课件共209页，创作于2023年2月蚂蚁的集群活动：通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度。而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发。模拟这种现象即可利用群体智能建立路径选择机制，使蚁群算法的搜索向最优解推进。蚁群算法所利用的搜索机制呈现出一种自催化或正反馈的特征，可将蚁群算法模型理解成增强型学习系统。3.3蚁群算法——概述9/10/202391第91页，课件共209页，创作于2023年2月蚁群算法是一种随机搜索算法，与其他模型进化算法一样，通过候选解组成的群体的进化来寻求最优解。该过程包括两个阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期产生性能更好的解。作为与遗传算法同属一类的通用型随机优化算法，蚁群算法不需要任何先验知识，最初只是随机地选择搜索路径，随着对解空间的“了解”，搜索变得更有规律，并逐渐逼近直至最终达到全局最优解。3.3蚁群算法——概述9/10/202392第92页，课件共209页，创作于2023年2月相同点之一：两个群体中都存在个体相互交流的通信机制真实蚂蚁在经过的路径上留下信息素，用以影响蚁群中的其他个体。且信息素随着时间推移逐渐挥发，减小历史遗留信息对蚁群的影响。同样，人工蚂蚁改变其所经过路径上存储的数字化信息素，该信息素记录了人工蚂蚁当前解和历史解的性能状态，而且可被后继人工蚂蚁读写。数字化的信息素同样具有挥发性，它像真实的信息量挥发一样使人工蚂蚁逐渐忘却历史遗留信息，在选择路径时不局限于以前人工蚂蚁所存留的经验。3.3蚁群算法——概述——人工蚂蚁与真实蚂蚁的异同9/10/202393第93页，课件共209页，创作于2023年2月相同点之二：都要完成寻找最短路径的任务真实蚂蚁要寻找一条从巢穴到食物源的最短路径。人工蚂蚁要寻找一条从源节点到目的节点间的最短路径。两种蚂蚁都只能在相邻节点间一步步移动，直到遍历所有节点。相同点之三：都采用根据当前信息进行路径选择的随机策略真实蚂蚁和人工蚂蚁从某一节点到下一节点的移动都是利用概率选择策略实现的。这里的概率选择策略是基于当前信息来预测未来情况的一种方法。3.3蚁群算法——概述——人工蚂蚁与真实蚂蚁的异同9/10/202394第94页，课件共209页，创作于2023年2月不同点人工蚂蚁具有记忆功能，而真实蚂蚁没有。人工蚂蚁可以记住曾经走过的路径或访问过的节点，可提高算法的效率。人工蚂蚁选择路径时并不是完全盲目的，受到问题空间特征的启发，按一定的算法规律有意识地寻找最短路径（如在旅行商问题中，可以预先知道下一个目标的距离）。人工蚂蚁生活在离散时间的环境中，即问题的求解规划空间是离散的，而真实蚂蚁生活在连续时间的环境中。3.3蚁群算法——概述——人工蚂蚁与真实蚂蚁的异同9/10/202395第95页，课件共209页，创作于2023年2月旅行商问题即TSP问题(TravelingSalesmanProblem)指给定n座城市和两两城市之间的距离，要求确定一条经过各个城市当且仅当一次的最短路线。其图论描述为：给定图G=(V,A)，其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路。3.3蚁群算法——应用于TSP问题的基本算法—TSP问题9/10/202396第96页，课件共209页，创作于2023年2月（1）它根据以城市距离和连接边上的信息素轨迹强度的数量为变量的概率函数选择下一个城市。（2）规定蚂蚁走合法路线，除非周游完成，不允许转到已访问的城市，由禁忌表控制（设tabuk表示第k只蚂蚁的禁忌表，tabuk(s)表示禁忌表中的第s个元素。）（3）它完成周游后，蚂蚁在它每一条访问的边上留下信息素。3.3蚁群算法——应用于TSP问题的基本算法—每只蚂蚁的特征9/10/202397第97页，课件共209页，创作于2023年2月bi(t)(i=1,2,

,n)：在t时刻城市i的蚂蚁数：全部蚂蚁数dij：两城市之间的距离

ij

：路径(i，j)上的能见度，反映城市i到城市j的启发程度，先验知识，由要解决的问题给出。TSP问题中一般取=1/dij

ij(t)：t时刻路径(i,j)上的信息素轨迹强度初始时刻，各条路径上的信息量相等，设

ij(0)＝C。n：城市数目3.3蚁群算法——应用于TSP问题的基本算法—基本符号9/10/202398第98页，课件共209页，创作于2023年2月蚂蚁k(k=1,2,

,m)在运动过程中，根据各条路径上积累的信息素轨迹强度和启发式信息决定转移方向。表示在t时刻蚂蚁k由位置i转移到位置j的概率，也就是其选择策略。allowedk={0,1,

,n-1}-tabuk：表示蚂蚁k下一步允许选择的城市。3.3蚁群算法——应用于TSP问题的基本算法—基本符号9/10/202399第99页，课件共209页，创作于2023年2月tabuk(k=1,2,

,m)：与实际蚁群不同，人工蚁群系统具有记忆功能，用tabuk记录蚂蚁k当前所走过的城市，集合tabuk随着进化过程做动态调整。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径就是问题的一个解。之后，禁忌表被清空，该蚂蚁又可以自由选择，开始下一个循环。和：表示信息素强度的相对重要性，表示能见度的相对重要性。分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性：3.3蚁群算法——应用于TSP问题的基本算法—基本符号9/10/2023100第100页，课件共209页，创作于2023年2月为了避免信息素过多而淹没启发信息，在每只蚂蚁走完一步或完成对所有n个城市的遍历后，要对残留信息素进行更新：：第k只蚂蚁在本次循环中留在路径ij上的信息量：本次循环中路径ij上的信息量增量

：表示轨迹的持久性，(1－

)称为信息的挥发系数，表示信息消逝程度，随时间推移，以前留下的信息逐渐消失。通常设置系数0<

<1来避免路径上信息素的无限累加。3.3蚁群算法——应用于TSP问题的基本算法—基本符号9/10/2023101第101页，课件共209页，创作于2023年2月根据信息素更新策略的不同，DorigoM提出了三种不同的基本蚁群算法模型，分别称为蚁周模型、蚁量模型和蚁密模型。三种模型的差别在于求法不同。3.3蚁群算法——应用于TSP问题的基本算法—信息素修改ant-cyclealgorithm（蚁环算法）蚁环算法（蚁周算法）的特点是行走的路径越短，对应保存的信息素的值就越大。9/10/2023102第102页，课件共209页，创作于2023年2月ant-quantityalgorithm（蚁量算法）ant-densityalgorithm（蚁密算法）信息浓度会因为城市距离的减小而增大。3.3蚁群算法——应用于TSP问题的基本算法—信息素修改9/10/2023103第103页，课件共209页，创作于2023年2月蚁周模型利用整体信息，蚂蚁完成一个循环后才更新所有路径上的信息。蚁量和蚁密模型利用局部信息，蚂蚁每走一步就要更新路径上的信息素。蚁周模型在求解TSP问题时效果较好，应用也比较广泛。3.3蚁群算法——应用于TSP问题的基本算法—信息素修改9/10/2023104第104页，课件共209页，创作于2023年2月（1）t0（t为迭代步数或搜索次数）；参数初始化。（2）假设有m只蚂蚁在工作，将各蚂蚁的初始出发点置于当前解集中；对每只蚂蚁k，按概率移至下一个顶点j；将顶点j置于当前解集，直至每只蚂蚁完成任务，完成内循环，即每只蚂蚁独立完成一个解。（3）计算各蚂蚁的路径长度Lk；记录当前最好解。（4）修改信息素。（5）tt+1。（6）若t<预定的迭代次数，且无退化行为（即找到的都是相同的解），则转步骤2。（7）输出目前最好解。3.3蚁群算法——应用于TSP问题的基本算法9/10/2023105第105页，课件共209页，创作于2023年2月3.3蚁群算法——应用于TSP问题的基本算法9/10/2023106第106页，课件共209页，创作于2023年2月ACO蚁环算法伪代码：begin初始化过程：ncycle=1;bestcycle=1;

ij=0=C;；；；q0;

ij(由某种启发式算法确定)；tabuk=while(notterminationcondition){

for(k=1;k<m;k++){将m只蚂蚁随机放置于初始城市上；}

for(index=0;index<n;index++){

for(k=1;k<m;k++){ 按转移概率确定每只蚂蚁要转移的位置；将刚刚选择的城市j加入到tabuk中；}

}

计算各蚂蚁的路径长度Lk

确定本次循环中找到的最佳路径L=min(Lk),k=1,2,…,m;蚁环算法信息素更新；ncycle=ncylce+1;}3.3蚁群算法——应用于TSP问题的基本算法9/10/2023107第107页，课件共209页，创作于2023年2月探索(exploration)和开发(exploitation)能力的平衡是影响算法性能的一个重要方面，也是蚁群算法研究的关键问题之一。探索能力是指蚁群算法要在解空间中测试不同区域以找到一个局优解的能力；开发能力是指蚁群算法在一个有希望的区域内进行精确搜索的能力。探索和开发实际上就是全局搜索能力和局域搜索能力。通过设定蚁群算法中的各种参数，实现探索和开发能力的平衡。3.3蚁群算法——应用于TSP问题的基本算法—参数选择9/10/2023108第108页，课件共209页，创作于2023年2月蚂蚁系统需要确定的参数有：m，Q、C、

、

、

。由于蚁群算法参数空间的庞大性能和各参数之间的关联性，很难确定最优组合参数使蚁群算法求解性能最佳。到目前还没有研究出蚂蚁算法模型的数学分析方法使之能够在每个情况下都能生成最优的参数设置，实际的应用中需要逐步试凑得到最优参数组合。目前已经公布的蚁群算法参数设置都是就特定问题所采用的特定蚁群算法而言，以应用最多的蚁周模型为例，其最好的试验结果为：0

5，0

5，0.1

0.99，10Q100003.3蚁群算法——应用于TSP问题的基本算法—参数选择9/10/2023109第109页，课件共209页，创作于2023年2月（1）信息素和启发函数对蚁群算法性能的影响信息素是表征过去信息的载体，而启发函数则是表示未来信息的载体，它们直接影响到蚁群算法的全局收敛性和求解效率。（2）信息素残留因子

对蚁群算法性能的影响在0.10.99范围内，

与迭代次数近似成正比。当

很大时，路径上的残留信息占主导地位，信息正反馈作用相对较弱，搜索的随机性增强，因而蚁群算法的收敛速度很慢。当

较小时，正反馈作用占主导地位，搜索的随机性减弱，导致收敛速度加快，但易于陷入局部最优。3.3蚁群算法——应用于TSP问题的基本算法—参数选择9/10/2023110第110页，课件共209页，创作于2023年2月（3）蚂蚁数目对蚁群算法性能的影响m大，会提高蚁群算法的全局搜索能力和稳定性，但数量太大会导致大量曾被搜索过的路径上的信息量变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度减慢。m小，会使从未被搜索到的解上的信息量减小到接近于0，随机性减弱，虽然收敛速度加快，但会使算法的稳定性变差，出现过早停滞现象。（4）信息素强度Q对蚁群算法性能的影响Q为蚂蚁循环一周时释放在所经路径上的信息素总量。Q越大，蚂蚁在已遍历路径上信息素的累积越快，加强蚂蚁搜索时的正反馈性，有助于算法的收敛速度。3.3蚁群算法——应用于TSP问题的基本算法—参数选择9/10/2023111第111页，课件共209页，创作于2023年2月（5）

、

对蚁群算法性能的影响

反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度。

越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱；

越小，易使蚁群算法过早陷入局优。

反映蚂蚁启发式信息在指导蚁群搜索中的相对重要程度，这些启发式信息表现为寻优过程中先验性、确定性因素。

越大，蚂蚁在局部点上选择局部最优路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易于陷入局部最优。如果

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

=0，则是纯粹的正反馈的启发式算法。3.3蚁群算法——应用于TSP问题的基本算法—参数选择9/10/2023112第112页，课件共209页，创作于2023年2月可以使用以下三步走的原则:2)参数粗调