软计算方法.ppt

1、软计算方法,第一讲,主讲教师简介,廖貅武：信息管理与电子商务系教授,博士. 研究方向： 决策分析 服务外包(ITO和BPO) 联系方式 地点:管院546房间,课程简介,1 软计算的发展 生命在长期进化过程中，积累了很多新奇的功能，人类很早就从中得到启发而改进自己的工具 (1)早期-偶然的模仿和发现。 如鲁班被茅苇划破，而发明锯子 (2)近现代-仿生学 (从自然界得到启迪, 模 仿其结构进行发明创造),(a) 模仿海豚皮-海豚皮游泳衣 (b) 依照鲸鱼皮的构造-蒙在飞机的表面薄膜- 可节约能源3%.若全国的飞机都蒙上这样的表面， 每年可节约几十亿。 (c) 研究蜘蛛的行走过程-发明了液压步行机

2、(d) 从自然的规律中得到启迪,利用其原理进行算法设 计-智能计算 (软计算),2 软计算定义 软计算(soft computing):又称为智能计算Computational intelligence) 借用自然界（生物界）规律的启迪，根据其原理，模仿设计求解问题的算法。,主要包括: (1) 通过对人类思维方式的模拟而产生的模糊计算 (Fuzzy computing) (2) 通过对自然界中生物进化机制的模拟而产生的进 化计算(Evolution computing) (3) 通过对动物脑神经的模拟而产生的神经计算 (Neural computing) (4) 通过对固体退火原理的模拟而产生

3、了模拟退 火算法 (Simulated Annealing),3 教学内容 遗传算法 人工神经网络 模拟退火算法 禁忌搜索算法,4 软计算方法中常用的记号 遗传算法（Genetic Algorithms) (GA) 人工神经网络(ANN) 禁忌搜索 (tabu search) (TS) 模拟退火 (Simulated Annealing) (SA),第一章 绪论,主要内容 (1) 最优化问题 (2) 优化算法与分类 (3) 邻域搜索方法 (4) 计算复杂性和NP问题,1.1 最优化问题,优化定义: 在满足一些等式和/或不等式约束条件下, 最大或最小某个多变量函数. 三个基本要素: 变量、约束和

4、目标函数 优化问题的表示,一般的优化问题主要指 函数优化问题：函数优化的对象是一定区域内的连续 变量 组合优化问题：组合优化的对象则是解空间中的离散 状态。,函数优化问题 （1）无约束 （2）有约束,组合优化问题,例1.3 调度问题（Scheduling problem) 单件作业（Job-shop)问题 基本特征: 工件的加工路线不同 流水作业(Flow Shop)问题: 基本特征: 所有工件的加工路线完全相同,例 1.4 装箱问题（Bin Packing) 例1.5 图着色问题,例 1.6 聚类问题（clustering problem),组合优化问题的困难： 组合爆炸,1.2 最优化算法

5、及分类,最优化算法实质上是一种搜索过程和规则.它是基于某种思想和机制,通过一定的途径或规则得到满足用户要求的问题的解的方法. 按优化机制和行为来分,目前工程中常用的优化算法可以分为:,(1)经典算法:包括线性规划、动态规划、整数规划和分枝定界法等。 (2)构造算法：用构造的方法快速建立问题的解。如调度问题中的Johnson法,Palmer法,CDS法 (3)邻域搜索法:从问题的任一解出发，通过对其邻域的不断搜索和当前解的替换来实现优化.,(4)基于系统动态演化的方法：将优化过程转变为系统动态 的演化过程，基于系统动态的演化来实现优化。如ANN等 (5)混合算法,1.3 邻域搜索算法,邻域搜索算

6、法可以分为两种类型: (a)局部搜索法：在当前解的邻域中搜索 (b)全局搜索法：用一些指导规则来指导整个解空间的优良解的搜索。（SA，GA，TS）,邻域搜索算法特点 (1) 在复杂函数优化过程中经常采用的迭代搜索技术。 (2) 在当前解所形成的邻域解中迭代，使目标函数逐步最优， 直到不能在优为止。 (3) 邻域函数和局部搜索是函数优化中的重要概念 邻域搜索算法主要包括： （1）设计邻域函数 （2）确定局部搜索方式,邻域函数的确定 （1）函数优化中邻域函数的确定 （2）组合优化中邻域函数的确定,例,鉴于以上分析: 智能优化算法从不同角度利用不同的搜索机制和策略实现对局部搜索算法的改进,以取得较好的全局优化性能,1.4 计算的复杂性与NP问题,复杂性可以分为: (1) 时间复杂性:算法对时间的需要量 (2) 空