从人工蚂蚁系统浅谈复杂的研究.pptVIP

从人工蚂蚁系统浅谈复杂性的研究 中国科技大学计算机系: 张巍 2001 年 11 月 20 日 weizhang@mail.ustc.edu.cn 主要的目的 汇报我对 Complexity，Ant System 学习的几点体会 主要的内容 复杂性 (Complexity) 研究的基本背景 多主体系统 (Multiagent System) 的简介 人工蚂蚁系统 (Ant System)求解TSP问题 一、复杂性 (Complexity) 研究的背景 1、起源：对决定论和还原论的质疑 整体往往大于部分的“简单和” 蚂蚁的低智能——蚁群的高智慧 蚂蚁的简单行为——蚁群的智能突现 2、复杂系统 多主体——规则——相互作用 二、多主体系统 (Multiagent System) 1、主体（Agent) 感知—决策—影响 自治性、交互性、协作性、可通信性、长寿性 2、自组织多主体系统的特征（蚁群） 负反馈 (Negative Feedback) 正反馈 (Positive Feedback) “滚雪球” 随机扰动的放大 多重的相互作用 3、AER模型（Agents-Environment-Rules Mode) 四、人工蚂蚁系统 (AS) 求解TSP问题 1、旅行商问题（TSP) 在全连接的赋权图中找到通过每个结点且只通过一次的最短通路。 * * 三、实际蚁群的觅食 1、主体：蚂蚁 2、规则：分工、通讯 3、相互作用： 蚂蚁==触角放电==蚂蚁 蚂蚁==气味积累==环境 2、人工蚂蚁系统（Ant System Algorithm) 四、人工蚂蚁系统 (AS) 求解TSP问题 蚂蚁：只利用局部信息 系统：找到全局的TSP通路 智能的突现（Emergence) AS算法的基本思想： AS算法的基本步骤 四、人工蚂蚁系统 (AS) 求解TSP问题——2、人工蚂蚁系统 初始：每个边==相同浓度的气味 绿蚂蚁从A开始爬， 根据气味和边长 (局部信息) 选择边，选了AB，到达 B。 在B： 看看还有哪些城没去，按照上述方法找到下一条边… … 这样进行下去，就得到一条通路。 其他的蚂蚁依次类推，都得到一条通路。 四、人工蚂蚁系统 (AS) 求解TSP问题——2、人工蚂蚁系统 一个新的旅程开始了 (又一次的迭代) 。 记录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）允许随机扰动 * * *