好算法噢

RispringWa · 发表于 2005-8-15 01:51:23

<

>这是新算法，很有用的
<H1 > 蚂蚁算法</H1>
<H2 >蚂蚁觅食时，在它走过的路上，留下外激素，这些外激素就象留下路标一样，留给后来“蚁”一个路径的标志。后面的蚂蚁，就会沿着有外激素的路径行走（外激素越多引诱蚂蚁的能力就越强）。科学家们对此进行过试验：用人造的外激素在纸上画上一条路径，对蚂蚁进行试验。结果蚂蚁果然都沿画有外激素的路径行走。</H2>
<

> 
<

> 
 
 
 
 B
<v:line></v:line><v:line></v:line><v:line></v:line><v:line><v:stroke endarrow="block"></v:stroke></v:line> 
 
 D
 蚁穴
<v

val></v

val> A C
<v:line><v:stroke endarrow="block"></v:stroke></v:line><v:line></v:line><v:line></v:line><v

val></v:oval>食物
 
蚂蚁寻食时，由蚁穴出发，可沿AC，也可沿ABC（见上图），设各蚂蚁寻到食物后沿原路回穴，并在路上留下外激素，那么因AC路径短，故当它们沿AC返回时，就在AC上留下两次外激素。而沿ABC返回者，因其路径长，仅回到D点，于是AD一段只留过一次外激素（即其上的外激素的浓度比AC上的浓度淡），故这时从蚁穴出来寻食者就会沿浓度大的路径AC行走。…..最后大多数的蚂蚁都会沿较短的路程进行寻食. 利用这个原理科学者们就设计了蚂蚁算法(进行求最短程).
上面是个简单的原理,当然要设计出切实可行的算法,还要将模型进一步精确,如要计及外激素的挥发(即激素的浓度将随时间而逐步降低等等).
 
 科学家根据这个现象，设计了一个寻找最优路径的“蚂蚁算法”。
<H2 > </H2>
<H1 >用蚂蚁算法求最短程</H1>
<H2 >1.一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回</H2>
<H2 >2. 蚂蚁在往返途中，在路上留下外激素标志。</H2>
<H2 >3. 外激素将随时间逐渐蒸发（一般可用负指数函数来描述，即乘上因子e-at）</H2>
 4. 由蚁穴出发的蚂蚁,其选择路径的概率与各路径上的外激素浓度成正比.
 
利用同样原理可以描述蚁群进行多食物源的寻食情况
有研究者将上述的蚂蚁算法应用于：
 
<H1 >3.1.1 用于重建通讯路由</H1>
 
<H1 >3.1.2. 用于求解TSP（流动货郎问题，即求一周游所有指定的城市，最后回到出发点的最短路径）（其算法可简述如下）</H1>
<H2 >•一群蚂蚁由A点同时出发，进行漫游，倾向选较近的城市</H2>
<H2 >•把所有城市都游过后，返回， 并留下外激素，其量与路程长度成反比</H2>
<H2 >•所有蚂蚁都返回后，图上留下外激素的标志</H2>
<H2 >•进行第二轮的漫游（倾向选激素多的路径）……..</H2>
<H1 >例：有人用蚂蚁算法求美国二十四个城市的TSP问题的解（蚂蚁算法的解）</H1>
 
<H1 >3.1.3. 蚂蚁清除垃圾</H1>
<H2 >蚂蚁能将巢里的垃圾或死蚂蚁,打扫成几大堆给以清除</H2>
<H2 > </H2>
<H1 >仿照蚂蚁这种功能,设计蚂蚁的分类算法（算法的大意如下）</H1>
<H2 >•一群蚂蚁随机出发,遇到垃圾,就将其拉走（方向也是随机的）</H2>
<H2 >•拉垃圾时,若碰到某一堆垃圾时,就放下.</H2>
放下垃圾后, 再随时机进行打扫工作……
<H1 >例</H1>
<H2 >•美国MCIWorld-com公司一直研究人工蚂蚁，用于管理公司的电话网；对用户记帐收费等工作.</H2>
<H1 >3.1.4. 蚂蚁搬大食物</H1>
<H2 >•一群蚂蚁同心协力搬大食物</H2>
<H2 >•可用来设计多机器人合作规划问题</H2>
<H2 >•算法:</H2>
<H3 >– 一群蚂蚁随机出发找食物</H3>
<H3 >– 遇到大食物, 先调整方向（使食物处在自己和目标之间）</H3>
<H3 >– 推动食物</H3>
<H3 >– 群体推动,计算其合力……</H3>
<H1 >例</H1>
<H2 >•阿尔伯塔大学设计几个小机器人共同推盒子的实验</H2>
 
<H1 >3.1.5. 任务分配问题</H1>
<H2 >在蚁群中, 蚂蚁的职责分工明确（蚁皇、工蚁、兵蚁）各司其职. 利用蚂蚁这个功能,人们设计了求解分配问题的蚂蚁算法，并应用于：</H2>
<H2 >用于求解任务分配问题：汽车喷漆问题</H2>
<H3 >– 分成各小组只喷一种颜色</H3>
<H3 >– 当某小组任务特别紧时，才分配另一小组，改喷其他颜色</H3>
<H1 >例</H1>
<H2 >•美国西北大学研究人工蚂蚁算法用于卡车厂中， 油漆车间负责给离开装配线的卡车上漆。</H2>
<H2 >•使工厂各车间改变颜色的次数更少。</H2>
 
3.2 群体智能
 上面我们介绍了，利用蚂蚁觅食和合作搬物体的功能设计出的对应的蚂蚁算法，本小节我们将介绍，我们最近利用分形几何的理论和方法，研究蚂蚁筑巢功能的模型。据我们所知目前国内外尚未见到对蚂蚁筑巢功能的建模研究的成果。目前研究群体智能的方法多是从多Agent系统的观点来进行的。
3.2.1. 多Agent观点
 利用多Agent系统的观点，来研究群体智能系统。
<H3 >将人类社会中的一些性能移植到群体智能中去，比如假定每个Agent都具有“意志”、“信念”等等，各Agent之间既有合作又有竞争，还要遵守各种协议等。然后研究这种系统的性质。</H3>
我们认为这种方法对研究象人类这样的大群体的性能也许是适合的，但用这种方法来研究象蚂蚁这样的群体也许是用“牛刀杀鸡（蚂蚁）”也许是不适合的，若将每个蚂蚁都看成一个Agent也具有“意志”、“信念”等，这就把本来是很简单的问题大大复杂化了，得不偿失。
我们对群体智能的研究，别开生面，从生物进化的观点研究群体智能，提出生物进化观点。
 
<H2 >3.2.2 进化的观点</H2>
 我们别开生面,从进化的过程来理解群体智能的现象, 我们认为1。人与蚂蚁都是从共同的祖先进化来的，一支进化成高等动物（包括人及其大脑），一支进化成群居昆虫，如蚁群等,故其中必有共同之处。
<H3 >2． 人的智能是人的脑袋的功能的表现, 那么将群体（如蚁群）看成是离散的脑袋（脑袋可看成是连接的群体），那么，它具有“智能”就不奇怪了。</H3>
<H3 >3． 既然人的智能的某些性能（即脑袋的某些性能），能用人工神经网络来模拟；那么“离散的脑袋”（如蚁群）也就可以用离散的人工神经网络来模拟。这就是我们的新观点。</H3>
<H1 >根据群体智能的进化的观点，我们提出：随机（连接）神经网络的群体智能模型。</H1>
 具体地说，就是将每个蚂蚁看成是一个神经元，它们之间的通讯联络，看成是各神经元之间的连接，只不过这时的连接不是固定的，而是随机的。即用一个随机连接的神经网络来描述一个群体。这种神经网络所具有的性质，就是群体的智能。
<H2 >我们用蚂蚁和蜜蜂筑巢为兰本，来建立这种模型</H2>
<H2 >在数学上我们利用分形几何中的函数迭代系统的理论建立蚂蚁（蜜蜂）筑巢的数学模型，并证明了，任给一个三维空间中的集合（可测集）S，和精度e，必能找到一个蚁群，它们能筑成蚁穴S’,且S与S’的对称差的测度<e.（粗略地说就是S与S’差<e）.</H2>
 
<H2 >3.2.3 计算机模拟的结果</H2>
 利用我们提出的新观点，对蚂蚁筑巢行为和蜜蜂筑巢进行模拟，其结果如下
<H2 >例一: 蚂蚁筑巢(三维的巢穴)</H2>
<H2 >•完成第一层巢穴（三向投影图） 第二层完成一半的情况</H2>
<H2 > </H2>
<v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock aspectratio="t" v:ext="edit"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape><v:shape><v:imagedata></v:imagedata></v:shape> 
 
 
 
 
 
 
<H2 > </H2>
<H1 > </H1>

amao · 发表于 2005-8-15 04:51:43

这个比较有趣。

zsy7758 · 发表于 2005-8-16 01:43:43

<

>很好玩哦

娴子 · 发表于 2005-8-16 02:25:12

<

>悲哀啊？我怎么就看不懂呢？5555

RispringWa · 发表于 2005-8-16 19:01:20

谢谢支持！！！

凌云 · 发表于 2005-8-16 23:43:32

<

>精彩

txdiniu · 发表于 2005-8-17 06:31:06

<

>很有新意很好

redmagic · 发表于 2005-8-17 10:20:53

神奇的大自然[em07]

zhenxiayu · 发表于 2005-8-17 23:05:39

呵呵，挺有意思的！

yifeng_200 · 发表于 2005-8-18 00:34:31

感谢了，很棒

		自动登录	找回密码
密码			注-册-帐-号