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