现代智能优化幻灯片.ppt

《现代智能优化幻灯片.ppt》由会员分享，可在线阅读，更多相关《现代智能优化幻灯片.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现代智能优化第1页，共70页，编辑于2022年，星期日引言 v现代优化算法包括禁忌搜索（Tabu search）、模拟退火（Simulated annealing）、遗传算法（Genetic algorithms）等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础而构造的算法，我们称之为启发式算法。启发式算法的兴起与计算复杂性理论的形成有密切的联系，当人们不满足常规算法求解复杂问题时，现代智能优化算法开始体现其作用。现代智能优化算法自八十年代初兴起，至今发展迅速，这些算法同人工智能、计算机科学和运筹学迅速融合，促进了复杂优化问题的分析和解决。下面

2、我们就简要介绍这些算法的基本理论以及MATLAB实现。第2页，共70页，编辑于2022年，星期日遗传算法 v特点 遗传算法直接以适应度作为搜索信息，求解问题时，搜索过程不受优化函数连续性的约束，无需导数或其他辅助信息；遗传算法具有很高的并行性，可以同时搜索解空间的多个区域搜索信息，从而降低算法陷入局部最优解的可能性；遗传算法具很强的鲁棒性。在待求解问题为非连续、多峰以及有噪声的情况下，它能够以很大的可能性收敛到最优解或近似最优解；遗传算法具有较高的可扩充性。它易于与其它领域的知识或算法相结合来求解特定问题；遗传算法的基本思想简单，具有良好的可操作性和简单性；遗传算法具有较强的智能性，可以用来解

3、决复杂的非结构化问题。第3页，共70页，编辑于2022年，星期日遗传算法v算法流程第4页，共70页，编辑于2022年，星期日遗传算法v基本要素 问题编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定(主要是指群体大小和使用遗传操作的概率等)第5页，共70页，编辑于2022年，星期日遗传算法v问题编码第6页，共70页，编辑于2022年，星期日遗传算法v初始群体的设定 遗传算法是群体型操作，这样必须为遗传操作准备一个由若干初始解组成的初始群体。初始种群的好坏对于遗传算法的计算结果的优劣和算法的效率有着重要影响。产生初始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待求解问题的解无

4、任何先验知识的情况；另一种是把某些先验知识转化为必须满足的一组要求，然后在满足这些要求的解中随机的选取。这种选择初始种群的方法可以使遗传算法较快地达到最优解。初始群体也称做进化的初始代，即第一代（first generation）。第7页，共70页，编辑于2022年，星期日遗传算法v适应度函数的确定解析性质：连续、非负 合理性：要求适应度函数设计应尽可能简单近似量小：适应度函数对某一类具体问题，应尽可能通用。v目标函数的处理方法第8页，共70页，编辑于2022年，星期日遗传算法第9页，共70页，编辑于2022年，星期日遗传算法v遗传算子 选择算子 交叉算子 变异算子 第10页，共70页，编辑于

5、2022年，星期日选择算子 第11页，共70页，编辑于2022年，星期日选择算子第12页，共70页，编辑于2022年，星期日选择算子第13页，共70页，编辑于2022年，星期日交叉算子 v两个步骤 首先在新复制的群体中随机选取两个个体；沿着两个个体（字符串）随机的取一个位置，二者互换从该位置起的末尾部分第14页，共70页，编辑于2022年，星期日 变异算子 v变异算子模拟了自然界中生物进化过程中个体的基因突变现象，从而改变染色体的结构和物理性状。它是指将个体编码串中的某些基因位上的基因值用该基因位上的其他等位基因来替换，从而产生新的个体。在遗传运算过程中，当交叉操作产生的后代适应度值不再进化，

6、且没有达到最优时，意味着算法陷入了早熟。早熟的根源在于有效基因的缺损，变异算子在一定程度上克服了这种情况，它可以改善遗传算法的局部搜索能力，增加种群的多样性。常见的变异算子包括位点变异、插入变异、对换变异、边界变异、非均匀变异和高斯变异等形式。v变异操作就是改变染色体某个（些）位上的基因。例如，设染色体，将其第三位上的0变为1，即。也可以看做是原染色体的子代染色体。第15页，共70页，编辑于2022年，星期日遗传算法的参数设置 第16页，共70页，编辑于2022年，星期日遗传算法的基本步骤 第17页，共70页，编辑于2022年，星期日遗传算法求解实例第18页，共70页，编辑于2022年，星期日

7、遗传算法求解实例第19页，共70页，编辑于2022年，星期日遗传算法求解实例第20页，共70页，编辑于2022年，星期日遗传算法求解实例第21页，共70页，编辑于2022年，星期日遗传算法求解实例第22页，共70页，编辑于2022年，星期日遗传算法求解实例第23页，共70页，编辑于2022年，星期日遗传算法求解实例第24页，共70页，编辑于2022年，星期日遗传算法求解实例第25页，共70页，编辑于2022年，星期日遗传算法求解实例第26页，共70页，编辑于2022年，星期日遗传算法求解实例第27页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现 v调用方法 x=ga(fitne

8、ssfcn,nvars)x=ga(fitnessfcn,nvars,A,b)x=ga(fitnessfcn,nvars,A,b,Aeq,beq)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)x,fval=ga(.)x,fval,exitflag=ga(.)第28页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现 v输入参数和输出参数 第29页

9、，共70页，编辑于2022年，星期日遗传算法的MATLAB实现 v控制参数设置 第30页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现 v命令详解 第31页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现 第32页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第33页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第34页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第35页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第36页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第37页，共7

10、0页，编辑于2022年，星期日遗传算法的MATLAB实现第38页，共70页，编辑于2022年，星期日遗传算法的MATLAB实现第39页，共70页，编辑于2022年，星期日模拟退火算法 第40页，共70页，编辑于2022年，星期日模拟退火算法的基本思想 第41页，共70页，编辑于2022年，星期日模拟退火的原理 第42页，共70页，编辑于2022年，星期日模拟退火算法新解的产生和接受 第43页，共70页，编辑于2022年，星期日冷却进度表参数 第44页，共70页，编辑于2022年，星期日模拟退火的算法步骤 第45页，共70页，编辑于2022年，星期日模拟退火算法的参数控制问题第46页，共70页，

11、编辑于2022年，星期日模拟退火算法的参数控制问题第47页，共70页，编辑于2022年，星期日模拟退火算法的参数控制问题第48页，共70页，编辑于2022年，星期日模拟退火算法的参数控制问题第49页，共70页，编辑于2022年，星期日模拟退火算法的应用实例第50页，共70页，编辑于2022年，星期日编码选择 第51页，共70页，编辑于2022年，星期日模拟退火新状态产生函数的设计 第52页，共70页，编辑于2022年，星期日新状态接受函数的设计 第53页，共70页，编辑于2022年，星期日初温和初始状态 第54页，共70页，编辑于2022年，星期日温度下降函数的设计 第55页，共70页，编辑于

12、2022年，星期日温度修改准则和算法终止准则的设计 第56页，共70页，编辑于2022年，星期日模拟退火算法的应用实例第57页，共70页，编辑于2022年，星期日模拟退火的MATLAB工具箱求解 第58页，共70页，编辑于2022年，星期日模拟退火的MATLAB工具箱求解 v函数详解第59页，共70页，编辑于2022年，星期日模拟退火的MATLAB工具箱求解 第60页，共70页，编辑于2022年，星期日禁忌搜索 v禁忌搜索(tabu search)算法是局部邻域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用G1over在1986年首次提出这一概念，进而形成一套完整算法，禁忌按索算法的

13、特点是采用了禁忌技术所谓禁忌就是禁止重复前面的工作。为了回避局部邻城搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择的搜索这些点，以此来跳出局部最优点。禁忌搜索算法是种人工智能算法。第61页，共70页，编辑于2022年，星期日局部邻域搜索简介 第62页，共70页，编辑于2022年，星期日局部邻域搜索简介第63页，共70页，编辑于2022年，星期日局部邻域搜索简介v局部邻域搜索是基于贪婪算法思想，在当前解的邻域进行持续的搜索，虽然算法比较通用且容易理解实现，但是搜索的性能完全依赖于邻域结构和初始解的选择，尤其容易陷入

14、局部极小值，而无法保证全局最优。针对局部邻域搜索，为了跳出局部最优的限制，可以采用的禁忌搜索尽量避免迂回搜索，禁忌搜索是一种人工智能算法，是局部搜索算法的扩展，它的一个重要思想是标记已得到的局部最扰解，并在进一步的迭代中避开这些局部最优解，下面我们讲解禁忌搜索算法如何避开和记忆这些点。第64页，共70页，编辑于2022年，星期日禁忌搜索的基本原理 第65页，共70页，编辑于2022年，星期日禁忌搜索算法流程图第66页，共70页，编辑于2022年，星期日禁忌搜索算法的简化步骤第67页，共70页，编辑于2022年，星期日禁忌搜索的关键技术 v初始解的设置 v适应度函数 v邻域结构 v禁忌对象 v候选解的选择 v禁忌表及禁忌长度 v特赦准则 v集中性与多样性搜索策略 v终止准则 第68页，共70页，编辑于2022年，星期日 禁忌搜索的MATLAB实现 第69页，共70页，编辑于2022年，星期日重点回顾v遗传算法中遗传算子以及算法的基本步骤和MATLAB实现；v模拟退火算法的基本思想、算法步骤、控制参数的设置和MATLAB实现；v禁忌搜索的基本原理、关键技术和MATLAB实现。第70页，共70页，编辑于2022年，星期日