部分用群集智能求解问题.ppt

《部分用群集智能求解问题.ppt》由会员分享，可在线阅读，更多相关《部分用群集智能求解问题.ppt（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四部分 用群集智能求解问题第4章 群集智能算法4.1群集智能算法的研究背景4.2群集智能的基本算法介绍4.3 集智系统介绍4.4 群集智能的优缺点 4.1群集智能算法的研究背景 起源于对人工生命的研究。“人工生命”是用来研究具有某些生命基本特征的人工系统。包括两方面的内容：1.研究如何利用计算技术研究生物现象2.研究如何利用生物技术研究计算问题4.1群集智能算法的研究背景对对群群集集智智能能的的研研究究是是受受社社会会性性昆昆虫虫行行为为的的启启发发，从从事事计计算算研研究究的的学学者者通通过过对对社社会会性性昆昆虫虫的的模模拟拟产产生生了了一一系系列列对对传传统统问问题题的的新新的的解解决

2、决方方法法，这这些些研研究究就就是群集智能的研究。是群集智能的研究。群群体体(Swarm)(Swarm)指指的的是是“一一组组相相互互之之间间可可以以进进行行直直接接通通信信或或者者间间接接通通信信(通通过过改改变变局局部部环环境境)的的主主体体，这这组主体能够合作进行分布问题求解组主体能够合作进行分布问题求解”；群群集集智智能能(Swarm(Swarm Intelligence)Intelligence)指指的的是是“无无智智能能的的主体通过合作表现出智能行为的特性主体通过合作表现出智能行为的特性”。4.2群集智能的基本算法介绍4.2.1 4.2.1 蚁群算法蚁群算法蚁群算法是对蚂蚁群落食物

3、采集过程的模拟，已经蚁群算法是对蚂蚁群落食物采集过程的模拟，已经蚁群算法是对蚂蚁群落食物采集过程的模拟，已经蚁群算法是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；成功运用在很多离散优化问题上；4.2.2 flock4.2.2 flock算法算法flockflock算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最算法后者也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程。初设想是模拟鸟群觅食的过程。初设想是模拟鸟群觅食的过程。初设想是模拟

4、鸟群觅食的过程。蚁蚁群群算算法法是是受受到到上上世世纪纪五五十十年年代代仿仿生生学学的的启启发发，由由意意大大利利学学者者M.DorigoM.Dorigo等等人人首首先先提提出出的的一一种种新新型型的的模模拟拟进进化化算算法法，该该算算法法在在求求解解组组合合优优化化问问题题中中体体现现出优良的特性。出优良的特性。作作为为一一种种基基于于种种群群的的启启发发式式搜搜索索算算法法，它它能能很很好好的的利利用用蚁蚁群群的的集集体体寻寻优优特特征征来来寻寻找找蚁蚁穴穴和和食食物物之之间间的的最最短短路路径径。因因此此，被被广广泛泛应应用用于于旅旅行行商商问问题题（TSPTSP）、Job-shopJo

5、b-shop调调度度问问题题、指指派派问问题题等等等等，都都取得了良好的仿真试验结果。取得了良好的仿真试验结果。蚁群算法蚁群算法1.1.蚁群算法的模拟试验蚁群算法的模拟试验l l该试验在各个蚂蚁在没有事先告诉它們食物在什该试验在各个蚂蚁在没有事先告诉它們食物在什么地方的前提下开始寻找食物。当一只找到食物以么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！过来，这样越来越多的蚂蚁会找到食物！l l但有些蚂蚁并没有像其它蚂蚁一样总重复同样的但有些蚂蚁并没有像其它蚂蚁一样总重复同样的

6、路，它們会另辟蹊径，如果令开辟的道路比原来的路，它們会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么更多的蚂蚁被吸引到这条较短其他道路更短，那么更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。一条最短的路径被大多数蚂蚁重复着。为为为为什什什什么么么么小小小小小小小小的的的的蚂蚂蚂蚂蚁蚁蚁蚁能能能能够够够够找找找找到到到到食食食食物物物物，它它它它們們們們具具具具有有有有智智智智能能能能么么么么？要要要要为为为为蚂蚂蚂蚂蚁蚁蚁蚁设设设设计计计计这这这这样样样样的的的的一一一一个个个个智智智智

7、能能能能程程程程序序序序，需需需需要要要要设设设设置置置置那些功能呢？那些功能呢？那些功能呢？那些功能呢？首首首首先先先先，我我我我们们们们要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁能能能能够够够够避避避避开开开开障障障障碍碍碍碍物物物物，就就就就必必必必须须须须根根根根据据据据适适适适当当当当的的的的地地地地形形形形给给给给它它它它编编编编进进进进指指指指令令令令让让让让它它它它們們們們能能能能够够够够巧巧巧巧妙妙妙妙的的的的避避避避开开开开障碍物；障碍物；障碍物；障碍物；其其其其次次次次，要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁找找找找到到到到食食食食物物物物，就就就就需需需需要要要要让让让让它它它它們們們

8、們遍遍遍遍历历历历空空空空间上的所有点；间上的所有点；间上的所有点；间上的所有点；再再再再次次次次，如如如如果果果果要要要要让让让让蚂蚂蚂蚂蚁蚁蚁蚁找找找找到到到到最最最最短短短短的的的的路路路路径径径径，那那那那么么么么需需需需要要要要计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。计算所有可能的路径并且比较它们的大小。这这个个试试验验程程序序的的每每个个蚂蚂蚁蚁的的核核心心程程序序编编码码不不过过100100多多行行。为为什什么么这这么么简简单单的的程程序序会会让让蚂蚂蚁蚁干干这这样样复复杂杂的事情？的事情？答案是：巧妙地利

9、用简单规则来实现集体智慧。答案是：巧妙地利用简单规则来实现集体智慧。每每只只蚂蚂蚁蚁并并不不是是像像我我们们想想象象的的需需要要知知道道整整个个世世界界的的信信息息，它它們們其其实实只只关关心心很很小小范范围围内内的的眼眼前前信信息息，而而且且根根据据这这些些局局部部信信息息利利用用几几条条简简单单的的规规则则进进行行决决策策，这这样样在在蚁蚁群群这这个个集集体体里里，复复杂杂性性的的行行为为就就会会凸凸现现出出来。这些规则就是下面所述的简单的来。这些规则就是下面所述的简单的6 6条规则条规则ACO 基本规则（一、二）l l范围：范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数蚂蚁观察到的

10、范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是为速度半径（一般是3 3），那么它能观察到的范围就），那么它能观察到的范围就是是3*33*3个方格世界。个方格世界。l l环境：环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。环境以一定的速率让信息素消蚁洒下的窝的信息素。环境以一定的速率让信息素消失。失。ACO 基本规则（三）l l觅食规则：

11、感知范围内寻找是否有食物，如果有就直接过去。感知范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，朝信息素多的地方走，并且哪一点的信息素最多，朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没不过它对窝的信息素做出反应，而对食物信息素没反应。反应。ACO 基本规则（四）l l移动规则：每只蚂蚁都朝向信息素最

12、多的方向移，并且，当周每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。点已经在最近走过了，它就会尽量避开。ACO 基本规则（五、六）l l避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机如果蚂蚁要移动的方向有障碍

13、物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会的选择另一个方向，并且有信息素指引的话，它会按照觅食按照觅食/找窝的规则行动。找窝的规则行动。l l播撒信息素规则：在不同的蚁群优化算法中，有的其中的蚂蚁每次在不同的蚁群优化算法中，有的其中的蚂蚁每次散播的信息素是一个常量，有的其中蚂蚁散播的信散播的信息素是一个常量，有的其中蚂蚁散播的信息素是一个变量，但是这些信息素都是动态变化并息素是一个变量，但是这些信息素都是动态变化并随时间逐渐消逝的。随时间逐渐消逝的。l l试验参数的说明试验参数的说明试验参数的说明试验参数的说明 l l最大信息素：蚂蚁在一开始拥有的信息素总量，最大信息素：蚂蚁

14、在一开始拥有的信息素总量，最大信息素：蚂蚁在一开始拥有的信息素总量，最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。越大表示程序在较长一段时间能够存在信息素。越大表示程序在较长一段时间能够存在信息素。越大表示程序在较长一段时间能够存在信息素。l l食物释放信息素的半径：在食物点和窝点附近都食物释放信息素的半径：在食物点和窝点附近都食物释放信息素的半径：在食物点和窝点附近都食物释放信息素的半径：在食物点和窝点附近都会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息素以便蚂蚁能更快的找到它们。会释放相应的信息

15、素以便蚂蚁能更快的找到它们。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。这个半径越大，则越容易被蚂蚁找到。l l信息素消减的速度：随着时间的流逝，已经存在信息素消减的速度：随着时间的流逝，已经存在信息素消减的速度：随着时间的流逝，已经存在信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么于世界上的信息素会消减，这个数值越大，那么消减的越快。消减的越快。消减的越快。消减的越快。l l错误概率：表示这个蚂蚁不往信息素最大的区

16、域错误概率：表示这个蚂蚁不往信息素最大的区域错误概率：表示这个蚂蚁不往信息素最大的区域错误概率：表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。走的概率，越大则表示这个蚂蚁越有创新性。走的概率，越大则表示这个蚂蚁越有创新性。走的概率，越大则表示这个蚂蚁越有创新性。l l速度半径：表示蚂蚁一次能走的最大长度，也表速度半径：表示蚂蚁一次能走的最大长度，也表速度半径：表示蚂蚁一次能走的最大长度，也表速度半径：表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。示这个蚂蚁的感知范围。l l记忆能力：表示蚂蚁能记住多少个刚刚走过点的记

17、忆能力：表示蚂蚁能记住多少个刚刚走过点的记忆能力：表示蚂蚁能记住多少个刚刚走过点的记忆能力：表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。坐标，这个值避免了蚂蚁在本地打转，停滞不前。坐标，这个值避免了蚂蚁在本地打转，停滞不前。坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。则蚂蚁越容易原地转圈。l l按钮：是把当前更改的所有蚂蚁的个体属性

18、应用按钮：是把当前更改的所有蚂蚁的个体属性应用按钮：是把当前更改的所有蚂蚁的个体属性应用按钮：是把当前更改的所有蚂蚁的个体属性应用到所有的蚂蚁身上。到所有的蚂蚁身上。到所有的蚂蚁身上。到所有的蚂蚁身上。l l实现的原理有两条路径通向食物 蚂蚁聚集到较短的路径l l现在的问题是蚂蚁究竟是怎么找到食物的呢？现在的问题是蚂蚁究竟是怎么找到食物的呢？现在的问题是蚂蚁究竟是怎么找到食物的呢？现在的问题是蚂蚁究竟是怎么找到食物的呢？l l在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信在没有蚂蚁找到食物的时候，环境没有有用的信息

19、素，那么蚂蚁为什么会相对有效的找到食物呢息素，那么蚂蚁为什么会相对有效的找到食物呢息素，那么蚂蚁为什么会相对有效的找到食物呢息素，那么蚂蚁为什么会相对有效的找到食物呢？l l这要归功于蚂蚁的移动规则，尤其是在没有信息这要归功于蚂蚁的移动规则，尤其是在没有信息这要归功于蚂蚁的移动规则，尤其是在没有信息这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。素时候的移动规则。素时候的移动规则。素时候的移动规则。l l首先，它要能尽量保持某种惯性，这样使得蚂蚁首先，它要能尽量保持某种惯性，这样使得蚂蚁首先，它要能尽量保持某种惯性，这样使得蚂蚁首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移

20、动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转；一个方向），而不是原地无谓的打转；一个方向），而不是原地无谓的打转；一个方向），而不是原地无谓的打转；l l其次，蚂蚁要有一定的随机性，虽然有了固定的其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像一个小球一样直线运动下去，方向，但它也不能像一个小球一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，来具

21、有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向。立即改变方向。l l这可以看成一种选择的过程，也就是环境的障碍这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁沿着是某个方向正确，而其他方向则不物让蚂蚁沿着是某个方向正确，而其他方向则不正确。在有一只蚂蚁找到了食物后，其他蚂蚁会正确。在有一只蚂蚁找到了食物后，其他蚂蚁会沿着信息素很快找到食物。沿着信息素很快找到食物。l l蚂蚁如何找到最短路径的？蚂蚁如何找到最短路径的？蚂蚁如何找到最短路径的？蚂蚁如何找到最短路径的？l l这一是要归功于信息素；二是要归功于环

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

23、从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。也无关紧要）。也无关紧要）。也无关紧要）。l l当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时间就短，这也意味着样，短的路蚂蚁来回一次的时

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

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

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

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

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

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

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

31、的行为过于僵硬，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。蚂蚁的行为过于僵硬，难以找到新的更佳的路径。用蚁群算法解决问题的步骤1.1.能够把待解决的问题用图的形式抽象表达出来；能够把待解决的问题用图的形式抽象表达出来；2.2.具体定义各种参数，如范围、信息素消逝函数等；具体定义各种参数，如范围、信息素消逝函数等；3.3.为算法中的蚂蚁制定相应的移动规则；为算法中的蚂蚁制定相应的移动规则；4.4.选择一种适应的蚁群优化算法并将其合理地应用选择一种适应的蚁群优化算法并将其合理地应用到自己的问题解决方案中去；到自己的问题解决方案中

32、去；5.5.适当调整所应用的蚁群算法中的对应参数以达到适当调整所应用的蚁群算法中的对应参数以达到较好的实验效果较好的实验效果.2.应用蚁群算法求解应用蚁群算法求解TSP问题问题设设mm为蚁群中蚂蚁的数量，为蚁群中蚂蚁的数量，n n 为旅行商要走过的城市数为旅行商要走过的城市数,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 连线上残留的信息量，初始时连线上残留的信息量，初始时刻

33、各条路径上的信息量相等，即刻各条路径上的信息量相等，即 ij ij(1)=C(1)=C（C C为常数）。为常数）。为信息残留系数，则为信息残留系数，则-1-1表征了从时刻表征了从时刻t t到到 t+n t+n在路在路径径ij ij上残留信息的挥发程度。表示第上残留信息的挥发程度。表示第k k只蚂蚁在本次循只蚂蚁在本次循环中留在路径环中留在路径 ij ij 上的信息量。上的信息量。如果在时间间隔如果在时间间隔(t,t+1)(t,t+1)中，中，m m 个蚂蚁都从当前城个蚂蚁都从当前城市选择下一个城市，则经过市选择下一个城市，则经过 n n 个时间间隔，所有蚂个时间间隔，所有蚂蚁都走完蚁都走完n

34、n个城市，构成一轮循环，此时，按如下方个城市，构成一轮循环，此时，按如下方法修改各条路径上的残留信息：法修改各条路径上的残留信息：（1）Ant-Circle System模型Q 为常量，Lk 为第 k 只蚂蚁在本次循环中所走路径的长度。（2）Ant-Quantity System模型（3）Ant-Density System模型4.2.2 flock算法算法FlockFlock算法是由算法是由算法是由算法是由Craig ReynoldsCraig Reynolds于于于于19871987年在一篇为年在一篇为年在一篇为年在一篇为SIGGRAPHSIGGRAPH所写的论文所写的论文所写的论文所写的

35、论文“Flocks,Herds,and“Flocks,Herds,and Schools:A Distributed Behavioral Model”Schools:A Distributed Behavioral Model”中首中首中首中首次提出的一种集智技术。这种技术有次提出的一种集智技术。这种技术有次提出的一种集智技术。这种技术有次提出的一种集智技术。这种技术有3 3个简单的规则，个简单的规则，个简单的规则，个简单的规则，当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（当它们组合在一起时，为自治主体（boidboid）群给出）群给出）群

36、给出）群给出了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真了一个类似于鸟群、鱼群或蜂群的群体行为的逼真表现形式。这些被表现形式。这些被表现形式。这些被表现形式。这些被ReynoldsReynolds称之为定向行为称之为定向行为称之为定向行为称之为定向行为（Steering BehaviorsSteering Behaviors）。）。）。）。4.2.2 flock算法算法定向行为的规则：定向行为的规则：分离：定向时要避免与本地分离：定向时要避免与本地分离：定向时要避免与本地分离：定向时要避免与本地flockf

37、lock同伴拥挤同伴拥挤同伴拥挤同伴拥挤列队：驶向本地列队：驶向本地列队：驶向本地列队：驶向本地flockflock同伴的平均航向同伴的平均航向同伴的平均航向同伴的平均航向 聚合：定向时朝着本地聚合：定向时朝着本地聚合：定向时朝着本地聚合：定向时朝着本地flockflock同伴的平均位置移同伴的平均位置移同伴的平均位置移同伴的平均位置移动动动动 分离列队聚合l l分离规则分离规则分离规则分离规则给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保给了一个主体试图与其它邻近的主体保持一定的距离的能力。确保主体之间以一个持一定的距离的能力。确保主体

38、之间以一个持一定的距离的能力。确保主体之间以一个持一定的距离的能力。确保主体之间以一个“看看看看似自然似自然似自然似自然”的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体，以的接近度，模拟真实世界中的群体，以避免主体拥挤在一起。避免主体拥挤在一起。避免主体拥挤在一起。避免主体拥挤在一起。l l队列规则队列规则队列规则队列规则为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队为一个主体提供了与其他邻近主体列队的能力（即与其他邻近主体航向或速度相同）。的能力（即与其他邻近主体航向或速度相同）。的能

39、力（即与其他邻近主体航向或速度相同）。的能力（即与其他邻近主体航向或速度相同）。与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个与分离类似，本文将队列说明为：通过每一个flockflock成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速成员观察邻近同伴，然后调整它的航向和速度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。度以与其邻近同伴的平均航向和速度相匹配。l l聚合规则聚合规则聚合规

40、则聚合规则给了一个主体与其他邻近主体给了一个主体与其他邻近主体给了一个主体与其他邻近主体给了一个主体与其他邻近主体“聚合聚合聚合聚合（groupgroup）”的能力，从而模拟自然界的类似行的能力，从而模拟自然界的类似行的能力，从而模拟自然界的类似行的能力，从而模拟自然界的类似行为。为。为。为。l lReynoldsReynolds在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被在稍后的实现和论文中又增加了有时被称作称作称作称作flocking“flocking“第四规则第四规则第四规则第四规则”的规则。的规则。的规则。的规则。躲避：使避免撞

41、上局部区域的障碍和敌人 l l躲避规则的作用是为主体提供了使它绕过障碍和躲避规则的作用是为主体提供了使它绕过障碍和躲避规则的作用是为主体提供了使它绕过障碍和躲避规则的作用是为主体提供了使它绕过障碍和避免碰撞的能力。这种控制行为是这样完成的：避免碰撞的能力。这种控制行为是这样完成的：避免碰撞的能力。这种控制行为是这样完成的：避免碰撞的能力。这种控制行为是这样完成的：通过赋予每个主体通过赋予每个主体通过赋予每个主体通过赋予每个主体“向前看向前看向前看向前看”一段距离的能力，一段距离的能力，一段距离的能力，一段距离的能力，决定与一些对象的碰撞是否可能，然后调整航向决定与一些对象的碰撞是否可能，然后调

42、整航向决定与一些对象的碰撞是否可能，然后调整航向决定与一些对象的碰撞是否可能，然后调整航向以避免碰撞。以避免碰撞。以避免碰撞。以避免碰撞。l lFlockFlock技术通过这四个简单的规则最终模拟出逼真技术通过这四个简单的规则最终模拟出逼真技术通过这四个简单的规则最终模拟出逼真技术通过这四个简单的规则最终模拟出逼真的群体行为，更有意思的是这种移动算法本身是的群体行为，更有意思的是这种移动算法本身是的群体行为，更有意思的是这种移动算法本身是的群体行为，更有意思的是这种移动算法本身是无状态的：在移动更新中，不记录任何信息。无状态的：在移动更新中，不记录任何信息。无状态的：在移动更新中，不记录任何信

43、息。无状态的：在移动更新中，不记录任何信息。l l在每次更新循环中，每只在每次更新循环中，每只boidboid都将重新评估其环都将重新评估其环境。这样不但降低了内存需求，同时让物群能够境。这样不但降低了内存需求，同时让物群能够对不断变化的环境状况做出实时的反应。因此，对不断变化的环境状况做出实时的反应。因此，物群将具备突发行为的（物群将具备突发行为的（Emergent BehaviorEmergent Behavior）特）特性，即物群中的所有成员都对要前往何方一无所性，即物群中的所有成员都对要前往何方一无所知，但作为一个整体行动，避开障碍物和天敌，知，但作为一个整体行动，避开障碍物和天敌，并

44、保持若即若离。并保持若即若离。4.3 集智系统介绍4.3.1 人工鱼4.3.2 Terrarium世界4.3.1 人工鱼人工鱼群体是一种典型的多智能主体（Multiple Intelligent Agent）的分布式人工智能系统（distributive artificial intelligent system）。中国青年学者涂晓媛研究开发的新一代计算机动画“人工鱼”被学术界称之为“晓媛鱼”（Xiaoyuans fish），她发表的论文“人工动物的计算机动画”(artificial animals for computer animation:biomechanics,locomotion,

45、perception and behavior)，在1996年获国际计算学会ACM最佳博士论文奖。l l涂晓媛研究开发的涂晓媛研究开发的“人工鱼人工鱼”构成了栖息在虚拟构成了栖息在虚拟海底世界中人工鱼群的社会，其中，每条海底世界中人工鱼群的社会，其中，每条“人工人工鱼鱼”都是一个自主的智能体（都是一个自主的智能体（autonomous autonomous intelligent agentintelligent agent），都可以独立地活动，也可以），都可以独立地活动，也可以相互交往。每条鱼都表现出某些人工智能，如：相互交往。每条鱼都表现出某些人工智能，如：自激发（自激发（self-ani

46、matingself-animating）、自学习（）、自学习（self-self-learninglearning）、自适应（）、自适应（self-adaptingself-adapting）等智能特性）等智能特性.l l会产生相应的智能行为，如：因饥饿而激发寻食、会产生相应的智能行为，如：因饥饿而激发寻食、进食行为；有性欲而激发求爱行为；能吸取其他进食行为；有性欲而激发求爱行为；能吸取其他鱼被鱼钩钓住的教训，而不去吞食有钩的鱼饵；鱼被鱼钩钓住的教训，而不去吞食有钩的鱼饵；能适应有鲨鱼的社会环境，逃避被捕食的危险等。能适应有鲨鱼的社会环境，逃避被捕食的危险等。人工鱼群的社会具有某些自组织（人

47、工鱼群的社会具有某些自组织（self-self-organizingorganizing）能力和智能集群行为，如：人工鱼群）能力和智能集群行为，如：人工鱼群体在漫游中遇到障碍物等，会识别障碍改变队形，体在漫游中遇到障碍物等，会识别障碍改变队形，绕过障碍后，又重组队列，继续前进。绕过障碍后，又重组队列，继续前进。4.3.1 人工鱼l l1.1.人工鱼与动画鱼人工鱼与动画鱼区别：区别：l l “人人工工鱼鱼”具具有有“人人工工生生命命”和和自自然然鱼鱼的的某某些些生生命命特征。特征。l l 在在一一般般的的计计算算机机动动画画中中，创创作作者者需需要要在在动动画画设设计计和和程程序序编编制制中中确

48、确定定动动画画鱼鱼的的所所有有动动作作的的细细节节，预预先先知知道道动动画画鱼鱼的的全全部部动动作作过过程程。然然而而，人人工工鱼鱼的的创创作作者者并并不不去去设设计计和和规规定定每每条条鱼鱼的的动动作作和和行行为为的的细细节节，也也不不能能预预知知人人工工鱼鱼群群中中可可能能发发生生的的各各种种具具体体动动作作和和实实际行为。际行为。4.3.1 人工鱼2.“人工鱼人工鱼”与与“人工生命人工生命”涂晓媛所说的涂晓媛所说的“人工生命人工生命”（artificial lifeartificial life）是）是指具有指具有“自然生命自然生命”特性和功能的人造系统，或者特性和功能的人造系统，或者说

49、是说是“人造活体人造活体”。人工生命的研究方法和技术途径，可以分：人工生命的研究方法和技术途径，可以分：l l生命科学途径生命科学途径 l l工程技术途径工程技术途径 4.3.1 人工鱼3.“3.“人工鱼人工鱼人工鱼人工鱼”的创作的创作的创作的创作 “人工鱼人工鱼”的动画创作方法和技术，已经突破了的动画创作方法和技术，已经突破了传统的计算机动画的框架。传统的计算机动画的框架。首先首先，“人工鱼人工鱼”不仅有逼真于不仅有逼真于“自然鱼自然鱼”的外的外形和彩色，而且具有类似于形和彩色，而且具有类似于“自然鱼自然鱼”的运动和姿的运动和姿态。态。其次其次，“人工鱼人工鱼”不仅具有不仅具有“自然鱼自然鱼

50、”的形态，的形态，而且具有而且具有“自然鱼自然鱼”类似的生命特性类似的生命特性“活性活性”。再次再次，“人工鱼人工鱼”是具有人工智能的是具有人工智能的“灵巧鱼灵巧鱼”，而传统的，而传统的“动画鱼动画鱼”是程序化的是程序化的“木偶鱼木偶鱼”。最后最后，“人工鱼人工鱼”是具有各种不同的人工鱼的鱼是具有各种不同的人工鱼的鱼群社会群社会 。l l“人工鱼人工鱼”的形态（外形、颜色、姿态）和的形态（外形、颜色、姿态）和“自然自然鱼鱼”非常相似，几乎达到了非常相似，几乎达到了“以假乱真以假乱真”的程度。的程度。在一次国际会议上，涂晓媛演示了在一次国际会议上，涂晓媛演示了“人工鱼人工鱼”的的录像，人们看到屏