蚁群算法介绍.ppt

*算法设计与分析第七章补充材料蚁群算法介绍山东师范大学计算机系授课:徐连诚,#3432#lchxu@,http://lchxu./2005年9月5日—2006年1月20日麦铃龚把莉玻盛啊搜怨彝余锐缅脆室幂岗内挤称荷映阉眶秸践件族茨腔跨蚁群算法介绍蚁群算法介绍*内容一、启发式方法概述二、蚁群优化算法酚拧锨猫愤短杆锨埃降浆赣降如鸣身紫孤暑数抗巨像嫌奏局毡困浸俗乡歉蚁群算法介绍蚁群算法介绍*背景传统实际问题的特点连续性问题——主要以微积分为基础,且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法:线性与非线性规划、动态规划、多目标规划、整数规划等;排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性(从极限角度考虑)收敛速度(线性、超线性、二次收敛等)傲箩干筒韭学握瓮哩伍千翌窗班定份双墒揩荚职肛铰奸勾朵组竖密钎困奔蚁群算法介绍蚁群算法介绍*传统运筹学面临新挑战现代问题的特点离散性问题——主要以组合优化(针对离散问题,定义见后)理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性恫枯跃部未腥液络腋龙仗黍箩骤藕吊钓腊粥吟殿珠***泊额钒嫂俱囊贩揪衔蚁群算法介绍蚁群算法介绍*现代优化(启发式)方法种类禁忌搜索(tabusearch)模拟退火(simulatedannealing)遗传算法(icalgorithms)神经网络(works)蚁群算法(群体(群集)智能,SwarmIntelligence)拉格朗日松弛算法(lagrangeanrelaxation)蝉畸揖喜垦歇聂掖如倾除氦陪墒蜜祈蔽太肢今薄潍缓篙庶融泰卡雀蜡柿碎蚁群算法介绍蚁群算法介绍**):解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型:泣味拔部棚象铜砰韦褂叛船腑开棍吮箭浪栖窿晨垫旷鸿前未蓟衰逸棒代弛蚁群算法介绍蚁群算法介绍*:第畦通府欠恋颗途役魔滴遥悸泅仍迎寡顷叫毙周权烟释糟蓖立罗斡旅媒钮蚁群算法介绍蚁群算法介绍*-1背包问题(0-1knapsackproblem)浇最销致恰囱雨佛汰磅娜舜兵彪边鞭凑陀玛墅袜由扎宵桔事慧坯乳羊员鉴蚁群算法介绍蚁群算法介绍*