算法设计与分析-蚁群算法介绍

《算法设计与分析-蚁群算法介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析第七章补充材料蚁群算法介绍山东师范大学计算机系授课：徐连诚，#3432#lchxu@163.com，http://lchxu.welkind.net/2005年9月5日—2006年1月20日1内容一、启发式方法概述二、蚁群优化算法2背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）3传统运筹学

2、面临新挑战现代问题的特点离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性4现代优化(启发式)方法种类禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚁群算法（群体（群集）智能，SwarmIntelligence

3、）拉格朗日松弛算法（lagrangeanrelaxation）51现代优化计算方法概述1.1组合优化问题1.2计算复杂性的概念1.3启发式算法61.1组合优化问题1/8组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：71.1组合优化问题2/8组合优化问题的三参数表示：81.1组合优化问题3/8例10-1背包问题（0-1knapsackproblem）91.1

4、组合优化问题4/8101.1组合优化问题5/8例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。111.1组合优化问题6/8121.1组合优化问题7/8例3装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。131.1组合优化问题8/8141.2计算复杂性的概念1/11评价算法的好坏——计算时间的多少、解的偏离程度例非对称距离TSP问题

5、的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：151.2计算复杂性的概念2/11城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。161.2

6、计算复杂性的概念3/11问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.171.2计算复杂性的概念4/11一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f

7、*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.181.2计算复杂性的概念5/11算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换)191.2计算复杂性的概念6/11算法计算量的度量之例——TSP枚举法计算量的统计：201.2计算复杂性的概念7/11实例的输入长度：实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.211.2计算复杂性的概念8/11221.2计算复杂性的

8、概念9/11定义多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A