《从人工蚂蚁系统浅谈复杂的研究》由会员分享，可在线阅读，更多相关《从人工蚂蚁系统浅谈复杂的研究（16页珍藏版）》请在金锄头文库上搜索。
1、从人工蚂蚁系统从人工蚂蚁系统浅谈复杂性的研究浅谈复杂性的研究中国科技大学计算机系中国科技大学计算机系: : 张巍张巍2001 2001 年年 11 11 月月 20 20 日日主要的目的 汇报我对汇报我对 Complexity，Ant System 学习的几点体会学习的几点体会主要的内容复杂性 (Complexity) 研究的基本背景多主体系统 (Multiagent System) 的简介人工蚂蚁系统 (Ant System)求解TSP问题一、复杂性 (Complexity) 研究的背景1、起源：对决定论和还原论的质疑整体往往大于部分的“简单和” 蚂蚁的低智能蚁群的高智慧 蚂蚁的简单行为蚁群
2、的智能突现2、复杂系统多主体规则相互作用1、主体（Agent) 感知决策影响自治性、交互性、协作性、可通信性、长寿性2、自组织多主体系统的特征（蚁群）负反馈 (Negative Feedback)正反馈 (Positive Feedback) “滚雪球”随机扰动的放大多重的相互作用3、AER模型（Agents-Environment-Rules Mode)二、多主体系统 (Multiagent System)三、实际蚁群的觅食1、主体：蚂蚁2、规则：分工、通讯3、相互作用： 蚂蚁蚂蚁 蚂蚁环境四、人工蚂蚁系统 (AS) 求解TSP问题1、旅行商问题（TSP)在全连接的赋权图中找到通过每个结点且
3、只通过一次的最短通路。2、人工蚂蚁系统（Ant System Algorithm)四、人工蚂蚁系统 (AS) 求解TSP问题蚂蚁：只利用局部信息系统：找到全局的TSP通路 智能的突现（Emergence)AS算法的基本思想：AS算法的基本步骤四、人工蚂蚁系统 (AS) 求解TSP问题2、人工蚂蚁系统初始：每个边=相同浓度的气味 绿蚂蚁从A开始爬， 根据气味和边长 (局部信息) 选择边，选了AB，到达 B。在B： 看看还有哪些城没去，按照上述方法找到下一条边 这样进行下去，就得到一条通路。其他的蚂蚁依次类推，都得到一条通路。四、人工蚂蚁系统 (AS) 求解TSP问题2、人工蚂蚁系统一个新的旅程开
4、始了 (又一次的迭代) 。记录DABC，长3；每个蚂蚁通路的每条边释放一个单位气味；DABC最短，追加气味。假设这四条通路分别为： ABCD，长9； BDCA，长为12； CABD,长为6； DABC，长为3。迭代次数=预设置时，TSP通路找到了（全局的结果）AS算法的几点说明 四、人工蚂蚁系统 (AS) 求解TSP问题2、人工蚂蚁系统边的选择P = f (C , d) C：边的气味浓度； d：边的长度（1）C、d：局部的信息（2）允许随机扰动正负反馈：AS算法的几点说明 四、人工蚂蚁系统 (AS) 求解TSP问题2、人工蚂蚁系统C(t+1) = (1-q)C(t) + kc(t)(1-q)C(t)：负反馈项；kc(t)：正反馈项。相互作用：蚂蚁环境释放气味影响行为算法的时间复杂度： 四、人工蚂蚁系统 (AS) 求解TSP问题2、人工蚂蚁系统AS算法的几点说明 结果与启示t：迭代次数，n：城市数“不收敛性”五、几个有待探讨的问题Ant System需要迭代多少次（t）才能产生第一个好解？Ant system算法不具备并发性！复杂性、混沌、分形之间到底有怎样的联系？ 谢谢大家！谢谢大家！
