湖南大学蚁群算法.ppt

蚁群算法 Yuehui Chen School of Inform. Sci. and Eng. University of Jinan, 2009 内 容 一、启发式方法概述 二、蚁群优化算法 背 景 传统实际问题的特点 连续性问题——主要以微积分为基础，且问题规模较小 传统的优化方法 追求准确——精确解 理论的完美——结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等） 传统运筹学面临新挑战 现代问题的特点 离散性问题——主要以组合优化理论为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决 策支持系统 大规模问题——并行计算、大型分解理论、近似理论 现代优化方法 追求满意——近似解 实用性强——解决实际问题 现代优化算法的评价方法 算法复杂性 现代优化(启发式)方法种类 禁忌有哪些信誉好的足球投注网站（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚁群算法（群体智能，Swarm Intelligence） 拉格朗日松弛算法（lagrangean relaxation） 1 现代优化计算方法概述 1.1 组合优化问题 1.2 计算复杂性的概念 1.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） 管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。 问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。 1.1 组合优化问题 1.1 组合优化问题 例3 装箱问题（bin packing） 尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1 的物品，物品集合为： 。 1.1 组合优化问题 1.2 计算复杂性的概念 评价算法的好坏——计算时间的多少、解的偏离程度 例 非对称距离TSP问题的算法实现：所有路径枚举。 计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表： 1.2 计算复杂性的概念 1.2 计算复杂性的概念 问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述： （1）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。 实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）. 1.2 计算复杂性的概念 一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*) C(f),称f*为这一具体问题的最优解（或全局最优解）. 1.2 计算复杂性的概念 算法计算量的度量： 加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。 正整数x的二进制位数是:(整数到二进制的转换) 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 计算复杂性的概念 利用复杂性分析对组合优化