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