BP神经网络在排序算法模拟中的应用研究

王小春

摘 要： 提出了用BP神经网络对排序算法进行模拟。首先利用BP神经网络对排序算法的实际输出结果进行预测，然后用匈牙利算法和全局贪心两种算法对网络输出结果与输入数据进行平衡匹配。实验证明两种算法均对低维数据的排序有更好的效果。针对10维数据经匈牙利算法匹配后排序正确率为75.70%，经贪心算法匹配后排序正确率为44.85%，且匈牙利算法的排序正确率均不低于贪心算法。

关键词： BP神经网络; 排序算法模拟; 匈牙利算法; 贪心算法

中图分类号： TP311文献标志码： A

Research on Simulation on Sorting Algorithm Based on BP Neural Network

WANG Xiaochun

（Computer Engineer College， Xian Aeronautical Polytechnic Institute， Xian， Shanxi 710089， China）

Abstract： An algorithm for sorting problem is proposed in this paper based on BP neural network.Firstly， a BP neural network is used to make a prediction for the output of the sorting algorithm. Then， Hungarian algorithm and global greedy algorithm are used to balance the output and input data. The experimental results show that Hungarian algorithm and global Greedy algorithm all have better effect on the sorting of data in low dimension.The correct rate of the 10 dimensional data processed by Hungary algorithm and Greedy algorithm is 75.70% and 44.85%. The conclusion can be drawn that the correct rate of the Hungarian algorithm is higher than the greedy algorithm in sorting according to a comprehensive comparison.

Key words： BP neural network; sorting algorithm simulation; Greedy algorithm

0 引言

算法模拟作为神经网络应用中很少被提及的一部分，对算法理解和优化及神经网络的应用领域方面有很大的意义。本研究提出用神经网络对排序算法进行模拟，为排序算法的实现提供了一种全新的方法，对其他算法模拟提供了参考方法。本研究将BP神经网络与其他算法相结合来实现排序算法模拟，也为神经网络的应用研究提供了一种新的思路。本研究中针对排序算法的模拟选用BP神经网络来实现，所开展的实验均是在MATLAB上编写并运行实现的。

1 关键技术研究

1.1 BP神经网络

BP算法作为一种典型的神经网络，一般用梯度下降法优化训练结果，基本BP算法通常包含以下两个部分：信息的前向传播和误差的后向传播[1]。通俗的说，输入数据构成的向量传递给网络时，这些信息通过网络逐层处理并向后传播直至输出层，传播过程中，各个神经节点的值由与之连接的节点的值和这些节點的权重决定[2]。然后对网络输出与期望输出进行对比，得到对应的误差值。BP神经网络的算法流程图如图1所示。

1.2 匈牙利算法

匈牙利算法是Harold Kuhn基于匈牙利数学家Koning关于矩阵中独立零元素定理提出的一种组合优化算法[3]，用于求解指派问题。排序算法模拟中BP神经网络输出的预测值和输入值之间的匹配可以看成一个指派问题，对应的最优解是使得整体匹配误差值最小的匹配结果。

1.3 贪心算法

贪心算法是一种获得局部最优解的算法，其寻优过程为：首先在效益矩阵中找出当前全局最小值，然后将对应的两个数据进行匹配，并对矩阵进行相应的处理，进而再找出最小值，最后再处理[4]。简而言之，贪心算法主要的出发点并不是全局，而是针对目前所面临的问题做出当下最优的选择，进而得到局部最优结果，最终获得全局最优结果。

排序算法模拟中，利用贪心算法对网络输出值与网络输入数据进行匹配，匹配算法流程为：

1） 依次对BP神经网络的输出数据与网络的输入数据求绝对误差，组成效益矩阵 （误差矩阵）;

2） 从误差矩阵中选取大于0的全局最小值;

3） 将全局最小值所在行和列对应的两个数据进行匹配;

4） 在误差矩阵中将全局最小值对应的行和列中的数据均置为-1;

5） 若误差矩阵元素不全为-1，重复步骤2）3）4）;

6） 误差矩阵元素全为-1，则匹配过程结束。

2 排序算法模拟实验设置及结果分析

2.1 数据获取和处理

2.1.1 数据获取和设置

本研究排序算法模拟中用到的数据是根据需要随机产生的（数值范围1-1 000），随机产生数据可以避免人为因素引起的不必要的误差，如需要对20个整数进行排序，则随机产生20维整数矩阵，将产生的数据划分为训练数据和测试数据两部分，训练数据的数量要远大于测试数据的数量，本研究中训练数据有2 000组数据，测试数据有200组数据，如训练数据大小为20×2 000，则测试数据大小为20×200。期望输出矩阵是训练数据和测试数据对应的排序（本研究选择升序） 结果，所以期望输出矩阵维度与训练数据和测试数据的维度相等。

2.1.2 数据预处理

归一化是把预处理数据通过对应算法处理将其限制在需要的一定范围内。一般情况下，将数据归一化为[0，1]或者[-1，1]之间。本研究根据实际需要，将各样本数据归一化到[0，1]之间。

虽然本研究过程中用到的数据度量单位都相同，但是归一化不仅有助于后续步骤数据的处理，而且可以加快网络的收敛速度，所以本研究也需要对输入数据进行归一化处理。归一化的方法如式（1）。

其中X是要归一化的矩阵，Xi是X的一个数据，min（X）是X的最小值，max（X）是X的最大值，xi是归一化后的数据。经过归一化处理后的部分数据如表1所示。

2.2 BP神经网络设计

2.2.1 评判标准

2.2.1.1 判定系数

判定系数是统计学中的一个重要参数，用来衡量两个变量之间的相关性，一般用R2表示。针对简单的线性回归问题来说，数据相关系数的平方值即为该系数，函数表达式如式（2）。

上式中，y1，…，yn表示n个期望输出值，即实际值，f1，…，fn表示n个网络预测值，表示期望输出值的平均值。

在本研究中，R2是用来判定BP神经网络输出数据与网络输入数据之间的相关性，是普通的线性回归。其中，R2越接近于1，表示网络的预测输出越接近实际期望值，模型的拟合度越高。

2.2.1.2 正确率

用匈牙利算法和贪心算法对网络输出和网络输入进行匹配后，如何判断匹配结果的好坏是一个关键问题。本研究选择了正确率对匹配结果进行评判，具体计算方法如式（5）。

上式中，Acc表示正确率，n表示匹配结果与正确排序结果不相等的元素个数，N表示匹配结果的总个数，N的大小为数据集维数与数据个数的乘积。所以，Acc的值越接近1表示匹配结果越好。

2.2.1.3 MSE（均方差）

均方差表示预测数据和原始数据对应误差的平方和的均值，经常作为评判标准来评判模型性能，计算方法如式（6）。

公式（6）中，n表示数据的个数，y1，…，yn表示n个期望输出值，即实际值，f1，…，fn表示n个网络预测值。由公式（6）可得，MSE越小，表示预测值越接近实际值，所以在实验过程中希望MSE较小。

2.2.2 输入和输出层节点数确定

BP神经网络结构中输入层节点数的选取是根据研究对象的特性进行选取的，其具体要求是所选的节点能反映事物的本质特征，这些节点被称为特征量，特征量的数值大小被称为特征值。如果选取的特征量不具有代表性或典型性，则会使BP神经网络的训练结果与实验数值产生较大的偏差，预测效果的精确度将会大大降低。

本研究的排序算法模拟中，输入输出关系决定了输入层节点数和输出层节点数相等，都等于训练数据的维数。

2.2.3 确定隐藏层节点数

BP神经网络结构中隐藏层节点数的选择是非常重要的。在BP神经网络中，隐藏层节点数过多或过少对网络结构都会造成一定程度的影响，如果隐藏层节点数过多，则会使BP神经网络收敛速度减慢，同时还会使网络记住更多没有意义的信息;如果隐藏层节点数过少，网络从样本输入中获得的有效信息太少，网络对某些复杂的问题可能达不到预期的处理效果，或出现预测结果偏差太大的情况。

对于BP神经网络，确定隐藏层节点数最常用的方法有如下3种：

a） m=numinput+numoutput+c

b） m=numinput+numoutput

c） m=log2numinput

以上公式中，m为隐藏层节点数，numinput为输入层节点数，numoutput为输出层节点数，c一般为1-10的常数，本次实验中，选择c=10。不同维数输入数据的隐藏层节点数与方法之间的实验结果如表2所示。

表2中各小数表示对于测试数据的网络输出与实际排序结果的判定系数，判定系数越接近1表示网络的输出和期望值越接近。从表2中数据可得，除了维数（维数表示需要排序的个数）为40和30的数据集之外，其他数据集方法a最有效，且在维数为40和30的数据集中，虽然方法c最优，但是方法a的结果也能满足要求，为了更好的实现排序算法模拟，本研究中对维数为40和30的数据集进行模拟时，隐藏层节点数按方法c确定，而对于其他数据集用方法a确定隐藏层节点数。

2.2.4 学习速率的确定

学习速率η在公式中表示权值和阈值调整的系数，具体调整方法如公式（7）。

其中，E代表第n次计算得到的目标函数，W（n）代表连接权值，ΔW（n）代表权值调整量。学习速率η影响着网络的收敛能力和收敛速率，如果η的值选取太大，则BP神经网络的稳定性就会降低;若η的值选取太小，BP神经网络的训练时间又会增加，使网络的收敛速度下降。η的选取直接影响着ΔW（n），即影响网络每一次权值的调整。本研究学习速率设置为0.1，由训练结果可得，此学习速率使网络的收敛速度和收敛能力均满足网络的要求。

2.2.5 网络层数的确定

单隐藏层部分预测数据与期望输出值的对比图如图2所示。

图中的数据是从测试数据的4 000（20×200）个数据中随机选取的100个数据点，从图2中可以看出，网络的输出值（预测值）与实际期望值之间的误差很小;从测试数据所有数据与期望值之间的散点图可以看出，单隐藏层网络结构对测试数据整体的预测精度也很高，判定系数为0.981 8，所以，单隐藏层的网络结构能较好地学习排序算法，使网络的预测精度满足要求。如图3所示。

本次实验选择的是20维的数据集，训练数据大小为20×2 000，测试数据大小为20×200，最大迭代次数为100，学习率为0.1，单隐藏层和双隐藏层网络结构的预测值与实际值的相关性比較实验结果如表3所示，表中的数值表示判定系数的值。

BP神經网络中的隐藏层的个数在网络中起着举足轻重的作用，增加网络隐藏层的个数，可以增强BP神经网络的非线性映射功能，但是隐藏层数过多，也会产生以下弊端：使得BP神经网络训练速度减慢，网络结构复杂。由表3可得，对于20维的数据来说，单隐藏层和双隐藏的预测结果都较好，且单个隐藏层的拟合效果更好（判定系数满足：0.981 8>0.956 3），另一方面，单个隐藏层神经网络结构简单，收敛速度快，所以本研究选择了单隐藏层网络结构。

2.2.6 训练数据大小确定

数据集的大小对神经网络的输出也有一定的影响作用，如果数据集太小，会使网络的学习能力下降，如果数据集过大，会使网络的收敛速度降低。所以选择大小合适的数据集对于网络也很重要。选择维数为20的数据进行实验，在其他条件不变的情况下只改变数据集大小，在网络收敛后，分别计算匈牙利算法和贪心算法的正确率，以此来说明数据集大小对网络性能的影响，数据集大小对排序算法模拟的影响如表4所示。

由表4可得，数据集太小对排序算法的模拟结果有影响，当数据集个数为200时，匈牙利算法的正确率为0.542 5，数据集大小为2 000时匈牙利算法的正确率较之前提高了13.36%，贪心算法对数据集大小不是很敏感，且正确率均低于匈牙利算法，但是数据集个数为2 000时的正确率也比数据集个数为200时高了4.73%。从表4还可以看出：对于维数为20的数据集，数据集大小为2 000时，匈牙利算法和贪心算法都取得了最好的效果，基于上述，所以本研究中对于每个维数的数据集，其大小均设定为2 000。

3 实验结果分析

本研究分别选了2维、4维、6维、8维、10维、12维、15维、20维、30维和40维的数据集，分别作为BP神经网络的输入来验证排序算法模拟的效果，每个测试数据集都有200组数据，各个数据集的测试结果如表5所示。

表5中Accx表示用匈牙利算法匹配网络输出与网络输入的正确率，Acct表示用贪心算法匹配后的正确率，对应的MSEx表示用匈牙利算法匹配后的均方差，MSEt表示用贪心算法匹配后的均方差，其中MSEx和MSEt的值都是在数据反归一化之前计算得到的。

由表5可得：随着维数的增加，本研究训练的排序算法模拟模型性能下降，匈牙利算法和贪心算法匹配结果的正确率都在不断下降，均方差都在不断增大，以至于在维数为40时，排序算法模型对于大多数数据来说，基本不能把对应数据匹配在正确的位置上，正确率分别下降到35.16%和16.01%，均方差分别增加到0.266 0和0.875 8。从上表可以看出，本研究提出的排序算法模拟对维数比较小的数据很有效，如两个算法对2维数据的排序正确率都可以达到100%，匈牙利算法对4个数据进行排序时正确率可以达到95.37%，贪心算法的正确率只达到了78.63%，且对于任何一个数据集，匈牙利算法的正确率均不小于贪心算法，所以本研究中匈牙利算法优于贪心算法。

4 总结

本研究选择了匈牙利算法和贪心算法来实现网络输出结果和输入数据的匹配，用匹配的正确率和均方差来评判匹配结果的好坏程度。实验结果可得：匈牙利算法的匹配正确率均不低于贪心算法，如：匈牙利算法对10维数据的排序结果正确率为75.70%，全局贪心对10维数据的排序结果正确率为44.85%。两种算法都对低维的数据更有效，数据维数越小，匹配的正确率越高，均方差越小，其中2维数据的排序结果正确率可以达到100%。

本研究对高维数据的排序结果正确率较低，今后会在提高BP神经网络的预测精度和匹配算法优化方面做出新的改进，如在BP神经网络的训练过程中使用文中提到的Trainbr算法、BFGS算法和LM算法，另一方面，在匹配算法优化方面也要进一步做点工作，旨在提高数据排序的正确率，最终实现更高维的数据排序。

参考文献

[1] 魏振，江智军，杨晓辉，等.基于BP神经网络的低电压短期预测的估算[J].现代电子技术，2019，42（23）：62-66.

[2] 李维华，张明武.修正BP神经网络应用于珠江洪水预报[J].通讯世界，2019，26（11）：21-22.

[3] 李廷鹏，钱彦岭，李岳.基于改进匈牙利算法的多技能人员调度方法[J].国防科技大学学报，2016，38（2）：144-149.

[4] 黄邦菊，熊惠敏，朱代武，等.基于贪心算法的航班-登机口模型[J].航空计算技术，2019，49（6）：10-13.

（收稿日期： 2019.11.05）