现代优化计算方法课件教学内容.ppt

1.3 邻域的概念 距离空间中，邻域是以一点为中心的一个球体 目的：寻找下一个迭代点 示例 局部最优 全局最优 1 2 3 4 5 6 7 8 9 10 ＋ ＋ ＋ ＋ ＋ ＋ ＋ ＋ ＋ ＋ 传统的优化算法可能陷入局部最优点。 现代优化算法就是解决如何跳出局部最优点以达到全局最优点。 1.4 启发式算法_定义 启发式算法（heuristic algorithm） 定义1. 基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计. 定义2. 启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。 特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度. 1.4 启发式算法_优点 优点： （1）有可能比简化数学模型解的误差小； （2）对有些难题，计算时间可接受； （3）可用于某些最优化算法（如分支定界算 法）之中的估界； （4）直观易行； （5）速度较快； （6）程序简单，易修改。 1.4 启发式算法_不足 不足： （1）不能保证求得全局最优解； （2）解的精度不稳定，有时好有时坏； （3）算法设计与问题、设计者经验、技术 有关，缺乏规律性； （4）不同算法之间难以比较。 1.4 启发式算法_分类 (1) 一步算法：不在两个可行解之间比较 (2) 改进算法（迭代算法）：从一个可行解到另一个可行解变换 (3) 数学规划算法：主要用连续优化的方法 如解空间松弛法 1.4 启发式算法_分类 （4）现代优化算法： 80年代初兴起 禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence） （5）其他算法： 多种启发式算法的集成. 理论上难以区分目标值的优劣 1.4启发式算法_性能分析 评价指标： 算法的复杂性（计算效率） 解的偏离程度（计算效果） 算法的鲁棒性 评价手段： 最坏情形分析 概率分析 计算模拟分析 1.4启发式算法_性能分析 全局优化启发式算法的特点 在一些限定条件下，理论上可以收敛到全局最优。 但付出的计算时间可能无法接受。 在限定计算时间后，无法保证收敛到全局最优。 随着计算时间的增加，算法的解越来越好。 策略1：集中 集中搜索，求得局部最优解 策略2：扩散 扩大搜索区域，达到全局最优解 第二章 禁忌搜索算法（ Tabu Search） Glover 1986 禁忌：禁止重复前面的工作 禁忌表：记录已经到达过的局部最优解或达到局部最优的过程。 2.1 局部搜索 是 停止 否 是 否 例2.1.1 五个城市的对称TSP 全邻域搜索 随机搜索 陷入局部最优解！ 例2.1.2四城市非对称TSP 特 点 依赖于初始点的选取和邻域的结构 选取足够多的初始点 2.2 禁忌搜索 基本思想： 标记已得到的局部最优解或求解的过程，并在进一步的迭代中避开这些局部最优解或过程。 禁忌搜索算法 停止准则 结果 是 否 禁忌对象：被禁的变化元素 禁忌长度：被禁对象不允许选取的迭代次数 候选集合的构成：邻域中的邻居组成 评价函数的构造：赋予候选集合中每个元素一个实数值，通常是目标函数。 特赦规则 记忆频率信息 终止规则 禁忌表 技术问题 禁忌对象如何选取？ 禁忌长度短会造成循环，长会造成算法的记忆存储量增加 被禁对象能否解禁？ 候选集合的确定 评价函数的构造 终止规则 。。。。。。 例2.2.1 四城市非对称TSP的距离矩阵 例2.2.2 禁忌长度从3变到2 禁忌对象：被禁的变化元素 解的简单变化 向量分量的变化 目标值变化 解的简单变化 从一个解变化到另一个解 例2.3.4(例2.1.1) 五个城市的对称TSP 现代优化计算方法 教 材 邢文训，谢金星－－《现代优化计算方法》（第二版） 清华大学出版社 主要内容 概论（49页） 禁忌搜索算法（26页）（tabu search） 模拟退火算法（35页） （simulated annealing） 遗传算法（35页） （genetic algorithms） 蚁群算法（23页） （群体（群集）智能，Swarm Intelligence） 人工神经网络（38页） （artificial neural networks