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

2020/3/171第三章求解优化问题的智能算法2020/3/1723.1概述2020/3/173最优化问题是指在一定的约束条件下，决定某个或某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。解决最优化问题的方法称为最优化方法。它具有高度应用性和技术性的特点。最优化问题可以追溯到十分古老的极值问题，在17世纪，伟大科学家Newton发明微积分的时候，已经提出了极值问题，后来又出现了Lagrange乘子法，Cauchy则利用最速下降法求解无约束极小化问题。然而，直到1947年Dantzig提出求解一般线性规划问题的单纯形法之后，它才成为一门独立的学科。3.1概述——最优化方法的研究起源和意义1/22020/3/174随着近代科学技术发展的需要，特别是由于计算机技术的飞速发展，促进了最优化方法的迅速发展，并很快渗透到各个领域。20世纪70年代，最优化方法这门应用技术科学又开始产生出最优设计、最优控制与最优管理等分支。到20世纪80年代，最优化技术又在这些分支中发展出了新的更细的分支，比如，工程技术领域的机械优化设计、建筑结构优化设计以及化工石油领域的优化设计等。3.1概述——最优化方法的研究起源和意义2/22020/3/175求解优化问题的步骤(1)分析待优化的问题，建立问题的数学模型；(2)分析数学模型，选择合适的最优化算法；(3)编写计算机程序、上机计算、求出最优解；(4)结果检验与最后决策。2020/3/176转化为最小化问题。3.1概述——最优化问题的数学描述2020/3/177(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。3.1概述——求最优解或近似最优解的方法1/22020/3/178(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到—种较好的平衡。3.1概述——求最优解或近似最优解的方法2/22020/3/179以最速下降法、牛顿法和共扼方向法等为代表的传统优化算法具有完善的数学基础，具有计算效率高、可靠性强和比较成熟等特点。这些算法的基本迭代步骤如下：3.1概述——求解最优化问题的传统方法2020/3/17103.1概述——求解最优化问题的传统方法——最速下降法2020/3/17113.1概述——求解最优化问题的传统方法——牛顿法2020/3/17123.1概述——求解最优化问题的传统方法——共轭方向法2020/3/1713对目标函数和约束函数表达的要求必须更为宽松计算的效率比理论上的最优性更重要算法随时终止能够随时得到较好的解对优化模型中数据的质量要求更为宽松实际生活中对最优化方法性能的需求促进了最优化方法的发展，最优化逐步走出“象牙塔”，面向实际需要，完成了从“方法定向”到“问题定向”的转换。3.1概述——对最优化提出的新的需求2020/3/17141975年，Holland提出遗传算法(GeneticAlgorithm)。这种优化方法模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。这种方法将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，从而大大提高了寻优过程的搜索效率。1983年，Kirkpatrick提出了模拟退火(SimulatedAnnealing)算法。这种算法模拟热力学中退火过程能使金属原子达到能量最低状态的机制，通过模拟的降温过程，按玻兹曼(Boltzmann)方程计算状态间的转移概率来引导搜索，从而使算法具有很好的全局搜索能力。3.1概述——新的优化方法不断出现1/22020/3/171520世纪90年代初，Dorigo等提出蚁群优化算法(AntColonyOptimization)算法。这种算法借鉴蚁群群体利用信息素相互传递信息来实现路径优化的机理，通过记忆路径信息素的变化来解决组合优化问题。1995年，Kenedy和Eberhart提出粒子群优化(ParticleSwarmOptimization)算法。这种方法模仿鸟类和鱼类群体觅食迁移中，个体与群体协调一致的机理，通过群体最优方向、个体最优方向和惯性方向的协调来求解实数优化问题。1999年，Linhares提出了捕食搜索(PredatorySearch)算法。这种算法模拟猛兽捕食中大范围搜寻和局部蹲守的特点，通过设置全局搜索和局部搜索间变换的阈值来协调两种不同的搜索模式，从而实现了对全局搜索能力和局部搜索能力的兼顾。3.1概述——新的优化方法不断出现2/22020/3/1716不以达到某个最优性条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率；对目标函数和约束函数的要求十分宽松；算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点；多数算法含有一个多个体的群体，寻优过程实际上就是种群的进化过程；理论工作相对比较薄弱，一般说来都不能保证收敛到最优解。3.1概述——新的算法的一些共同特点2020/3/1717由于算法理论薄弱，最早被称为“现代启发式(ModernHeuristics)”或“高级启发式(AdvancedHeuristics)”；从其人工智能的特点，被称为“智能计算(IntelligentComputation)”或“智能优化算法(IntelligentOptimizationAlgorithms)”；从不以精确解为目标的特点，又被归到“软计算(SoftComputing)”方法中；从种群进化的特点看，它们又可以称为“进化计算(EvolutionaryCompuation)”；从模仿自然规律的特点出发，又有人将它们称为“自然计算(NaturalComputing)”。3.1概述——新的优化方法的不同名称2020/3/1718应用智能优化算法解决各类问题是重点；算法改进有很大的创新空间；多种算法结合的混合算法是一条捷径；不提倡刻意去追求理论成果；算法性能的测算是一项要下真功夫的工作；选择测试例题的一般规律：网上题库中的例题→文献中的例题→随机产生的例题→实际应用问题→自己编的例题；算法性能测试的主要指标：达优率(解的目标平均值和最优解的目标值的比，所有解的目标值的标准差等)，计算速度，计算大规模问题的能力；创造出新算法3.1概述——怎样学习研究智能优化方法2020/3/17193.2遗传算法2020/3/1720生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。3.2遗传算法——概要2020/3/1721虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生物的性状。(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。(3)生物的繁殖过程是由其基因的复制过程来完成的：(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。3.2遗传算法——概要2020/3/1722遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。3.2遗传算法——概要2020/3/1723URRXX..)(maxtsf式中，为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。Tnxxx21X对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可描述为下述数学规划模型：满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。3.2遗传算法——概要2020/3/1724U基本空间R可行解集合X可行解3.2遗传算法——概要2020/3/1725对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。3.2遗传算法——概要2020/3/1726遗传算法中，将n维决策向量用n个记号xi(n=l，2，，n)所组成的符号串X来表示：Tnxxx21X1212TnnXxxxxxxX把每一个xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。—般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的。相应的染色体就可表示为一个二进制符号串。3.2遗传算法——概要2020/3/1727这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。染色休X也称为个体X。对于每一个个体X，要按照一定的规则确定出其适应度；个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。通过编码和解码，使得问题的解空间和搜索空间一一对应。3.2遗传算法——概要2020/3/1728生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是出M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第t代群体记做P(t)，经过一代遗传和进化后，得到第t+l代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的，与此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(geneticoperators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。3.2遗传