企业官网建设流程全解析

上一篇文章C++模拟蚁群（一），介绍了使用SDL2库模拟绘制蚁群在正方形地板格找食物的场景。本文继续介绍，将地板格改成正六边形，实现模拟蚁群，核心算法没有变，理解和实现上难度有所提升。

一、数学基础

（一）蚂蚁选择方向概率模型

推荐看一篇文章数学建模学习笔记（一）蚁群算法(MATLAB)，我设置的场景是六边形砖块平铺，蚂蚁只有6个方向，且距离都相等设为1，于是我对该模型进行了简化：
P k = τ k α ⋅ 1 ∑ k = 1 4 τ k α ⋅ 1 P_k=\frac{\tau_k^\alpha \cdot 1}{\sum_{k=1}^4 \tau_k^\alpha \cdot 1}Pk​=∑k=14​τkα​⋅1τkα​⋅1​，其中α \alphaα是信息素重要程度，我在程序里设置成2，τ \tauτ是该方向上邻近的砖块所含的信息素浓度,P k P_kPk​就是蚂蚁选择方向k的概率。

（二）轮盘赌抽取随机数

轮盘赌是一种以转动轮盘上滚动的小球最终落入编号格子来决定赌注输赢的随机赌博游戏。假设蚂蚁6个方向都能走，信息素浓度最大的那个方向肯定走的概率大。假设我有1个100面的骰子，而6个方向信息素之和为200怎么办呢？我需要掷一次骰子必然要选一个方向，就需要做一个映射，即：1 ∼ 2 → 1 ， 3 ∼ 4 → 2... ， 199 ∼ 200 → 100 1\sim2 \to1，3\sim4\to2...，199\sim200\to1001∼2→1，3∼4→2...，199∼200→100，如果我掷取的数是3，落在方向0的区间，就可以选择方向0；若没有落在方向0的区间，我就依次检查有没有落在其他方向的数字区间。这样，通过掷一次骰子，我就能实现按各方向的信息素浓度对应一定的根据来选择前进方向了。

（三）六角格与世界坐标

推荐看我写的另一篇文章SDL2画六角格地板，选学部分要求掌握，在此不作赘述。

（四）微分思想绘制圆（使用SDL库要求掌握）

SDL2库没有专门的绘制圆的函数，需要自己实现。我实现了一个高效算法，有兴趣的请移步SDL2高效画实心圆的算法（一）。

二、关键方法实现

（一）参数设置

所有参数统一在ant.h头文件中定义:

staticdouble_INFO_=1000;staticdouble_INFO_MAX_=10000;//单个地板信息素上限（防止无限累加）staticdouble_INFO_DELTA_=50;//信息素递减staticdouble_IMPORTANT_=1.2;//信息素浓度重要程度staticdouble_EVADE_=0.75;//挥发保留系数

• _INFO_DELT_代表蚂蚁每移动一格信息素浓度递减的数值，也就是蚂蚁走的越远信息素浓度越小，直到没有，这样可以有效防止蚂蚁陷入局部最优解。
• _INFO_蚂蚁分别在找到食物和把食物放回家这2种状态下可以补充信息素回到_INFO_的数值。
• _IMPORTANT_就是数学模型里的α \alphaα，于是概率方程就变成了P k = τ k 1.2 ∑ k = 0 5 τ k 1.2 P_k=\frac{\tau_k^{1.2}}{\sum_{k=0}^5 \tau_k^{1.2}}Pk​=∑k=05​τk1.2​τk1.2​​
• _EVADE_气味消散系数，定义蚂蚁每移动1格为进行一次气味挥发，地面上的所有信息素会变成原来的0.75倍。

（二）蚂蚁嗅探函数

//蚂蚁嗅探方向voidAnt::sniffDirection(){intrandD[6]={-1,-1,-1,-1,-1,-1};//随机方向存储器doubleinfoD[6]={};//各方向上信息素浓度^adoubleinfoSum=0;//各方向上总浓度^aintcur=0;//随机方向存储器尺寸指针for(intd=0;d<6;d++){//遍历6个方向，找要可用方向if(!(Foods::position[this->sy*N+this->sx]||(Home::x==this->sx&&Home::y==this->sy))&&d==(this->direction+3)%6)continue;//不能是反方向回头路if(this->directionToDestination(d)){randD[cur]=d;//标记可行方向if(this->food){infoD[cur]=pow(Ground::getInfoHome(this->dx,this->dy),_IMPORTANT_);}else{infoD[cur]=pow(Ground::getInfoFood(this->dx,this->dy),_IMPORTANT_);}infoSum+=infoD[cur];cur++;};}//end of forassert(cur);//断言必有可行方向if(infoSum<0.5){//周围没有探索过this->direction=randD[rand()%cur];this->directionToDestination(this->direction);//随机方向}else{//轮盘赌doubler=rand()*1.0/RAND_MAX*infoSum;//制取infoSum以内随机数doublet=0;for(inti=0;i<cur;i++){//直到选出方向t+=infoD[i];if(r<=t){this->direction=randD[i];this->directionToDestination(this->direction);break;}}}}

三、效果展示

实测对于N*N个地板格，大概2/3 * N * N只蚂蚁演示效果最好。请看我上传的视频模拟蚁群

四、源码下载

C++模拟蚁群（需使用SDL、SDL-image库）