文档介绍：算法设计与分析第七章补充材料蚁群算法介绍
山东师范大学计算机系
授课:徐连诚,#3432#
lchxu@,http://lchxu./
2005年9月5日—2006年1月20日
1
内容
一、启发式方法概述
二、蚁群优化算法
2
背景
传统实际问题的特点
连续性问题——主要以微积分为基础,且问题规模较小
传统的优化方法
追求准确——精确解
理论的完美——结果漂亮
主要方法:线性与非线性规划、动态规划、多目标规划、整数规划等;排队论、库存论、对策论、决策论等。
传统的评价方法
算法收敛性(从极限角度考虑)
收敛速度(线性、超线性、二次收敛等)
3
传统运筹学面临新挑战
现代问题的特点
离散性问题——主要以组合优化(针对离散问题,定义见后)理论为基础
不确定性问题——随机性数学模型
半结构或非结构化的问题——计算机模拟、决
策支持系统
大规模问题——并行计算、大型分解理论、近似理论
现代优化方法
追求满意——近似解
实用性强——解决实际问题
现代优化算法的评价方法
算法复杂性
4
现代优化(启发式)方法种类
禁忌搜索(tabu search)
模拟退火(simulated annealing)
遗传算法(ic algorithms)
神经网络(works)
蚁群算法(群体(群集)智能,Swarm Intelligence)
拉格朗日松弛算法(lagrangean relaxation)
5
1 现代优化计算方法概述
组合优化问题
计算复杂性的概念
启发式算法
6
组合优化问题 1/8
binatorial optimization):解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。
数学模型:
7
组合优化问题 2/8
组合优化问题的三参数表示:
8
组合优化问题 3/8
例1 0-1背包问题(0-1 knapsack problem)
9
组合优化问题 4/8
10