《第三章求解优化问题的智能算法课件.ppt》由会员分享，可在线阅读，更多相关《第三章求解优化问题的智能算法课件.ppt（210页珍藏版）》请在三一办公上搜索。
1、2022/11/26,1,第 三 章求解优化问题的智能算法,2022/11/26,2,3.1 概述,2022/11/26,3,最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。解决最优化问题的方法称为最优化方法。它具有高度应用性和技术性的特点。最优化问题可以追溯到十分古老的极值问题，在17世纪，伟大科学家Newton发明微积分的时候，已经提出了极值问题，后来又出现了Lagrange乘子法，Cauchy则利用最速下降法求解无约束极小化问题。然而，直到1947年Dantzig提出求解一般线性规划问题的单纯形法之后，它才成为一门独立的学科。,3
2、.1 概述最优化方法的研究起源和意义 1/2,2022/11/26,4,随着近代科学技术发展的需要，特别是由于计算机技术的飞速发展，促进了最优化方法的迅速发展，并很快渗透到各个领域。20世纪70年代，最优化方法这门应用技术科学又开始产生出最优设计、最优控制与最优管理等分支。到20世纪80年代，最优化技术又在这些分支中发展出了新的更细的分支，比如，工程技术领域的机械优化设计、建筑结构优化设计以及化工石油领域的优化设计等。,3.1 概述最优化方法的研究起源和意义 2/2,2022/11/26,5,求解优化问题的步骤,(1)分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算
3、法；(3)编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。,2022/11/26,6,转化为最小化问题。,3.1 概述最优化问题的数学描述,2022/11/26,7,(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。,(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个
4、启发式规则无通用性，不适合于其他问题。,3.1 概述求最优解或近似最优解的方法 1/2,2022/11/26,8,(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到种较好的平衡。,3.1 概述求最优解或近似最优解的方法 2/2,2022/11/26,9,以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：,3.1 概述求解最优化问题的传统方
5、法,2022/11/26,10,3.1 概述求解最优化问题的传统方法最速下降法,2022/11/26,11,3.1 概述求解最优化问题的传统方法牛顿法,2022/11/26,12,3.1 概述求解最优化问题的传统方法共轭方向法,2022/11/26,13,对目标函数和约束函数表达的要求必须更为宽松计算的效率比理论上的最优性更重要算法随时终止能够随时得到较好的解对优化模型中数据的质量要求更为宽松,实际生活中对最优化方法性能的需求促进了最优化方法的发展，最优化逐步走出“象牙塔”，面向实际需要，完成了从“方法定向”到“问题定向”的转换。,3.1 概述对最优化提出的新的需求,2022/11/26,14
6、,1975年，Holland提出遗传算法(Genetic Algorithm)。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover提出禁忌搜索(Tabu Search)算法。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出了模拟退火(Simulated Annealing)算法。这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程，按玻兹曼(Boltzmann)方程计算状态间的转移概率来引导搜索，
7、从而使算法具有很好的全局搜索能力。,3.1 概述新的优化方法不断出现 1/2,2022/11/26,15,20世纪90年代初，Dorigo等提出蚁群优化算法(Ant Colony Optimization)算法。这种算法借鉴蚁群群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。1995年，Kenedy和Eberhart提出粒子群优化(Particle Swarm Optimization)算法。这种方法模仿鸟类和鱼类群体觅食迁移中，个体与群体协调一致的机理，通过群体最优方向、个体最优方向和惯性方向的协调来求解实数优化问题。1999年，Linhares提
8、出了捕食搜索(Predatory Search)算法。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阈值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。,3.1 概述新的优化方法不断出现 2/2,2022/11/26,16,不以达到某个最优性条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率；对目标函数和约束函数的要求十分宽松；算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；多数算法含有一个多个体的群体，寻优过程实际上就是种群的进化过程；理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。,3.1 概述
9、新的算法的一些共同特点,2022/11/26,17,由于算法理论薄弱，最早被称为“现代启发式(Modern Heuristics)”或“高级启发式(Advanced Heuristics)”；从其人工智能的特点，被称为“智能计算(Intelligent Computation)”或“智能优化算法(Intelligent Optimization Algorithms)”；从不以精确解为目标的特点，又被归到“软计算(Soft Computing)”方法中；从种群进化的特点看，它们又可以称为“进化计算(Evolutionary Compuation)”；从模仿自然规律的特点出发，又有人将它们称为“
10、自然计算(Natural Computing)”。,3.1 概述新的优化方法的不同名称,2022/11/26,18,应用智能优化算法解决各类问题是重点；算法改进有很大的创新空间；多种算法结合的混合算法是一条捷径；不提倡刻意去追求理论成果；算法性能的测算是一项要下真功夫的工作；选择测试例题的一般规律：网上题库中的例题文献中的例题随机产生的例题实际应用问题自己编的例题；算法性能测试的主要指标：达优率(解的目标平均值和最优解的目标值的比，所有解的目标值的标准差等)，计算速度，计算大规模问题的能力；创造出新算法,3.1 概述怎样学习研究智能优化方法,2022/11/26,19,3.2 遗传算法,202
11、2/11/26,20,生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。,遗传算法(Genetic Algorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。,基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。,遗传算法所借鉴的生物学基础就是生物的遗传和进化。,3.2 遗传算法概要,2022/11/26,21,虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更
12、不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：,(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生物的性状。,(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。,(3)生物的繁殖过程是由其基因的复制过程来完成的：,(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。,(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。,3.2 遗传算法概要,2022/11/26,22,遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。,它最早由美国密执安大学的
13、Holland教授提出，起源于60年代对自然和人工自适应系统的研究。,70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。,在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。,3.2 遗传算法概要,2022/11/26,23,式中， 为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。,对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可描述为下述数学规划模型：,满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所
14、示。,3.2 遗传算法概要,2022/11/26,24,3.2 遗传算法概要,2022/11/26,25,对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。,随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。,3.2 遗传算法概要,2022/11/26,26,遗传算法中，将n维决策向量 用n个记号xi (n=l，2，n)所组成的符号串X来表示：,把每一个xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就
15、可看做是由n个遗传基因所组成的一个染色体。,般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。,根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。,最简单的等位基因是由0和1这两个整数组成的。相应的染色体就可表示为一个二进制符号串。,3.2 遗传算法概要,2022/11/26,27,这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。,通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。,染色休X也称为个体X。,对于每一个个体X，要按照一定的规则确定出其适应度；个体的适应度与其对应的个
16、体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。,遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。通过编码和解码，使得问题的解空间和搜索空间一一对应。,3.2 遗传算法概要,2022/11/26,28,生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出M个个体所组成的集合，称为群体。,与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第t代群体记做P(t)，经过一代遗传和进化后，得到第t+l代群体，它们也是由多个个体组成
17、的集合，记做P(t+1)。,这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。,生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的，与此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(genetic operators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。,3.2 遗传算法概要,2022/11/26,29,选择(selection)：根据各个个体的适应度，按照一定的规则或方法
18、，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。,交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每对个体，以某个概率(称为交叉概率，crossover rate)交换它们之间的部分染色体。,变异(mutation)：对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutation rate)改变某一个或某一些基因座上的基因值为其他的等位基因。,3.2 遗传算法概要,2022/11/26,30,使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下所述：,步骤一：初始化。设置进化代数计数器t0；设置最大进化代数
19、T；随机生成M个个体作为初始群体P(0)。,步骤二：个体评价。计算群体P(t)中各个个体的适应度。,步骤三：选择运算。将选择算子作用于群体。,3.2 遗传算法运算过程,2022/11/26,31,步骤四：交叉运算。将交叉算子作用于群体。,步骤五：变异运算。将变异算于作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。,步骤六：终止条件判断。若tT，则：tt+1，转到步骤二。若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。,3.2 遗传算法运算过程,2022/11/26,32,基于对自然界中生物遗传与进化机理的模仿，针对不向的问题，很多学者
20、设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。,但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。,3.2 遗传算法基本遗传算法的实现,2022/11/26,33,基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法基本遗传算法(Simple Genetic Algorithms，简称SGA)。,基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组
21、成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。基本遗传算法使用比例选择算子、单点交叉算子和基本位变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,3.2 遗传算法基本遗传算法的实现,2022/11/26,34,用二进制编码来离散自变量，码长根据离散精度来确定。例如当自变量a的变化区间为amin，amax ，当离散精度为时，码长m的计算公式为：,相应的解码公式为：,3.2 遗传算法基本遗传算法的实现编码和解码,2022/11/26,35,在遗传算法中，以个体适应度的大小来
22、确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。,基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。,为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。,3.2 遗传算法基本遗传算法的实现适应度评价 1/4,2022/11/26,36,对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即： minf (X)max(f (X),当优化目标是求函数最大值，并且目标函数总取正值时，可以
23、直接设定个体的适应度F(x)就等于相应的目标函数值f (X)，即：F(X)f (X),但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。,上面两式保证不了所有情况下个体的适应度都是非负数这个要求。所以必须寻求出一种通用且有效的由目标函数值到个体适应度之间的转换关系，由它来保证个体适应度总取非负值。,3.2 遗传算法基本遗传算法的实现适应度评价 2/4,2022/11/26,37,为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值f (X)变换为个体的适应度F(x)。,式中，Cmin为一个适当地相对比较小的数，它可以用下面几种方法之一来选
24、择：,方法一：对于求目标函数最大值的优化问题，变换方法为：,预先指定的一个较小的数。,进化到当前代为止的最小目标函数值。,当前代或最近几代群体中的最小目标函数值。,3.2 遗传算法基本遗传算法的实现适应度评价 3/4,2022/11/26,38,方法二：对于求目标函数最小值的优化问题，变换方法为：,式中，Cmax为一个适当地相对比较大的数，它可以用下面几种方法之一来选择：,预先指定的一个较大的数。,进化到当前代为止的最大目标函数值。,前代或最近几代群体中的最大目标函数值。,3.2 遗传算法基本遗传算法的实现适应度评价 4/4,2022/11/26,39,选择算子或复制算子的作用是从当前代群体中
25、选择出一些比较优良的个体，并将其复制到下一代群体中。最常用和最基本的选择算子是比例选择算子。,比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette wheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。,所谓比例选择算子，是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。,3.2 遗传算法基本遗传算法的实现比例选择算子 1/4,2022/11/26,40,整个赌盘被分为大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。,虽然赌盘的指针具体停止在哪一个扇面是无法预测的，但指针指向各
26、个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比：圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。,与此类似，在遗传算法中，整个群体被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。,3.2 遗传算法基本遗传算法的实现比例选择算子 2/4,2022/11/26,41,3.2 遗传算法基本遗传算法的实现比例选择算子 3/4,2022/11/26,42,令：,3.2 遗传算法基本遗传算法的实现比例选择算子 4/4,2022/11/26,43,算子的具体执行
27、过程如下 ：,(1)对群体中的个体进行两两随机配对。若群体的大小为M，则共有M/2对相互配对的个体组。其中x表示不大于x的最大整数。,(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为n，则共有(n-1)个可能的交叉点位置。,(3)对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。,3.2 遗传算法基本遗传算法的实现单点交叉算子 1/2,2022/11/26,44,单点交叉示意如下所示：,3.2 遗传算法基本遗传算法的实现单点交叉算子 2/2,2022/11/26,45,对于基本遗传算法中用二进制编码
28、符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为l，则变异操作将其变为0。,(1)对个体的每一个基因座，依变异概率pm指定其为变异点。,(2)对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。,3.2 遗传算法基本遗传算法的实现基本位变异算子,2022/11/26,46,基本遗传算法有下述4个运行参数需要提前设定：,M：群体大小，即群体中所含个体的数量，一般取为201000,T：遗传运算的终止进化代数，一般取为100500,Pc：交叉概率，般取为0.40.99。,Pm：变异概率，一般
29、取为0.00010.1,这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。,3.2 遗传算法遗传算法的运行参数 1/2,2022/11/26,47,在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。,一般来说，选择较大数目的初始种群可以同时处理更多的解，因而容易找到全局的最优解，其缺点使增加了每次迭代所需要的时间。,交叉概率的选择决定了交叉操作的频率。频率越高，可以越快收敛到最有希望的最优解区域；但是太高的频率也可能导致收敛于一个解。,变异概率通常只取较小的数值。若选取高的变异率，一方面可以增加样本的多样性，另
30、一方面可能引起不稳定。但是若选取太小的变异概率，则可能难于找到全局的最优解。,3.2 遗传算法遗传算法的运行参数 2/2,2022/11/26,48,该函数有两个局部极大值，分别是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者为全局最大值。,首先确定决策变量和约束条件，确定优化模型,例：Rosenbrock函数的全局最大值计算。,3.2 遗传算法在函数优化中的应用确定优化模型,2022/11/26,49,用长度为l0位的二进制编码串来分别表示二个决策变量x1，x2。,10位二进制编码串可以表示从0到1023之间的1024个不同
31、的数，故将x1，x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。,从离散点2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。,再将分别表示x1，x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。,例如X：000011011l 1101110001就表示一个个体的基因型，其中前10位表示x1，后10为表示x2。,3.2 遗传算法在函数优化中的应用确定编码方法,2022/11/26,50,解码时需先将20位长的二
32、进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。,例如，对于前述个体 X：000011011l 1101110001它由这样的两个代码所组成：y155 y2881经解码处理后，可得到：x1=1.828 x2=1.476,依据前述个体编码方法和对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：,3.2 遗传算法在函数优化中的应用确定解码方法,2022/11/26,51,第六步：设计遗传算子。,可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，即有：F
33、(X)=f(x1，x2),选择运算使用比例选择算子；,交叉运算使用单点交叉算子；,变异运算使用基本位变异算子。,3.2 遗传算法在函数优化中的应用确定个体评价方法,2022/11/26,52,对于本例，设定基本遗传算法的运行参数如下：,群体大小：M80,终止代数：T200,交叉概率：pc0.6,变异概率：pm0.001,通过上述七个步骤就可构成用于Rosenbrock函数优化计算的基本遗传算法。,3.2 遗传算法在函数优化中的应用确定运行参数,2022/11/26,53,myGA.mfunction xv,fv=myGA(fitness,a,b,NP,NG,Pc,Pm,eps)function
34、 result = Initial(length) function y = Dec(a,b,x,L),myGA2.m,3.2 遗传算法在函数优化中的应用程序,2022/11/26,54,传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象。,这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。
35、,3.2 遗传算法特点以决策变量的编码作为运算对象,2022/11/26,55,传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。,而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。,这个特性对很多目标函数无法或是很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。,再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。,3.2
36、遗传算法特点直接以目标函数值作为搜索信息,2022/11/26,56,传统的优化算法往往是从解空间个的一个初始点开始最优解的这代搜索过程，单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时其至使搜索过程陷入局部最优解而停滞不前。,遗传算法从很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。,这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。,3.2 遗传算法特点同时使用多个搜索点的搜索信息,2022/11
37、/26,57,传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。,遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。,虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体，实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。,当然，交叉概率和变异概率等参数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在
38、其应用中是一个比较重要的问题。而另一方面，与其他一些算法相比遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能地低。,3.2 遗传算法特点使用概率搜索技术,2022/11/26,58,约束优化(Constrained Optimization)是处理具有等式和(或)不等式约束的目标函数问题，其一般形式可以表示为：,可记约束集（可行集）为：,用于操作染色体的遗传算法常会产生不可行的染色体的问题。,3.2 遗传算法约束的处理 1/3,2022/11/26,59,拒绝策略：抛弃进化过程中产生的所有不可行解。这是遗传算法处理约束问题的最简单也是效率最低的方法。修复策略：在进化过程中获得不可行解后，
39、将其修复为可行解。对于很多组合优化问题创建修复过程相对容易，但可能导致失去种群的多样性。惩罚策略：对约束进行处理的最一般的方式，是通过对不可行解的惩罚来将约束问题转化为无约束问题。任何对于约束的违反都要在目标函数中添加惩罚项。需要设计合适的惩罚函数，不合适的惩罚函数会掩盖目标函数的优化。,3.2 遗传算法约束的处理 2/3,2022/11/26,60,特殊的编码和遗传策略：使用特殊的编码策略，在编码时就充分考虑约束问题，在编码时产生的都是符合约束的染色体。为了使染色体在遗传操作后仍然保持可行性，也有使用特殊的遗传策略，使遗传操作后染色体仍然保持可行。,3.2 遗传算法约束的处理 3/3,202
40、2/11/26,61,现实的生产和生活中人们常常遇到存在的目标超过一个，并且需要同时处理的情况，而这些不同的目标又往往是相互冲突的，这就是多目标优化(Multiobjective Optimization)问题。具有p个目标的多目标问题的一般形式为：,3.2 遗传算法多目标的处理 1/4,2022/11/26,62,在大多数情况下，各个目标函数间可能是冲突的。这就使得多目标优化问题不存在唯一的全局最优解，使所有目标函数同时最优。但是，可以存在这样的解：对一个或几个目标函数不可能进一步优化，而对其他目标函数不至于劣化，这样的解称之为非劣最优解，也称有效解，或Pareto最优解。遗传算法种群进化特
41、征使其适合于这样的问题。处理多目标问题时，遗传算法遇到的一个主要问题是如何根据多个目标函数值来确定个体的适应值，即适应值分配机制。,3.2 遗传算法多目标的处理 2/4,2022/11/26,63,向量评价方法：采用向量形式评价的适应值度量来产生下一代，而不是使用标量适应值度量方式来评价染色体。对于有p个目标的给定问题，每代中的选择过程是一个循环，它重复p次，每次循环依次使用一个目标，选出下一代中的一部分个体。权重和方法：为每个目标函数分配权重并将权重目标组合为单一目标函数。权重的调整方法包括：固定权重方法、随机权重方法、适用性权重方法。,3.2 遗传算法多目标的处理 3/4,2022/11/
42、26,64,基于Pareto的方法：有两种基于Pareto的方法： Pareto排序和Pareto竞争。妥协方法：通过某种距离的度量来确定与理想解最近的解。目标规划方法：采用基于排序的适应值分配方法来判断个体的价值。具体过程为：根据第一优先目标进行种群排序，如果某些个体具有相同的目标值，根据第二优先目标进行排序，如此进行下去。如果各个目标上各个个体均相同，则随机对其进行排序。然后采用从最好到最差的指数插值进行个体的适应值分配。,3.2 遗传算法多目标的处理 4/4,2022/11/26,65,GADS 这个是Matlab7.0版本自带的工具箱，全名叫Genetic Algorithm and
43、Direct Search Toolbox。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。它还提供了一个图形用户界面的工具，名为“Genetic Algorithm Tool”，有了这个工具就可以不必输入繁琐的命令行参数，能方便而且直观的观察算法的运行过程。在命令行里输入“gatool”，就可以进入该图形用户界面。,3.2 遗传算法MATLAB遗传算法工具箱,2022/11/26,66,x fval = ga(fitnessfun, nvars, options)Where fitnessfun is a handle to the fitness funct
44、ion. nvars is the number of independent variables for the fitness function.options is a structure containing options for the genetic algorithm. If you do not pass in this argument, ga uses its default options. The results are given by:x Point at which the final value is attainedfval Final value of t
45、he fitness function,3.2 遗传算法MATLAB遗传算法工具箱命令行函数,2022/11/26,67,3.2 遗传算法MATLAB遗传算法工具箱图形用户界面,2022/11/26,68,求下列函数的最小值：,建立适应函数FitFun.m文件：function y=FitFun(x)y=0.01;for i=1:5 y=y+1/(i+(x(i)-1)2);endy=1/y,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,69,适应度函数的文件名,待寻优变量的个数,变量的下边界和上边界,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11
46、/26,70,寻优结果,优化参数,迭代次数,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,71,该例题的理论最小值为0.436，且在(x1,x2,x3,x4,x5)=(1,1,1,1,1)时取到。从结果的比较可以看出，遗传算法求出的结果精度是很高的。,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,72,建立适应函数FitFun.m文件：function y=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
47、)2+x(2)2-9;ceq=;,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,73,非线性约束函数,Nonlinear constraint function defines the nonlinear constraints. Specify the function as an anonymous function or as a function handle of the form nonlcon, where nonlcon.m is an M-file that returns the vectors c and ceq. The nonlinear
48、equalities are of the form ceq=0, and the nonlinear inequalities are of the form c0.,线性等式和不等式约束,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,74,此例题的理论最小值为3，在(x1,x2)=(2,2)时取得。从结果可以看出，结果精度是很高的。,3.2 遗传算法MATLAB遗传算法工具箱应用实例,2022/11/26,75,如果双亲的基因非常相近，所产生的后代相对于双亲也必然比较接近。这样所期待的性能改善也必然较小。类似于“近亲繁殖”。,所以基因模式的单一性不仅减慢进化历程
49、，而且可能导致进化停滞，过早地收敛于局部的极值解。,Srinvivas等提出一种自适应遗传算法，交叉概率和变异概率能够随适应度自动改变。当种群各个个体适应度趋于一致或者趋于局部最优时，使交叉概率和变异概率二者增加，而当群体适应度比较分散时，使交叉概率和变异概率减少。同时，对于适应值高于群体平均适应值的个体，对应于较低的交叉概率和变异概率，使该个体得以保护进入下一代；而低于平均适应值的个体，相对于较高的交叉概率和变异概率，使该个体被淘汰。,3.2 遗传算法改进自适应遗传算法,2022/11/26,76,因此，自适应遗传算法能够提供相对某个解的最佳交叉概率和变异概率。自适应遗传算法中交叉概率和变异
50、概率的计算公式为：,3.2 遗传算法改进自适应遗传算法,2022/11/26,77,设PG为上一代进化到下一代时被替换的个体的比例，则按此比例，部分个体被新的个体所取代，而其他部分的个体则直接进入下一代。,PG越大，进化得越快，但算法的稳定性和收敛性将受到影响；而PG越小，算法的稳定性越好，但进化速度将变慢。可见，应该寻求运行速度与稳定性、收敛性之间的协调平衡。,3.2 遗传算法改进部分替代法,2022/11/26,78,这种方法对于每代中一定数量的最优个体，使之直接进入下一代。,这样可以防止优秀个体由于复制、交叉或变异中的偶然因素而被破坏掉。,这是增强算法稳定性和收敛性的有效方法。,但同时也
