现代优化计算方法课件.ppt

现代优化计算方法 授课：张 彩 霞 #四教204# 3690 caixiazhang@ 教 材 邢文训，谢金星－－《现代优化计算方法》（第二版） 清华大学出版社 主要内容 概论（49页） 禁忌有哪些信誉好的足球投注网站算法（26页）（tabu search） 模拟退火算法（35页） （simulated annealing） 遗传算法（35页） （genetic algorithms） 蚁群算法（23页） （群体（群集）智能，Swarm Intelligence） 人工神经网络（38页） （artificial neural networks） 拉格朗日松弛算法（35页） （lagrangean relaxation） 第一章 概论 组合最优化问题 计算复杂性 邻域 启发式算法 背 景 传统实际问题的特点 连续性问题——主要以微积分为基础，且问题规模较小 传统的优化方法 追求准确——精确解 理论的完美——结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等） 传统运筹学面临新挑战 现代问题的特点 离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决策支持系统 大规模问题——并行计算、大型分解理论、近似理论 现代优化方法 追求满意——近似解 实用性强——解决实际问题 现代优化算法的评价方法 算法复杂性 1.1 组合优化问题 组合优化（combinatorial optimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。 数学模型： 1.1 组合优化问题 组合优化问题的三参数表示： 1.1 组合优化问题 例1 0-1背包问题（0-1 knapsack problem） 1.1 组合优化问题 1.1 组合优化问题 例2 旅行商问题（TSP,traveling salesman problem） 管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。 问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。 1.1 组合优化问题 1.1 组合优化问题 例4 装箱问题（bin packing） 尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1 的物品，物品集合为： 。 1.1 组合优化问题 例3 整数线性规划(integer linear programming) 特 点 决策变量的定义域和可行解集合都是有限的 在问题的规模较小时，用枚举法容易得最优解 组合优化问题常用整数规划模型表示 由于组合最优化问题的复杂性，很多快速的算法只给出可行解 1.2 计算复杂性的概念 评价算法的好坏——计算时间的多少、解的偏离程度 以二进制计算机中的存储和计算为基础 理论产生于20世纪70年代 例 非对称距离TSP问题的算法实现：所有路径枚举。 计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举 设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表： 1.2 计算复杂性的概念 1.2 计算复杂性的概念 问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述： （1）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。 实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据. 1.2 计算复杂性的概念 数的规模 实例 课 堂 练 习 1.2 计算复杂性的概念 算法计算量的度量之例——TSP枚举法 1.2 计算复杂性的概念 实例的输入长度： 1.2 计算复杂性的概念 1.2 计算复杂性的概念 定义 多项式算法 给定问题P，算法A，对一个实例I，存在多项式 函数g(x)，使（XX ）成立，称算法A对实例I是 多项式算法； 若存在多项式函数g(x)，使（XX）对问题P的任 意实例I都成立，称算法A为解决该问题P的多项 式算法. 当g(x)为指数函数时，称A为P的指数时间算法。 1.2 计算复杂性的概念 利用复杂性分析对组合优化问题归类。 定义多项式问题 给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P