# 蚁群算法和BP神经网络的Java实现
## 0. 前言
本项目包括两个算法的Java实现:
* 一个是蚁群算法中的蚂蚁系统(Ant System),使用该算法对著名的旅行商问题进行求解,例子使用经典的berlin52数据集
* 一个是BP(Back Propagation Neural Network)神经网络,使用该模型对函数进行模拟,例子对于 y = x ^ 2 - x 进行模拟
> 算法使用纯Java实现,而且是对算法本身进行原始的实现,代码中有比较多的注释,帮助理解
## 1. 准备
* IDE:MyEclipse 2016
* JDK版本:1.8.0_121
* 测试数据:berlin52.txt(项目里有)
> 由于是纯Java算法实现,所以无需额外的jar包
## 2. 蚁群算法
将蚁群算法应用于解决优化问题的基本思路为:用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多,**随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多**。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上,此时对应的便是待优化问题的最优解。
### 2.1 算法步骤
算法整体过程如下:
1. 初始化数据,如蚂蚁数、迭代数等
2. 逐一处理蚂蚁,随机选择起点,然后为蚂每只蚁计算、选择下一城市,直到到达终点,更新最优路径
3. 重复第2步直到处理完所有的蚂蚁
4. 更新信息素矩阵
5. 以第2步到第4步为一次迭代,总共迭代n次
6. 输出结果
### 2.2 实现
详细代码看源码AntSystem.java和Ant.java
### 2.3 测试结果
多次运行后的最佳结果如下:
![最佳结果](http://kanarien-1254133416.cosgz.myqcloud.com/Image%20Bed/ant-best.png)
> 用来测试的berlin52.txt数据集的内容格式是每行表示二维坐标轴上的一个点。最优解为7542,本算法实现的运行结果大部分在8000 - 10000,由于是概率型算法所以结果不一而且与最优结果存在偏差。
## 3. BP神经网络
人工神经网络(Artificial Neural Network,ANN)是由大量处理单元互联组成的**非线性、自适应**信息处理系统。它是在现代神经科学研究成果的基础上提出的,试图通过**模拟大脑神经网络处理、记忆信息的方式**进行信息处理。
![神经网络模型](http://kanarien-1254133416.cosgz.myqcloud.com/Image%20Bed/%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C%E6%A8%A1%E5%9E%8B.png)
BP(back propagation)神经网络是1986年由Rumelhart和McClelland为首的科学家提出的概念,是一种按照**误差逆向传播**算法训练的多层前馈神经网络,是目前应用最广泛的神经网络。简单来说,**BP神经网络是人工神经网络的一种实现,特点是使用了反向传播修正权重,**,也就是著名的**梯度下降法**。另外BP神经网络也是深度学习的底层基础,如卷积神经网络(Convolutional Neural Networks, CNN)。
### 3.1 算法步骤
算法整体过程如下(目的是根据输入数据训练出模型):
1. 初始化网络,准备训练
2. 前向处理
1. 输入层赋值
2. 输入层到隐层权值和计算
3. 隐层使用S函数对权值和进行激活
4. 隐层到输出层权值和计算
5. 利用输出层权值和计算当前误差
3. 反向处理(梯度下降和动量调整)
1. 输入层到隐层的权值修正
2. 隐层到输出层的权值修正
4. 重复第2步到第3步直到当前误差小于初始化中设定的误差参数
5. 训练完毕
> 激活函数:Sigmod函数,误差函数:平方和函数
### 3.2 实现
详细代码看源码BPNet.java
> 训练时务必注意训练数据的规范性,数据要规约到[-1,1]或者[0,1],否则实际输出会出现NaN或者结果之间非常相近
### 3.3 运行结果
对 y = x ^ 2 - x 的模拟结果如下:
![BPNet运行结果](http://kanarien-1254133416.cosgz.myqcloud.com/Image%20Bed/BPNet%20-%20%E8%BF%90%E8%A1%8C%E7%BB%93%E6%9E%9C001.png)
> 当输入较小时会有较大的误差