AAI现代优化算法说课.ppt

Advanced AI 高级人工智能 引言 优化问题 传统优化方法 现代优化方法 最优化问题及其分类 函数优化问题 组合优化问题 启发式算法 启发式算法的定义 启发式算法的分类 启发式算法的性能分析 计算复杂性与NP完全问题 计算复杂性的基本概念 P,NP,NP-C和NP-hard 优化问题 优化技术？ 以数学为基础，解决各种工程问题优化解 优化技术的用途 系统控制 人工智能 模式识别 生产调度 最优化问题的描述 最优化问题的数学模型的一般描述： 传统优化方法 待解决的问题 连续性问题，以微积分为基础，规模较小 传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性、收敛速度 牛顿 现代优化方法 待解决的问题 离散性、不确定性、大规模 现代的优化方法 启发式算法（heuristic algorithm） 追求满意（近似解） 实用性强（解决实际工程问题） 现代的评价方法 算法复杂性 函数优化问题 数学表述 难点 高维，多峰值 最优化问题及其分类 函数优化问题 Sphere Model 其最优状态和最优值为 最优化问题及其分类 测试函数 Schwefel’s Problem 其最优状态和最优值为 最优化问题及其分类 测试函数 Generalized Rosenbrock’s Function 其最优状态和最优值为 有约束的函数优化 常用受约束测试函数； 影响因素： （1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解； （2）可行区域的疏密程度，通常以可行区域占整个有哪些信誉好的足球投注网站空间的比值来度量； （3）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。 组合优化问题 启发式算法 最优算法 一个问题的最优算法求得该问题每个实例的最优解； 启发式算法 一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。 启发式算法 启发式算法的特点 是一种技术； 不能保证所得解的最优性； 启发式算法的发展历史 20世纪40年代——起步 20世纪60～70年代——被鄙视 20世纪70年代——观点转变 20世纪80年代至今——研究热潮 启发式算法 例子——背包问题的贪婪算法（Greedy algorithm） 贪婪算法：采用逐步构造最优解的方法。 在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。 启发式算法 例子——背包问题的贪婪算法（Greedy algorithm） STEP 1 STEP 2 启发式算法 启发式算法的优点 1. 模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差； 2. 复杂问题无法求得最优算法或最优算法太复杂； 3. 简单易行，直观，程序简单。 启发式算法的缺点 1. 不能保证最优； 2. 不稳定； 3. 依赖于实际问题、设计者经验。 启发式算法的分类 简单直观的算法 数学规划算法 现代优化算法 禁忌有哪些信誉好的足球投注网站算法 模拟退火算法 遗传算法 人工神经网络 蚁群算法 粒子群算法 混合算法 启发式算法的性能分析 评价算法优劣的指标 算法的复杂性（计算效率） 解的偏离程度（计算效果） 算法的稳健性（不同实例、不同时间、不同起点的差异） 评价算法优劣的手段 最坏情况分析（纯理论） 概率分析（理论分析） 计算模拟分析（统计特性） 计算复杂性与NP完全问题 时间复杂性和空间复杂性概念 算法的时间复杂性：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）； 算法的空间复杂性：算法对空间的需要量（存储空间的大小，二进制位数）； 问题的时间复