现代优化计算方法

《现代优化计算方法》由会员分享，可在线阅读，更多相关《现代优化计算方法（78页珍藏版）》请在金锄头文库上搜索。

1、现代优化计算方法,授课：张 彩 霞 #四教204# 3690 caixiazhang,教 材,邢文训，谢金星现代优化计算方法（第二版） 清华大学出版社,主要内容,概论（49页） 禁忌搜索算法（26页）（tabu search） 模拟退火算法（35页） （simulated annealing） 遗传算法（35页） （genetic algorithms） 蚁群算法（23页） （群体（群集）智能，Swarm Intelligence） 人工神经网络（38页） （artificial neural networks） 拉格朗日松弛算法（35页） （lagrangean relaxation）,第一

2、章 概论,组合最优化问题 计算复杂性 邻域 启发式算法,背 景,传统实际问题的特点 连续性问题主要以微积分为基础，且问题规模较小 传统的优化方法 追求准确精确解 理论的完美结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等）,传统运筹学面临新挑战,现代问题的特点 离散性问题主要以组合优化（针对离散问题，定义见后）理论为基础 不确定性问题随机性数学模型 半结构或非结构化的问题计算机模拟、决策支持系统 大规模问题并行计算、大型分解理论、近似理论 现代优化方法 追

3、求满意近似解 实用性强解决实际问题 现代优化算法的评价方法 算法复杂性,1.1 组合优化问题,组合优化（combinatorial optimization）:解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。 数学模型：,1.1 组合优化问题,组合优化问题的三参数表示：,1.1 组合优化问题,例1 0-1背包问题（0-1 knapsack problem）,1.1 组合优化问题,1.1 组合优化问题,例2 旅行商问题（TSP,traveling salesman problem

4、） 管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。 问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。,1.1 组合优化问题,1.1 组合优化问题,例4 装箱问题（bin packing） 尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1 的物品，物品集合为： 。,1.1 组合优化问题,每个物品都被装箱,装在每个箱子的物品总尺寸不能超过箱子的容量,例3 整数线性规划(integer linear programming),特 点,决策变量的定义域和可行解集合都是有限的 在问题的规模较小时，用枚举法容易得最优解 组合优化问题常用整数规划模型表示 由

5、于组合最优化问题的复杂性，很多快速的算法只给出可行解,1.2 计算复杂性的概念,评价算法的好坏计算时间的多少、解的偏离程度 以二进制计算机中的存储和计算为基础 理论产生于20世纪70年代 例 非对称距离TSP问题的算法实现：所有路径枚举。 计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举 设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：,1.2 计算复杂性的概念,随城市增多，计算时间增加很快。到31个城市时，要计算325年。,描述算法的好坏计算复杂性讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础

6、。,1.2 计算复杂性的概念,问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述： （1）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。 实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据.,1.2 计算复杂性的概念,数的规模（编码长度） ：,一个数在计算机中存储时占据的位数,实例的规模：,一个实例所有参数数值的规模之和,算法的计算量：,算法求解中的加、减、乘、除、比较、读、写等基本运算的总次数,数的规模,正整数x的二进制位数是:(整数到二进制的转换),实例,课 堂 练 习,1.2

7、 计算复杂性的概念,算法计算量的度量之例TSP枚举法,计算量的统计：,1.2 计算复杂性的概念,实例的输入长度：,实例的输入长度是n的多项式函数 枚举法的基本计算量是n的阶乘函数， 随n的增加，比指数函数增加得还快.,1.2 计算复杂性的概念,算法复杂性分析：由最坏实例的输入规模与算法的计算量之间的关系来衡量算法的好坏。,问题复杂性分析,1.2 计算复杂性的概念,定义 多项式算法 给定问题P，算法A，对一个实例I，存在多项式 函数g(x)，使（XX ）成立，称算法A对实例I是 多项式算法； 若存在多项式函数g(x)，使（XX）对问题P的任 意实例I都成立，称算法A为解决该问题P的多项 式算法.

8、 当g(x)为指数函数时，称A为P的指数时间算法。,随着变量的增加，多项式函数增长的速度比指数函数增长的速度慢得多,1.2 计算复杂性的概念,利用复杂性分析对组合优化问题归类。 定义多项式问题 给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题). 所有多项式问题的集合记为P. 例：线性规划是否为多项式问题？,是,通常将存在多项式时间算法的问题看作是易解问题（Easy Problem），将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。,为什么把多项式时间复杂性作为易解问题和难解问题的分界线？,多项式函数与指数函数的增长率

9、有本质的差别,1.3 邻域的概念,距离空间中，邻域是以一点为中心的一个球体 目的：寻找下一个迭代点,示例,局部最优 全局最优,传统的优化算法可能陷入局部最优点。 现代优化算法就是解决如何跳出局部最优点以达到全局最优点。,1.4 启发式算法_定义,启发式算法（heuristic algorithm） 定义1. 基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计. 定义2. 启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。 特点（与传统优化方

10、法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.,1.4 启发式算法_优点,优点： （1）有可能比简化数学模型解的误差小； （2）对有些难题，计算时间可接受； （3）可用于某些最优化算法（如分支定界算 法）之中的估界； （4）直观易行； （5）速度较快； （6）程序简单，易修改。,1.4 启发式算法_不足,不足： （1）不能保证求得全局最优解； （2）解的精度不稳定，有时好有时坏； （3）算法设计与问题、设计者经验、技术 有关，缺乏规律性； （4）不同算法之间难以比较。,1.4 启发式算法_分类,(1) 一步算法：不在两个可行解之间比较 (2) 改进算法（迭代算法）：从一个可行

11、解到另一个可行解变换 (3) 数学规划算法：主要用连续优化的方法 如解空间松弛法,1.4 启发式算法_分类,（4）现代优化算法： 80年代初兴起 禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence） （5）其他算法： 多种启发式算法的集成.,理论上难以区分目标值的优劣,1.4启发式算法_性能分析,评价指标： 算法的复杂性（计算效率） 解的偏离程度（计算效果） 算法的鲁棒性,

12、评价手段： 最坏情形分析 概率分析 计算模拟分析,1.4启发式算法_性能分析,全局优化启发式算法的特点,在一些限定条件下，理论上可以收敛到全局最优。 但付出的计算时间可能无法接受。 在限定计算时间后，无法保证收敛到全局最优。 随着计算时间的增加，算法的解越来越好。,策略1：集中 集中搜索，求得局部最优解 策略2：扩散 扩大搜索区域，达到全局最优解,第二章 禁忌搜索算法（ Tabu Search）,Glover 1986,禁忌：禁止重复前面的工作,禁忌表：记录已经到达过的局部最优解或达到局部最优的过程。,2.1 局部搜索,停止,例2.1.1 五个城市的对称TSP,全邻域搜索 随机搜索,陷入局部最

13、优解！,例2.1.2四城市非对称TSP,特 点,依赖于初始点的选取和邻域的结构,选取足够多的初始点,2.2 禁忌搜索,基本思想： 标记已得到的局部最优解或求解的过程，并在进一步的迭代中避开这些局部最优解或过程。,禁忌搜索算法,停止准则,结果,是,否,禁忌对象：被禁的变化元素 禁忌长度：被禁对象不允许选取的迭代次数 候选集合的构成：邻域中的邻居组成 评价函数的构造：赋予候选集合中每个元素一个实数值，通常是目标函数。 特赦规则 记忆频率信息 终止规则,技术问题,禁忌对象如何选取？ 禁忌长度短会造成循环，长会造成算法的记忆存储量增加 被禁对象能否解禁？ 候选集合的确定 评价函数的构造 终止规则 。,

14、例2.2.1 四城市非对称TSP的距离矩阵,例2.2.2 禁忌长度从3变到2,禁忌对象：被禁的变化元素,解的简单变化 向量分量的变化 目标值变化,解的简单变化,从一个解变化到另一个解,例2.3.4(例2.1.1) 五个城市的对称TSP,向量分量的变化,对解向量的每个分量进行变化,例2.3.1 0-1背包问题 例2.3.2 TSP问题,例2.3.5(例2.1.1) 五个城市的对称TSP,目标值变化,等值线,例2.3.3,例2.3.6(例2.1.1) 五个城市的对称TSP,解的简单变化比解的分量变化和目标值变化的受禁忌范围要小,禁忌长度,被禁对象x不允许选取的迭代次数t,tabu(x)=t,tab

15、u(x)=t-1,tabu(x)=0,特赦规则,让一些禁忌对象重新可选：,候选集中的全部对象都被禁忌 一对象被禁，但若解禁后其当前最优值将下降,例2.3.7 五个城市的非对称TSP,基于评价值的规则 基于最小错误的规则 基于影响力的规则,选评价值最小的解禁,关注影响大的变化,候选集合的确定,由邻域中的邻居组成,从邻域中所有邻居中选择若干个目标值或评价值最佳的邻居 从邻域中的一部分邻居中选择若干个目标值或评价值最佳的邻居 随机选取,评价函数,赋予候选集合中每个元素一个实数值，以此选取下一步的替代点,目标函数,直接评价函数：含目标函数 间接评价函数：尽量反映目标函数的特性,CLPS：约束批量计划与

16、调度,记忆频率信息,记忆信息的出现频率,解集合、被禁对象、目标值集合,动态控制禁忌的长度,一个元素或一个序列重复出现，可以增加禁忌长度 一个序列的目标值变化较小时，有必要增加序列每个对象的禁忌长度。 一个最佳的目标值出现的频率很高，可认为是最优值而终止,终止规则,确定步数终止：迭代次数超过一定的值 频率控制原则：解的频率超过一定的值 目标控制原则：在一定步长内，最优值不变 目标值偏离程度原则：与下界差小于一定的值,应用案例：图节点着色问题,对于图着色的研究是从m可着色性问题的 著名特例四色问题开始的。 这个问题要求证明平面或球面上的任何地图的 所有区域都至多可用四种颜色来着色， 并使任何两个有一段公共边界的相邻区域 没有相同的颜色。,例2.4.1,A,E,D,C,B,用禁忌搜索算法求得无向图的一个最小划分,定义函数：,目标函数： 解的形式 邻域 禁忌对象 特赦规则 终止规则,禁忌搜索算法,停止准则,结