基于差分進(jìn)化算法的教育資源分配模型

劉寶寶,王賀應(yīng),陶 露,楊菁菁

(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048)

0 引 言

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

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

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

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

1.1 DE算法

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

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

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

(1)

(2)

(3)

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

ⅰ) 邊界吸收，

(4)

ⅱ) 重新隨機(jī)生成新的個(gè)體，即當(dāng)u′w時(shí),

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

(5)

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

(6)

算法通過不斷的迭代計(jì)算，保留優(yōu)良個(gè)體，淘汰劣勢個(gè)體，引導(dǎo)搜索過程向全局最優(yōu)解逼近，最終輸出最優(yōu)結(jié)果[22]。

1.2 教育資源分配模型的實(shí)施

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

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

Step 1 初始化種群并進(jìn)行歸一化。根據(jù)目標(biāo)函數(shù)計(jì)算初始化種群中的個(gè)體，得到每個(gè)個(gè)體的適應(yīng)度值。該模型的種群規(guī)模NP影響著算法的尋優(yōu)能力：NP越大，種群的多樣性也就越好，尋優(yōu)能力也就越強(qiáng)。但NP不能過大，否則會(huì)增加計(jì)算難度。綜合考慮,此模型中的種群規(guī)模NP取20。

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

1.3 目標(biāo)函數(shù)

本文模型采用了文獻(xiàn)[3]中的均方差作為適應(yīng)度值函數(shù)，適應(yīng)度值的表示為

(7)

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

2 仿真實(shí)驗(yàn)

本文使用文獻(xiàn)[3]的統(tǒng)計(jì)數(shù)據(jù),見表1。表1中，生師比越小表示每位教師能夠更有效地輔導(dǎo)學(xué)生； 生均圖書冊數(shù)值越大表示每個(gè)學(xué)生可擁有圖書冊的數(shù)量越多。通過表1中的統(tǒng)計(jì)數(shù)據(jù)可以看出，部分區(qū)縣之間的生師比和生均圖書冊數(shù)存在著較大的差距，說明了原有的教育資源分配不均衡的情況比較嚴(yán)重。

為了改善區(qū)縣之間原有的教育資源分配不均的現(xiàn)狀，教育資源分配模型會(huì)根據(jù)目標(biāo)函數(shù)，在分配資源的過程中適當(dāng)?shù)亟档蜕鷰煴龋岣呱鶊D書冊數(shù)，使得區(qū)縣之間的生師比和生均圖書冊數(shù)盡可能地趨于均衡狀態(tài)。

表 1 教育資源統(tǒng)計(jì)數(shù)據(jù)[3]

2.1 生師比分配

根據(jù)目標(biāo)函數(shù)，基于DE算法的教育資源分配模型會(huì)將教師優(yōu)先分配給生師比較高的區(qū)縣，從而降低適應(yīng)度總值Yi。模型會(huì)比較各個(gè)分配方案的Yi值，并將Yi取最小值時(shí)所對應(yīng)的分配結(jié)果作為最佳方案，從而降低區(qū)縣之間教師資源的差距。

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

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

圖 2 各區(qū)縣生師比分配前后對比

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

表 2 生師比變化情況

2.2 生均圖書冊分配

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

表 3 生均圖書冊數(shù)變化情況

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

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

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

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

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

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

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

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

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

圖 5 圖書冊數(shù)資源適應(yīng)度值收斂趨勢Fig.5 Convergence trend of book resource fitness value

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

表 4 適應(yīng)度值收斂時(shí)的平均迭代次數(shù)

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

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

表5為3種模型在分配教育資源過程中，適應(yīng)度值收斂時(shí)平均運(yùn)行時(shí)間。

表 5 教育資源分配模型的平均運(yùn)行時(shí)間

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

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

3 MATLAB的GUI仿真

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

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

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

點(diǎn)擊Teachers按鈕，則會(huì)在資源分配結(jié)果的模塊中的左側(cè)表格顯示3種教育資源分配模型分配教師資源的方案，在教師資源分配時(shí)間模塊也會(huì)分別顯示3種模型分配教師所執(zhí)行的時(shí)間，同時(shí)在模型收斂趨勢的模塊中顯示3種模型分配教師資源的適應(yīng)度值收斂趨勢。Book按鈕有3種教育資源模型對圖書冊資源進(jìn)行分配的功能,并顯示圖書冊資源分配的結(jié)果、模型運(yùn)行的時(shí)間對比和模型分配圖書資源時(shí)的適應(yīng)度值收斂趨勢。

4 結(jié) 語

教育資源的合理分配對于教育管理部門是一個(gè)挑戰(zhàn)。資源分配到各個(gè)區(qū)縣后，還需要分配到具體的學(xué)?；蛘呓逃龣C(jī)構(gòu)，是一項(xiàng)比較繁瑣的任務(wù)。在教育資源分配的過程中，需要考慮各區(qū)縣原有的資源情況，盡可能地改善教育資源分配不均衡。從資源分配的結(jié)果分析，當(dāng)待分配的資源與原有的教育資源的總基數(shù)相差不大時(shí)，使用教育資源分配模型分配教育資源，可以適當(dāng)?shù)乜s小區(qū)縣之間的差距，從而使得教育資源的分配更加科學(xué)合理。對于某些教育資源基數(shù)過大的問題，則需引起教育管理部門的重視。在今后的教育機(jī)構(gòu)基礎(chǔ)建設(shè)時(shí)，應(yīng)充分考慮到教育區(qū)域資源的均衡問題，否則區(qū)縣之間的教育資源差距不易縮小。

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