# algorithm_2221

**Repository Path**: stonesong/algorithm_2221

## Basic Information

- **Project Name**: algorithm_2221
- **Description**: 启发式算法之蚁群算法、遗传算法，没有兔子。
- **Primary Language**: Python
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 4
- **Forks**: 0
- **Created**: 2022-10-19
- **Last Updated**: 2025-05-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# ZF2221330_探索者_大作业

本项目为22年秋季《程序设计与算法》课程大作业，团队名称为：“探索者”，选题为：“智能算法”。

项目选择遗传算法、蚁群算法两种具有代表性的智能算法，并对其进行了分析、实现和测试；分析了其算法复杂度受影响的可能因素；分析了其在解决旅行商问题和非线性函数求极值问题中的优劣势。

本篇README.md面向开发者。

## 1. 目录

- [1. 目录](#1-目录)
  - [1.1. 上手指南](#11-上手指南)
  - [1.2. 文件目录说明](#12-文件目录说明)
  - [1.3. 主要代码说明](#13-主要代码说明)
    - [1.3.1. ant\_cal\_f.py](#131-ant_cal_fpy)
    - [1.3.2. ant\_tsp.py](#132-ant_tsppy)
    - [1.3.3. gen\_cal\_f.py](#133-gen_cal_fpy)
    - [1.3.4. gen\_tsp.py](#134-gen_tsppy)
  - [1.4. 贡献者](#14-贡献者)
  - [1.5. 版本控制](#15-版本控制)
  - [1.6. 参考资料](#16-参考资料)

### 1.1. 上手指南

本项目使用 `Python 3.8.13` 开发，建议使用相同环境运行。所用依赖及版本参照 `requirements.txt`

1. 安装 `git` 克隆代码，或者直接下载zip包
```sh
git clone https://gitee.com/stonesong/algorithm_2221.git
```
2. 搭建 Python 环境，建议使用 Conda
3. 安装依赖
```sh
pip3 install -r requirements.txt
```
4. 运行代码
蚁群算法求解非线性函数极值问题
```sh
python3 ant_cal_f.py
```
蚁群算法求解旅行商问题
```sh
python3 ant_tsp.py
```
遗传算法求解非线性函数极值问题
```sh
python3 gen_cal_f.py
```
遗传算法求解旅行商问题
```sh
python3 gen_tsp.py
```

### 1.2. 文件目录说明

```bash
algorithm_2221
├── LICENSE
├── README.md
├── images
│   └── ……
├── src
│   ├── ant_cal_f.py
│   ├── ant_tsp.py
│   ├── gen_cal_f.py
│   └── gen_tsp.py
└── test_data
    └── tsp
        ├── answer.txt
        └── opt_tour
            └── ……
```

`src`为源码文件夹，其中`ant_cal_f.py`为蚁群算法求解非线性函数极值问题、`ant_tsp.py`为蚁群算法求解旅行商问题、`gen_cal_f.py`为遗传算法求解非线性函数极值问题、`gen_tsp.py`为遗传算法求解旅行商问题。

`images`文件夹中存储README中的相关插图。`test_data`中存储了一些 TSPLIB 95 提供的的测试数据集，而`answer.txt`存储了相关问题当前已知最优解。


### 1.3. 主要代码说明

#### 1.3.1. ant_cal_f.py
该程序使用蚁群算法求解一元非线性函数极值问题，使用时需要修改源码中的目标函数为待求函数
```python
def func(x):
    # 目标函数
    return abs(x[0] * math.sin(x[0]) * math.cos(2 * x[0]) - 2 * x[0] * math.sin(3 * x[0]) + 3 * x[0] * math.sin(4 * x[0]))
```
并调用以下方法求解
```python
""" 默认寻找最大值，以及对应自变量取值
:param func: 所要求解的目标函数
:param n: 蚁群蚂蚁的个数
:param var: 函数中自变量的个数，即：几元函数
:param iter: 迭代次数
:param lb: 每一个自变量的下界，顺序应和自变量一一对应
:param ub: 每一个自变量的上界，顺序应和自变量一一对应
"""
aco = ACO(func, 50, 1, 50, [0], [50]) # x:0~50
max_x, max_x_log, curr_max_x_log = aco.solve()
```
其中需要规定自变量个数，和自变量取值范围，案例中求解一元非线性函数极大值。若需要求解极小值，则目标函数取负值，求解完毕后，再取相反数即可。
返回的`max_x`为最优解的自变量，`max_x_log`为每次迭代后，全局最优解的自变量数组，`curr_max_x_log`为每次迭代中，该次局部最优解的自变量数组。

运行结果：
![运行结果](images/ant_cal_f.png)

#### 1.3.2. ant_tsp.py
该程序使用蚁群算法求解旅行商问题，使用时需要修改源码中的问题描述文件
```python
problem = tsplib95.load('../test_data/tsp/opt_tour/berlin52.tsp')
```
并调用以下方法求解
```python
"""
:param generations: 最大迭代次数
:param alpha: 信息启发因子，反映了蚁群在运动过程中残留信息量的相对重要程度
:param beta: 期望启发因子，反映了期望值（距离）的相对重要程度
:param rho: 信息素挥发系数
:param Q: 常量，表示蚂蚁循环一个过程在经过的路径上锁匙放的信息素总量
:param ant_count: 蚁群中蚂蚁的总数，默认为问题规模的1.5倍
:param strategy: 信息素更新策略：0-蚁周模型（ant-cycle）默认, 1-蚁量模型（ant-quality）, 2-蚁密模型（ant-density）
"""
aco = ACO(20, 1.0, 4.0, 0.7, 150,300)
best_solution, best_cost, cost_log, best_cost_log = aco.solve(problem)
```
调用蚁群算法时，需要指定最大迭代次数（终止条件），信息启发因子，期望启发因子，信息素挥发系数，信息素常量；而蚁群规模默认为城市数量的1.5倍（可指定），信息素更新策略为蚁周模型。

返回的`best_solution`为最优解的路径，`best_cost`为最优解（遍历城市的最短距离），`cost_log`为每次迭代中，该次局部最优解，`best_cost_log`为每次迭代后，全局最优解。

需要说明的是，这个算法加载的文件需要满足“TSPLIB 95 数据集”规定的格式，具体可参考[TSPLIB 95 数据集中文介绍](https://blog.csdn.net/junzhepan/article/details/8498707)

适应值函数变化：
![适应值函数变化](images/ant_tsp_fitness.png)

最优路径：
![最优路径](images/ant_tsp_path.png)

#### 1.3.3. gen_cal_f.py

该程序使用遗传算法求解一元非线性函数极值问题，使用时需要修改源码中的目标函数定义
```python
# 需要求解的数学函数
function = lambda x: np.abs(x * np.sin(x)*np.cos(2*x) - 2*x*np.sin(3*x)+3*x*np.sin(4*x))     
```
运行结果存储在以下变量中
```python
results = []      # 存储每一代的最优解，二维列表
all_fitness = []  # 存放每一代中的最高适应度和种群适应度
```
运行结果：
![运行结果](images/gen_cal_f.png)

#### 1.3.4. gen_tsp.py

该程序使用遗传算法求解旅行商问题，使用时需要修改源码中自定义的城市坐标
```python
#路径坐标
data = np.array([16.47,96.10,16.47,94.44,20.09,92.54,
    22.39,93.37,25.23,97.24,22.00,96.05,20.47,97.02,
    17.20,96.29,16.30,97.38,14.05,98.12,16.53,97.38,
    21.52,95.59,19.41,97.13,20.09,92.55]).reshape(14,2)
```
并调用以下方法求解
```python
Path_short=main(data)
```
返回的`Path_short`为最优解的路径。
具体的每次迭代的局部最优解和全局最优解，会在程序运行时打印
```python
print('第' + str(i + 1) + '步的最短的路程: ' + str(curr_best))
print('第' + str(i + 1) + '步后的最短的路程: ' + str(Path_short.fitness[index]))
print('第' + str(i + 1) + '步后的最优路径:')
```
程序运行开始，会先展示初始的路径规划图，并在运行结束后，展示求得的最优路径

适应值函数变化：
![适应值函数变化](images/gen_tsp_fitness.png)

初始路径：
![初始路径](images/gen_tsp_init_path.png)

最优路径：
![最优路径](images/gen_tsp_best_path.png)

### 1.4. 贡献者

队伍名称：探索者

成员信息：

| 学号      | 姓名   | 角色 | 分工     |
| --------- | ------ | ---- | -------- |
| ZF2221330 | 宋磊   | 组长 | 蚁群算法 |
| ZF2221407 | 宛华海 | 组员 | 遗传算法 |

### 1.5. 版本控制

该项目使用Git进行版本管理。

### 1.6. 参考资料

- 《程序设计与算法》第九讲：现代启发式算法
- [TSPLIB 95’s documentation](https://tsplib95.readthedocs.io)
- [TSPLIB 95 数据集中文介绍](https://blog.csdn.net/junzhepan/article/details/8498707)
- [TSP data](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/)
- [Optimal solutions for symmetric TSPs](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html)
- [Gitee Gump Best_README_template](https://gitee.com/quansen2019/Best_README_template.git)
- [在线函数绘图工具](https://www.desmos.com/calculator)

<!-- links -->
<!-- [license-url]: https://github.com/shaojintian/Best_README_template/blob/master/LICENSE.txt -->