基于Spark+遺傳算法智能組卷方法

張若冰

摘 要：隨著計算機應(yīng)用技術(shù)的不斷發(fā)展，由計算機與教育相結(jié)合而產(chǎn)生的計算機輔助教育系統(tǒng)得到了快速發(fā)展。在目前的素質(zhì)教育下，考試仍然是衡量教師教學(xué)能力和學(xué)生學(xué)習(xí)成績的主要衡量標(biāo)準(zhǔn)之一，同時不同層次的考試對試卷衡量標(biāo)準(zhǔn)也是不盡相同的。那么，如何依靠算法組出一套科學(xué)合理且高質(zhì)量的試卷是評定計算機與教育結(jié)合效果的手段之一。因此，對高效智能組卷算法的研究是非常具有實際應(yīng)用價值的。

關(guān)鍵詞：計算機輔助教育；智能組卷；遺傳算法；

主要內(nèi)容

隨著計算機應(yīng)用技術(shù)的不斷發(fā)展，由計算機與教育相結(jié)合而產(chǎn)生的計算機輔助教育系統(tǒng)得到了快速發(fā)展。在目前的素質(zhì)教育下，考試仍然是衡量教師教學(xué)能力和學(xué)生學(xué)習(xí)成績的主要衡量標(biāo)準(zhǔn)之一，同時不同層次的考試對試卷衡量標(biāo)準(zhǔn)也是不盡相同的。那么，如何依靠算法組出一套科學(xué)合理且高質(zhì)量的試卷是評定計算機與教育結(jié)合效果的手段之一。因此，對高效智能組卷算法的研究是非常具有實際應(yīng)用價值的。

遺傳算法是一種模擬自然界生物進(jìn)化過程與機制的元啟發(fā)式搜索技術(shù)，被廣泛應(yīng)用于求解復(fù)雜的優(yōu)化問題。通常，窮盡搜索完整的輸入空間是不可行的，遺傳算法可以用來通過搜索較小的輸入空間，在合理的時間里求出好的問題解。傳統(tǒng)遺傳算法通過順序執(zhí)行選擇、交叉、變異等遺傳操作，尋找問題的最優(yōu)解。傳統(tǒng)遺傳算法用于求解復(fù)雜的優(yōu)化問題時，通常需要較長的計算時間。

為了解決遺傳算法帶來的計算性能問題，本發(fā)明提供一種基于Spark的并行化遺傳算法。Spark是一種快速、通用的并行計算框架，它的核心是一種彈性分布式數(shù)據(jù)集RDD。Spark通過對RDD進(jìn)行并行切片，然后分發(fā)到集群中的多個節(jié)點上完成相應(yīng)的變換操作，最后由行動操作觸發(fā)所有的運算。Spark的這種運算方式非常適合并行化遺傳算法的實現(xiàn)。

試題庫自動組卷是運用信息處理技術(shù)，從試題庫中自動選擇試題組成試卷的。自動組卷的主要難題是如何保證生成的試卷能最大程度地滿足用戶的需要，并具有隨機性、科學(xué)性、合理性。因此需要選擇一個高效的自動組卷算法。

目前，已有運用遺傳算法進(jìn)行自動組卷的方法。遺傳算法是一種模擬自然界適者生存的淘汰選擇方式和遺傳機制的計算機隨機優(yōu)化算法。遺傳算法的遺傳操作主要有 ：選擇、交叉、變異。遺傳算法需要采用某種編碼方式將解空間映射到編碼空間。類似于生物染色體結(jié)構(gòu)，這樣容易用生物遺傳理論解釋，各種遺傳操作也易于實現(xiàn)。因此，編碼理論是遺傳算法效率的重要決定因素之一。二進(jìn)制編碼是最常用的編碼方式，算子處理的模式較多也較易于實現(xiàn)。但是，自動組卷過程中，采用二進(jìn)制編碼的方式往往效率較低。

因此，在利用遺傳算法進(jìn)行自動組卷的過程中，就需要選取合適的編碼方式。另外，也需要對遺傳操作進(jìn)行改進(jìn)，以實現(xiàn)更好的組卷效果。

具體實施方式

本發(fā)明旨在解決上面描述的問題。本發(fā)明的目的是提供一種利用遺傳算法的自動組卷方法，根據(jù)本發(fā)明的一個方面，本發(fā)明提供了一種利用遺傳算法的自動組卷方法，所述自動組卷方法包括以下步驟 ：（1） 根據(jù)設(shè)定的條件生成初始種群，所述初始種群中包括 n 個個體，其中 n 為正整數(shù)，每個個體的生成方法如下 ：將題庫中的試題根據(jù)題型形成多個題型集合并將每個題型集合中的試題按照實數(shù)方式排序，從各個題型集合中選取設(shè)定數(shù)量的試題，并按照相同題型集合中的試題序號相鄰的方式將所選取試題的序號組成實數(shù)序列，所述實數(shù)序列即為種群中的個體 ；（2） 計算每個所述個體的適應(yīng)度函數(shù)值，如果有個體的適應(yīng)度函數(shù)值符合優(yōu)化準(zhǔn)則，則選中適應(yīng)度函數(shù)值符合優(yōu)化準(zhǔn)則的個體并結(jié)束所述自動組卷方法，如果沒有個體適應(yīng)度函數(shù)值符合優(yōu)化準(zhǔn)則，則執(zhí)行步驟 （3） ；（3） 進(jìn)行遺傳操作，所述遺傳操作包括選擇操作、交叉操作、變異操作，其中，根據(jù)所述個體的適應(yīng)度函數(shù)值對種群中的個體進(jìn)行選擇操作，根據(jù)題型集合將所述實數(shù)序列分成相應(yīng)的序列段，根據(jù)序列段進(jìn)行交叉操作 ；（4） 由所述遺傳操作生成的新個體生成新一代的種群，并返回到步驟 （2）。

其中，所述步驟 （2） 中的述適應(yīng)度函數(shù)值的計算公式為：

其中，Psi 為該個體適應(yīng)度函數(shù)值，fi 為每個條件要素的權(quán)值，F(xiàn)i 為每個條件要素的適應(yīng)度，M 為所有條件要素的個數(shù)，且 fi 滿足：

其中，所述條件要素的適應(yīng)度 Fi 的計算公式為 Fi = 1-（|ai-bi|/bi），bi 為條件要素的要求得分，ai 為條件要素的實際得分。

其中，所述條件要素包括試卷難度、分值分布。

其中，所述步驟 （3） 包括 ：（31） 對種群中的個體進(jìn)行選擇操作，得到第一個體，然后對種群中剩下的個體進(jìn)行選擇操作，得到第二個體 ；（32） 將所述第一個體和所述第二個體進(jìn)行交叉操作，得到兩個交叉后的個體 ；（33） 對所述兩個交叉后的個體進(jìn)行變異操作，得到兩個新個體 ；（34） 重復(fù)步驟 （31）、步驟 （32） 和步驟 （33），直到生成滿足種群中個體數(shù)量的所有新個體。

其中，所述步驟 （31） 中的選擇操作包括 ：（311） 累加種群中每個所述個體的適應(yīng)度函數(shù)值，得到總值 ；（312）生成隨機數(shù)，所述隨機數(shù)大于等于零，小于等于1 ；（313）將所述總值乘以所述隨機數(shù)，得到轉(zhuǎn)輪值 ；（314） 依次累加種群中每個所述個體的適應(yīng)度函數(shù)值，得到與所述個體相應(yīng)的總值′，如果所述總值′大于或等于所述轉(zhuǎn)輪值，則與所述總值′相對應(yīng)的所述個體被選中。

其中，所述步驟 （32） 包括 ：（321） 隨機選擇一個題型集合 ；（322） 將選擇操作得到的所述第一個體和所述第二個體中與所選擇的題型集合相應(yīng)的序列段進(jìn)行交換，從而得到所述兩個交叉后的個體。

其中，在所述步驟 （1） 中，所述設(shè)定的條件包括 ：總體量、章節(jié)分值分配、題型分值分配。

其中，在所述步驟 （2） 中，所述優(yōu)化準(zhǔn)則為個體的適應(yīng)度函數(shù)值大于設(shè)定的閾值。

本發(fā)明的利用遺傳算法的自動組卷方法，在遺傳算法中引入有條件生產(chǎn)初始種群、對個體進(jìn)行實數(shù)編碼，以及在交叉操作中進(jìn)行分段交叉的方式，使得所利用的遺傳算法搜索速度快，盡量避免同一試卷中出現(xiàn)同一考查點多道題的情況，使試卷的覆蓋面廣，組出更合理的試卷。此外，該自動組卷方法大大減少教師在考試命題中的工作量，同時還可以避免由于人為因素造成的偏差，在對目前的組卷系統(tǒng)進(jìn)行分析了解的基礎(chǔ)上結(jié)合實際命題經(jīng)驗，并利用了遺傳算法的全局尋優(yōu)和收斂速度快的特點。

參照附圖來閱讀對于示例性實施例的以下描述，本發(fā)明的其他特征和優(yōu)點將變得清晰。

附圖說明

并入到說明書中并且構(gòu)成說明書的一部分的附圖示出了本發(fā)明的實施例，并且與描述一起用于解釋本發(fā)明的原理。在這些附圖中，類似的附圖標(biāo)記用于表示類似的要素。下面描述中的附圖是本發(fā)明的一些實施例，而不是全部實施例。對于本領(lǐng)域普通技術(shù)人員來講，在不付出創(chuàng)造性勞動的前提下，可以根據(jù)這些附圖獲得其他的附圖。

圖 1 示例性地示出了根據(jù)本發(fā)明的利用遺傳算法的自動組卷方法的流程圖。

技術(shù)方案：基于Spark的并行化遺傳算法智能組卷方法，包括如下步驟：

（1）適應(yīng)度值計算并行化：隨機生成初始種群，從初始種群創(chuàng)建Spark的RDD，并將RDD劃分為多個分區(qū)分布到集群的多個節(jié)點中，每個分區(qū)對應(yīng)一個子種群，各個子種群在各自的節(jié)點上進(jìn)行適應(yīng)度值的計算，并將計算結(jié)果收回到Spark的主節(jié)點上；

（2）遺傳操作并行化：將帶有適應(yīng)度值的種群劃分為多個子種群，并作為RDD的多個分區(qū)再次分布到集群的多個節(jié)點中，各個子種群在各自的節(jié)點上進(jìn)行獨立進(jìn)化，在進(jìn)化滿足終止條件時收集RDD不同分區(qū)中的最好的個體，并將結(jié)果返回到Spark的主節(jié)點上。

進(jìn)一步的，步驟（1）具體包括如下子步驟：

（1.1）隨機生成初始種群，隨機生成的初始種群通過Spark的parallelize函數(shù)轉(zhuǎn)換為種群RDD，并將種群RDD劃分為多個分區(qū)分布到集群的多個節(jié)點中，RDD包含的分區(qū)的數(shù)量，以及每個分區(qū)包含的個體的數(shù)量，由Spark自動分配；

（1.2）通過Spark的mapPartitions（assessFitness（））函數(shù)將種群RDD轉(zhuǎn)換為適應(yīng)度值RDD，該RDD包含鍵值對，其中key是一個個體，value是該個體的適應(yīng)度值，函數(shù)assessFitness（）用于計算個體的適應(yīng)度值，它被分布到集群中不同的節(jié)點上并行計算；

（1.3）Spark的collect函數(shù)觸發(fā)Spark的運算流程，完成步驟（1.2）中的所述轉(zhuǎn)換，并將這些鍵值對收回到主節(jié)點上。

進(jìn)一步的，步驟（2）具體包括如下子步驟：

（2.1）將帶有適應(yīng)度值的種群再次通過Spark的parallelize函數(shù)變換為種群RDD；

（2.2）通過Spark的mapPartitions（evolution（））函數(shù)將種群RDD中的各個子種群分布到Spark集群的不同的工作節(jié)點上，并轉(zhuǎn)換為進(jìn)化RDD，函數(shù)evolution（）用于執(zhí)行遺傳操作，被分布到集群中不同的節(jié)點上并行進(jìn)化，所述遺傳操作包括選擇、交叉和變異；

（2.3）通過Spark的map（getBest（））函數(shù)將進(jìn)化RDD轉(zhuǎn)換為最優(yōu)個體RDD，該RDD包含鍵值對，其中key是一個鍵值對，value是發(fā)現(xiàn)解決方案時的進(jìn)化代數(shù)；函數(shù)getBest（）用于獲得每個子種群中的最好個體，被分布到集群中不同的節(jié)點上并行執(zhí)行；

（2.4）Spark的collect函數(shù)觸發(fā)Spark的運算流程，將步驟（2.3）中每個子種群中的最好個體都收回到主節(jié)點上，找出其中最好的一個，作為最優(yōu)結(jié)果輸出。

進(jìn)一步的，步驟（2.2）中所述遺傳操作具體為：選擇操作采用適應(yīng)度值比例法；交叉操作采用多點隨機交叉；變異操作采用多點隨機變異。

有益效果：本發(fā)明利用Spark的基于內(nèi)存的計算模型，充分利用Spark分布式并行計算能力，從適應(yīng)度值計算和遺傳操作兩方面將遺傳算法并行化，提高了遺傳算法的性能。大提高了通過遺傳算法獲取最優(yōu)個體的效率，使得出卷的效率更高，成功率更高。

備注：

parallelize：函數(shù)來創(chuàng)建并行集合。

mapPartition：為每個partition創(chuàng)建一個鏈接。

assessFitness：用于計算個體的適應(yīng)度值。

collect：收集鍵值對到主節(jié)點上。

evolution：執(zhí)行遺傳操作，并行進(jìn)化。

getBest：獲得每個子種群中的最好個體。