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）