智智 能能 优优 化化 计计 算算1课程名称课程名称 智能计算智能计算教师联系方式教师联系方式 办公地点：实验楼办公地点：实验楼2408，Tel：13871511971 E-mail：zhao_tongzhou126.com上课时间地点上课时间地点 周四周四 34节，节，2408智能计算智能计算2课程定位课程定位 解决的问题：优化问题解决的问题：优化问题 解决的方法：智能方法解决的方法：智能方法 数学工具数学工具 实用方法实用方法考核方式考核方式 笔试或报告笔试或报告 智能计算智能计算3内容安排内容安排 最优化问题概述最优化问题概述 禁忌搜索算法禁忌搜索算法(Tabu search) 模拟退火算法模拟退火算法(Simulated Annealing) 遗传算法遗传算法(Genetic Algorithm) 神经网络优化算法神经网络优化算法(Neural Network) 群智能算法，包括蚁群算法群智能算法，包括蚁群算法(Ant Colony Optimization)、粒子群算法、粒子群算法(Particle Swarm Optimization) 广义领域搜索算法及其统一结构广义领域搜索算法及其统一结构 智能计算智能计算4参考书参考书 1 邢文训邢文训, 谢金星谢金星. 现代优化计算方法现代优化计算方法. 北京北京: 清华大学出版社清华大学出版社, 2005.2 王凌王凌. 智能优化算法及其应用智能优化算法及其应用. 北京北京: 清华大学出版社清华大学出版社, 2001.3 阎平凡阎平凡, 张长水张长水. 人工神经网络与模人工神经网络与模拟进化计算拟进化计算. 北京北京: 清华大学出版社清华大学出版社, 2005.智能计算智能计算5参考书参考书 4王小平王小平, 曹立明曹立明. 遗传算法遗传算法理论、理论、应用与软件实现应用与软件实现. 西安西安: 西安交通大学出西安交通大学出版社版社, 2002.5黄席樾等黄席樾等. 现代智能算法理论及应用现代智能算法理论及应用. 北京：科学出版社北京：科学出版社, 2005.6高尚高尚, 杨静宇杨静宇. 群智能算法及其应用群智能算法及其应用. 北京北京: 中国水利水电出版社中国水利水电出版社, 2006.智能计算智能计算6第一章第一章 绪论绪论 智能计算智能计算71.1 1.1 引言引言引言引言 1.1.1 1.1.1 优化问题优化问题优化问题优化问题 1.1.2 1.1.2 传统优化方法传统优化方法传统优化方法传统优化方法 1.1.3 1.1.3 现代优化方法现代优化方法现代优化方法现代优化方法 1.2 1.2 最优化问题及其分类最优化问题及其分类最优化问题及其分类最优化问题及其分类 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 1.3 1.3 启发式算法启发式算法启发式算法启发式算法 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 1.3.2 1.3.2 启发式算法的分类启发式算法的分类启发式算法的分类启发式算法的分类 1.3.3 1.3.3 启发式算法的性能分析启发式算法的性能分析启发式算法的性能分析启发式算法的性能分析 1.4 1.4 计算复杂性与计算复杂性与计算复杂性与计算复杂性与NPNP完全问题完全问题完全问题完全问题 1.4.1 1.4.1 计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 81.1 引言引言 智能计算智能计算优化技术？优化技术？ 以数学为基础，解决各种工程问题优化解以数学为基础，解决各种工程问题优化解优化技术的用途优化技术的用途 系统控制系统控制 人工智能人工智能 模式识别模式识别 生产调度生产调度 1.1.1 1.1.1 优化问题优化问题优化问题优化问题 91.1 引言引言 智能计算智能计算最优化问题的描述最优化问题的描述 最优化问题的数学模型的一般描述：最优化问题的数学模型的一般描述： 1.1.1 1.1.1 优化问题优化问题优化问题优化问题 即：讨论求函数即：讨论求函数f(x)的最小值问题，的最小值问题，即确定即确定xD,使使F(x*)=minF(x),g(x)=g(x)是是F(x)的梯度，的梯度，H(x)是是F(x)的的Hesse矩阵。矩阵。 101.1 引言引言 智能计算智能计算待解决的问题待解决的问题 连续性问题，以微积分为基础，规模较小连续性问题，以微积分为基础，规模较小传统的优化方法传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。库存论、对策论、决策论等。 传统的评价方法传统的评价方法 算法收敛性、收敛速度算法收敛性、收敛速度 1.1.2 1.1.2 传统优化方法传统优化方法传统优化方法传统优化方法 111.1 引言引言 智能计算智能计算待解决的问题待解决的问题 离散性、不确定性、大规模离散性、不确定性、大规模现代的优化方法现代的优化方法 启发式算法（启发式算法（heuristic algorithm） 追求满意（近似解）追求满意（近似解） 实用性强（解决实际工程问题）实用性强（解决实际工程问题） 现代的评价方法现代的评价方法 算法复杂性算法复杂性 1.1.3 1.1.3 现代优化方法现代优化方法现代优化方法现代优化方法 121.2 最优化问题及其分类最优化问题及其分类（函数优化和组合优化）（函数优化和组合优化） 智能计算智能计算数学表述数学表述难点难点 高维高维 多峰值多峰值 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 131.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数（测试函数（Benchmark问题）问题） （1）Sphere Model 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 141.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （2）Schwefels Problem 2.22 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 151.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （3）Schwefels Problem 1.2 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 161.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （4）Schwefels Problem 2.21 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 171.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （5）Generalized Rosenbrocks Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 181.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （6）Step Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 191.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （6）Step Function 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 201.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （7）Quartic Function i.e. Niose 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 211.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （8）Generalized Schwefels Problem 2.26 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 221.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （8）Generalized Schwefels Problem 2.26 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 231.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （9）Generalized Rastrigins Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 241.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （10）Ackleys Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 251.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （10）Ackleys Function 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 261.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （11）Generalized Griewank Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 271.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （11）Generalized Griewank Function 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 281.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （12）Generalized Penalized Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 291.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 301.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （13）Generalized Penalized Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 311.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （14）Shekels Foxholes Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 321.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 331.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （15）Kowaliks Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 341.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 351.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （16）Six-Hump Camel-Back Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 361.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （17）Branin Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 371.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （18）Goldstein-Price Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 381.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （19）Hartmans Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 391.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 401.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （20）Hartmans Function 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 411.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 421.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （21）Shekels Family m分别取分别取5，7和和10，其最优状态和最优值，其最优状态和最优值为为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 431.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 其中，其中， 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 iaijcij=1234144440.1211110.2388880.2466660.4537370.4629290.6755330.3881810.7962620.51073.673.60.5441.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （22）J. D. Schaffer 其最优状态和最优值为其最优状态和最优值为 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 451.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算测试函数测试函数 （22）J. D. Schaffer 此函数在距全局最优点大约此函数在距全局最优点大约3.14范围内存在无范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。穷多个局部极小将其包围，并且函数强烈振荡。 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 461.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算有约束的函数优化有约束的函数优化 常用受约束测试函数；常用受约束测试函数； 影响因素：影响因素： （1）曲面拓扑性质，线性或凸函数比无规律的函）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解；数更容易求解； （2）可行区域的疏密程度，通常以可行区域占整）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；个搜索空间的比值来度量； 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 471.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算有约束的函数优化有约束的函数优化 常用受约束测试函数；常用受约束测试函数； 影响因素：影响因素： （3）整体最优解与可行区域最优解之比；）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。越多则最优解离可行区域的边界越近。 1.2.1 1.2.1 函数优化问题函数优化问题函数优化问题函数优化问题 481.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算数学表述数学表述所属范畴所属范畴 涉及离散事件的最优编排、分类、次序筛选等问题，涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。是运筹学的一个重要分支。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 491.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题旅行商问题（旅行商问题（Traveling salesman problem, TSP） 给定给定n个城市和两两个城市和两两 城市之间的距离，要城市之间的距离，要 求确定一条经过各城求确定一条经过各城 市当且仅当一次的最市当且仅当一次的最 短路线。短路线。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 123412181032501.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题旅行商问题（旅行商问题（Traveling salesman problem, TSP） 计算复杂度：指数灾难计算复杂度：指数灾难 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year511.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题加工调度问题（加工调度问题（Scheduling problem,如如Flow-shop, Job-shop） Job-shop：n个工件在个工件在m台机器上加工，台机器上加工，Oij：第：第i个工件在第个工件在第j台机器上的操作，台机器上的操作， Tij：相应的操作时：相应的操作时间，已知。事先给定各工件在各机器上的加工次序间，已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容（技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指的各机器上所有工件的加工顺序，使得加工性能指标达到最优。标达到最优。 若各工件技术约束条件相同，转化为若各工件技术约束条件相同，转化为Flow-shop。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 521.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题加工调度问题（加工调度问题（Scheduling problem,如如Flow-shop, Job-shop） 计算复杂性：可能的排列方式有（计算复杂性：可能的排列方式有（n！）！）m 多目标优化多目标优化 动态性动态性 状态相依状态相依 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 531.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题01背包问题（背包问题（Knapsack problem） 对于对于n个体积为个体积为ai、价值分别为、价值分别为ci的物品，如何将它的物品，如何将它们装入总体积为们装入总体积为b的背包中，使得所选物品的总价的背包中，使得所选物品的总价值最大。值最大。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 背包问题的贪婪算法背包问题的贪婪算法541.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题装箱问题（装箱问题（Bin packing problem） 有有n个尺寸不超过个尺寸不超过1的物品，有数个尺寸为的物品，有数个尺寸为1的箱子，的箱子，如何将这些物品装入箱子，使得所需箱子的个数最如何将这些物品装入箱子，使得所需箱子的个数最少。少。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 551.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题图着色问题（图着色问题（Graph coloring problem） 对于对于n个顶点的无环图个顶点的无环图G，要求对其各个顶点进行，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。且所用颜色种类最少。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 C1：第一：第一种颜色种颜色C2：第二：第二种颜色种颜色C3：第三：第三种颜色种颜色C1C1C2C3C2ABDCE561.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算典型问题典型问题聚类问题（聚类问题（Clustering problem） m维空间上的维空间上的n个模式个模式Xi|i=1,2,n，要求聚成，要求聚成k类，类，使得各类本身内的点最相近，如要求使得各类本身内的点最相近，如要求 其中其中Rp为第为第p类的中心，即类的中心，即 其中，其中，p=1,2,k，np为第为第p类中的点数。类中的点数。 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 571.2 最优化问题及其分类最优化问题及其分类 智能计算智能计算Benchmark问题问题 n城市城市TSP问题（问题（n=30，50，75） Hopfield-10城市城市TSP问题问题 Grotschel-442城市城市TSP问题问题 Car n Flow-shop问题（问题（n=1,2,8） Rec n Flow-shop问题（问题（n=1,3,5,39,41） FT n or MT n Job-shop问题（问题（n=6,10,20） LA n Job-shop问题问题（n=1,6,11,16,21,26,31,36） 1.2.2 1.2.2 组合优化问题组合优化问题组合优化问题组合优化问题 30城市城市TSP问题（问题（d*=423.741 by D B Fogel） 41 94; 37 84; 54 67; 25 62; 7 64; 2 99; 68 58; 71 44; 54 62; 83 69; 64 60; 18 54; 22 60; 83 46; 91 38; 25 38; 24 42; 58 69; 71 71; 74 78; 87 76; 18 40; 13 40; 82 7; 62 32; 58 35; 45 21; 41 26; 44 35; 4 50581.3 启发式算法启发式算法 智能计算智能计算最优算法最优算法 一个问题的最优算法求得该问题每个实例的一个问题的最优算法求得该问题每个实例的最优最优解解；启发式算法启发式算法 一个基于直观或经验构造的算法，在可接受的花费一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个每一个实例的一个可行解可行解，该可行解与最优解的偏，该可行解与最优解的偏离程度不一定事先可以预计。离程度不一定事先可以预计。 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 591.3 启发式算法启发式算法 智能计算智能计算启发式算法的特点启发式算法的特点 是一种技术；是一种技术； 不能保证所得解的最优性；不能保证所得解的最优性；启发式算法的发展历史启发式算法的发展历史 20世纪世纪40年代年代起步起步 20世纪世纪6070年代年代被鄙视被鄙视 20世纪世纪70年代年代观点转变观点转变 20世纪世纪80年代至今年代至今研究热潮研究热潮 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 601.3 启发式算法启发式算法 智能计算智能计算例子例子背包问题的贪婪算法（背包问题的贪婪算法（Greedy algorithm） 贪婪算法：采用逐步构造最优解的方法。贪婪算法：采用逐步构造最优解的方法。 在每个阶段，都作出一个看上去最优的决策在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。）。 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 611.3 启发式算法启发式算法 智能计算智能计算例子例子背包问题背包问题的贪婪算法（的贪婪算法（Greedy algorithm）STEP 1 STEP 2 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 621.3 启发式算法启发式算法 智能计算智能计算启发式算法的优点启发式算法的优点 1. 模型误差、数据不精确性、参数估计误差等可能模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；造成最优算法的解比启发式算法的解更差； 2. 复杂问题无法求得最优算法或最优算法太复杂；复杂问题无法求得最优算法或最优算法太复杂； 3. 简单易行，直观，程序简单。简单易行，直观，程序简单。 启发式算法的缺点启发式算法的缺点 1. 不能保证最优；不能保证最优； 2. 不稳定；不稳定； 3. 依赖于实际问题、设计者经验。依赖于实际问题、设计者经验。 1.3.1 1.3.1 启发式算法的定义启发式算法的定义启发式算法的定义启发式算法的定义 631.3 启发式算法启发式算法 智能计算智能计算简单直观的算法简单直观的算法 一步算法一步算法：不在两个可行解之间比较，在未终止的：不在两个可行解之间比较，在未终止的迭代过程中，得到的中间解有可能不是可行解；迭代过程中，得到的中间解有可能不是可行解； 例：背包问题的贪婪算法例：背包问题的贪婪算法 改进算法改进算法：迭代过程是从一个可行解到另一个可行：迭代过程是从一个可行解到另一个可行解变换，通过两个解的比较而选择好的解，直到满解变换，通过两个解的比较而选择好的解，直到满足一定的要求为止；足一定的要求为止； 例：例：TSP问题的问题的2opt方法方法 1.3.2 1.3.2 启发式算法的分类启发式算法的分类启发式算法的分类启发式算法的分类 P1P6P2P5P3P422031222244343641.3 启发式算法启发式算法 智能计算智能计算数学规划算法数学规划算法 用连续优化（如线性规划）的方法求解组合优化问用连续优化（如线性规划）的方法求解组合优化问题（如整数线性规划模型），其中包括一些启发式题（如整数线性规划模型），其中包括一些启发式规则。规则。 基于数学规划的理论。基于数学规划的理论。 1.3.2 1.3.2 启发式算法的分类启发式算法的分类启发式算法的分类启发式算法的分类 651.3 启发式算法启发式算法 智能计算智能计算现代优化算法现代优化算法 禁忌搜索算法禁忌搜索算法 模拟退火算法模拟退火算法 遗传算法遗传算法 人工神经网络人工神经网络 蚁群算法蚁群算法 粒子群算法粒子群算法 混合算法混合算法 1.3.2 1.3.2 启发式算法的分类启发式算法的分类启发式算法的分类启发式算法的分类 特点：特点：基于客观世界中的一些自基于客观世界中的一些自然现象；然现象；建立在计算机迭代计算的建立在计算机迭代计算的基础上；基础上；具有普适性，可解决实际具有普适性，可解决实际应用问题。应用问题。661.3 启发式算法启发式算法 智能计算智能计算评价算法优劣的指标评价算法优劣的指标 算法的复杂性（计算效率）算法的复杂性（计算效率） 解的偏离程度（计算效果）解的偏离程度（计算效果） 算法的稳健性（不同实例、不同时间、不同起点的算法的稳健性（不同实例、不同时间、不同起点的差异）差异）评价算法优劣的手段评价算法优劣的手段 最坏情况分析（纯理论）最坏情况分析（纯理论） 概率分析（理论分析）概率分析（理论分析） 计算模拟分析（统计特性）计算模拟分析（统计特性） 1.3.3 1.3.3 启发式算法的性能分析启发式算法的性能分析启发式算法的性能分析启发式算法的性能分析 671.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算时间复杂性和空间复杂性概念时间复杂性和空间复杂性概念 算法算法的的时间时间复杂性复杂性：算法对时间的需要量（加、减、：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）；乘、除、比较、读、写等操作的总次数）； 算法算法的的空间空间复杂性复杂性：算法对空间的需要量（存储空：算法对空间的需要量（存储空间的大小，二进制位数）；间的大小，二进制位数）； 问题问题的的时间时间复杂性复杂性：所有算法中时间复杂性最小的：所有算法中时间复杂性最小的算法时间复杂性；算法时间复杂性； 问题问题的的空间空间复杂性复杂性：所有算法中空间复杂性最小的：所有算法中空间复杂性最小的算法空间复杂性；算法空间复杂性； 1.4.1 1.4.1 计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念 681.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算复杂性复杂性问题问题分类分类 P类、类、NP类、类、NP完全类完全类复杂性表示方法复杂性表示方法 复杂性表示为问题规模复杂性表示为问题规模n（如（如TSP的的n）的函数，）的函数， 时间复杂性时间复杂性T(n)，关键操作的次数；，关键操作的次数； 空间复杂性空间复杂性S(n)，占用的存储单元数量；，占用的存储单元数量； 1.4.1 1.4.1 计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念 691.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算复杂性表示方法复杂性表示方法 若算法若算法A的时间复杂性为的时间复杂性为TA(n)=O(p(n)，O(p(n)为复杂性函数为复杂性函数p(n)主要项的阶，且主要项的阶，且p(n)为为n的多项的多项式函数，则称式函数，则称算法算法A为多项式算法为多项式算法。 当不存在多项式函数当不存在多项式函数p(n)时，称相应的算法为非多时，称相应的算法为非多项式时间算法或指数时间算法；项式时间算法或指数时间算法； 随着变量的增加，多项式函数增长的速度比指数函随着变量的增加，多项式函数增长的速度比指数函数和非多项式函数增长的速度要慢得多。数和非多项式函数增长的速度要慢得多。 1.4.1 1.4.1 计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念计算复杂性的基本概念 701.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算P类问题（类问题（ deterministic polynomial ） 具有多项式时间求解算法的问题类具有多项式时间求解算法的问题类 迄今为止，许多组合优化问题都没有找到求最优解迄今为止，许多组合优化问题都没有找到求最优解的多项式时间算法。的多项式时间算法。NP类问题类问题(Nondeterministic polynomial) 定义定义1 实例实例是问题的特殊表现，所谓实例就是确定是问题的特殊表现，所谓实例就是确定了描述问题特性的所有参数的问题，其中参数值称了描述问题特性的所有参数的问题，其中参数值称为为数据数据，这些数据占有计算机的空间称为，这些数据占有计算机的空间称为实例的输实例的输入长度入长度。 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 711.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算NP类问题类问题(Nondeterministic polynomial) 定义定义2 若一个问题的每个实例只有若一个问题的每个实例只有“是是”或或“否否”两种回答，则称该问题为两种回答，则称该问题为判定问题判定问题。 例，例，TSP的判定问题：给定的判定问题：给定z，是否存在，是否存在n个城市的个城市的一个排列一个排列W，使得，使得f(W)z。满足。满足f(W)z的一个排列的一个排列W称为判定问题的称为判定问题的“是是”答案（可行解）。答案（可行解）。 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 721.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算NP类问题类问题(Nondeterministic polynomial) 若存在一个多项式若存在一个多项式 g(x) 和一个验证算法和一个验证算法 H ，对一，对一类判定问题类判定问题 A 的任何一个的任何一个“是是”的判定实例的判定实例 I 都都存在一个字符串存在一个字符串 S 是是 I 的的“是是”回答，满足其输回答，满足其输入长度入长度 d(S) 不超过不超过 g(d(I) （其中（其中 d(I) 为为 I 的输的输入长度），且验证算法验证入长度），且验证算法验证 S 为为 I 的的“是是”回答回答的计算时间不超过的计算时间不超过 g(d(I)，则称判定问题，则称判定问题 A 为非为非多项式确定问题，简称多项式确定问题，简称 NP问题问题。 NP类问题是比类问题是比P问题更为广泛的问题类问题更为广泛的问题类。 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 73简单地理解简单地理解 如果计算工作量在计算数据规模如果计算工作量在计算数据规模n的多项式（如的多项式（如n，n2，n3等）的范围内，则计算花费的机时是可以等）的范围内，则计算花费的机时是可以接受的，该问题称为接受的，该问题称为P问题；问题； 有些问题尚未证实是否属于有些问题尚未证实是否属于P类，又未找到有效算类，又未找到有效算法，则称法，则称NP问题。问题。1.4 1.4 计算复杂性与计算复杂性与计算复杂性与计算复杂性与NPNP完全问题完全问题完全问题完全问题 智能计算智能计算 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 741.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算NPC （NP-Complete）和）和NPhard类问题类问题 Cook在在1971年给出并证明了有一类问题具有下述年给出并证明了有一类问题具有下述性质性质（1）这类问题中任何一个问题至今未找出多）这类问题中任何一个问题至今未找出多项式时间算法；（项式时间算法；（2）如果这类问题中的一个问题）如果这类问题中的一个问题存在有多项式时间算法，那么这类问题都有多项式存在有多项式时间算法，那么这类问题都有多项式时间的算法，这类问题中的每一个问题称为时间的算法，这类问题中的每一个问题称为NP完完全问题，这个问题的集合简记全问题，这个问题的集合简记NPC。 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 75NPC（NP-Complete）和）和NPhard类问题类问题 定义：定义： 称判定问题称判定问题ANP-C，若，若ANP 且且NP中中的任何一个问题可多项式规约为问题的任何一个问题可多项式规约为问题A。称判定问。称判定问题题A为为NPhard，只要上述第二个条件成立。，只要上述第二个条件成立。 1.4 1.4 计算复杂性与计算复杂性与计算复杂性与计算复杂性与NPNP完全问题完全问题完全问题完全问题 智能计算智能计算 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 1276四类问题的关系四类问题的关系 NP-C问题具有重要的实际意义和工程背景问题具有重要的实际意义和工程背景: 第一个第一个NP完全问题（完全问题（Cook定理定理 1971） 六个六个NP完全问题（完全问题（Karp 1972) 更多的更多的NP完全问题完全问题1979年：年：300多个多个1998年：年：2000多个多个 TSP问题、背包问题、装箱问题、问题、背包问题、装箱问题、Job-shop和和Flow-shop问题、集合覆盖问题等均是问题、集合覆盖问题等均是NP-C问题。问题。1.4 计算复杂性与计算复杂性与NP完全问题完全问题 智能计算智能计算 1.4.2 P,NP,NP-C1.4.2 P,NP,NP-C和和和和NP-hardNP-hard 77第一章第一章 结束结束智能计算智能计算78