【2022精品课件】几种智能算法的原理和应用介绍专题培训课件.pptVIP

2.1 蚂蚁的生理学特征 蚂蚁在8000万年前就建立起了自己的社会。许多“蚂蚁城市”往往由5000万个成员组成，并且是一个组织完好的复杂“城市”。 蚂蚁的群体行为主要包括寻找食物、任务分配和构造墓穴。 研究中主要是以蚂蚁寻找食物之后能选择一条最短路径来连接蚁穴和食物源。 蚂蚁具有智能么？ 生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固的蚁穴，依靠群体的能力发挥出了超出个体的智能。 * 精品课件资料 2.2 Deneubourg双桥实验 Pasteels，Deneubourg和Goss（1987）全部都在实验中研究真实蚂蚁信息素的遗留行为，他们称之为“双桥实验”。在这个双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相等的桥连接。作者使用能够辨认路径的阿根廷蚂蚁，简而言之这些蚂蚁可以预测或者搜索他们的群类。 * 精品课件资料 2.2 Deneubourg双桥实验 等长双桥实验 在前面的设定下，蚂蚁开始探索蚁穴周围的环境最终到达食物源。沿着他们的在蚁穴和食物源之间的路径，阿根廷释放信息素，开始每个蚂蚁都随机选择两条桥之间的的一个，在随后的阶段里因为随机的波动，其中一个桥的信息素表现出比另外一条的信息素更为集中，因此吸引了更多的蚂蚁。这个行为增加了这个桥上的信息素，也就吸引了更多的蚂蚁。因此，过了一段时间以后，整个种群都聚合于使用这个高度集中的桥运送。 * 精品课件资料 2.2 Deneubourg双桥实验 Goss，Aron，Deneubourg和Pasteel（1989）提出上述双桥实验的变种，在其中一个桥要比另一个桥更长，如下图所示；在这种情况下，蚂蚁选择了近的路径首先到达了蚁穴。因此，短桥比长桥得到了更为密集的信息素增长了蚂蚁选择短桥的的可能性。Goss，Aron，Deneubourg和Pasteel（1990）将观察的的真实的蚂蚁建立到假设的模型中。首先，假设桥上残留的信息素量和过去一段时间经过该桥的蚂蚁数成正比(信息素挥发的情况);其次某一时刻蚂蚁按照桥上信息素量的多少来选择某支桥，即蚂蚁选择某支桥的概率与经过该桥的蚂蚁数成正比。当所有的m只蚂蚁都经过两支桥以后，设Am和Bm分别为经过A桥和B桥的蚂蚁数(Am+Bm=m)，则第m+1只蚂蚁选择A(B)桥的概率为: * 精品课件资料 2.2 Deneubourg双桥实验 公式表明：往A走的蚂蚁越多，选择分支A的概率就越高。 n和k用以匹配真实实验数据。 “n”决定选择公式的非线性程度。（n越大，信息素多一点的分支选择概率越高） “k”表示对未标记的分支的吸引程度。（k越大，则进行非随机化选择所需的信息素浓度越高） 这种概率的表达方式是实际的蚂蚁路径选择实验推导而来的，比较符合实验的参数设置是n=2和k=20. * 精品课件资料 2.3 蚁群算法的定义 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。 这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种新型的启发式优化算法。 人工蚁群与真实蚂蚁的异同比较： 相同点： （1）都存在一个群体中个体相互交流通信的机制 （2）都要完成一个相同的任务 （3）利用当前信息进行路径选择的随机选择策略 不同点： （1）人工蚂蚁他们的移动是从一个状态到另一个 状态的转换 （2）人工蚂蚁具有一个记忆其本身过去行为的内在状态 （3）人工蚂蚁存在于一个与时间无关联的环境之中 （4）人工蚁不是盲从的，受环境空间的启发 （5）人工蚁可以根据要求增加功能 * 精品课件资料 2.4 蚁群算法的原理 蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物——信息素来寻找路径。当它碰到一个还没有走过的路口是就随机的选择一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口时，选择信息量较大的路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上得信息量越来越大，而其他路径上的信息量却随时间逐渐减少最终整个蚁群会找出最优路径。 （1）蚁群之间通过信息素和环境进行通信。 （2）蚂蚁对环境的反应由其内部模式决定。 （3）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的行为是随机的。 蚁群算法的理论假设 * 精品课件资料 2.5 蚁群算法的规则 蚁群算法中的蚂蚁满足的规则主要有以下几个方面： 蚂蚁