# AL_C2_G255_AntConoly

**Repository Path**: Mei_HW/al_-c2_-g255_-ant-conoly

## Basic Information

- **Project Name**: AL_C2_G255_AntConoly
- **Description**: 算法设计-2班-255组-蚁群算法
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-20
- **Last Updated**: 2022-06-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 蚁群算法C++

## 介绍

蚁群算法  SEU-Algorithm-C2

算法二班小组作业



## 开发环境

Visual Studio2019

## GUI库

easyX  ([Download](https://easyx.cn/down.aspx?id=10&no=0))

## 程序流程

```mermaid
graph TD
A(开始)-->B[随机生成地图]
B-->|开始迭代|C[随机放置蚂蚁到各个城市]
C-->D[蚂蚁分别遍历所有城市]
D-->E[更新信息素浓度]
E-->H[更新最短距离和路线]
H-->I[刷新图形界面]
I-->F{最大迭代次数?}
F-->|YES|G[结束]
F-->|NO|C



```



## 主要公式

### 1.i城市和j城市之间的转移概率：

$$
P_{ij} = \left\{\begin{matrix}
&\frac{\tau_{ij}^{\alpha}(t)\ *\ \eta_{ij}^{\beta}}{\Sigma_{j\in city_allowed}} &j\in city_allowed \\
&0 &j\notin city_allowed
\end{matrix}\right.\\ 
\begin{matrix}
  &i:当前城市 &j:可选城市 \\
  &eta :ij之间的信息素浓度 &allowed_city:接下来可访问的所有城市集合
\end{matrix}
$$

### 2.信息素更新公式：

$$
\eta_{ij}(t+1) = \eta_{ij}(t)*(1-\rho) + \Delta\tau_{ij}\quad 0<\rho<1 \\
\Delta\tau_{ij} = \sum_{k=1}^{m}\Delta_\tau{ij}^k \\
\begin{matrix}
  &m:蚂蚁数量\\
  &\Delta\tau_{ij}:所有蚂蚁在i到j的路上留下的信息素 \\
  &\Delta_\tau{ij}^k ：第k只蚂蚁在i到j的路上留下的信息素
\end{matrix}
$$

## 运行结果：
### 路线结果
![image-20201020223310197](RouteResult.bmp)
### 平均路径长度变化趋势
![image-20201020223310197](AverageLenthTrendLine.bmp)

**效果并不好，可能程序中有bug，也可能参数需要调整**