AAI51自然计算及群体智能.ppt

1,高级人工智能,第一章 人工智能概述 第二章 归结推理方法 第三章 不确定性推理 第四章 知识表达方法 第五章 自然计算及群体智能蚁群算法 第六章 自然计算及群体智能遗传算法,2,自然计算与群体智能,赵林亮 计算机应用技术研究所 ,3,创新：向大自然学习,生物体、自然生态系统 通过自身演化解决优化问题 模拟自然生态系统求解复杂优化问题 仿生优化算法 遗传算法 蚁群算法 微粒群算法 人工免疫算法 人工鱼群算法 混合蛙跳算法,4,遗传算法(GA) 物竞天择，设计染色体编码，交配 突变与适应函数的萃取，优化求解 神经网络(ANN) 模彷生物神经元，透过神经元的讯息传递、训练学习、回溯，优化求解 模拟退火演算法(SA) 模彷金属退火过程 基因表达式编程,5,基因 DNA,6,7,神经网络,8,9,昆虫 蚁，蜂,10,11,蚁群算法 Ant Colony Optimization (ACO),12,鸟群算法 Particle Swarm Optimization 有个 带头鸟,13,鱼群算法 Fish Swarm Optimization,14,蜂群算法 Marriage in Honey Bees Optimization (MBO),15,禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚁群算法（群体（群集）智能，Swarm Intelligence） 拉格朗日松弛算法（lagrangean） 蜜蜂算法 飞姿传信，圈轴方向：蜜向，飞行圈数：距离,16,被模拟对象的智能层次,昆虫（低智能） 蜜蜂、蚂蚁蜂群算法，蚁群算法 脊椎动物门 （较低智能） 鱼群、鸟群鱼群算法，鸟群算法，PSO 遗传算法家族（模拟 生物界 基本性质，中智能） GA, GP GEP 基因表达式编程 GEP 变异和杂交 = PSO,17,AI上这一特殊分支的发展历史,Genetic Algorithm,Tabu Search,1953,Ants System,Particle Swarm Optimization,Swarm Intelligence,1969,Expert System,1953 Simulated Annealing 模拟退火,18,Genetic Algorithm,Tabu Search,1953,Ants System,Particle Swarm Optimization,Swarm Intelligence,1969,1969 Expert System 专家系统,AI上这一特殊分支的发展历史,19,Tabu Search,1953,Ants System,Particle Swarm Optimization,Swarm Intelligence,1969,Expert System,1975 遗传算法Genetic Algorithm,AI上这一特殊分支的发展历史,20,Genetic Algorithm,Tabu Search,1953,Ants System,Particle Swarm Optimization,1969,Expert System,1989 Swarm Intelligence 群体智能 Tabu Search,AI上这一特殊分支的发展历史,21,Genetic Algorithm,Tabu Search,1953,Ants System,Particle Swarm Optimization,1969,Expert System,1991 Swarm Intelligence 蚁群算法 Ants System,AI上这一特殊分支的发展历史,22,Genetic Algorithm,Tabu Search,1953,Ants System,1969,Expert System,1995 Particle Swarm Optimization 粒子群优化算法,AI上这一特殊分支的发展历史,23,出版社：人民邮电出版社 作者：美James Kennedy/ Russell C.Eberhart/ Yuhui Shi/ 2009年2月第1版第1次印刷,24,几本相关的中文书,25,蚁群优化算法 Ant Colony Algorithm (ACA),26,参考文献,APPEARED IN PROCEEDINGS OF ECAL91-EUROPEAN CONFERENCE ON ARTIFICIAL LIFE, PARIS, FRANCE, ELSEVIER PUBLISHING,134142. Distributed Optimization by Ant Colonies Alberto Colorni, Marco Dorigo, Vittorio Maniezzo Dipartimento di Elettronica, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, Italy IEEE Transactions on Systems, Man, And Cybernetics- Part B: Cybernetics,Vol.26, No.1, Feb 1996. 29-41 Ant System: Optimization by a Colony of Cooperating Agents Marco Dorigo, Member, IEEE, Vittorio Maniezzo, and Alberto Colorni http:/iridia.ulb.ac.be/mdorigo/HomePageDorigo/,27,对蚂蚁的观察,单只蚂蚁智能不高; 没有集中的指挥 无所作为 蚁群，复杂的社会行为： 协同工作 筑巢、觅食、迁徙、清扫蚁巢、抚养后代 依靠群体能力发挥出超出个体的智能,28,蚁群算法特点,模拟蚂蚁群体智能行为的仿生优化算法 较强的鲁棒性 优良的分布式计算机制 易于与其它方法结合,29,蚂蚁的生物学特征,别称：玄驹、蚍蜉、状元子 属节肢动物门，昆虫纲，膜翅目，蚁科 在昆虫界种类最多，生存量最大 约260属，16000多种，已命名的9000多种 拖动1400自重的食物 举起自重400倍的物体 起源于1亿年前的恐龙时代,30,蚂蚁的社会形态,蚁后、雄蚁、工蚁、兵蚁 信息交流方式：化学通信 分泌化学刺激物：信息素 (pheromone) 彼此平等，利他主义 个体协作，协调一致 共和国,31,蚂蚁的群体行为,蚂蚁个体简单 群体：高度机构化的社会组织 远超蚂蚁个体能力 行为1：觅食 食物随机散布 找到一条蚁巢到食物源的最佳路径 适应环境变化：出现障碍 方法：蚁过留素（雁过留声），闻素而跟 信息正反馈,32,良性循环 ： 路好（有食且近）蚁多信息素多蚁多 （随时 会蒸发掉一部分）， 开始： 信息素浓度 路短 素浓。,33,良性循环如何进行？,符号和假定：路径上的信息素浓度记为 X 蚂蚁均匀释放信息素，dx/dt =常数 蚁穴A，食物源C， 路径1：AC，路径2：ABC 等边三角形ABC 找到食物，沿原路返回,B,A,C,34,良性循环如何进行？,蚂蚁M1：AC，蚂蚁M2：ABC 找到食物（分布、并行），沿原路返回 AC 比ABC短， M1回到A点时， M2 才到C点。 AC上蚁气 ：两次信息素叠加（去-回） AB路只有去一次信息素 X(AC)X(ABC)，下一只蚂蚁：选择路径AC AC上信息素越来越多，进入良性循环,35,Fig. 1. An example with real ants,a) Ants follow a path between points A and E. b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is laid down.,36,Fig. 2. An example with artificial ants,a) The initial graph with distances. b) At time t=0 there is no trail on the graph edges; therefore, ants choose whether to turn right or left with equal probability. c) At time t=1 trail is stronger on shorter edges, which are therefore, in the average, preferred by ants.,37,要点,蚂蚁群居群动，很少有独行侠， 选择信息素浓的路径 ， 喜欢热闹， 追求蚁气（人气） 人也类似。 两家饭店，一家热热火火，一家门可罗雀，选哪家？ 选登山旅游线，一般人选人气多的（信息素浓的） 信息素启发性知识：人气高的，自有其优点 饭店请名人写诗歌作画、写对联，留下信息素 商业 ”托” , 假造信息素 优势： 并行+分布+信息素,70%选红火的， 不一定每人是这样 称为按概率.0.7选红火的,38,双桥实验(Goss S, 1989),Naturwissenschaften 76, 579-581 (1989) Self-organized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels Unit of Behavioural Ecology, C.P. 231, Universit6 Libre de Bruxelles, B- 1050 Bruxelles,39,Fig. 1. A colony of I humilis selecting the short branches on both modules of the bridge,a) one module of the bridge b) and c): photos taken 4 and 8 min after placement of the bridge,40,双桥实验数学模型,假设条件： 1、非对称桥上的信息量与过去一个时间段内经过该桥的蚂蚁数目成正比； 2、某一时刻蚂蚁按照桥上残留的信息量多少来选择其中某座桥 3、经过该桥的蚂蚁数目越多则桥上的残留信息量就越大,设短桥为A，长桥为B，mA和mB分别表示经过桥A和桥B的蚂蚁数目 mA + mB = m 当所有m只蚂蚁都经过两座桥之后，第m+1只蚂蚁选择桥A的概率为：,而选择桥B的概率为：,41,参数h 和 k用以匹配真实实验数据 第m+1只蚂蚁首先计算 然后生成一个在区间0,1上均匀分布的随机数 若 ，则选择桥A，否则选择桥B,42,发展,意大利学者M Dorigo，Vmaniezzo和A Colorni 20世纪90年代 ：蚂蚁系统（ant system，AS） 求解旅行商问题（Traveling Salesman Problem，简称TSP） 90年代中期，用于广泛领域，取得成果 M Dorigo 发展为优化技术-蚁群优化 （Ant Colony Optimization，简称ACO） W J Gutjahr ：ACO的收敛性 用于合优化，函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由,43,ACO国际研讨会,ACO国际研讨会 1998、2000年、2002年、2004年，2006年，比利时布鲁塞尔大学,44,基本蚁群算法的数学模型,45,P、NP、NP-C、NP-hard问题,P类问题 所有可用DTM (Deterministic one-tape Turing Machine) 在多项式时间内求解的判定问题的集合。简记为O(p(n) 即 P=L: 存在一个多项式时间DTM程序M，是的L=LM , 其中LM表示程序M所识别的语言。 若存在一个多项式时间DTM程序，它在编码策略e之下求解判定问题，即L, eP,则称该判定问题属于P类问题。,46,P、NP、NP-C、NP-hard问题,NP类问题 (Non-deterministic Polynomial) 若存在一个多项式函数 g(x) 和一个验证算法H, 对一类判定问题A的任何一个“是”回答，满足其输入长度d(s)不超过g(d(I), 其中d(I)为I的输入长度，且验证算法中S为I的“是”回答的计算时间不超过g(d(I), 则称判定问题A为非多项式确定问题。 NP类问题是所有可用NDTM (Non-Deterministic one-tape Turing Machine)在多项式时间内求解的判定问题的集合,47,P、NP、NP-C、NP-hard问题,NP-C类问题 (NP-Complete) 是NP类中最困难的一类问题。 有重要实际意义和工程背景 TSP (Traveling Salesman Problem) Symmetric; Asymmetric NP-hard类问题 NP-C NP-hard,NP,P,NP-hard,NP-C,48,基本蚁群算法模型,基本假设 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对周围的局部环境产生影响； 蚂蚁对环境的反应由其内部模式决定。即蚂蚁是反应型适应性主体 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。,49,TSP (Traveling Salesman Problem),有向图 有向图D的三元组为 (V, E, f)，其中V是一个非空集合，其元素称为有向图的结点；E是一个集合，其元素称为有向图的弧段（边）；f是从E到VxV上的一个映射（函数）。 E中的元素总是和V中的序偶对有对应关系，可用V中的序偶代替E中的元素。 一个有向图可简记为(V, E).,50,TSP (Traveling Salesman Problem),TSP 设C=c1, c2, , cn 是n个城市的集合， L=lij|ci, cj C是集合C中的元素（城市）两两连接的集合， dij(i, j=1,1,n)是lij的Euclidean距离，即,G=(C, L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈， 即一条对C=c1, c2, , cn中n个元素（城市）访问且只访问一次的最短封闭曲线,51,TSP (Traveling Salesman Problem),TSP简单形象描述 给定n个城市，