部分用群集智能求解问题.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 跟着蚂蚁的踪迹,我们能够发现什么呢?通过跟着蚂蚁的踪迹,我们能够发现什么呢?通过跟着蚂蚁的踪迹,我们能够发现什么呢?通过跟着蚂蚁的踪迹,我们能够发现什么呢?通过上面的原理叙述和实际操作,我们不难发现蚂蚁上面的原理叙
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 部分 群集 智能 求解 问题
限制150内