第三章求解优化问题的智能算法课件.ppt
《第三章求解优化问题的智能算法课件.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,整个赌盘被分为大小不同的一些扇面,分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下来时,其指针所指扇面上的物品就归赌博者所有。,虽然赌盘的指针具体停止在哪一个扇面是无法预测的,但指针指向各
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 求解 优化 问题 智能 算法 课件
链接地址:https://www.31ppt.com/p-1454432.html