软计算方法.ppt

软计算方法软计算方法第一讲第一讲主讲教师简介n廖貅武：廖貅武：信息管理与电子商务系教授信息管理与电子商务系教授,博士博士.n研究方向：研究方向：决策分析决策分析 服务外包服务外包(ITO(ITO和和BPO)BPO)n联系方式联系方式 n地点地点:管院管院546房间房间 课程简介1 1 软计算的发展软计算的发展 生命在长期进化过程中，积累了很多新奇的功生命在长期进化过程中，积累了很多新奇的功能，人类很早就从中得到启发而改进自己的工具能，人类很早就从中得到启发而改进自己的工具 (1)(1)早期早期-偶然的模仿和发现。偶然的模仿和发现。如鲁班被茅苇划破，而发明锯子如鲁班被茅苇划破，而发明锯子 (2)(2)近现代近现代-仿生学仿生学 (从自然界得到启迪从自然界得到启迪,模模 仿其结构进行发明创造仿其结构进行发明创造)(a)(a)模仿海豚皮模仿海豚皮-海豚皮游泳衣海豚皮游泳衣(b)(b)依照鲸鱼皮的构造依照鲸鱼皮的构造-蒙在飞机的表面薄膜蒙在飞机的表面薄膜-可节约能源可节约能源3%.3%.若全国的飞机都蒙上这样的表面，若全国的飞机都蒙上这样的表面，每年可节约几十亿。每年可节约几十亿。(c)(c)研究蜘蛛的行走过程研究蜘蛛的行走过程-发明了液压步行机发明了液压步行机(d)(d)从自然的规律中得到启迪从自然的规律中得到启迪,利用其原理进行算法设利用其原理进行算法设 计计-智能计算智能计算 (软计算软计算)2 2 软计算定义软计算定义 软计算软计算(soft computing):(soft computing):又称为智能计算又称为智能计算Computational intelligence)Computational intelligence)借用自然界（生物界）规律的启迪，根据其原理，借用自然界（生物界）规律的启迪，根据其原理，模仿设计求解问题的算法。模仿设计求解问题的算法。主要包括主要包括:(1)(1)通过对人类思维方式的模拟而产生的模糊计算通过对人类思维方式的模拟而产生的模糊计算 (Fuzzy computing)(Fuzzy computing)(2)(2)通过对自然界中生物进化机制的模拟而产生的进通过对自然界中生物进化机制的模拟而产生的进 化计算化计算(Evolution computing)(Evolution computing)(3)(3)通过对动物脑神经的模拟而产生的神经计算通过对动物脑神经的模拟而产生的神经计算 (Neural(Neural computing)computing)(4)(4)通过对通过对固体退火原理的模拟而产生了模拟退固体退火原理的模拟而产生了模拟退 火算法火算法 (Simulated Annealing)Simulated Annealing)3 3 教学内容教学内容 遗传算法遗传算法 人工神经网络人工神经网络 模拟退火算法模拟退火算法 禁忌搜索算法禁忌搜索算法 4 4 软计算方法中常用的记号软计算方法中常用的记号 遗传算法（遗传算法（Genetic Algorithms)(GA)Genetic Algorithms)(GA)人工神经网络人工神经网络(ANN)(ANN)禁忌搜索禁忌搜索 (tabutabu search)(TS)search)(TS)模拟退火模拟退火 (Simulated Annealing)(SA)(Simulated Annealing)(SA)第一章 绪论主要内容(1)最优化问题(2)优化算法与分类(3)邻域搜索方法(4)计算复杂性和NP问题1.1 最优化问题n优化定义优化定义:在满足一些等式和在满足一些等式和/或不等式约束条件下或不等式约束条件下,最大或最小某个多变量函数最大或最小某个多变量函数.n三个基本要素三个基本要素:变量、约束和目标函数变量、约束和目标函数n优化问题的表示优化问题的表示 一般的优化问题主要指一般的优化问题主要指函数优化问题函数优化问题：函数优化的对象是一定区域内的连续：函数优化的对象是一定区域内的连续 变量变量组合优化问题组合优化问题：组合优化的对象则是解空间中的离散：组合优化的对象则是解空间中的离散 状态。状态。函数优化问题函数优化问题（1 1）无约束）无约束 （2 2）有约束）有约束n组合优化问题组合优化问题例例1.3 1.3 调度问题（调度问题（Scheduling problem)Scheduling problem)单件作业（单件作业（Job-shop)Job-shop)问题问题 基本特征基本特征:工件的加工路线不同工件的加工路线不同 流水作业流水作业(Flow Shop)(Flow Shop)问题问题:基本特征基本特征:所有工件的加工路线完全相同所有工件的加工路线完全相同例例 1.4 1.4 装箱问题（装箱问题（Bin Packing)Bin Packing)例例1.5 1.5 图着色问题图着色问题 例例 1.6 1.6 聚类问题聚类问题（clustering problem)n组合优化问题的困难：组合优化问题的困难：组合爆炸组合爆炸1.2 1.2 最优化算法及分类最优化算法及分类 n最优化算法实质上是一种最优化算法实质上是一种搜索过程和规则搜索过程和规则.它是基它是基于某种于某种思想和机制思想和机制,通过一定的通过一定的途径或规则途径或规则得到满得到满足用户要求的问题的解的方法足用户要求的问题的解的方法.n按优化机制和行为来分按优化机制和行为来分,目前工程中常用的优化算目前工程中常用的优化算法可以分为法可以分为:(1)(1)经典算法经典算法:包括线性规划、动态规划、整数规划和分包括线性规划、动态规划、整数规划和分枝定界法等。枝定界法等。(2)(2)构造算法构造算法：用构造的方法快速建立问题的解。如调度：用构造的方法快速建立问题的解。如调度问题中的问题中的JohnsonJohnson法法,Palmer,Palmer法法,CDS,CDS法法(3)(3)邻域搜索法邻域搜索法:从问题的任一解出发，通过对其邻域的从问题的任一解出发，通过对其邻域的不断搜索和当前解的替换来实现优化不断搜索和当前解的替换来实现优化.(4)(4)基于系统动态演化的方法：基于系统动态演化的方法：将优化过程转变为系将优化过程转变为系统动态统动态 的演化过程，基于系统动态的演化来实现的演化过程，基于系统动态的演化来实现优化。如优化。如ANNANN等等(5)(5)混合算法混合算法1.3 1.3 邻域搜索算法邻域搜索算法邻域搜索算法可以分为两种类型邻域搜索算法可以分为两种类型:(a)(a)局部搜索法：局部搜索法：在当前解的邻域中搜索在当前解的邻域中搜索(b)(b)全局搜索法：全局搜索法：用一些指导规则来指导整个解空间用一些指导规则来指导整个解空间的优良解的搜索。（的优良解的搜索。（SASA，GAGA，TSTS）n邻域搜索算法特点邻域搜索算法特点(1)(1)在复杂函数优化过程中经常采用的迭代搜索技术。在复杂函数优化过程中经常采用的迭代搜索技术。(2)(2)在当前解所形成的邻域解中迭代，使目标函数逐步最优，在当前解所形成的邻域解中迭代，使目标函数逐步最优，直到不能在优为止。直到不能在优为止。(3)(3)邻域函数和局部搜索是函数优化中的重要概念邻域函数和局部搜索是函数优化中的重要概念n邻域搜索算法主要包括：邻域搜索算法主要包括：（1 1）设计邻域函数）设计邻域函数 （2 2）确定局部搜索方式）确定局部搜索方式n邻域函数的确定邻域函数的确定 （1 1）函数优化中邻域函数的确定）函数优化中邻域函数的确定 （2 2）组合优化中邻域函数的确定）组合优化中邻域函数的确定n n例鉴于以上分析鉴于以上分析:智能优化算法从不同角度利用不同的搜索机制智能优化算法从不同角度利用不同的搜索机制和策略实现对局部搜索算法的改进和策略实现对局部搜索算法的改进,以取得较好的以取得较好的全局优化性能全局优化性能1.4 计算的复杂性与NP问题复杂性可以分为复杂性可以分为:(1)(1)时间复杂性时间复杂性:算法对时间的需要量算法对时间的需要量(2)(2)空间复杂性空间复杂性:算法对空间的需要量算法对空间的需要量问题的复杂性问题的复杂性:问题的时间复杂性问题的时间复杂性:求解该问题的所有算法中时间复求解该问题的所有算法中时间复杂性最小的算法的时间复杂性杂性最小的算法的时间复杂性问题的空间复杂性问题的空间复杂性:求解该问题的所有算法中空间复求解该问题的所有算法中空间复杂性最小的算法的时间复杂性杂性最小的算法的时间复杂性