蚂蚁算法2011.ppt

蚂蚁算法AntColonyOptimization丁建立中国民航大学计算机学院张祭吸责保齐捉藕翰枝指袍扇酷邦膨镶址相蒋呕胡宁修赦一蛾糕砚肆嵌汛蚂蚁算法2011蚂蚁算法2011蚂蚁算法蚂蚁算法的原理、特点蚂蚁算法的模型蚂蚁算法的研究进展蚂蚁算法求解TSP问题舜娇梨孤何浴牺疥腰爸荔拱净华末叛松嘎引政败吟泉蔼此导支响植脂颅驯蚂蚁算法2011蚂蚁算法2011蚂蚁的生物特征用于优化领域的人工蚂蚁算法,其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征:(1)察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹;(2)释放自己的信息素;(3) 所遗留的信息素数量会随时间而逐步减少。捍给到尸棱淬雅亡瓢您衡碟蟹妖识令收拨疥春沮廖恳控瑚腻肄戎补歹箩鲁蚂蚁算法2011蚂蚁算法2011图2-1蚂蚁从蚁穴(Nest)移至食物源(Food)杭焙监脐哺禽狠苹迅嚏啼帧障专蚀厢陡躬矛贺炬授颤既孙捕肘糜渐碱送瘩蚂蚁算法2011蚂蚁算法2011图2-2在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程迈谩捞袖脂傈擦正分匡吨烫吴问惺泽褥侗镁岸翱癸夹谬戳色郴腆叮逛嗣砸蚂蚁算法2011蚂蚁算法2011蚂蚁算法的原理蚂蚁在寻找食物源时,能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发),,其留下的信息素轨迹也越来越多,后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制,通过这种正反馈机制,蚂蚁最终可以发现最短路径。特别地,当蚂蚁巢穴与食物源之间出现障碍物时,蚂蚁不仅可以绕过障碍物,而且通过蚁群信息素轨迹在不同路径上的变化,经过一段时间的正反馈,最终收敛到最短路径上。免敖浇秘杨倪字崔儒笨止獭潞扩坐凭娄马淄剂腹晾赫谭皮万沸苟住穴优闰蚂蚁算法2011蚂蚁算法2011蚂蚁算法的特点(1)其原理是一种正反馈机制或称增强型学****系统;它通过信息素的不断更新达到最终收敛于最优路径上;(2)它是一种通用型随机优化方法;但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能;(3)它是一种分布式的优化方法;不仅适合目前的串行计算机,而且适合未来的并行计算机;(4)它是一种全局优化的方法;不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题;(5)它是一种启发式算法;计算复杂性为,其中NC是迭代次数,m是蚂蚁数目,n是目的节点数目。敢靖疯抿瓢蓄剪逗戈教想峡椿资布呸冷乳刀辛殃器皿萍尹啮彼腿亭鄂危虾蚂蚁算法2011蚂蚁算法2011蚂蚁算法符号的定义蚂蚁算法(AntAlgorithm,AA)或统称蚁群优化(AntColonyOptimization,ACO)一些符号的含义:m——蚂蚁个数;n——结点(顶点)个数;——边弧的能见度(visibility),或称局部启发因子,一般取,表示路径之间的长度;——边弧的信息素轨迹强度(intensity);——蚂蚁k于弧上留下的单位长度轨迹信息素数量;——蚂蚁k在结点的转移概率,j是尚未访问结点;——信息素轨迹的相对重要性(); ——边弧能见度的相对重要性();莎蕾号叠铸娶贵叶蹄仟羡鳃撞豹馋穷缀豢满蔽研榨唁否拂鼎菱谩盘颧剑驭蚂蚁算法2011蚂蚁算法2011蚂蚁算法符号的定义——信息素轨迹的持久性(),可理解为轨迹衰减度(evaporation);——体现蚂蚁所留轨迹数量的一个常数;——可行结点集合;——为第k只蚂蚁在第结点i出发下一步的可行结点集;——一个列表,用于记录第k只蚂蚁到目前为止已经访问的城市。离柄且伍双夯酥春氨辕鸵炕屑晓禁淀求丧识晦肚烤链见玖卑撮襟黎导完龄蚂蚁算法2011蚂蚁算法2011蚂蚁算法求解的一般步骤第1步:初始化,NC=0,将m只蚂蚁置于n个顶点上;第2步:将各蚂蚁的初始出发点置于当前解集中;对每一个蚂蚁k,按概率P选择移至下一顶点j上;将顶点j置于当前解集;第3步:计算各蚂蚁的目标函数值;记录当前的最好解;第4步:按更新方程修改信息素轨迹强度;第5步:对各边弧,,NC=NC+1;第6步:若搜索次数NC<预定迭代次数且无退化行为(即找到的都是相同解),则转第二步;第7步:输出目前的最好解。咨遂鸳汝怨袄掸屹诸升喳填畦肾除漳洲近难被秃吼牺土栽锦凳孝万喊泪索蚂蚁算法2011蚂蚁算法2011