基于差分進化算法的教育資源分配模型

劉寶寶,王賀應,陶 露,楊菁菁

(西安工程大學 計算機科學學院，陜西 西安 710048)

0 引 言

教育資源配置均衡不僅關乎著我國教育事業的發展，而且體現著教育事業的公平公正，在教育體系中發揮著重要作用。教育的可持續發展能夠使其保持著生機和活力，促進創新型人才的培養。教育資源分配不均會導致教育質量的非均衡性發展，在一定程度上會對教育的可持續發展產生阻礙。教育資源分配不均衡還會影響基層教育目標的實現，影響著學生的德智體美勞全面發展。如何有效并合理地分配教育資源是教育管理部門的一項重要工作，也是一項嚴峻的挑戰。文獻[1]提出了由于教育資源分配不均產生的部分社會問題，如教育服務于市場并與房地產市場緊密聯系，從而出現了“學區房”相關問題。教育資源分配不均還會加劇課外輔導熱。因此，對教育資源進行合理的分配是促進區域教育均衡發展的重要環節。文獻[2]認為教育資源的不均衡是資源分配不合理和固有的教育體制所引起的。優化教育資源在一定程度上促進了教育資源分配的均衡發展，同時可以有效地減少教育資源不均所帶來的不利因素。

目前大部分教育資源的分配是依靠人工統計完成，存在成本高、效率低、統計工作復雜等問題。不利于教育事業的發展。近年來，智能算法在教育事業統計和資源分配方面的應用引起了研究者的關注。文獻[3]以某13個區縣原有的教育資源數據為依據，提出基于粒子群算法的教育資源分配模型，在一定程度上改善了教育資源的分配不均衡問題。粒子群[4](particle swarm optimization, PSO)算法是群體智能算法的一種[5]。該算法通過群體中個體之間的協作和信息共享尋找最優解,每個粒子視為一個個體[6]，并且具有速度特征和位置特征，分別表示粒子移動的快慢和方向，在迭代過程中粒子的速度和位置會不斷更新變化[7]。PSO算法的優勢在于簡單、容易實現，并且只需要調整少許的參數。但該算法在數據維度較高時，容易陷入局部最優解[8]，需要較大的迭代次數才能使適應度值收斂。

本文提出了一類基于差分進化(differential evolution, DE)算法的教育資源分配模型，該模型結構簡單、參數較少、性能優越。DE算法具有內在并行性，種群中的個體之間可以協同搜索。在相同的條件下，DE算法具有較快的收斂速度，能夠實現教育資源合理有效的分配[9]。與基于PSO算法的教育資源分配模型相比，該模型在迭代速度、運行時間方面具有一定的優勢。為了驗證此模型對教育資源分配的有效性，文中還建立了基于人工魚群算法[10](artificial fish swarms algorithm，AFSA)的教育資源分配模型，實現了某13個區縣教育資源數據分配的圖形用戶界面(graphical user interface, GUI)，為教育管理部門提供資源分配依據，同時為教育統計大數據模型的優化提供一定的理論基礎。

1 教育資源分配模型的建立

1.1 DE算法

DE算法是一種基于群體差異的啟發式并行搜索方法[11]，群體中每個個體對應一個解向量。該算法的流程與遺傳算法相似，都包括變異、交叉和選擇操作，但這些操作的具體定義與遺傳算法有所不同。

DE算法的基本思想是從某一隨機種群開始，對個體進行初始化、變異、交叉和選擇操作，最終保留最優個體[12]。該算法具有較強的搜索能力[13]，是一種高效的全局優化算法。首先，種群經過初始化操作,從中隨機選擇2個不同的個體進行差分和縮放[14],并從種群中再隨機挑選個體進行向量合成進而產生變異個體；然后，對父代個體和變異個體進行交叉操作[15]，從而獲得新的個體；最后，對個體與父代個體的適應度值進行比較,選擇個體適應度值最優的個體進入下一代繼續迭代，直到滿足終止準則[16]。具體分5個步驟。

1) 初始化。在解空間里隨機產生滿足約束條件的N個由D維向量組成的個體[17]，第i個個體的j維取值方式為

(1)

(2)

(3)

4) 邊界條件處理。DE算法經過交叉操作和變異操作后，可能會導致種群中部分個體范圍超出給定的范圍。假設u的范圍是[v,w],u′是經過交叉和變異操作后產生的新個體，需要對上述操作后得到的個體進行邊界條件判斷并做出相應的處理。處理方法一般有2種：

ⅰ) 邊界吸收，

(4)

ⅱ) 重新隨機生成新的個體，即當u′w時,

u′=v+rand(0,1)×(w-v)

(5)

5) 選擇。選擇操作使用錦標賽選擇機制，從種群中的個體和通過變異和交叉操作得到的個體中選擇出最好的個體進入下一代[21]。具體方式為

(6)

算法通過不斷的迭代計算，保留優良個體，淘汰劣勢個體，引導搜索過程向全局最優解逼近，最終輸出最優結果[22]。

1.2 教育資源分配模型的實施

基于DE算法的教育資源分配模型流程如圖1所示。

圖 1 基于DE算法的教育資源分配模型Fig.1 Educational resource allocation model based on DE algorithm

Step 1 初始化種群并進行歸一化。根據目標函數計算初始化種群中的個體，得到每個個體的適應度值。該模型的種群規模NP影響著算法的尋優能力：NP越大，種群的多樣性也就越好，尋優能力也就越強。但NP不能過大，否則會增加計算難度。綜合考慮,此模型中的種群規模NP取20。

Step 3 驗證結束條件。基于DE算法的教育資源分配模型分配教育資源的結束條件為當前的迭代次數超過初始化的迭代次數，或者為多次迭代后，適應度值的結果沒有發生變化，教育資源分配模型流程結束。為了縮小區縣之間教育資源分配不均衡的狀況，假設現有1 000名新招教師和100 000冊新圖書要分配到這13個區縣?；贒E算法的教育資源分配模型中算法的迭代次數根據分配教育資源數目的不同而不同：根據教師資源數，在教師分配時模型的迭代次數設置為200；在分配圖書冊資源時，模型的迭代次數為2 000。教育資源分配模型根據教育資源分配數目的不同，迭代次數取不同的值，進而保證基于DE算法的教育資源分配模型尋優結果的全局最優性[3]。

1.3 目標函數

本文模型采用了文獻[3]中的均方差作為適應度值函數，適應度值的表示為

(7)

式中:Yi表示教育資源分配到各區縣之后的適應度總值，i≥1；Y0表示初始適應度總值，且初始值為0;Ni表示分配前各區縣的資源總數;ni表示教育資源分配模型分配到各區縣的資源數;si表示各區縣的學生人數。已知待分配的資源總數和原有的教育資源數，式(7)中僅存在一個變量，即待分配到各區縣的資源數ni。Yi的值恒大于零，分配資源ni≥0。經過上述分析，若要降低Yi的值，需要將教育資源優先分配給低于總區縣資源平均值的區縣。

2 仿真實驗

本文使用文獻[3]的統計數據,見表1。表1中，生師比越小表示每位教師能夠更有效地輔導學生； 生均圖書冊數值越大表示每個學生可擁有圖書冊的數量越多。通過表1中的統計數據可以看出，部分區縣之間的生師比和生均圖書冊數存在著較大的差距，說明了原有的教育資源分配不均衡的情況比較嚴重。

為了改善區縣之間原有的教育資源分配不均的現狀，教育資源分配模型會根據目標函數，在分配資源的過程中適當地降低生師比，提高生均圖書冊數，使得區縣之間的生師比和生均圖書冊數盡可能地趨于均衡狀態。

表 1 教育資源統計數據[3]

2.1 生師比分配

根據目標函數，基于DE算法的教育資源分配模型會將教師優先分配給生師比較高的區縣，從而降低適應度總值Yi。模型會比較各個分配方案的Yi值，并將Yi取最小值時所對應的分配結果作為最佳方案，從而降低區縣之間教師資源的差距。

表2分別給出了基于DE算法和PSO算法的教育資源分配模型對1 000名教師進行分配的結果。從表2中可以看出:2種模型具有相近的教育資源分配性能，5個生師比較高的區縣，即區縣11，10，8，12和7都有新教師被分配，在一定幅度上降低了這5個區縣的生師比的比值。

圖2描述了基于DE算法的教育資源分配模型分配教師資源前后的生師比變化趨勢。

圖 2 各區縣生師比分配前后對比

從圖2可以看出：各區縣生師比分配前，區縣11的生師比接近12，而區縣4的生師比僅有3.456，原有的教師資源分配差距較大；分配后，區縣11、10、8、12和7的生師比都有著明顯的下降趨勢。從而驗證了該模型在分配教師資源方面能夠有效改善區縣之間教師資源分配不均衡的問題。因此，應用該模型對教師資源進行分配，能夠有效地縮小各個區縣生師比的差距，在一定程度上改善教師資源分配不均衡的現況，促進教育事業的公平公正。

表 2 生師比變化情況

2.2 生均圖書冊分配

表3分別給出了基于差分進化算法的教育資源分配模型和基于POS算法的教育資源分配模型對100 000冊圖書進行分配的結果。

表 3 生均圖書冊數變化情況

從表3可以看出：2種模型都能對圖書資源進行合理的分配，提高了部分區縣的生均圖書冊數，并且具有相近的分配結果。

圖3描述了基于DE算法的教育資源分配模型分配圖書冊資源前后的生均圖書冊數變化趨勢。

圖 3 各區縣生均圖書冊數分配前后對比Fig.3 The number of books before and after allocation of each area

從圖3可以看出，區縣之間的生均圖書冊數的差異較大，最小值是最大值的1/4，圖書冊數資源分配不均衡的情況比較嚴重。經過對圖書冊數資源數據的分析，個別區縣原有的圖書冊數多達190多萬冊，少則26萬冊，所以13個區縣總的圖書冊數基數差異較大。而待分配的圖書冊數僅有10萬冊，相比原有的圖書冊總數差距較大。經過教育資源分配模型的分配，圖書僅分配到圖書資源較少的2個區縣，即區縣10和區縣12，但生均圖書冊數在各區縣之間的差距并沒有得到根本的改善。

可見，通過教育資源分配模型對圖書冊數進行分配，并不能從根本上改善區縣之間生均圖書冊數的差距。若想改善由于基數過大而造成的教育資源分配不均衡的問題，需要耗費大量的財力和人力才可能縮短區縣之間的教育資源差距。所以，在初始的圖書冊數分配階段，應充分考慮圖書冊數資源的分配是否合理，而不能只依靠教育資源分配模型分配新的圖書解決區縣之間的圖書冊數資源不均衡問題。

2.3 不同教育資源分配模型的比較

為了進一步說明基于DE算法的教育資源分配模型的有效性，建立了基于AFSA的教育資源分配的仿真模型。通過大量的仿真實驗數據，驗證了DE、PSO及AFSA等3種智能算法的教育資源分配模型的分配結果相近，但在算法的執行效率上有所差異。

從教育資源適應度值的收斂趨勢、教育資源適應度值收斂時的平均迭代次數、教育資源分配模型的時間復雜度以及模型分配教育資源的平均運行時間(單位：s)等4個方面對3種智能算法的教育資源分配模型進行比較和分析。圖4、5分別描述了3種智能算法教育資源分配模型教師資源分配和圖書冊資源分配所得到的適應度值收斂趨勢。

圖 4 教師資源適應度值收斂趨勢Fig.4 Convergence trend of teacherresource fitness value

圖 5 圖書冊數資源適應度值收斂趨勢Fig.5 Convergence trend of book resource fitness value

表4為3種模型在分配教育資源過程中，適應度值收斂時平均迭代次數。

表 4 適應度值收斂時的平均迭代次數

從表4可以看出，基于PSO算法的教育資源分配模型的迭代次數最高，收斂速度最慢。其主要原因在于PSO算法在處理高維度問題時容易陷入局部最優解，所以算法需要較長的迭代的次數才能使適應度值收斂。基于AFSA的教育資源分配模型的迭代次數最低，收斂速度最快，是因為人工魚群算法具有并行處理的能力[25]，即人工魚群通過并行搜索進而尋找最優解。AFSA中的聚群行為能夠使算法快速擺脫局部最優解，追尾行為能使算法在較少的迭代次數中使適應度值達到收斂，從而加快AFSA尋找最佳適應度值的速度。

分析3種資源分配模型的時間復雜度:設m為算法的迭代次數;n為種群的數目;D為維度，即區縣的個數;t為人工魚群算法中魚群的嘗試次數。計算得出基于AFSA的教育資源分配模型具有較高的時間復雜度,為O(m·n·D·(t+n));基于PSO算法的教育資源分配模型和基于DE的教育資源分配模型具有相同的時間復雜度,即O(m·n·D)。不過，基于DE的教育資源分配模型與基于PSO算法的教育資源分配模型相比，需要較少的迭代次數便可以獲得最優解。

表5為3種模型在分配教育資源過程中，適應度值收斂時平均運行時間。

表 5 教育資源分配模型的平均運行時間

從表5可以看出，基于DE算法的教育資源分配模型的平均運行時間最短，而基于AFSA的教育資源分配模型的平均運行時間最長。因為AFSA包括覓食行為、聚群行為、追尾行為和隨機行為等4種行為，在算法的每一次迭代中，計算過程比較復雜，因此該模型在分配教育資源的運行時間較長，分配效率較低。

經過對3種模型的綜合分析可以得出：AFSA的教育資源分配模型在分配教師資源時能夠在較少的迭代次數使適應度值達到收斂，但模型得到最終分配結果所運行的時間最長。隨著教育資源數據量的增大，DE算法的教育資源分配模型和AFSA的教育資源分配模型都能夠在較少的迭代次數中使適應度值收斂，而PSO算法的教育資源分配模型仍需較多的迭代次數才能使適應度值收斂。在3種資源分配模型中，AFSA教育資源分配模型的運行時間遠大于DE算法教育資源分配模型的運行時間，資源分配的效率較低。通過比較和分析，驗證了DE算法的教育資源分配模型的有效性。

3 MATLAB的GUI仿真

利用MATLAB GUI能夠設計出人機交互式的圖形化界面，方便用戶使用。用戶在GUI界面上執行相關操作便可以使計算機運行相關的回調函數，進而顯示用戶所期望的輸出結果。因此，為了更加直觀地顯示3種模型分配教師和圖書冊數資源的差異，圖6構建了3種模型對某13個區縣的教育資源數據分配結果的可視化界面。其GUI界面主要包括資源分配的按鈕、資源分配所需要的時間、資源分配結果的展示和教育資源分配模型適應度值的收斂趨勢等4個模塊。

圖 6 教育資源數據分配可視化界面Fig.6 Educational resource data distribution visualization

用戶在GUI界面的資源分配模塊中，輸入待分配的教育資源數后，點擊分配教師資源模塊中的PSO_TE按鈕，則會在資源分配結果展示模塊中的左側表格中顯示一列PSO教育資源分配模型分配教師資源的方案，同時也會在模型收斂趨勢的模塊中顯示該模型分配教師資源時適應度值的收斂趨勢。DE_TE按鈕和AFSA_TE按鈕的功能與PSO_TE按鈕相同。點擊分配圖書冊資源模塊中的PSO_Book按鈕，則會在資源分配結果展示模塊中的右側表格顯示PSO教育資源分配模型分配圖書冊資源的方案，同時也會在模型收斂趨勢的模塊中顯示該模型分配圖書資源時的適應度值收斂趨勢。DE _Book按鈕和AFSA _Book按鈕功能等同于PSO_Book按鈕，會分別展示模型分配圖書冊資源的結果以及適應度值的收斂趨勢。

點擊Teachers按鈕，則會在資源分配結果的模塊中的左側表格顯示3種教育資源分配模型分配教師資源的方案，在教師資源分配時間模塊也會分別顯示3種模型分配教師所執行的時間，同時在模型收斂趨勢的模塊中顯示3種模型分配教師資源的適應度值收斂趨勢。Book按鈕有3種教育資源模型對圖書冊資源進行分配的功能,并顯示圖書冊資源分配的結果、模型運行的時間對比和模型分配圖書資源時的適應度值收斂趨勢。

4 結 語

教育資源的合理分配對于教育管理部門是一個挑戰。資源分配到各個區縣后，還需要分配到具體的學?；蛘呓逃龣C構，是一項比較繁瑣的任務。在教育資源分配的過程中，需要考慮各區縣原有的資源情況，盡可能地改善教育資源分配不均衡。從資源分配的結果分析，當待分配的資源與原有的教育資源的總基數相差不大時，使用教育資源分配模型分配教育資源，可以適當地縮小區縣之間的差距，從而使得教育資源的分配更加科學合理。對于某些教育資源基數過大的問題，則需引起教育管理部門的重視。在今后的教育機構基礎建設時，應充分考慮到教育區域資源的均衡問題，否則區縣之間的教育資源差距不易縮小。

此外，本文的模型是基于差分進化算法提出的，即算法中的縮放因子F為固定值。F過大會降低模型的收斂速度；F過小會降低種群的多樣性。同理，交叉算子CR也可以設置動態值，保持種群的多樣性。因此，在未來的工作中，基于改進的DE教育資源分配模型可以將縮放因子F設置為動態的值：在算法的迭代初期F較大，可以保持種群的多樣性，加快尋找最優解；隨著迭代次數的增加，可以適當減小F值，以保存種群中的優良個體，避免破壞最優解，從而更加合理有效地分配教育資源，逐漸縮短各區縣之間的差距。