群集智能算法.ppt

《群集智能算法.ppt》由会员分享，可在线阅读，更多相关《群集智能算法.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、群集智能算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第第7章章 群集智能算法群集智能算法7.1 群集智能算法的研究背景7.2 群集智能的基本算法介绍7.3 集智系统介绍7.4 群集智能的优缺点 7.1群集智能算法的研究背景群集智能算法的研究背景 起源于对人工生命的研究。“人工生命”是用来研究具有某些生命基本特征的人工系统。包括两方面的内容：1.研究如何利用计算技术研究生物现象2.研究如何利用生物技术研究计算问题7.1群集智能算法的研究背景群集智能算法的研究

2、背景对群集智能的研究是受社会性昆虫行为的启发，从事计算研究的学者通过对社会性昆虫的模拟产生了一系列对传统问题的新的解决方法，这些研究就是群集智能的研究。群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”；群集智能(Swarm Intelligence)指的是“无智能的主体通过合作表现出智能行为的特性”。7.2群集智能的基本算法介绍群集智能的基本算法介绍7.2.1 7.2.1 蚁群算法蚁群算法蚁群算法是对蚁群算法是对蚁群算法是对蚁群算法是对蚂蚁群落食物采集过程的模拟蚂蚁群落食物采集过程的模拟蚂蚁群落食物采集过程的模拟蚂

3、蚁群落食物采集过程的模拟，已经，已经，已经，已经成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；7.2.2 7.2.2 flockflock算法算法flockflock算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最初设想是初设想是初设想是初设想是模拟鸟群觅食模拟鸟群觅食模拟鸟群觅食模拟鸟群觅食的过程。的过程。的过程。的过程。蚁群算法是受到上世纪五十年代仿生学的启发，由意大利学者M.Dorigo等人首先提出的一种

4、新型的模拟进化算法，该算法在求解组合优化问题中体现出优良的特性。作为一种基于种群的启发式搜索算法，它能很好的利用蚁群的集体寻优特征来寻找蚁穴和食物之间的最短路径。因此，被广泛应用于旅行商问题（TSP）、Job-shop调度问题、指派问题等等，都取得了良好的仿真试验结果。7.2.1蚁群算法蚁群算法1.1.蚁群算法的模拟试验l该试验在各个蚂蚁在没有事先告诉它們食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！l但有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，它們会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么更多

5、的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。为为为为什什什什么么么么小小小小小小小小的的的的蚂蚂蚂蚂蚁蚁蚁蚁能能能能够够够够找找找找到到到到食食食食物物物物，它它它它們們們們具具具具有有有有智智智智能能能能么么么么？要要要要为为为为蚂蚂蚂蚂蚁蚁蚁蚁设设设设计计计计这这这这样样样样的的的的一一一一个个个个智智智智能能能能程程程程序序序序，需需需需要要要要设设设设置置置置那些功能呢？那些功能呢？那些功能呢？那些功能呢？首首首首先先先先，我我我我们们们们要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁能能能能够够够够避避避避开开开开障障障障碍碍碍碍物物物物，就

6、就就就必必必必须须须须根根根根据据据据适适适适当当当当的的的的地地地地形形形形给给给给它它它它编编编编进进进进指指指指令令令令让让让让它它它它們們們們能能能能够够够够巧巧巧巧妙妙妙妙的的的的避避避避开开开开障碍物；障碍物；障碍物；障碍物；其其其其次次次次，要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁找找找找到到到到食食食食物物物物，就就就就需需需需要要要要让让让让它它它它們們們們遍遍遍遍历历历历空空空空间上的所有点间上的所有点间上的所有点间上的所有点；再再再再次次次次，如如如如果果果果要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁找找找找到到到到最最最最短短短短的的的的路路路路径径径径，那那那那么么么么需需需需要要要要

7、计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。这个试验程序的每个蚂蚁的核心程序编码不过100多行。为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：巧妙地利用简单规则来实现集体智慧。每只蚂蚁并不是像我们想象的需要知道整个世界的信息，它們其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样在蚁群这个集体里，复杂性的行为就会凸现出来。这些规则就是下面所述的简单的6条规则ACO 基本规则（一、二）基本规则（一、二）l范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有

8、一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界。l环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。环境以一定的速率让信息素消失。ACO 基本规则（三）基本规则（三）l l觅食规则：感知范围内寻找是否有食物，如果有就直接过去。感知范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，哪一点的信息素最多，朝信息素多的地方走朝信息素多的地方走，并且，并且每只蚂蚁多会每

9、只蚂蚁多会以小概率犯错误以小概率犯错误，从而并不是往信息，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没不过它对窝的信息素做出反应，而对食物信息素没反应。反应。ACO 基本规则（四）基本规则（四）l l移动规则：每只蚂蚁都朝每只蚂蚁都朝向信息素最多的方向移向信息素最多的方向移，并且，当周，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向动的方向惯性的运动惯性的运动下去，并且，在运动的方向有下去，并且，在运动的方向有一个一个随机的小的扰动

10、随机的小的扰动。为了。为了防止蚂蚁原地转圈防止蚂蚁原地转圈，它，它会记住最近刚走过了哪些点，如果发现要走的下一会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。点已经在最近走过了，它就会尽量避开。ACO 基本规则（五、六）基本规则（五、六）l l避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会如果蚂蚁要移动的方向有障碍物挡住，它会随机随机的选择的选择另一个方向，并且有另一个方向，并且有信息素指引信息素指引的话，它会的话，它会按照觅食按照觅食/找窝的规则行动。找窝的规则行动。l l播撒信息素规则：在不同的蚁群优化算法中，有的其中的蚂蚁每次在不同的蚁群优化算法中，有的

11、其中的蚂蚁每次散播的信息素是一个散播的信息素是一个常量常量，有的其中蚂蚁散播的信，有的其中蚂蚁散播的信息素是一个息素是一个变量变量，但是这些信息素都是动态变化并，但是这些信息素都是动态变化并随时间逐渐消逝随时间逐渐消逝的。的。l l试验参数的说明试验参数的说明试验参数的说明试验参数的说明 l l最大信息素最大信息素最大信息素最大信息素：蚂蚁在一开始拥有的信息素总量，：蚂蚁在一开始拥有的信息素总量，：蚂蚁在一开始拥有的信息素总量，：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。越大表示程序在较长一段时间能够存在信息素。越大表示程序在较长一段时间能够存在信息素。越大表示程

12、序在较长一段时间能够存在信息素。l l食物释放信息素的半径食物释放信息素的半径食物释放信息素的半径食物释放信息素的半径：在食物点和窝点附近都：在食物点和窝点附近都：在食物点和窝点附近都：在食物点和窝点附近都会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息素以便蚂蚁能更快的找到它们。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。l l信息素消减的速度信息素消减的速度信息素消减的速度信息素消减的速度：随着时间的

13、流逝，已经存在：随着时间的流逝，已经存在：随着时间的流逝，已经存在：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么消减的越快。消减的越快。消减的越快。消减的越快。l l错误概率错误概率错误概率错误概率：表示这个蚂蚁不往信息素最大的区域：表示这个蚂蚁不往信息素最大的区域：表示这个蚂蚁不往信息素最大的区域：表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。走的概率，越大则表示这个蚂蚁越有创新性。走的概率，越大则表示这个蚂蚁越有创新性

14、。走的概率，越大则表示这个蚂蚁越有创新性。l l速度半径速度半径速度半径速度半径：表示蚂蚁一次能走的最大长度，也表：表示蚂蚁一次能走的最大长度，也表：表示蚂蚁一次能走的最大长度，也表：表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。l l记忆能力记忆能力记忆能力记忆能力：表示蚂蚁能记住多少个刚刚走过点的：表示蚂蚁能记住多少个刚刚走过点的：表示蚂蚁能记住多少个刚刚走过点的：表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。坐标，这个值避免了蚂蚁在本地打转，停滞不前。坐标，这个值避免了蚂蚁在本地打转，

15、停滞不前。坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。l l按钮按钮按钮按钮：是把当前更改的所有蚂蚁的个体属性应用：是把当前更改的所有蚂蚁的个体属性应用：是把当前更改的所有蚂蚁的个体属性应用：是把当前更改的所有蚂蚁的个体属性应用到所有的蚂蚁身上。到所有的蚂蚁身上。到所有的蚂蚁身上。到所有的蚂蚁身上。l l实现的原理有两条路径通向食物 蚂蚁聚集

16、到较短的路径l l现在的问题是蚂蚁究竟是现在的问题是蚂蚁究竟是现在的问题是蚂蚁究竟是现在的问题是蚂蚁究竟是怎么找到食物怎么找到食物怎么找到食物怎么找到食物的呢？的呢？的呢？的呢？l l在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会息素，那么蚂蚁为什么会息素，那么蚂蚁为什么会息素，那么蚂蚁为什么会相对有效的找到食物相对有效的找到食物相对有效的找到食物相对有效的找到食物呢呢呢呢？l l这要归功于蚂蚁的这要归功于蚂蚁的这要归功于蚂蚁的这要归功于蚂蚁的移动规则

17、移动规则移动规则移动规则，尤其是在没有信息，尤其是在没有信息，尤其是在没有信息，尤其是在没有信息素时候的移动规则。素时候的移动规则。素时候的移动规则。素时候的移动规则。l l首先，它要能尽量保持某种首先，它要能尽量保持某种首先，它要能尽量保持某种首先，它要能尽量保持某种惯性惯性惯性惯性，这样使得蚂蚁，这样使得蚂蚁，这样使得蚂蚁，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转；一个方向），而不是原地无谓的打转；一个方向），而不是原地

18、无谓的打转；一个方向），而不是原地无谓的打转；l其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像一个小球一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向。l这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁沿着是某个方向正确，而其他方向则不正确。在有一只蚂蚁找到了食物后，其他蚂蚁会沿着信息素很快找到食物。l l蚂蚁如何找到蚂蚁如何找到蚂蚁如何找到蚂蚁如何找到最短路径最短路径最短路径最短路径的？的？的？的？l l这一是要归功于这一是要归功于这一是要归功于这一是要归功于信息素信息

19、素信息素信息素；二是要归功于；二是要归功于；二是要归功于；二是要归功于环境环境环境环境，即，即，即，即计算机时钟。信息素多的地方显然经过这里的蚂计算机时钟。信息素多的地方显然经过这里的蚂计算机时钟。信息素多的地方显然经过这里的蚂计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有蚁会多，因而会有更多的蚂蚁聚集过来。假设有蚁会多，因而会有更多的蚂蚁聚集过来。假设有蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路两条路从窝通向食物，开始的时候，走这两条路两条路从窝通向食物，开始的时候，走这两条路两条路从窝通向食物，开始的时候，走这

20、两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。也无关紧要）。也无关紧要）。也无关紧要）。l l当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就

21、快，因而在单位时间里走过的蚂蚁数重复的频率就快，因而在单位时间里走过的蚂蚁数重复的频率就快，因而在单位时间里走过的蚂蚁数重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多目就多，洒下的信息素自然也会多，自然会有更多目就多，洒下的信息素自然也会多，自然会有更多目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素，而长的蚂蚁被吸引过来，从而洒下更多的信息素，而长的蚂蚁被吸引过来，从而洒下更多的信息素，而长的蚂蚁被吸引过来，从而洒下更多的信息素，而长的路径则正好相反。因此，越来越多地蚂蚁聚集到的路径则正好相反。因此，越来越多地蚂蚁聚

22、集到的路径则正好相反。因此，越来越多地蚂蚁聚集到的路径则正好相反。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。较短的路径上来，最短的路径就近似找到了。较短的路径上来，最短的路径就近似找到了。较短的路径上来，最短的路径就近似找到了。蚁群算法过程模拟蚁群算法过程模拟 l l模拟试验结果的思考模拟试验结果的思考模拟试验结果的思考模拟试验结果的思考l l 跟着蚂蚁的踪迹，我们能够发现什么呢？通过跟着蚂蚁的踪迹，我们能够发现什么呢？通过跟着蚂蚁的踪迹，我们能够发现什么呢？通过跟着蚂蚁的踪迹，我们能够发现什么呢？通过上面的原理叙述和实际操作，我们不难发现蚂蚁上面的原理叙述和实际操作，

23、我们不难发现蚂蚁上面的原理叙述和实际操作，我们不难发现蚂蚁上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为之所以具有智能行为，完全归功于它的简单行为之所以具有智能行为，完全归功于它的简单行为之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的规则，而这些规则综合起来具有下面两个方面的规则，而这些规则综合起来具有下面两个方面的规则，而这些规则综合起来具有下面两个方面的特点：特点：特点：特点：l l多样性多样性多样性多样性l l正反馈正反馈正反馈正反馈l l多样性多样性多样性多样性保证了蚂蚁在觅食的时候不置走进死胡同保证了蚂蚁在觅

24、食的时候不置走进死胡同保证了蚂蚁在觅食的时候不置走进死胡同保证了蚂蚁在觅食的时候不置走进死胡同而无限循环；而无限循环；而无限循环；而无限循环；l l正反馈正反馈正反馈正反馈机制则保证了相对优良的信息能够被保存机制则保证了相对优良的信息能够被保存机制则保证了相对优良的信息能够被保存机制则保证了相对优良的信息能够被保存下来。下来。下来。下来。l l我们可以把多样性看成是一种我们可以把多样性看成是一种我们可以把多样性看成是一种我们可以把多样性看成是一种创造能力创造能力创造能力创造能力，而正反，而正反，而正反，而正反馈是一种学习馈是一种学习馈是一种学习馈是一种学习强化能力强化能力强化能力强化能力。正反

25、馈的力量也可以比。正反馈的力量也可以比。正反馈的力量也可以比。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创喻成权威的意见，而多样性是打破权威体现的创喻成权威的意见，而多样性是打破权威体现的创喻成权威的意见，而多样性是打破权威体现的创新性。新性。新性。新性。l l正是这两点巧妙的结合才使得智能行为涌现出来。正是这两点巧妙的结合才使得智能行为涌现出来。正是这两点巧妙的结合才使得智能行为涌现出来。正是这两点巧妙的结合才使得智能行为涌现出来。l l 从广义来讲，大自然的进化，社会的进步、人类从广义来讲，大自然的进化，社会的进步、人类从广义来讲，大自然的进化，社会的进步、人类从广义来讲

26、，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证的创新实际上都离不开这两样东西，多样性保证的创新实际上都离不开这两样东西，多样性保证的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够了系统的创新能力，正反馈保证了优良特性能够了系统的创新能力，正反馈保证了优良特性能够了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。得到强化，两者要恰到好处的结合。得到强化，两者要恰到好处的结合。得到强化，两者要恰到好处的结合。l l如果如果如果如果多样性过剩多样性过剩多样性过剩多样性过剩，也就是系统过于活跃，这相当，也就是系统过

27、于活跃，这相当，也就是系统过于活跃，这相当，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；于蚂蚁会过多的随机运动，它就会陷入混沌状态；于蚂蚁会过多的随机运动，它就会陷入混沌状态；于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，而相反，多样性不够，而相反，多样性不够，而相反，多样性不够，正反馈机制过强正反馈机制过强正反馈机制过强正反馈机制过强，那么系，那么系，那么系，那么系统就好比一潭死水。这在蚁群中来讲就表现为，统就好比一潭死水。这在蚁群中来讲就表现为，统就好比一潭死水。这在蚁群中来讲就表现为，统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬

28、，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。用蚁群算法解决问题的步骤用蚁群算法解决问题的步骤1.能够把待解决的问题用图的形式抽象表达出来；2.具体定义各种参数，如范围、信息素消逝函数等；3.为算法中的蚂蚁制定相应的移动规则；4.选择一种适应的蚁群优化算法并将其合理地应用到自己的问题解决方案中去；5.适当调整所应用的蚁群算法中的对应参数以达到较好的实验效果.2.应用蚁群算法求解应用蚁群算法求解TSP问题问题设设mm为蚁群中蚂蚁的数量，为蚁群中蚂蚁的数量，n n 为旅行商要走过的城市数

29、为旅行商要走过的城市数,d dij ij(i,j=1,2,3,n)(i,j=1,2,3,n)为城市为城市i i到到j j的距离，的距离，b bi i(t)(t)为为 t t 时刻位于城市时刻位于城市 i i 的蚂蚁个数的蚂蚁个数 ij ij(t)(t)为为 t t 时刻在时刻在 ij ij 连线上残留的信息量，初始时连线上残留的信息量，初始时刻各条路径上的信息量相等，即刻各条路径上的信息量相等，即 ij ij(1)=C(1)=C（C C为常数）。为常数）。为信息残留系数，则为信息残留系数，则-1-1表征了从时刻表征了从时刻t t到到 t+nt+n在路在路径径ij ij上残留信息的挥发程度。表示

30、第上残留信息的挥发程度。表示第k k只蚂蚁在本次循只蚂蚁在本次循环中留在路径环中留在路径 ij ij 上的信息量。上的信息量。如果在时间间隔如果在时间间隔 (t,t+1)(t,t+1)中，中，m m 个蚂蚁都从当前城市个蚂蚁都从当前城市选择下一个城市，则经过选择下一个城市，则经过 n n 个时间间隔，所有蚂蚁个时间间隔，所有蚂蚁都走完都走完n n个城市，构成一轮循环，此时，按如下方法个城市，构成一轮循环，此时，按如下方法修改各条路径上的残留信息：修改各条路径上的残留信息：（1）Ant-Circle System模型Q 为常量，Lk 为第 k 只蚂蚁在本次循环中所走路径的长度。（2）Ant-Qu

31、antity System模型（3）Ant-Density System模型7.2.2 flock算法算法FlockFlock算法是由算法是由算法是由算法是由Craig ReynoldsCraig Reynolds于于于于19871987年在一篇为年在一篇为年在一篇为年在一篇为SIGGRAPHSIGGRAPH所写的论文所写的论文所写的论文所写的论文“Flocks,Herds,and Flocks,Herds,and Schools:A Distributed Behavioral Model”Schools:A Distributed Behavioral Model”中首中首中首中首次提出的

32、一种次提出的一种次提出的一种次提出的一种集智技术集智技术集智技术集智技术。这种技术有。这种技术有。这种技术有。这种技术有3 3个简单的规则，个简单的规则，个简单的规则，个简单的规则，当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（boidboid）群给出）群给出）群给出）群给出了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真表现形式。这些被表现形式。这些被表现形式。这些被表现形式。这些被R

33、eynoldsReynolds称之为定向行为称之为定向行为称之为定向行为称之为定向行为（Steering BehaviorsSteering Behaviors）。）。）。）。7.2.2 flock算法算法定向行为的规则：定向行为的规则：分离：定向时要避免与本地分离：定向时要避免与本地分离：定向时要避免与本地分离：定向时要避免与本地flockflock同伴拥挤同伴拥挤同伴拥挤同伴拥挤列队：驶向本地列队：驶向本地列队：驶向本地列队：驶向本地flockflock同伴的平均航向同伴的平均航向同伴的平均航向同伴的平均航向 聚合：定向时朝着本地聚合：定向时朝着本地聚合：定向时朝着本地聚合：定向时朝着本地

34、flockflock同伴的平均位置移同伴的平均位置移同伴的平均位置移同伴的平均位置移动动动动 分离列队聚合l l分离规则分离规则分离规则分离规则给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保持一定的距离的能力。确保主体之间以一个持一定的距离的能力。确保主体之间以一个持一定的距离的能力。确保主体之间以一个持一定的距离的能力。确保主体之间以一个“看看看看似自然似自然似自然似自然”的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体

35、，以避免主体拥挤在一起。避免主体拥挤在一起。避免主体拥挤在一起。避免主体拥挤在一起。l l队列规则队列规则队列规则队列规则为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队的能力（即与其他邻近主体航向或速度相同）。的能力（即与其他邻近主体航向或速度相同）。的能力（即与其他邻近主体航向或速度相同）。的能力（即与其他邻近主体航向或速度相同）。与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个flockfl

36、ock成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。l l聚合规则聚合规则聚合规则聚合规则给了一个主体与其他邻近主体给了一个主体与其他邻近主体给了一个主体与其他邻近主体给了一个主体与其他邻近主体“聚合聚合聚合聚合（groupgroup）”的能力，从而模拟自然界的类似行的能力，从而模拟自然界的类似行的能力，从而模拟自然界的类似行的能力

37、，从而模拟自然界的类似行为。为。为。为。l lReynoldsReynolds在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被称作称作称作称作flocking“flocking“第四规则第四规则第四规则第四规则”的规则。的规则。的规则。的规则。躲避：使避免撞上局部区域的障碍和敌人 l躲避规则的作用是为主体提供了使它绕过障碍和躲避规则的作用是为主体提供了使它绕过障碍和避免碰撞的能力。这种控制行为是这样完成的：避免碰撞的能力。这种控制行为是这样完成的：通过赋予每个主体通过赋予每个主体“向前看向前看”一段距离的能

38、力，一段距离的能力，决定与一些对象的碰撞是否可能，然后调整航向决定与一些对象的碰撞是否可能，然后调整航向以避免碰撞。以避免碰撞。lFlock技术通过这四个简单的规则最终技术通过这四个简单的规则最终模拟出逼真模拟出逼真的群体行为的群体行为，更有意思的是这种移动算法本身是，更有意思的是这种移动算法本身是无状态的：在移动更新中，不记录任何信息。无状态的：在移动更新中，不记录任何信息。l在每次更新循环中，每只boid都将重新评估其环境。这样不但降低了内存需求，同时让物群能够对不断变化的环境状况做出实时的反应。因此，物群将具备突发行为的（Emergent Behavior）特性，即物群中的所有成员都对要

39、前往何方一无所知，但作为一个整体行动，避开障碍物和天敌，并保持若即若离。7.3 集智系统介绍集智系统介绍7.3.1 人工鱼7.3.2 Terrarium世界7.3.1 人工鱼人工鱼人工鱼群体是一种典型的多智能主体（Multiple Intelligent Agent）的分布式人工智能系统（distributive artificial intelligent system）。中国青年学者涂晓媛研究开发的新一代计算机动画“人工鱼”被学术界称之为“晓媛鱼”（Xiaoyuans fish），她发表的论文“人工动物的计算机动画”(artificial animals for computer anim

40、ation:biomechanics,locomotion,perception and behavior)，在1996年获国际计算学会ACM最佳博士论文奖。l涂晓媛研究开发的“人工鱼”构成了栖息在虚拟海底世界中人工鱼群的社会，其中，每条“人工鱼”都是一个自主的智能体（autonomous intelligent agent），都可以独立地活动，也可以相互交往。每条鱼都表现出某些人工智能，如：自激发（self-animating）、自学习（self-learning）、自适应（self-adapting）等智能特性.l会产生相应的智能行为，如：因饥饿而激发寻食、进食行为；有性欲而激发求爱行为；

41、能吸取其他鱼被鱼钩钓住的教训，而不去吞食有钩的鱼饵；能适应有鲨鱼的社会环境，逃避被捕食的危险等。人工鱼群的社会具有某些自组织（self-organizing）能力和智能集群行为，如：人工鱼群体在漫游中遇到障碍物等，会识别障碍改变队形，绕过障碍后，又重组队列，继续前进。7.3.1 人工鱼人工鱼l l1.1.人工鱼与动画鱼区别：l “人工鱼”具有“人工生命”和自然鱼的某些生命特征。l 在一般的计算机动画中，创作者需要在动画设计和程序编制中确定动画鱼的所有动作的细节，预先知道动画鱼的全部动作过程。然而，人工鱼的创作者并不去设计和规定每条鱼的动作和行为的细节，也不能预知人工鱼群中可能发生的各种具体动作

42、和实际行为。7.3.1 人工鱼人工鱼2.“人工鱼人工鱼”与与“人工生命人工生命”涂晓媛所说的涂晓媛所说的“人工生命人工生命”（artificial lifeartificial life）是）是指具有指具有“自然生命自然生命”特性和功能的人造系统，或者特性和功能的人造系统，或者说是说是“人造活体人造活体”。人工生命的研究方法和技术途径，可以分：人工生命的研究方法和技术途径，可以分：l l生命科学途径生命科学途径 l l工程技术途径工程技术途径 7.3.1 人工鱼人工鱼3.“3.“人工鱼人工鱼人工鱼人工鱼”的创作的创作的创作的创作 “人工鱼”的动画创作方法和技术，已经突破了传统的计算机动画的框架

43、。首先，“人工鱼”不仅有逼真于“自然鱼”的外形和彩色，而且具有类似于“自然鱼”的运动和姿态。其次，“人工鱼”不仅具有“自然鱼”的形态，而且具有“自然鱼”类似的生命特性“活性”。再次，“人工鱼”是具有人工智能的“灵巧鱼”，而传统的“动画鱼”是程序化的“木偶鱼”。最后，“人工鱼”是具有各种不同的人工鱼的鱼群社会。l l “人工鱼”的形态（外形、颜色、姿态）和“自然鱼”非常相似，几乎达到了“以假乱真”的程度。在一次国际会议上，涂晓媛演示了“人工鱼”的录像，人们看到屏幕上一群色彩美丽、活泼可爱的热带鱼，在海水中漫游，逼真的外形、生动的姿态，伴随着水流的运动，还以为是在水族馆中拍摄的真热带鱼的录像。直到

44、涂晓媛把“人工鱼”的彩色消隐，变成黑白的鱼，再把“人工鱼”的肌肉剥离，剩下一群热带鱼的骨架在游泳，才确信这是计算机动画的”人工鱼”。“人工鱼”和一般的“动画鱼”的不同之处还在于：l“人工鱼”具有某些自然鱼的“本能”性。l“人工鱼”能感知其他的”人工鱼”和海底环境，有“鱼肉”、“鱼骨”、“鱼嘴”、“鱼头”、“鱼尾”、“鱼鳍”等，能产生类似于自然鱼的随意动作和行为。例如：人工鱼有性欲；人工鱼有饥饿感；人工鱼有学习能力，若一条鱼误吞了鱼饵，被鱼钩钩上，会进行挣扎，而其他的“人工鱼”，就会吸取教训不再上当，不去吞食带钩的鱼饵，离开钓鱼的水域；“人工鱼”有恐惧感，如果发现凶恶的鲨鱼来侵犯，都迅速散开，东

45、奔西逃，脱离危险，。7.3.1 人工鱼人工鱼图图12.8 雄鱼向雌鱼求爱雄鱼向雌鱼求爱 图图12.9 侵略者鲨鱼偷袭被扑食的小鱼群侵略者鲨鱼偷袭被扑食的小鱼群7.3.1 人工鱼人工鱼4.“人工鱼人工鱼”有何意义和价值？有何意义和价值？（1 1）“人人工工鱼鱼”开开拓拓了了计计算算机机动动画画创创作作的的新新途途径径。（2 2）“人工鱼人工鱼”提供了提供了“人工生命人工生命”的新范例。的新范例。（3 3）“人工鱼人工鱼”实现了分布式实现了分布式“人工智能人工智能”。饲养场模式（Terrarium Mode）：这种模式给用户提供了两种选择。l用户可以独立运行，无须与其他节点连接。在这种情况下，屏幕

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

47、计算机只是该生态系统的一个局部场景。在上述两种模式下，开发者都可以使用Terrarium类库、.NET框架开发包和Visual Studio.NET工具随意创建它們自己的生物。或者，可以简单地把Terrarium当作一个独立运行的应用程序或是屏幕保护程序运行，并通过Terrarium观看其他开发者创建的生物在生态系统中为生存而战。7.4 群集智能的优缺点群集智能的优缺点 特点和优点：1.1.群体中相互合作的个体是分布的群体中相互合作的个体是分布的(Distributed)(Distributed)，这样更能够适应当前网络环境下的工作状态；，这样更能够适应当前网络环境下的工作状态；2.2.没有中

48、心控制的机制与数据，这样的系统更没有中心控制的机制与数据，这样的系统更具有具有鲁棒性鲁棒性(Robust)(Robust)，不会由于某一个或者某，不会由于某一个或者某几个个体的故障而影响整个问题的求解；几个个体的故障而影响整个问题的求解；7.4 群集智能的优缺点群集智能的优缺点3.3.可以不通过个体之间直接通信而是通过非直接可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的通信进行合作，这样的系统具有更好的可扩充可扩充性性(Scalability)(Scalability)，由于系统中个体的增加而造，由于系统中个体的增加而造成的系统的通信开销的增加在这里非常小；成的系统

49、的通信开销的增加在这里非常小；4.4.系统中每个个体的能力十分简单，这样每个个系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，体的执行时间比较短，并且实现也比较简单，具有具有简单性简单性(Simplicity)(Simplicity)。7.4 群集智能的优缺点群集智能的优缺点缺陷：1.1.并不是总能从涌现的群体行为中推导出个体的并不是总能从涌现的群体行为中推导出个体的行为行为;2 2真实生物个体如此复杂，以至于几乎不可能真实生物个体如此复杂，以至于几乎不可能在一个仿真系统中完成复制在一个仿真系统中完成复制;3.3.简单的规则产生类似生命的群体行为并不能保简单的规则产生类似生命的群体行为并不能保证证真实的生态系统真实的生态系统一定能够遵循这些简单的规一定能够遵循这些简单的规则。则。