群体智能仿真之简单蚁群算法

2024-04-24 19:48

本文主要是介绍群体智能仿真之简单蚁群算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在生活中我们或多或少都会看到过蚂蚁,面对这个奇怪的家伙我们平时并不怎么关注它,但偶尔也会发现这个东西的神奇之处,为什么它们能成群结队的搬家,它们为什么能在群体中如此密切的配合行动,分工明确而不会乱成一团。
这就是我们要探讨的问题,这要从蚁群算法开始说起,蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这是百度百科中对蚁群算法的简短描述,那么要想了解一个事物就要从他的本质开始了解。所以我就查找了一些相关的资料。首先我们知道蚂蚁是一种昆虫,而且蚂蚁的种类繁多,世界上已知有11700多种。这个就不做过多的描述了,到处都可以查得到。而蚂蚁算法的由来是从蚂蚁的社会形态中得到启发的。我们知道蚂蚁在8000万之前就建立了自己的社会,而我们人类的只有5000余年的文明史,可是我们经常会发现,小小的蚂蚁却能建立起组织完好的复杂城市,也就所谓的蚁穴。有许多“蚂蚁城市”往往由5000万个成员组成,而对比我们人类社会,人口稠密的大城市也不过1000多万人,但是却有不少的都市问题。
接下来我们了解下蚂蚁的分工,蚂蚁有四种不同的蚁型,即蚁后、雄蚁、工蚁和兵蚁,不同的蚁型有不同的分工,那么这些蚂蚁之间是怎么进行交流的呢?化学通信是蚂蚁采取的基本信息交流方式,自然界中的蚂蚁会分泌一种化学刺激物——信息素(pheromone)。这是一种很重要的东西,也是接下来算法中的一个很重要的条件。蚂蚁的许多行为受信息素调控,如蚁后分泌名为“女皇物质”的信息素来控制工蚁的发育。说到信息素我们开始进入正题了,在自然界中,尽管蚂蚁个体比较简单,但是整个蚂蚁群体却表现得高度机构化,在许多情况下可以完成许多复杂的任务,这种能力来源于蚂蚁群体中的个体协作行为,其群体行为主要包括寻找食物、任务分配和构造墓地。
那么我们主要来浅谈一下寻找食物,在自然界中,蚂蚁的食物来源总是随机散布于蚁巢周围。我们只要仔细观察就可以发现,经过一段时间之后,蚂蚁总能找到一条从蚁巢到食物的最短路线,这条路上蚂蚁都整整齐齐的排着队,在路线上来回运动。


 下面我们用几幅图来说明一下


如图a所示可以看到蚂蚁和事物源之间是一条直线;当食物和巢穴之间出现一个障碍物的时候如图b所示,我们可以看到各只蚂蚁之间的分布是均匀的,不管路径长短,蚂蚁总是按同等概率选择各条路径;蚂蚁在运动的过程中能留下信息素,而且能感知这种物质的存在及其强度,并倾向于信息素浓度高的方向运动的概率也会比浓度低的方向概率要高,也就形成了如图c所示的现象障碍物较短的一边蚂蚁比较多,因为路径比较短来回的蚂蚁所用的时间比较短次数多留下的信息素浓度比较高,也就慢慢的吸引了其他更多的蚂蚁往这条路上走。最后形成了图d的场景,蚂蚁都集中到了路线短的一边去了。这就是蚂蚁最优路线形成的关键原因。
下面去看一下用代码实现的Demo:
规则:1、首先固定蚁巢的位置在中间位置,开始的时候利用随机数random,蚂蚁从蚁巢随机走向各个位置。
2、蚂蚁活动的最大距离为屏幕斜线距离,当移动距离达到最大距离和步数时,蚂蚁开始自动回到家的位置进行重置,进行下一轮随机;移动距离在找到家或者食物的时候清零。
3、蚂蚁移动的方向是偏向信息素浓度高的一侧移动的,信息素撒播规则按照 屏幕斜线距离/蚂蚁移动距离,也就是蚂蚁移动的距离越远撒播的信息素浓度就越低,选择方向的计算公式采用 单元格浓度/8个方向单元格浓度总和,也就蚂蚁的的观察范围是9个单元格。
4、信息素在每次迭代时,进行统一挥发一个常量值,随着时间的推移信息素如果没有跟新就会消失。
5、如果周围没有信息素的指引时,蚂蚁的运动具有一定的惯性,并有一定的概率选择其他路径,蚂蚁遇到障碍物会绕开。


首先看初始的状态,蚂蚁向四周随机散开,图中黄色方块的是食物,白色圆点的代表蚂蚁,棕色方块的代表障碍物,黄色圆点代表找到食物的蚂蚁。


  
蚂蚁找到了去到食物的最优路线


 设置障碍物之后我们可以看到蚂蚁绕开了障碍物还是能找到食物

  这时候蚂蚁们进入了局部最优的状态,也是这个简单的蚁群算法的缺陷的地方,在蚂蚁的周围虽然还有很多的食物,但是搜索到一定程度,就会出现停滞状态陷入局部最优,或者盲目随机搜索,搜索时间较长,最后造成蚂蚁一直在一两个地方来回的搬运食物。

 
参考博客: http://www.cnblogs.com/Leo_wl/p/5665715.html
参考资料: 蚁群算法原理及其应用/段海滨著

这篇关于群体智能仿真之简单蚁群算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/932676

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO