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) 求解 TSP问题蚂蚁：只利用 局部 信息系统：找到 全局 的 TSP通路智能的 突现 （ Emergence)AS算法的基本思想：AS算法的基本步骤四、人工蚂蚁系统 (AS) 求解 TSP问题 2 、人工蚂蚁系统初始：每个边 =相同浓度的气味 绿蚂蚁从 A开始爬，根据气味和边长 (局部信息 ) 选择边，选了 AB， 到达 B。在 B：看看还有哪些城没去，按照上述方法找到下一条边 这样进行下去，就得到一条通路。其他的蚂蚁依次类推，都得到一条通路。
