Video在线视频

大家好

这一节我们介绍

算法设计方法之仿生

仿生学是利用生物的结构

和功能原理来研制

机械或各种新技术的科学技术

它是要在工程上实现

并有效地

应用生物功能的一门学科

比如

将海豚的体形或皮肤结构

应用到潜艇的设计上

再比如

在人类研究鸟类飞行

造出飞机后

当飞机飞行时

机翼会发生颤振现象

飞得越快

机翼的颤振越强烈

甚至会使机翼折断

生物学家在研究蜻蜓翅膀时

发现在每个翅膀前沿的上方

有一块深色的角质加厚区

称之为“翼眼”

实验证明

正是翼眼的角质组织

使蜻蜓飞行的翅膀

消除了颤振的危害

这一发现

被用到飞机上

在飞机两翼末端的前沿

制成翼眼一样的平衡棒

它就能够保持

飞机在飞行中的平衡了

自从人类发明了电灯

生活变得方便多了

但电灯只能将电能的很少一部分

转变成可见光

其余大部分

都以热能的形式浪费掉了

那么

有没有只发光不发热的光源呢

在自然界中

有许多生物都能发光

比如细菌 真菌 软体动物

昆虫等等

而且这些动物发出的光

都不产生热

所以又被称为“冷光”

特别是萤火虫发出的冷光

不仅具有很高的发光效率

而且发出的冷光还很柔和

适合人类的眼睛

光的强度也比较高

人们根据这个原理

研制出了日光灯

使人类的照明光源

发生了很大的变化

蚂蚁

是大家司空见惯的一种昆虫

它们的群体合作精神

比如觅食 御敌

筑巢之精巧令人惊叹

人类能够建高楼大厦

并不觉得惊奇

但蚂蚁能筑巢

却让人感到非常惊讶

人和蚂蚁

都是从低等的单细胞生物

进化而来的

一个蚁群

就像一个人的大脑

两者的差异在于

后者（大脑）是连通的

前者（蚁群）是离散的

一个蚂蚁

就相当于大脑中的一个细胞

或者神经元

蚂蚁之间的信息交流

就相当于

人脑中各个细胞之间的连接

有人正是以这种认知为出发点

提出了“群体智能”之概念

及其数学模型

并研究其基本的性质

具体来说

20世纪90年代初

一个意大利学者(Marco Dorigo)

在他的博士论文中

首次提出了蚁群算法

他就是依照蚂蚁觅食原理

设计的一个群体智能算法

小小的蚂蚁

它怎么能找到食物

它们具有什么样的智能呢

据研究

当蚂蚁找到并搬运食物时

会在其经过的路上

撒下“信息素”

也就是一种激素

其他蚂蚁

嗅到该激素的“味道”

就会沿路觅食而去

事实上

每只蚂蚁并不需要知道

整个世界的信息

它们关注的范围其实很小

并且只利用几条简单的规则

进行决策

但就是这样

在蚁群这个集体里面

复杂性的行为就会凸现出来

那么

这些简单规则是什么呢

一 蚂蚁能观察到的范围

可看作是这样一个

3乘3的方格世界

二 蚂蚁所处的环境中

有障碍物

有别的蚂蚁

还有信息素

信息素有两种

一种是找到食物的蚂蚁

洒下的食物信息素

一种是找到窝的蚂蚁

洒下的蚁窝信息素

这些信息素

会以一定的速度消失

每个蚂蚁仅能感知

它所在范围内的环境信息素

三 每只蚂蚁

在感知的范围内

寻找是否有食物

如果有 就直接过去

否则 看是否有信息素

并且比较在能感知的范围内

哪一点的信息素最多

通常朝信息素多的地方走

当然偶尔也有例外

四 当周围没有信息素指引的时候

每只蚂蚁几乎都按照

自己原来运动的方向

惯性地往前走

只是偶尔有例外

为了防止原地转圈

蚂蚁会记住

最近刚走过了哪些点

如果发现要走的下一个点

已经在最近走过了

它会尽量地避开

五 如果前方有障碍物挡住去路

蚂蚁会随机地选择另一个方向

当然 如果有信息素指引的话

它会选择信息素多的方向走

六 每只蚂蚁在刚找到食物

或者蚁窝的时候

播撒的信息素最多

并随着它越走越远

播撒的信息素就越来越少

根据这么几条规则

蚂蚁之间虽然没有直接的关系

但是每只蚂蚁都和环境发生交互

而通过信息素这个纽带

实际上把各个蚂蚁之间

联系起来了

比如 当一只蚂蚁找到了食物

它并没有直接告诉其他蚂蚁

这儿有食物

而是向环境播撒信息素

当其他的蚂蚁经过它附近的时候

就会感觉到信息素的存在

进而根据信息素的指引

找到食物

蚂蚁究竟是怎么找到食物的呢

在没有蚂蚁找到食物的时候

环境没有有用的信息素

那么蚂蚁为什么

能相对有效地找到食物呢

首先 它要尽可能地保持

某种向前移动的惯性

当然 开始的时候

这个方向是随机的

否则会原地打转或者摆动

其次 蚂蚁偶尔也会改变

原来的运动方向

不会那么死板地直线往前走

尤其当碰到障碍物的时候

它会立即改变方向

这样蚂蚁既具有一定的目的性

又会有新的试探

这就解释了为什么单个蚂蚁

在复杂的环境中

仍然能找到

隐蔽得很好的食物的原因

当然

在有一只蚂蚁找到食物的时候

其他蚂蚁

会沿着信息素很快找到食物

那么蚂蚁又是如何

找到最短路径的呢

这要归功于信息素

信息素多的地方

显然经过这里的蚂蚁就多

因而就会有更多的蚂蚁聚集过来

我们假设有两条路

从蚁窝通向食物

开始时走这两条路的蚂蚁

数量一样多

当蚂蚁沿着一条路到达终点以后

它会马上返回来

这样 路程较短的路

蚂蚁来回一次的时间就短

因而在单位时间里

走过的蚂蚁数目就多

撒下的信息素自然也会多

自然就会有更多的蚂蚁

被吸引过来

从而撒下更多的信息素

而路程较长的路径则相反

这样最短的路径就近似找到了

比如假设有两只蚂蚁从O点出发

都在A点找到食物

且都沿原路返回

从这个图中可以看出

OA比OBA短

当第一只蚂蚁回到O点时

第二只沿路径OBA

往回走的蚂蚁

才回到C点

于是OA路上

有两次信息素的遗留物

因为去一次 回来一次

而在OC路上

只有去一次的信息素遗留物

所以OA的信息（素）浓度

比OC这条路径上的

信息（素）浓度要大

由于蚂蚁会沿

信息素浓度大的路径上前行

于是后面的蚂蚁

就会选择路径OA

而不是OBA

蚁群算法可用以解决

某些实际问题

比如求解144个城市的

最短回路问题

求得的解

与其它方法求到得解一样精确

借助蚂蚁分工合作的特点

比如蚁皇管生男育女

工蚁管干活

兵蚁管保卫

这样的启迪

美国西北大学设计了

求解任务分配问题的蚂蚁算法

并应用于工厂中汽车喷漆的问题

提高了生产效率

另外

蚁群算法还在车辆路线问题

车间任务调度问题

机械设计领域普遍存在的

机构同构判定问题

网络路由优化等方面

都有不少成功的应用实例

好 这一节就讲到这儿

谢谢大家