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

張若冰

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

關鍵詞：計算機輔助教育；智能組卷；遺傳算法；

主要內容

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

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

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

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

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

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

具體實施方式

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

其中，所述步驟 （2） 中的述適應度函數值的計算公式為：

其中，Psi 為該個體適應度函數值，fi 為每個條件要素的權值，Fi 為每個條件要素的適應度，M 為所有條件要素的個數，且 fi 滿足：

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

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

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

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

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

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

其中，在所述步驟 （2） 中，所述優化準則為個體的適應度函數值大于設定的閾值。

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

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

附圖說明

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

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

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

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

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

進一步的，步驟（1）具體包括如下子步驟：

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

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

（1.3）Spark的collect函數觸發Spark的運算流程，完成步驟（1.2）中的所述轉換，并將這些鍵值對收回到主節點上。

進一步的，步驟（2）具體包括如下子步驟：

（2.1）將帶有適應度值的種群再次通過Spark的parallelize函數變換為種群RDD；

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

（2.3）通過Spark的map（getBest（））函數將進化RDD轉換為最優個體RDD，該RDD包含鍵值對，其中key是一個鍵值對，value是發現解決方案時的進化代數；函數getBest（）用于獲得每個子種群中的最好個體，被分布到集群中不同的節點上并行執行；

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

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

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

備注：

parallelize：函數來創建并行集合。

mapPartition：為每個partition創建一個鏈接。

assessFitness：用于計算個體的適應度值。

collect：收集鍵值對到主節點上。

evolution：執行遺傳操作，并行進化。

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