智能计算与现代优化方法(精)

1、智能计算与现代优化方法王永骥联系方式：D2-309Email： wangyjch2014-4-14I参考书籍1. 汪定伟;王俊伟;王洪唏;张瑞友;郭哲，智能优 化方法，高等教育出版社，20072. 谢金星，邢文训，现代优化计算方法（第二 版）北京：清华大学出版社，20053. 王凌，智能优化算法及其应用，北京：清华 大学出版社，20052014-4-15智能计算与优化2I第一章概论>引言> 智能计算、现代优化算法的发展历史>智能计算、现代优化算法与控制科学2014-4-14智能计算与优化3:实际生活中的优化问题:最优化问题模型min f(x)x 丘 S 二 R“st gi二0

2、/?,(x)<0 或 >0:全局最优与局部最优2014-4-14智能计算与优化4经典的计算方法:17世纪Newtown 微积分 1847年Cauchy最速下降法 1939年Kantorovich下料问题和运输问题 问题求解 1947年Dantzig单纯形方法2014-4-14智能计算与优化5(1 ) 选初始解(2) 停止准则LP:检验数为正;NLP:Vf(x) = 0f(x)<sV2f(x)>02014-4-14智能计算与优化162014-4-14智能计算与优化10(3)向改进点移动LP:转轴变换；NLP: 选一个移动方向：负梯度方向，牛顿方向,共轨梯度方向确定移动步长

3、：线性搜索，黄金分割，2014-4-14智能计算与优化7二、传统优化方法特点与缺陷：一个初始点运算只对一个点进行;2.向改进方向移动不能跳出局部最优解；3只有在凸集凸函数条件下才能找到全 局最优解；4. 模型必须是连续可微，甚至是二阶可微;三、实际对新优化方法的要求：1. 实际中希望模型的描述方法更宽松例:配料问题minCTXs.t.AX >bX>0若有数量折扣?2014-4-14智能计算与优化92. 计算效率LP指数算法3. 不一定要找最优解4. 希望方法能模糊I最优化方法的研究对象及特点1）最优化方法研究和解决问题的基础是最优化技术, 并强调系统整体最优；2）最优化方法研究和解

4、决问题的优势是应川各学科 交叉的方法，具有综合性；3）最优化方法研究和解决问题的方法具有显著的系 统分析特征，其各种方法的运用，儿乎都需要建 立数学模型和利用计算机求解；4）最优化方法具有强烈的实践性和应用的广泛性。2014-4-14智能计算与优化UI最优化问题的分类1）函数优化：连续空间上的优化问题；2）组合优化：离散点集的状态组合属薮祝化的标准测试函数Spere Function：NFl = xix-22i=Rastigrin function:NF2 =工x； -10cos（2z/） 4-10, x g -2,2 z/=l2014-4-14智能计算与优化13属薮祝化的标准测试函数Rose

5、nbrock Function:N-尸3 =工100（£+疋）2 +（兀一l）2,xe2,2n=Griewank Function:F4 = 1 + 血£ 疋-口爲 cos（xH /厶）,w -10,1012014-4-14智能计算与优化14际I薮祝化的标准测试函数Ackley functionF5 = 20 + 幺 一 20expe0.22014-4-14智能计算与优化18Nexp&工cos(2;zx”),xu -2,2n=l2014-4-14智能计算与优化15Schwefefs function/(x) = Y(-xJsin(J|x)/=1where-500&l

6、t;xz <500 global minimum/(x) = /?-418.9829;xt. = -420.9687 = 1: nHa去优化的典型示例1 ） TSP问题2）加工调度问题3）0 1背包问题4）装箱问题5）图着色问题6）聚类问题2014-4-14智能计算与优化17启发式计算方法【定义1-1】启发式算法是一种基于直观或经验 构造的算法，在可接受的耗费（指计算时间.占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。【定义1-2】启发式算法是一种技术，该技术使 得能在可接受的计算费用内去寻找尽可能好的解， 但不一定能保证所得解的可行性和

7、最优性，甚至在 多数情况下，无法描述所得解与最优解的近似程度。履典的启发式方法基本原理根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据走2014-4-14智能计算与优化22来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。2014-4-14智能计算与优化19启发式计算方法分类:物理启发式模拟退火算法（模拟固体熔化状态下由逐渐冷却至最终达到结晶状态的物理过程）量子计算（模拟量子态的叠加性和相干性 以及量子比特之间的纠缠性）:社会与文化启发文化算法（模拟人类社会的演化过程）人口迁移算法（

8、模拟人口流动与人口迁移）启发式导致计算智能智能计算或称计算智能(Computational Intelligenee, Cl)2014-4-14智能计算与优化21关于计算智能(CI)1992年，美国学者James首次提出:能(CI)是依靠生产者提供的数字、数据材料进行加工处,而不是依赖于知识。人工智能(Artificial Intelligence, AI)则是须用知 识进行处理。1994年，James在Florida, Orlando, 94 IEEEEWCCI会议上又阐述他的观点：智能有三个层次:生物智能(Biological Intelligence, Bl)由人脑的物理化学过程反映出来

9、的，人脑是有机物, 它是智能的基础。人工智能(Artificial Intelligence，Al)是非生物的，人造的，常用符号来表示，AI的来源 是人类知识的精华。计算智能(Computational Intelligence, Cl)是由数学方法和计算机实现的，ci的来源数值计算的传感器。2014-4-14智能计算与优化232014-4-14智能计算与优化24I关系:从复杂性来看:I > Al > CI ；从所属关系来看:AI是CI到啲过渡,因为AI中除计算算法之外，还包括符号表示及数值信息处理。模糊集合和模糊逻辑是AI到CI的过渡。也有些人认为Cl不属于Al,仅有部分重合。

10、AI：符号主义，知识、规则、推理。 左脑 CI：连接主义，数据、学习、记忆。 右脑2014-4-14智能计算与优化25I什么是智能优化算法（范围）智能计算也有人称之为“软计算”，是人们受自 然（生物界）规律的启迪，根据其原理，模仿求 解问题的算法。从自然界得到启迪，模仿其结构 进行发明创造，这就是仿生学。另一方面，我们还可以利用仿生原理进行设计（包 括设计算法），这就是智能计算的思想。这方面的内容很多，如人工神经网络技术、遗传 算法、模拟退火算法、模拟退火技术和群集智能 技术等。2014-4-14智能计算与优化26遗传算法生物启发式计算是指以生物界的各种自然现象或过程 为灵感，而提出的一系列启

11、发式智能计算方法。:遗传算法:神经网络:模糊逻辑知能计与优化272014-4-14遗传算法咬物遂祀过程是一个目銘， 界行，稳健的优祀过程，这 一优祀过程的目的在子使唆 命保达到适注环轨的锻仕毎 枸鸟数臬，而唆物种群通过进化过程 <=> 优化过程"优胜彷坎"及遗怯变异来 达別址祀（优祀丿目的的。生物的进化机制自然选择适应环境的个体具有更高 的生存能力，同时染色体 特征被保留下來杂交随机组合来白父代的染色体上的遗传物质，产生不 同于它们父代的染色休突变随机改变父代的染色体基 因结构，产生新染色体2014-4-14智能计29I粒子群优化2014-4-14習旋！I見P伉

12、化30蚁群优化（ACO）2014-4-14智能计算与优化312014-4-14智能计算与优化33树突树1突输 入输岀神经计算人工神经网络是由具有 适应性的简单单元组成的 广泛并行互连的网络，它 的组织能够模拟生物神经 系统对真实世界物体所作 出的交互反应。电脉冲 细胞体|丄込|轴突 信息处理传输神经计算2014-4-14智能计算与优化35人工神经网络(Artificial Neural Networks, ANN ), 一种模范动 物神经网络行为特征，进行分布式并行信息处理的算法数学模型。 这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连 接的关系，从而达到处理信息的目的。人工神经网

13、络具有自学习和 自适应的能力。2014-4-14智能计算与优化33无一去模糊化模糊推理系统是建立在模糊集合理论、模糊if-then规则和模 糊推理等概念基础上的先进的计算框架。模糊推理系统的基本结构由三个重要部件组成：一个规则库, 包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶 属度函数(Membership Functions, MF );以及一个推理机制， 按照规则和所给事实执行推理过程求得合理的输出或结论。智能优化方法的产生与发展:1.1975年 H olland 提出 GA随机实验法模拟生物遗传机制一点“多点（种群）> 遗传> 可并行计算2. 1977年Glover

14、提出 Tabu Search设禁搜索有记忆功能一用TABU表封锁搜索过的区域2014-4-14智能计算与优化353.1983年Kirkpatrick提出成熟的模拟退火方法模拟物理的退火过程目标v=>能量函数，在退火过程中达到最小4. 80年代重新兴起的ANN，用于优化2014-4-14智能计算与优化36五。研究应用的前景与局限性:1. 应用前景广阔2. 研究的主要问题:扩大应用范围多种方法应用 算法改进-针对不同问题，改进 性能比较理论探索收敛性，最优性条件，收敛速 度，参数选择的依据，2014-4-14智能计算与优化373. 智能优化方法的局限性:不能保证取得最优解，启发式算法，次优化

15、算法评估寻优率2014-4-14智能计算与优化38与最优解相对误差智能计算、现代优化算法与控制科学需求是发明之母控制领域的三个需求1. 处理不断复杂的对象2. 完成不断复杂的设计3在对象和环境的知识所知甚少的情况下达到以上 两点要求2014-4-14智能计算与优化39I控制科学基本问题优化是基本要求，及最小的代价，取得最大的效果。2014-4-14智能计算与优化40控制系统建模, 实质上优化问题;控制器设计，多参数下的给定性能指标的优化问题;控制结构的选择，优化问题;评估与决策，等价优化问题屠能祝化在控制领域应用1)基于NN的系统建模、辨识和控制;2)基于遗传算法的控制器优化设计;3)基于粒子

16、群的控制器优化设计；2014-4-14智能计算与优化42基于蚁群算法的控制器优化设计,5)移动机器人路径规划;6)基于禁忌搜索的预测控制器设计7)基于模拟退火算法的系统优化2014-4-14智能计算与优化41I有待研究的问题(1) 智能科学的数学体系计算智能(从进化计算到自然计算)；(2) 多类模型条件下的智能化综合集成与优化决策方法;(3)多模式反馈机制的优化协调策略和算法;(4) 信息融合与机器学习(尤其是小样本学习)；(5) 不确定性问题的智能化建模与推理。(6) 实时智能系统的协调与优化。以负反馈实现系统的运动状态镇定，以正反馈促进系统的进化与发展I有待研究的问题(6 )自下而上的涌现(emergence )机制和自上 而下的浸没(贯彻)机制(immergence );2014-4-14智能计算与优化43I本课程内容1 )遗传算法和DE2) PSO3) ACO4) 模拟退火5) 研讨：蜂群，鱼群等等2014-4-14智能计算与优化44附录3 优化算法笔记（部分转载）局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻: 为了找出地球上最高的山，一群有志气的兔子们开始想办法。1. 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它 不能保证局部最优值就是全局最优值。2. 兔子喝醉了。他随机地跳了很长时间