《蚁群算法》PPT课件

《《蚁群算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蚁群算法YuehuiChenSchoolofInform.Sci.andEng.UniversityofJinan,2009http://cilab.ujn.edu.cn2021/8/241内容一、启发式方法概述二、蚁群优化算法2021/8/242背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）2021/8/243传统运

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

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

4、）2021/8/2491.1组合优化问题2021/8/24101.1组合优化问题例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。2021/8/24111.1组合优化问题2021/8/24121.1组合优化问题例3装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。2021/8/24131.1组合优化问题2021/8/24141.2计算复杂性的概念评价

5、算法的好坏——计算时间的多少、解的偏离程度例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：2021/8/24151.2计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基

6、础，以理论的形式系统描述，是评估算法性能的基础。2021/8/24161.2计算复杂性的概念问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.2021/8/24171.2计算复杂性的概念一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是

7、费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.2021/8/24181.2计算复杂性的概念算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换)2021/8/24191.2计算复杂性的概念算法计算量的度量之例——TSP枚举法计算量的统计：2021/8/24201.2计算复杂性的概念实例的输入长度：实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加