群集智能算法.ppt

《群集智能算法.ppt》由会员分享，可在线阅读，更多相关《群集智能算法.ppt（55页珍藏版）》请在三一办公上搜索。

1、第7章 群集智能算法,第7章 群集智能算法,7.1 群集智能算法的研究背景7.2 群集智能的基本算法介绍7.3 集智系统介绍7.4 群集智能的优缺点,7.1群集智能算法的研究背景,起源于对人工生命的研究。“人工生命”是用来研究具有某些生命基本特征的人工系统。包括两方面的内容：1.研究如何利用计算技术研究生物现象2.研究如何利用生物技术研究计算问题,7.1群集智能算法的研究背景,对群集智能的研究是受社会性昆虫行为的启发，从事计算研究的学者通过对社会性昆虫的模拟产生了一系列对传统问题的新的解决方法，这些研究就是群集智能的研究。群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过

2、改变局部环境)的主体，这组主体能够合作进行分布问题求解”；群集智能(Swarm Intelligence)指的是“无智能的主体通过合作表现出智能行为的特性”。,7.2群集智能的基本算法介绍,7.2.1 蚁群算法蚁群算法是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上；7.2.2 flock算法flock算法后者也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程。,蚁群算法是受到上世纪五十年代仿生学的启发，由意大利学者M.Dorigo等人首先提出的一种新型的模拟进化算法，该算法在求解组合优化问题中体现出优良的特性。作为一种基于种群的启发式搜索算法，它能很好的利用蚁群的集体

3、寻优特征来寻找蚁穴和食物之间的最短路径。因此，被广泛应用于旅行商问题（TSP）、Job-shop调度问题、指派问题等等，都取得了良好的仿真试验结果。,7.2.1蚁群算法,1.蚁群算法的模拟试验该试验在各个蚂蚁在没有事先告诉它們食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！但有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，它們会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。,为什么小小的蚂蚁能够找到食物，它

4、們具有智能么？要为蚂蚁设计这样的一个智能程序，需要设置那些功能呢？首先，我们要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让它們能够巧妙的避开障碍物；其次，要让蚂蚁找到食物，就需要让它們遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小。,这个试验程序的每个蚂蚁的核心程序编码不过100多行。为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：巧妙地利用简单规则来实现集体智慧。每只蚂蚁并不是像我们想象的需要知道整个世界的信息，它們其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样在蚁群这个集体里，复杂性

5、的行为就会凸现出来。这些规则就是下面所述的简单的6条规则,ACO 基本规则（一、二）,范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界。环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。环境以一定的速率让信息素消失。,ACO 基本规则（三）,觅食规则：感知范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并

6、不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。,ACO 基本规则（四）,移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。,ACO 基本规则（五、六）,避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食/找窝的规则行动。播撒信息素规则：在不同的蚁群优化算法中，有的其中的蚂

7、蚁每次散播的信息素是一个常量，有的其中蚂蚁散播的信息素是一个变量，但是这些信息素都是动态变化并随时间逐渐消逝的。,试验参数的说明 最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。食物释放信息素的半径：在食物点和窝点附近都会释放相应的信息素以便蚂蚁能更快的找到它们。这个半径越大，则越容易被蚂蚁找到。,信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。错误概率：表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。速度半径：表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。,记忆能力：表示蚂蚁能

8、记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。按钮：是把当前更改的所有蚂蚁的个体属性应用到所有的蚂蚁身上。,实现的原理,有两条路径通向食物 蚂蚁聚集到较短的路径,现在的问题是蚂蚁究竟是怎么找到食物的呢？在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转；,其次，蚂蚁要有一定的随机性，虽然有了固定的方向，

9、但它也不能像一个小球一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向。这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁沿着是某个方向正确，而其他方向则不正确。在有一只蚂蚁找到了食物后，其他蚂蚁会沿着信息素很快找到食物。,蚂蚁如何找到最短路径的？这一是要归功于信息素；二是要归功于环境，即计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。,当蚂蚁沿着一条路到达

10、终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素，而长的路径则正好相反。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。,蚁群算法过程模拟,模拟试验结果的思考 跟着蚂蚁的踪迹，我们能够发现什么呢？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：多样性正反馈,多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环；正反馈机制则保证了相对优良的信息能够

11、被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创新性。正是这两点巧妙的结合才使得智能行为涌现出来。,从广义来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，难以找到新的更佳的路径。,用蚁群算法解决问题的步骤,能够把待解

12、决的问题用图的形式抽象表达出来；具体定义各种参数，如范围、信息素消逝函数等；为算法中的蚂蚁制定相应的移动规则；选择一种适应的蚁群优化算法并将其合理地应用到自己的问题解决方案中去；适当调整所应用的蚁群算法中的对应参数以达到较好的实验效果.,2.应用蚁群算法求解TSP问题,设m为蚁群中蚂蚁的数量，n 为旅行商要走过的城市数,dij(i,j=1,2,3,n)为城市i到j的距离，bi(t)为 t 时刻位于城市 i 的蚂蚁个数 ij(t)为 t 时刻在 ij 连线上残留的信息量，初始时刻各条路径上的信息量相等，即 ij(1)=C（C为常数）。,为信息残留系数，则-1表征了从时刻t到 t+n在路径ij上残

13、留信息的挥发程度。表示第k只蚂蚁在本次循环中留在路径 ij 上的信息量。,如果在时间间隔(t,t+1)中，m 个蚂蚁都从当前城市选择下一个城市，则经过 n 个时间间隔，所有蚂蚁都走完n个城市，构成一轮循环，此时，按如下方法修改各条路径上的残留信息：,（1）Ant-Circle System模型Q 为常量，Lk 为第 k 只蚂蚁在本次循环中所走路径的长度。,（2）Ant-Quantity System模型（3）Ant-Density System模型,7.2.2 flock算法,Flock算法是由Craig Reynolds于1987年在一篇为SIGGRAPH所写的论文“Flocks,Herds

14、,and Schools:A Distributed Behavioral Model”中首次提出的一种集智技术。这种技术有3个简单的规则，当它们组合在一起时，为自治主体（boid）群给出了一个类似于鸟群、鱼群或蜂群的群体行为的逼真表现形式。这些被Reynolds称之为定向行为（Steering Behaviors）。,7.2.2 flock算法,定向行为的规则：分离：定向时要避免与本地flock同伴拥挤列队：驶向本地flock同伴的平均航向 聚合：定向时朝着本地flock同伴的平均位置移动,分离,列队,聚合,分离规则给了一个主体试图与其它邻近的主体保持一定的距离的能力。确保主体之间以一个“看

15、似自然”的接近度，模拟真实世界中的群体，以避免主体拥挤在一起。队列规则为一个主体提供了与其他邻近主体列队的能力（即与其他邻近主体航向或速度相同）。与分离类似，本文将队列说明为：通过每一个flock成员观察邻近同伴，然后调整它的航向和速度以与其邻近同伴的平均航向和速度相匹配。,聚合规则给了一个主体与其他邻近主体“聚合（group）”的能力，从而模拟自然界的类似行为。Reynolds在稍后的实现和论文中又增加了有时被称作flocking“第四规则”的规则。,躲避：使避免撞上局部区域的障碍和敌人,躲避规则的作用是为主体提供了使它绕过障碍和避免碰撞的能力。这种控制行为是这样完成的：通过赋予每个主体“向

16、前看”一段距离的能力，决定与一些对象的碰撞是否可能，然后调整航向以避免碰撞。Flock技术通过这四个简单的规则最终模拟出逼真的群体行为，更有意思的是这种移动算法本身是无状态的：在移动更新中，不记录任何信息。,在每次更新循环中，每只boid都将重新评估其环境。这样不但降低了内存需求，同时让物群能够对不断变化的环境状况做出实时的反应。因此，物群将具备突发行为的（Emergent Behavior）特性，即物群中的所有成员都对要前往何方一无所知，但作为一个整体行动，避开障碍物和天敌，并保持若即若离。,7.3 集智系统介绍,7.3.1 人工鱼7.3.2 Terrarium世界,7.3.1 人工鱼,人工

17、鱼群体是一种典型的多智能主体（Multiple Intelligent Agent）的分布式人工智能系统（distributive artificial intelligent system）。中国青年学者涂晓媛研究开发的新一代计算机动画“人工鱼”被学术界称之为“晓媛鱼”（Xiaoyuans fish），她发表的论文“人工动物的计算机动画”(artificial animals for computer animation:biomechanics,locomotion,perception and behavior)，在1996年获国际计算学会ACM最佳博士论文奖。,涂晓媛研究开发的“人工鱼

18、”构成了栖息在虚拟海底世界中人工鱼群的社会，其中，每条“人工鱼”都是一个自主的智能体（autonomous intelligent agent），都可以独立地活动，也可以相互交往。每条鱼都表现出某些人工智能，如：自激发（self-animating）、自学习（self-learning）、自适应（self-adapting）等智能特性.,会产生相应的智能行为，如：因饥饿而激发寻食、进食行为；有性欲而激发求爱行为；能吸取其他鱼被鱼钩钓住的教训，而不去吞食有钩的鱼饵；能适应有鲨鱼的社会环境，逃避被捕食的危险等。人工鱼群的社会具有某些自组织（self-organizing）能力和智能集群行为，如：人

19、工鱼群体在漫游中遇到障碍物等，会识别障碍改变队形，绕过障碍后，又重组队列，继续前进。,7.3.1 人工鱼,1.人工鱼与动画鱼区别：“人工鱼”具有“人工生命”和自然鱼的某些生命特征。在一般的计算机动画中，创作者需要在动画设计和程序编制中确定动画鱼的所有动作的细节，预先知道动画鱼的全部动作过程。然而，人工鱼的创作者并不去设计和规定每条鱼的动作和行为的细节，也不能预知人工鱼群中可能发生的各种具体动作和实际行为。,7.3.1 人工鱼,2.“人工鱼”与“人工生命”涂晓媛所说的“人工生命”（artificial life）是指具有“自然生命”特性和功能的人造系统，或者说是“人造活体”。人工生命的研究方法和

20、技术途径，可以分：生命科学途径 工程技术途径,7.3.1 人工鱼,3.“人工鱼”的创作“人工鱼”的动画创作方法和技术，已经突破了传统的计算机动画的框架。首先，“人工鱼”不仅有逼真于“自然鱼”的外形和彩色，而且具有类似于“自然鱼”的运动和姿态。其次，“人工鱼”不仅具有“自然鱼”的形态，而且具有“自然鱼”类似的生命特性“活性”。再次，“人工鱼”是具有人工智能的“灵巧鱼”，而传统的“动画鱼”是程序化的“木偶鱼”。最后，“人工鱼”是具有各种不同的人工鱼的鱼群社会。,“人工鱼”的形态（外形、颜色、姿态）和“自然鱼”非常相似，几乎达到了“以假乱真”的程度。在一次国际会议上，涂晓媛演示了“人工鱼”的录像，人

21、们看到屏幕上一群色彩美丽、活泼可爱的热带鱼，在海水中漫游，逼真的外形、生动的姿态，伴随着水流的运动，还以为是在水族馆中拍摄的真热带鱼的录像。直到涂晓媛把“人工鱼”的彩色消隐，变成黑白的鱼，再把“人工鱼”的肌肉剥离，剩下一群热带鱼的骨架在游泳，才确信这是计算机动画的”人工鱼”。,“人工鱼”和一般的“动画鱼”的不同之处还在于：“人工鱼”具有某些自然鱼的“本能”性。“人工鱼”能感知其他的”人工鱼”和海底环境，有“鱼肉”、“鱼骨”、“鱼嘴”、“鱼头”、“鱼尾”、“鱼鳍”等，能产生类似于自然鱼的随意动作和行为。例如：人工鱼有性欲；人工鱼有饥饿感；人工鱼有学习能力，若一条鱼误吞了鱼饵，被鱼钩钩上，会进行挣

22、扎，而其他的“人工鱼”，就会吸取教训不再上当，不去吞食带钩的鱼饵，离开钓鱼的水域；“人工鱼”有恐惧感，如果发现凶恶的鲨鱼来侵犯，都迅速散开，东奔西逃，脱离危险，。,7.3.1 人工鱼,图12.8 雄鱼向雌鱼求爱,图12.9 侵略者鲨鱼偷袭被扑食的小鱼群,7.3.1 人工鱼,4.“人工鱼”有何意义和价值？（1）“人工鱼”开拓了计算机动画创作的新途径。（2）“人工鱼”提供了“人工生命”的新范例。（3）“人工鱼”实现了分布式“人工智能”。,饲养场模式（Terrarium Mode）：这种模式给用户提供了两种选择。用户可以独立运行，无须与其他节点连接。在这种情况下，屏幕上显示的生态系统就代表了整个生态

23、环境。这种模式最适合于对我们开发出来的生物进行测试。用户也可以选择加入到一组特定的节点环境中，所有连入此环境的计算机共同组成一个小型生态系统。,7.3.2 Terrarium世界,加入特定节点组的方法非常简单，每个用户选择一个特定的专网，并在Terrarium控制台的“Channel”一项中输入一个事先约定好的字串，就可以加入该网络了。输入字串后，用户的计算机只与那些输入了相同字串的计算机构成一个独立的对等网络，并一同组建生态系统。,生物圈模式（Ecosystem Mode）：这是游戏的标准模式。全世界所有连入游戏的计算机共同构成一个完整的生态系统。每个参与者的计算机只是该生态系统的一个局部场

24、景。在上述两种模式下，开发者都可以使用Terrarium类库、.NET框架开发包和Visual Studio.NET工具随意创建它們自己的生物。或者，可以简单地把Terrarium当作一个独立运行的应用程序或是屏幕保护程序运行，并通过Terrarium观看其他开发者创建的生物在生态系统中为生存而战。,7.4 群集智能的优缺点,特点和优点：群体中相互合作的个体是分布的(Distributed)，这样更能够适应当前网络环境下的工作状态；没有中心控制的机制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解；,7.4 群集智能的优缺点,3.可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability)，由于系统中个体的增加而造成的系统的通信开销的增加在这里非常小；4.系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。,7.4 群集智能的优缺点,缺陷：1.并不是总能从涌现的群体行为中推导出个体的行为;2真实生物个体如此复杂，以至于几乎不可能在一个仿真系统中完成复制;3.简单的规则产生类似生命的群体行为并不能保证真实的生态系统一定能够遵循这些简单的规则。,