# 智能算法：蚁群优化算法（TSP问题）

**Repository Path**: letere/ant

## Basic Information

- **Project Name**: 智能算法：蚁群优化算法（TSP问题）
- **Description**: 用Java实现蚁群优化算法，来解决TSP问题
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 8
- **Forks**: 1
- **Created**: 2021-01-03
- **Last Updated**: 2025-05-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 一、算法介绍
参考文章：https://zhuanlan.zhihu.com/p/404181189

#### 1.1 三个重要式子
+ （1）每条路选中概率
    + 其中**alpha**和**beta**参数自定义
    + **alpha**为信息因子占的权重，权重过高，蚂蚁选中已走的路概率越高，开始走新路概率低
    + **beta**为两点距离的权重（能见度），权重过高，蚂蚁优先走两点最短距离的路
```java
rate = Math.pow(pheromoneMatrix[currentCity][city], ALPHA) * Math.pow(1.0 / distanceMatrix[currentCity][city], BETA);
```

+ （2）信息素更新
    + 信息素更新包括：**信息素挥发**以及**信息素新增**
    + 蚂蚁走完一遍所有城市后，就开始先计算挥发，再计算新增
```java
//信息素挥发
for(int i=0; i<distanceMatrix.length; i++) {
    for(int j=0; j<distanceMatrix.length; j++) {
        pheromoneMatrix[i][j] = pheromoneMatrix[i][j] * (1.0 - VOLATILIZATION_RATE);
    }
}
//信息素新增
for(Ant ant : ants) {
    List<Integer> route = ant.getRoute();
    for(int i=0; i<route.size()-1; i++){
        pheromoneMatrix[route.get(i)][route.get(i+1)] += 1.0 / ant.getRouteLength();
    }
}
```

---

### 二、Java实现代码（TSP问题）
#### 2.1 TSP问题
+ 简单来说，就是寻找一条访问所有城市，最短的一条路线
    + 前提：所有城市之间是互通的，任意两个城市可以来往

#### 2.2 代码结构介绍
```txt
| -- algorithm
  | -- bean
    | -- Ant.java (蚂蚁类：模拟蚂蚁行为遍历城市，并记录路线)
  | -- data
    | -- position.txt (坐标文件，记录城市的xy坐标，用于生成距离矩阵)
    | -- PositionUtil.java (读取坐标文件，生成距离矩阵工具类)
  | -- AcoAlg.java (蚁群优化算法：处理信息素和记录最短路线)
| -- Sample.java (运行案例，可直接运行)
| -- README.md (说明文档)
```