1、by 谢广明 ， 20052006学年度第一学期,1,第一章 绪论,优化问题的分类与描述Benchmark问题介绍优化算法及其分类邻域函数与局部搜索计算复杂性与NP、NP-hard、NP-Complete,by 谢广明 ， 20052006学年度第一学期,2,1.1 优化问题分类,严格数学化以后的狭义优化问题函数优化问题组合优化问题混合型优化问题,by 谢广明 ， 20052006学年度第一学期,3,函数优化问题 1,本质求解自变量为连续变量的函数的最小值定义,by 谢广明 ， 20052006学年度第一学期,4,函数优化问题 2,有约束和无约束是否存在一些限制自变量取值的约束条件，一般以不等
2、式和等式形式出现g(x)0, h(x)=0,by 谢广明 ， 20052006学年度第一学期,5,函数优化问题 3,有约束转化为无约束的处理,by 谢广明 ， 20052006学年度第一学期,6,组合优化问题,本质求解自变量为离散变量的函数的最小值定义组合爆炸！,by 谢广明 ， 20052006学年度第一学期,7,1.2 Benchmark问题,含义基准研究对象很多科学研究和实际事物都有意义具有一些典型特征，便于验证有关方法便于比较不同方法的性能优略产生最先研究者提出后来者加以改进,by 谢广明 ， 20052006学年度第一学期,8,函数优化Benchmark问题,典型特点单极小非凸非线性
3、多极小高维强振荡噪声不可微平台,by 谢广明 ， 20052006学年度第一学期,9,by 谢广明 ， 20052006学年度第一学期,10,by 谢广明 ， 20052006学年度第一学期,11,by 谢广明 ， 20052006学年度第一学期,12,by 谢广明 ， 20052006学年度第一学期,13,组合问题旅行商问题(TSP)加工调度问题背包问题装箱问题着色问题聚类问题实际问题生产线、交通、网络路由、VLSI等,组合优化Benchmark问题,by 谢广明 ， 20052006学年度第一学期,14,TSP(Traveling Salesman Problem),by 谢广明 ， 20
4、052006学年度第一学期,15,1.3 优化算法及其分类,所谓优化算法, 其实就是一种搜索过程或规则, 它基于某种原理和机制, 通过一定的途径或规则来得到满足用户要求的问题的解.就优化机制与行为而分, 常用的优化算法主要可分为: 经典算法, 构造型算法, 改进型算法, 基于系统动态演化的算法, 混合型算法等.从其他角度分类, 如确定性算法和不确定性算法, 局部优化算法和全局优化算法等.,by 谢广明 ， 20052006学年度第一学期,16,经典算法,如线性规划、动态规划、整数规划和分枝定界等。其算法计算复杂性大, 只适于求解小规模问题, 在工程中往往不实用。,by 谢广明 ， 200520
5、06学年度第一学期,17,构造型算法,用构造的方法快速建立问题的解, 通常解的质量差, 难以满足工程需要.调度中的典型构造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、Baker的基于枚举树的分区法和NEH法等.,by 谢广明 ， 20052006学年度第一学期,18,改进型算法,从任一解出发, 对其邻域的不断搜索和当前解的替换来实现优化.通常可分为局部搜索法和指导性搜索法.局部搜索法. 以局部优化策略在当前解的邻域中贪婪搜索, 如只接受优于当前解的状态作为下一当前解的爬山法, 接受当前解邻域中的最好解作为下一当前解的最陡下降法等.指导
6、性搜索法. 利用一些指导规则来指导整个解空间中优良解的探索, 如SA、GA、EP、ES和TS等.,by 谢广明 ， 20052006学年度第一学期,19,基于动态演化的方法,将优化过程转化为系统动态的演化过程, 基于系统动态的演化来实现优化, 如神经网络、混沌搜索、蚁群搜索等.,by 谢广明 ， 20052006学年度第一学期,20,混合算法,上述各算法从结构或操作上相混合而产生的各类算法。如GASA,by 谢广明 ， 20052006学年度第一学期,21,一些值得重视和发展的优化技术与算法,量子优化蚁群系统基于生命行为的优化技术：人工选择、迁徙、免疫混合算法计算智能的研究,by 谢广明 ，
7、20052006学年度第一学期,22,1.4 邻域函数和局部搜索,邻域函数是优化中的一个重要概念, 其作用就是指导如何由一个(组)解来产生一个(组)新的解, 其设计往往依赖于问题的特性和解的表达方式(编码).,by 谢广明 ， 20052006学年度第一学期,23,组合优化问题,传统距离问题不在适用，必须重新定义。根据具体问题类型不同采用有针对性的方法同时所谓局部极小、全局极小也要重新定义,by 谢广明 ， 20052006学年度第一学期,24,by 谢广明 ， 20052006学年度第一学期,25,by 谢广明 ， 20052006学年度第一学期,26,by 谢广明 ， 20052006学年
8、度第一学期,27,by 谢广明 ， 20052006学年度第一学期,28,1.5 计算复杂性,算法对时间和空间的需要量称为算法的时间复杂性和空间复杂性. 问题的时间复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂性, 问题的空间复杂性也可类似定义. 按照计算复杂性理论研究问题求解的难易程度, 可把问题分为P类、NP类和NP完全类.,by 谢广明 ， 20052006学年度第一学期,29,by 谢广明 ， 20052006学年度第一学期,30,by 谢广明 ， 20052006学年度第一学期,31,by 谢广明 ， 20052006学年度第一学期,32,by 谢广明 ， 20052006学年度第一学期,33,by 谢广明 ， 20052006学年度第一学期,34,
