張若冰

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

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

主要內(nèi)容

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

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

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

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

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

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

具體實(shí)施方式

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

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

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

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

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

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

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

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

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

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

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

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

附圖說明

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

備注：

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

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

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

collect：收集鍵值對(duì)到主節(jié)點(diǎn)上。

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

getBest：獲得每個(gè)子種群中的最好個(gè)體。