《智能计算与现代优化方法课件》由会员分享，可在线阅读，更多相关《智能计算与现代优化方法课件（46页珍藏版）》请在金锄头文库上搜索。
1、2020/9/28,智能计算与优化,1,智能计算与现代优化方法,王永骥 联系方式：D2-309 Email：,2020/9/28,智能计算与优化,2,参考书籍,1. 汪定伟;王俊伟;王洪峤;张瑞友;郭哲 ，智能优化方法，高等教育出版社，2007 2. 谢金星，邢文训，现代优化计算方法（第二版）北京：清华大学出版社，2005 3. 王凌，智能优化算法及其应用 ，北京：清华大学出版社，2005,2020/9/28,智能计算与优化,3,第一章概论,引言 智能计算、现代优化算法的发展历史 智能计算、现代优化算法与控制科学,2020/9/28,智能计算与优化,4,最优化问题模型,引言,全局最优与局部最优
2、,实际生活中的优化问题,2020/9/28,智能计算与优化,5,经典的计算方法,17世纪Newtown 微积分,1847年 Cauchy 最速下降法,1947年 Dantzig 单纯形方法,1939年 Kantorovich下料问题和运输问题 问题求解,2020/9/28,智能计算与优化,6,（）. 选初始解,LP: 检验数为正;,（2）. 停止准则,NLP:,2020/9/28,智能计算与优化,7,（3）向改进点移动,LP: 转轴变换;,NLP:,选一个移动方向: 负梯度方向,牛顿方向,共轭梯度方向,确定移动步长: 线性搜索,黄金分割, . . .,2020/9/28,智能计算与优化,8,二
3、、传统优化方法特点与缺陷：,1. 一个初始点-运算只对一个点进行;,2. 向改进方向移动 -不能跳出局部最优解;,3. 只有在凸集凸函数条件下才能找到全局最优解;,4. 模型必须是连续可微, 甚至是二阶可微;,2020/9/28,智能计算与优化,9,例:,配料问题,三、实际对新优化方法的要求：,1. 实际中希望模型的描述方法更宽松,若有数量折扣?,2020/9/28,智能计算与优化,10,LP-指数算法,2. 计算效率,3. 不一定要找最优解,4. 希望方法能模糊,2020/9/28,智能计算与优化,11,最优化方法的研究对象及特点,1）最优化方法研究和解决问题的基础是最优化技术，并强调系统整
4、体最优； 2）最优化方法研究和解决问题的优势是应用各学科交叉的方法，具有综合性； 3）最优化方法研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用计算机求解； 4）最优化方法具有强烈的实践性和应用的广泛性。,2020/9/28,智能计算与优化,12,1）函数优化：连续空间上的优化问题； 2）组合优化：离散点集的状态组合,最优化问题的分类,2020/9/28,智能计算与优化,13,函数优化的标准测试函数,Spere Function： Rastigrin function:,2020/9/28,智能计算与优化,14,函数优化的标准测试函数,Rosenbro
5、ck Function: Griewank Function:,2020/9/28,智能计算与优化,15,函数优化的标准测试函数,Ackley function,2020/9/28,智能计算与优化,16,Schwefels function,2020/9/28,智能计算与优化,17,组合优化的典型示例,1）TSP问题 2）加工调度问题 3）01背包问题 4）装箱问题 5）图着色问题 6）聚类问题,2020/9/28,智能计算与优化,18,启发式计算方法,【定义1-1】 启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该
6、可行解与最优解的偏离程度未必可事先估计。 【定义1-2】 启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。,2020/9/28,智能计算与优化,19,经典的启发式方法基本原理,根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。,2020/9/28,智能计算与优化,20,启发式计算方法分类,物理启发式 模拟退火算法 （模拟
7、固体熔化状态下由逐渐冷 却至最终达到结晶状 态的物理过程） 量子计算 （模拟量子态的叠加性和相 干性 以及量子 比特之间的纠缠性）,社会与文化启发 文化算法 （模拟人类社会的演化过程） 人口迁移算法（模拟人口流动与人口迁移）,2020/9/28,智能计算与优化,21,启发式导致计算智能,智能计算或称计算智能 （Computational Intelligence, CI）,2020/9/28,智能计算与优化,22,关于计算智能（CI）,1992年，美国学者James首次提出：计算智能(CI)是依靠生产者提供的数字、数据材料进行加工处理，而不是依赖于知识。 人工智能（Artificial Int
8、elligence, AI）则是须用知识进行处理。 1994年，James在Florida, Orlando, 94 IEEEE WCCI会议上又阐述他的观点：,2020/9/28,智能计算与优化,23,智能有三个层次： 生物智能（Biological Intelligence, BI） 由人脑的物理化学过程反映出来的，人脑是有机物，它是智能的基础。 人工智能（Artificial Intelligence, AI） 是非生物的，人造的，常用符号来表示，AI的来源是人类知识的精华。 计算智能（Computational Intelligence, CI） 是由数学方法和计算机实现的，CI的来源
9、数值计算的传感器。,2020/9/28,智能计算与优化,24,关系：,从复杂性来看：BI AI CI ； 从所属关系来看： AI是CI到BI的过渡，因为AI中除计算算法之外，还包括符号表示及数值信息处理。 模糊集合和模糊逻辑是AI到CI的过渡。,2020/9/28,智能计算与优化,25,也有些人认为CI不属于AI，仅有部分重合。 AI：符号主义，知识、规则、推理。 左脑 CI：连接主义，数据、学习、记忆。 右脑,2020/9/28,智能计算与优化,26,什么是智能优化算法（范围）,智能计算也有人称之为“软计算”，是人们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪
10、，模仿其结构进行发明创造，这就是仿生学。 另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。 这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。,2020/9/28,智能计算与优化,27,生物启发式（智能）优化方法,遗传算法 神经网络 模糊逻辑 。,生物启发式计算是指以生物界的各种自然现象或过程 为灵感，而提出的一系列启发式智能计算方法。,2020/9/28,智能计算与优化,28,遗传算法,进化过程,优化过程,生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种
11、群通过” “优胜劣汰”及遗传变异来达到进化（优化）目的的。,2020/9/28,智能计算与优化,29,遗传算法,生物的进化机制,自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来 杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体 突变 随机改变父代的染色体基因结构，产生新染色体,2020/9/28,智能计算与优化,30,粒子群优化,Food,Global Best Solution,Past Best Solution,2020/9/28,智能计算与优化,31,蚁群优化（ACO）,2020/9/28,智能计算与优化,32,神经计算,人工神经网络是由 具有
12、适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。,2020/9/28,智能计算与优化,33,神经计算,人工神经网络（Artificial Neural Networks, ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。,2020/9/28,智能计算与优化,34,模糊逻辑,是 A1,集结器,去模 糊化,y,规则1,y 是 B1,y 是 B2,y 是 Br,是 A2,是 Ar,规则2,
13、规则r,模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。 模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（Membership Functions, MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论 。,2020/9/28,智能计算与优化,35,四。智能优化方法的产生与发展：,1. 1975年Holland提出GA,-随机实验法-模拟生物遗传机制,一点-多点(种群)-遗传-可并行计算,2. 1977年Glover提出Tabu Search,设禁搜索-
14、有记忆功能,-用TABU表封锁搜索过的区域,2020/9/28,智能计算与优化,36,3. 1983年Kirkpatrick提出成熟的模拟退火方法,目标能量函数, 在退火过程中达到最小,4. 80年代重新兴起的ANN,用于优化,-模拟物理的退火过程,2020/9/28,智能计算与优化,37,2. 研究的主要问题：,扩大应用范围-多种方法应用,五。研究应用的前景与局限性:,1. 应用前景广阔,算法改进-针对不同问题,改进,性能比较,理论探索-收敛性,最优性条件,收敛速度,参数选择的依据, .,2020/9/28,智能计算与优化,38,3. 智能优化方法的局限性：,不能保证取得最优解,启发式算法,
15、次优化,算法评估 -寻优率,-与最优解相对误差,2020/9/28,智能计算与优化,39,智能计算、现代优化算法与控制科学,需求是发明之母 控制领域的三个需求 处理不断复杂的对象 完成不断复杂的设计 在对象和环境的知识所知甚少的情况下达到以上两点要求,2020/9/28,智能计算与优化,40,控制科学基本问题,优化是基本要求，及最小的代价，取得最大的效果。 控制系统建模，实质上优化问题； 控制器设计，多参数下的给定性能指标的优化问题； 控制结构的选择，优化问题； 评估与决策，等价优化问题 。,2020/9/28,智能计算与优化,41,智能优化在控制领域应用,1）基于NN的系统建模、辨识和控制； 2）基于遗传算法的控制器优化设计； 3）基于粒子群的控制器优化设计； 4）基于蚁群算法的控制器优化设计， 5）移动机器人路径规划； 6）基于禁忌搜索的预测控制器设计 7）基于模拟退火算法的系统优化 等等。,2020/9/28,智能计算与优化,42,有待研究的问题,（1）智能科学的数学体系 计算智能（从进化计算到自然计算）； （2）多类模型条件下的智能化综合集成与优化决策方法； （3）多模式反馈机制的优化协调策略和算法； （4）信息
