基于改進遺傳算法智能組卷系統的研究

李國安

摘 要：智能組卷的方法有很多，目前應用遺傳算法、模擬退火算法、隨機抽取算法、回溯試探法等方法進行組卷，對比發現遺傳算法在智能組卷問題上的解決方法具有一定的優越性。為了避免遺傳算法的“早熟”，引入聚類思想，形成質心集，最終得到最優解，提高算法的性能。

關鍵詞：遺傳算法；智能組卷

【中圖分類號】G 【文獻標識碼】B 【文章編號】1008-1216（2016）10C-0065-02

生成試卷的方法有很多，可以通過手工或通過算法智能組卷進行組合，滿足一定規則下進行組卷。手工組卷不能高效、合理地完成組卷，智能組卷可以通過一定約束條件，完成一個組合問題，組合效率比較高。如何通過某種算法使組卷過程智能化，使試卷更有科學性、合理性？

智能組卷在國內從20世紀90年代開始逐漸增多，在中國知網搜索的“智能組卷”算法種類比較多，目前研究比較多的方法有遺傳算法、模擬退火算法、隨機抽取算法等。

隨機抽取算法在組卷算法中是比較常用的一種算法，根據約束條件，滿足用戶需求，隨機抽取試題，進行判斷，滿足條件，則生成試卷成功，否則，重新生成一組試卷，直到滿足條件為止。這種算法的特點是在語言實現上比較容易，但是這種方式的組卷重復率高、成功率低，效率比較低，所需時間長。

回溯試探法是基于深度及廣度搜索的算法，它建立在隨機抽取算法的基礎上，此算法對所有的情況進行窮盡搜索。在題庫中存在滿足約束條件的試題，系統最終一定會找出它的解。這種算法的結構復雜，運行起來比較耗費時間，所以適用于題量較少的情況。

遺傳算法是解決并行計算問題，并逐步得到優化的解題過程，它通過模擬生物進化過程，對問題進行求解，迭代過程中找到最優解。操作步驟有選擇、交叉和變異，完成這三個基本操作并抽取試題，最終得到滿足約束條件的試卷集合。它具有運行效率高、靈活性大的特點，適用于具有多種約束條件的求解問題。

遺傳算法是智能組卷中比較靈活的方法，將不確定的問題進行求解，這種但是在應用遺傳算法過程中，應避免“早熟”，這也是遺傳算法在智能組卷過程中值得研究的。目的就是解決組合優化問題，提高算法的執行效率。

一、改進遺傳算法在組卷問題中的研究

組卷目標是從一個試題庫集合中，通過某種方式重新組合成一組科學合理的組合試卷。

根據題目類型進行順序排序，并在滿足其他規則的情況下，根據確定的參數，從題庫中根據算法組合成一組試卷，為了讓試卷具有科學性，更接近確定的試卷，本文討論的試卷生成主要滿足題量、難度系數、區分度、知識點和題型等相關參數，使用遺傳算法組合生成試卷，避免遺傳算法“早熟”現象，將遺傳算法進行改進。

（一）改進遺傳算法基本思想

以遺傳算法進行組合試卷，主要避免初始群體“早熟”現象發生，找到最優解。此過程中引入聚類思想，在不影響種群的情況下，將初始種群使用聚類算法，群體中的每個染色體代表一個初始聚類的中心集，根據評價函數（根據試題的屬性完成聚類算法K-Means，得到一個數值）對每個染色體進行評價，得到適應值，染色體的適應值越大，說明染色體代表的中心集的聚類效果越好。根據約束條件進行選擇，隨機生成一組染色個體。進行交叉操作，染色體長度會發生變化，染色體長度的變化說明在遺傳算法過程中，中心集的選擇在發生變化，正是因為這一操作，經過多次迭代，可以得到聚類劃分數目和最優的質心集。最后根據變異概率，進行變異操作，在尋找最優質心集迭代過程中，找到的個體具有多樣性，從而保證了搜索全局，避免了“早熟”現象，找到最優解。