王小春

摘 要： 提出了用BP神經(jīng)網(wǎng)絡(luò)對排序算法進(jìn)行模擬。首先利用BP神經(jīng)網(wǎng)絡(luò)對排序算法的實際輸出結(jié)果進(jìn)行預(yù)測，然后用匈牙利算法和全局貪心兩種算法對網(wǎng)絡(luò)輸出結(jié)果與輸入數(shù)據(jù)進(jìn)行平衡匹配。實驗證明兩種算法均對低維數(shù)據(jù)的排序有更好的效果。針對10維數(shù)據(jù)經(jīng)匈牙利算法匹配后排序正確率為75.70%，經(jīng)貪心算法匹配后排序正確率為44.85%，且匈牙利算法的排序正確率均不低于貪心算法。

關(guān)鍵詞： BP神經(jīng)網(wǎng)絡(luò); 排序算法模擬; 匈牙利算法; 貪心算法

中圖分類號： TP311文獻(xiàn)標(biāo)志碼： 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 引言

算法模擬作為神經(jīng)網(wǎng)絡(luò)應(yīng)用中很少被提及的一部分，對算法理解和優(yōu)化及神經(jīng)網(wǎng)絡(luò)的應(yīng)用領(lǐng)域方面有很大的意義。本研究提出用神經(jīng)網(wǎng)絡(luò)對排序算法進(jìn)行模擬，為排序算法的實現(xiàn)提供了一種全新的方法，對其他算法模擬提供了參考方法。本研究將BP神經(jīng)網(wǎng)絡(luò)與其他算法相結(jié)合來實現(xiàn)排序算法模擬，也為神經(jīng)網(wǎng)絡(luò)的應(yīng)用研究提供了一種新的思路。本研究中針對排序算法的模擬選用BP神經(jīng)網(wǎng)絡(luò)來實現(xiàn)，所開展的實驗均是在MATLAB上編寫并運行實現(xiàn)的。

1 關(guān)鍵技術(shù)研究

1.1 BP神經(jīng)網(wǎng)絡(luò)

BP算法作為一種典型的神經(jīng)網(wǎng)絡(luò)，一般用梯度下降法優(yōu)化訓(xùn)練結(jié)果，基本BP算法通常包含以下兩個部分：信息的前向傳播和誤差的后向傳播[1]。通俗的說，輸入數(shù)據(jù)構(gòu)成的向量傳遞給網(wǎng)絡(luò)時，這些信息通過網(wǎng)絡(luò)逐層處理并向后傳播直至輸出層，傳播過程中，各個神經(jīng)節(jié)點的值由與之連接的節(jié)點的值和這些節(jié)點的權(quán)重決定[2]。然后對網(wǎng)絡(luò)輸出與期望輸出進(jìn)行對比，得到對應(yīng)的誤差值。BP神經(jīng)網(wǎng)絡(luò)的算法流程圖如圖1所示。

1.2 匈牙利算法

匈牙利算法是Harold Kuhn基于匈牙利數(shù)學(xué)家Koning關(guān)于矩陣中獨立零元素定理提出的一種組合優(yōu)化算法[3]，用于求解指派問題。排序算法模擬中BP神經(jīng)網(wǎng)絡(luò)輸出的預(yù)測值和輸入值之間的匹配可以看成一個指派問題，對應(yīng)的最優(yōu)解是使得整體匹配誤差值最小的匹配結(jié)果。

1.3 貪心算法

貪心算法是一種獲得局部最優(yōu)解的算法，其尋優(yōu)過程為：首先在效益矩陣中找出當(dāng)前全局最小值，然后將對應(yīng)的兩個數(shù)據(jù)進(jìn)行匹配，并對矩陣進(jìn)行相應(yīng)的處理，進(jìn)而再找出最小值，最后再處理[4]。簡而言之，貪心算法主要的出發(fā)點并不是全局，而是針對目前所面臨的問題做出當(dāng)下最優(yōu)的選擇，進(jìn)而得到局部最優(yōu)結(jié)果，最終獲得全局最優(yōu)結(jié)果。

排序算法模擬中，利用貪心算法對網(wǎng)絡(luò)輸出值與網(wǎng)絡(luò)輸入數(shù)據(jù)進(jìn)行匹配，匹配算法流程為：

1） 依次對BP神經(jīng)網(wǎng)絡(luò)的輸出數(shù)據(jù)與網(wǎng)絡(luò)的輸入數(shù)據(jù)求絕對誤差，組成效益矩陣 （誤差矩陣）;

2） 從誤差矩陣中選取大于0的全局最小值;

3） 將全局最小值所在行和列對應(yīng)的兩個數(shù)據(jù)進(jìn)行匹配;

4） 在誤差矩陣中將全局最小值對應(yīng)的行和列中的數(shù)據(jù)均置為-1;

5） 若誤差矩陣元素不全為-1，重復(fù)步驟2）3）4）;

6） 誤差矩陣元素全為-1，則匹配過程結(jié)束。

2 排序算法模擬實驗設(shè)置及結(jié)果分析

2.1 數(shù)據(jù)獲取和處理

2.1.1 數(shù)據(jù)獲取和設(shè)置

本研究排序算法模擬中用到的數(shù)據(jù)是根據(jù)需要隨機(jī)產(chǎn)生的（數(shù)值范圍1-1 000），隨機(jī)產(chǎn)生數(shù)據(jù)可以避免人為因素引起的不必要的誤差，如需要對20個整數(shù)進(jìn)行排序，則隨機(jī)產(chǎn)生20維整數(shù)矩陣，將產(chǎn)生的數(shù)據(jù)劃分為訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)兩部分，訓(xùn)練數(shù)據(jù)的數(shù)量要遠(yuǎn)大于測試數(shù)據(jù)的數(shù)量，本研究中訓(xùn)練數(shù)據(jù)有2 000組數(shù)據(jù)，測試數(shù)據(jù)有200組數(shù)據(jù)，如訓(xùn)練數(shù)據(jù)大小為20×2 000，則測試數(shù)據(jù)大小為20×200。期望輸出矩陣是訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)對應(yīng)的排序（本研究選擇升序） 結(jié)果，所以期望輸出矩陣維度與訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的維度相等。

2.1.2 數(shù)據(jù)預(yù)處理

歸一化是把預(yù)處理數(shù)據(jù)通過對應(yīng)算法處理將其限制在需要的一定范圍內(nèi)。一般情況下，將數(shù)據(jù)歸一化為[0，1]或者[-1，1]之間。本研究根據(jù)實際需要，將各樣本數(shù)據(jù)歸一化到[0，1]之間。

雖然本研究過程中用到的數(shù)據(jù)度量單位都相同，但是歸一化不僅有助于后續(xù)步驟數(shù)據(jù)的處理，而且可以加快網(wǎng)絡(luò)的收斂速度，所以本研究也需要對輸入數(shù)據(jù)進(jìn)行歸一化處理。歸一化的方法如式（1）。

其中X是要歸一化的矩陣，Xi是X的一個數(shù)據(jù)，min（X）是X的最小值，max（X）是X的最大值，xi是歸一化后的數(shù)據(jù)。經(jīng)過歸一化處理后的部分?jǐn)?shù)據(jù)如表1所示。

2.2 BP神經(jīng)網(wǎng)絡(luò)設(shè)計

2.2.1 評判標(biāo)準(zhǔn)

2.2.1.1 判定系數(shù)

判定系數(shù)是統(tǒng)計學(xué)中的一個重要參數(shù)，用來衡量兩個變量之間的相關(guān)性，一般用R2表示。針對簡單的線性回歸問題來說，數(shù)據(jù)相關(guān)系數(shù)的平方值即為該系數(shù)，函數(shù)表達(dá)式如式（2）。

上式中，y1，…，yn表示n個期望輸出值，即實際值，f1，…，fn表示n個網(wǎng)絡(luò)預(yù)測值，表示期望輸出值的平均值。

在本研究中，R2是用來判定BP神經(jīng)網(wǎng)絡(luò)輸出數(shù)據(jù)與網(wǎng)絡(luò)輸入數(shù)據(jù)之間的相關(guān)性，是普通的線性回歸。其中，R2越接近于1，表示網(wǎng)絡(luò)的預(yù)測輸出越接近實際期望值，模型的擬合度越高。

2.2.1.2 正確率

用匈牙利算法和貪心算法對網(wǎng)絡(luò)輸出和網(wǎng)絡(luò)輸入進(jìn)行匹配后，如何判斷匹配結(jié)果的好壞是一個關(guān)鍵問題。本研究選擇了正確率對匹配結(jié)果進(jìn)行評判，具體計算方法如式（5）。

上式中，Acc表示正確率，n表示匹配結(jié)果與正確排序結(jié)果不相等的元素個數(shù)，N表示匹配結(jié)果的總個數(shù)，N的大小為數(shù)據(jù)集維數(shù)與數(shù)據(jù)個數(shù)的乘積。所以，Acc的值越接近1表示匹配結(jié)果越好。

2.2.1.3 MSE（均方差）

均方差表示預(yù)測數(shù)據(jù)和原始數(shù)據(jù)對應(yīng)誤差的平方和的均值，經(jīng)常作為評判標(biāo)準(zhǔn)來評判模型性能，計算方法如式（6）。

公式（6）中，n表示數(shù)據(jù)的個數(shù)，y1，…，yn表示n個期望輸出值，即實際值，f1，…，fn表示n個網(wǎng)絡(luò)預(yù)測值。由公式（6）可得，MSE越小，表示預(yù)測值越接近實際值，所以在實驗過程中希望MSE較小。

2.2.2 輸入和輸出層節(jié)點數(shù)確定

BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中輸入層節(jié)點數(shù)的選取是根據(jù)研究對象的特性進(jìn)行選取的，其具體要求是所選的節(jié)點能反映事物的本質(zhì)特征，這些節(jié)點被稱為特征量，特征量的數(shù)值大小被稱為特征值。如果選取的特征量不具有代表性或典型性，則會使BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練結(jié)果與實驗數(shù)值產(chǎn)生較大的偏差，預(yù)測效果的精確度將會大大降低。

本研究的排序算法模擬中，輸入輸出關(guān)系決定了輸入層節(jié)點數(shù)和輸出層節(jié)點數(shù)相等，都等于訓(xùn)練數(shù)據(jù)的維數(shù)。

2.2.3 確定隱藏層節(jié)點數(shù)

BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中隱藏層節(jié)點數(shù)的選擇是非常重要的。在BP神經(jīng)網(wǎng)絡(luò)中，隱藏層節(jié)點數(shù)過多或過少對網(wǎng)絡(luò)結(jié)構(gòu)都會造成一定程度的影響，如果隱藏層節(jié)點數(shù)過多，則會使BP神經(jīng)網(wǎng)絡(luò)收斂速度減慢，同時還會使網(wǎng)絡(luò)記住更多沒有意義的信息;如果隱藏層節(jié)點數(shù)過少，網(wǎng)絡(luò)從樣本輸入中獲得的有效信息太少，網(wǎng)絡(luò)對某些復(fù)雜的問題可能達(dá)不到預(yù)期的處理效果，或出現(xiàn)預(yù)測結(jié)果偏差太大的情況。

對于BP神經(jīng)網(wǎng)絡(luò)，確定隱藏層節(jié)點數(shù)最常用的方法有如下3種：

a） m=numinput+numoutput+c

b） m=numinput+numoutput

c） m=log2numinput

以上公式中，m為隱藏層節(jié)點數(shù)，numinput為輸入層節(jié)點數(shù)，numoutput為輸出層節(jié)點數(shù)，c一般為1-10的常數(shù)，本次實驗中，選擇c=10。不同維數(shù)輸入數(shù)據(jù)的隱藏層節(jié)點數(shù)與方法之間的實驗結(jié)果如表2所示。

表2中各小數(shù)表示對于測試數(shù)據(jù)的網(wǎng)絡(luò)輸出與實際排序結(jié)果的判定系數(shù)，判定系數(shù)越接近1表示網(wǎng)絡(luò)的輸出和期望值越接近。從表2中數(shù)據(jù)可得，除了維數(shù)（維數(shù)表示需要排序的個數(shù)）為40和30的數(shù)據(jù)集之外，其他數(shù)據(jù)集方法a最有效，且在維數(shù)為40和30的數(shù)據(jù)集中，雖然方法c最優(yōu)，但是方法a的結(jié)果也能滿足要求，為了更好的實現(xiàn)排序算法模擬，本研究中對維數(shù)為40和30的數(shù)據(jù)集進(jìn)行模擬時，隱藏層節(jié)點數(shù)按方法c確定，而對于其他數(shù)據(jù)集用方法a確定隱藏層節(jié)點數(shù)。

2.2.4 學(xué)習(xí)速率的確定

學(xué)習(xí)速率η在公式中表示權(quán)值和閾值調(diào)整的系數(shù)，具體調(diào)整方法如公式（7）。

其中，E代表第n次計算得到的目標(biāo)函數(shù)，W（n）代表連接權(quán)值，ΔW（n）代表權(quán)值調(diào)整量。學(xué)習(xí)速率η影響著網(wǎng)絡(luò)的收斂能力和收斂速率，如果η的值選取太大，則BP神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性就會降低;若η的值選取太小，BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間又會增加，使網(wǎng)絡(luò)的收斂速度下降。η的選取直接影響著ΔW（n），即影響網(wǎng)絡(luò)每一次權(quán)值的調(diào)整。本研究學(xué)習(xí)速率設(shè)置為0.1，由訓(xùn)練結(jié)果可得，此學(xué)習(xí)速率使網(wǎng)絡(luò)的收斂速度和收斂能力均滿足網(wǎng)絡(luò)的要求。

2.2.5 網(wǎng)絡(luò)層數(shù)的確定

單隱藏層部分預(yù)測數(shù)據(jù)與期望輸出值的對比圖如圖2所示。

圖中的數(shù)據(jù)是從測試數(shù)據(jù)的4 000（20×200）個數(shù)據(jù)中隨機(jī)選取的100個數(shù)據(jù)點，從圖2中可以看出，網(wǎng)絡(luò)的輸出值（預(yù)測值）與實際期望值之間的誤差很小;從測試數(shù)據(jù)所有數(shù)據(jù)與期望值之間的散點圖可以看出，單隱藏層網(wǎng)絡(luò)結(jié)構(gòu)對測試數(shù)據(jù)整體的預(yù)測精度也很高，判定系數(shù)為0.981 8，所以，單隱藏層的網(wǎng)絡(luò)結(jié)構(gòu)能較好地學(xué)習(xí)排序算法，使網(wǎng)絡(luò)的預(yù)測精度滿足要求。如圖3所示。

本次實驗選擇的是20維的數(shù)據(jù)集，訓(xùn)練數(shù)據(jù)大小為20×2 000，測試數(shù)據(jù)大小為20×200，最大迭代次數(shù)為100，學(xué)習(xí)率為0.1，單隱藏層和雙隱藏層網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測值與實際值的相關(guān)性比較實驗結(jié)果如表3所示，表中的數(shù)值表示判定系數(shù)的值。

BP神經(jīng)網(wǎng)絡(luò)中的隱藏層的個數(shù)在網(wǎng)絡(luò)中起著舉足輕重的作用，增加網(wǎng)絡(luò)隱藏層的個數(shù)，可以增強(qiáng)BP神經(jīng)網(wǎng)絡(luò)的非線性映射功能，但是隱藏層數(shù)過多，也會產(chǎn)生以下弊端：使得BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練速度減慢，網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜。由表3可得，對于20維的數(shù)據(jù)來說，單隱藏層和雙隱藏的預(yù)測結(jié)果都較好，且單個隱藏層的擬合效果更好（判定系數(shù)滿足：0.981 8>0.956 3），另一方面，單個隱藏層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡單，收斂速度快，所以本研究選擇了單隱藏層網(wǎng)絡(luò)結(jié)構(gòu)。

2.2.6 訓(xùn)練數(shù)據(jù)大小確定

數(shù)據(jù)集的大小對神經(jīng)網(wǎng)絡(luò)的輸出也有一定的影響作用，如果數(shù)據(jù)集太小，會使網(wǎng)絡(luò)的學(xué)習(xí)能力下降，如果數(shù)據(jù)集過大，會使網(wǎng)絡(luò)的收斂速度降低。所以選擇大小合適的數(shù)據(jù)集對于網(wǎng)絡(luò)也很重要。選擇維數(shù)為20的數(shù)據(jù)進(jìn)行實驗，在其他條件不變的情況下只改變數(shù)據(jù)集大小，在網(wǎng)絡(luò)收斂后，分別計算匈牙利算法和貪心算法的正確率，以此來說明數(shù)據(jù)集大小對網(wǎng)絡(luò)性能的影響，數(shù)據(jù)集大小對排序算法模擬的影響如表4所示。

由表4可得，數(shù)據(jù)集太小對排序算法的模擬結(jié)果有影響，當(dāng)數(shù)據(jù)集個數(shù)為200時，匈牙利算法的正確率為0.542 5，數(shù)據(jù)集大小為2 000時匈牙利算法的正確率較之前提高了13.36%，貪心算法對數(shù)據(jù)集大小不是很敏感，且正確率均低于匈牙利算法，但是數(shù)據(jù)集個數(shù)為2 000時的正確率也比數(shù)據(jù)集個數(shù)為200時高了4.73%。從表4還可以看出：對于維數(shù)為20的數(shù)據(jù)集，數(shù)據(jù)集大小為2 000時，匈牙利算法和貪心算法都取得了最好的效果，基于上述，所以本研究中對于每個維數(shù)的數(shù)據(jù)集，其大小均設(shè)定為2 000。

3 實驗結(jié)果分析

本研究分別選了2維、4維、6維、8維、10維、12維、15維、20維、30維和40維的數(shù)據(jù)集，分別作為BP神經(jīng)網(wǎng)絡(luò)的輸入來驗證排序算法模擬的效果，每個測試數(shù)據(jù)集都有200組數(shù)據(jù)，各個數(shù)據(jù)集的測試結(jié)果如表5所示。

表5中Accx表示用匈牙利算法匹配網(wǎng)絡(luò)輸出與網(wǎng)絡(luò)輸入的正確率，Acct表示用貪心算法匹配后的正確率，對應(yīng)的MSEx表示用匈牙利算法匹配后的均方差，MSEt表示用貪心算法匹配后的均方差，其中MSEx和MSEt的值都是在數(shù)據(jù)反歸一化之前計算得到的。

由表5可得：隨著維數(shù)的增加，本研究訓(xùn)練的排序算法模擬模型性能下降，匈牙利算法和貪心算法匹配結(jié)果的正確率都在不斷下降，均方差都在不斷增大，以至于在維數(shù)為40時，排序算法模型對于大多數(shù)數(shù)據(jù)來說，基本不能把對應(yīng)數(shù)據(jù)匹配在正確的位置上，正確率分別下降到35.16%和16.01%，均方差分別增加到0.266 0和0.875 8。從上表可以看出，本研究提出的排序算法模擬對維數(shù)比較小的數(shù)據(jù)很有效，如兩個算法對2維數(shù)據(jù)的排序正確率都可以達(dá)到100%，匈牙利算法對4個數(shù)據(jù)進(jìn)行排序時正確率可以達(dá)到95.37%，貪心算法的正確率只達(dá)到了78.63%，且對于任何一個數(shù)據(jù)集，匈牙利算法的正確率均不小于貪心算法，所以本研究中匈牙利算法優(yōu)于貪心算法。

4 總結(jié)

本研究選擇了匈牙利算法和貪心算法來實現(xiàn)網(wǎng)絡(luò)輸出結(jié)果和輸入數(shù)據(jù)的匹配，用匹配的正確率和均方差來評判匹配結(jié)果的好壞程度。實驗結(jié)果可得：匈牙利算法的匹配正確率均不低于貪心算法，如：匈牙利算法對10維數(shù)據(jù)的排序結(jié)果正確率為75.70%，全局貪心對10維數(shù)據(jù)的排序結(jié)果正確率為44.85%。兩種算法都對低維的數(shù)據(jù)更有效，數(shù)據(jù)維數(shù)越小，匹配的正確率越高，均方差越小，其中2維數(shù)據(jù)的排序結(jié)果正確率可以達(dá)到100%。

本研究對高維數(shù)據(jù)的排序結(jié)果正確率較低，今后會在提高BP神經(jīng)網(wǎng)絡(luò)的預(yù)測精度和匹配算法優(yōu)化方面做出新的改進(jìn)，如在BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程中使用文中提到的Trainbr算法、BFGS算法和LM算法，另一方面，在匹配算法優(yōu)化方面也要進(jìn)一步做點工作，旨在提高數(shù)據(jù)排序的正確率，最終實現(xiàn)更高維的數(shù)據(jù)排序。

參考文獻(xiàn)

[1] 魏振，江智軍，楊曉輝，等.基于BP神經(jīng)網(wǎng)絡(luò)的低電壓短期預(yù)測的估算[J].現(xiàn)代電子技術(shù)，2019，42（23）：62-66.

[2] 李維華，張明武.修正BP神經(jīng)網(wǎng)絡(luò)應(yīng)用于珠江洪水預(yù)報[J].通訊世界，2019，26（11）：21-22.

[3] 李廷鵬，錢彥嶺，李岳.基于改進(jìn)匈牙利算法的多技能人員調(diào)度方法[J].國防科技大學(xué)學(xué)報，2016，38（2）：144-149.

[4] 黃邦菊，熊惠敏，朱代武，等.基于貪心算法的航班-登機(jī)口模型[J].航空計算技術(shù)，2019，49（6）：10-13.

（收稿日期： 2019.11.05）