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