Memetic算法智能組卷策略研究

【摘要】智能組卷是一個多約束條件的組合優化問題，算法的效率是決定智能組卷算法是否能獲得高質量試卷的核心。Memetic算法組卷策略采用整數編碼的形式、單點交叉策略、隨機變異策略和爬山算法，以難度、知識點分布和認識層次設計適應度函數，以期達到快速生成高質量試卷的目的。文章的最后用隨機組卷算法（Random）和標準遺傳算法（GA_random）作為對照算法，以詳細的實驗結果證明了Memetic算法的有效性。綜上所述，Memetic算法是一種有效實用的組卷策略。

【關鍵詞】智能組卷;算法;適應度函數;數學模型

1.引言

隨著計算機輔助教學的不斷發展，智能組卷系統已成為教育學和計算機科學領域研究的熱點。如何根據教學的需要自動生成考卷是計算機考試系統中的關鍵。智能組卷實質上是一個基于對試卷約束條件求解的多目標參數優化問題。目前常見的解決辦法有：隨機抽取、回溯試探、遺傳算法、粒子群算法等[1]，但都存在一定的局限性。Memetic算法結合了遺傳算法和局部搜索算法的優點，既具有全局尋優能力，又能通過局部搜索優化種群分布，保證了較高收斂性能[2]，是求解多目標優化問題的最有效方法之一。本文嘗試用Memetic算法來解決智能組卷的問題，以期達到高可靠性和實用性的組卷目的。

2.組卷約束模型

2.1 指導思想

組卷的主要依據是教學大綱，系統生成的試卷必須全面反映大綱的廣度和深度[3];系統生成的試卷要利于考核考生的知識水平和促進考生智力發展;試題要有總分和時間限制。

2.2 試卷的屬性指標

試卷的屬性指標指試卷必須達到的用戶需求，由試題本身的屬性來體現，是建立組卷系統的核心。試卷的屬性越貼近用戶的需求，試卷的質量越高。一般來說，試卷的屬性指標由以下部分組成：分數（Score）、難度（Degree of Difficulty）、認知層次（Cognitive Level）、知識點（Knowledge Point）、題型（Item Topic）及時間（Answer Time ） [4] [5]。假設一張試卷由m道試題組成，每道題有n個屬性，則一張試卷可以由m×n的矩陣R來表示。

矩陣的每行表示一道試題，列表示該題的屬性。每道試題的屬性amn所代表的含義如下：am1表示題目的分數、am2表示難度系數、am3表示對應的認知層次、am4表示所屬的知識點章節、am5表示題型及am6表示估計答題時間。

2.3 組卷約束模型

（1）試卷總分，即計算試卷矩陣所有題目的分數（第一列所有元素）之和。

（2）試卷難度系數，即計算試卷矩陣中每一道試題的分數與其對應的難度系數乘積之和，再除以試卷總分，則得出該試卷的難度系數。

（3）認知層次為x的題目分數，其中，即計算試卷矩陣中認知層次為x的試題的分數之和。

（4）知識點為y的題目分數，其中，即計算試卷矩陣中知識點為y的試題的分數之和。

（5）題型為z的題目分數，其中，即計算試卷矩陣中題型為z的試題的分數之和。

（6）估計總答題時間，即計算試卷矩陣所有題目的答題時間（第六列所有元素）之和。

組卷約束模型可以分為簡單目標約束（即：試卷總分和估計總答題時間）和曲線分布約束（即：由試題相應屬性所占的分數總和來體現）組成。為了簡化試卷的約束模型，我們可以根據實際情況通過指定總分、時間、試卷總難度系數和各知識點所占的分數等措施降低算法的搜索空間。

3.Memetic算法描述

3.1 算法流程

Memetic算法就是在遺傳算法中通過局部搜索使個體達到局部最優，算法流程如圖1所示。

圖1 Memetic算法流程

3.2 算法模型

3.2.1 染色體編碼

為便于理解和計算適應度函數，本文采用整數編碼的方式。試卷可以表示成染色體的形式，染色體的長度代表了試卷的題量，染色體每位基因的數值代表組成該試卷的題號。

3.2.2 試卷初始化

本文將隨機產生n份試卷作為初始種群，其中每份試卷將按題型從試題庫中隨機選取m道題，保證同一試卷不存在同號試題，且盡量滿足總分和總的時間要求。

3.2.3 選擇算子

采用輪盤賭策略來完成選擇操作。

3.2.4 交叉算子

采用單點交叉策略作為交叉操作的方式，即： 依據交叉概率，首先各自在兩條進行交叉操作的染色體中隨機選擇交叉點;將第一條染色體的交叉點以前的代碼加在第二條染色體之前，將第二條染色體的交叉點以前的代碼加在第一條染色體之前;然后對新產生的兩條染色體依次刪除相同的基因，得到最終的兩條新染色體。

3.2.5 變異算子

采用隨機變異策略作為變異操作的方式，即： 根據變異概率，在需進行變異操作的染色體中隨機選擇交叉點;然后在相應的題型庫中選擇不與當前染色體基因重復的一道滿足要求的試題基因來替代當前交叉點所存在的基因，從而形成新的染色體。

3.2.6 局部搜索策略

本文采用爬山算法對遺傳算子產生的新個體進行爬山操作，從而獲得最優解。

3.2.7 適應度函數

為了降低算法的搜索空間，提高算法的效率，本文在初始化試卷矩陣時就已經滿足了試卷估計答題時間、題型分布和試卷總分的要求，因此適應度函數只考慮難度分布、認知層次分布和知識點分布的要求，具體構建如下：

設生成的試卷各難度級別占的分數用sds表示，預期各難度級別占的分數用yds表示，各難度級別允許的誤差用es表示，則難度分布的誤差函數可用下式表示：

（7）其中，f1越小，說明試卷越接近難度分布的要求。

同理可得到認知層次分布的誤差函數f2和知識點分布的誤差函數f3：

設生成的試卷各認知層次占的分數用scs表示，預期各難度級別占的分數用ycs表示，各難度級別允許的誤差用ec表示，則認知層次分布的誤差函數可用下式表示：

（8）其中，f2越小，說明試卷越接近認知層次分布的要求。

設生成的試卷各知識點所占的分數用sks表示，預期各難度級別占的分數用yks表示，各難度級別允許的誤差用ek表示，則知識點分布的誤差函數可用下式表示：

（9）試卷的誤差函數是f1 、f2 和f3的加權和。試卷的誤差函數越小，則試卷的質量越高。為了便于計算，讓試卷的質量與適應度函數成正比，本文用試卷誤差函數的倒數來設計適應度函數，同時為了防止出現分母為0的現象，本文用試卷誤差函數加1作為分母，即：

（10），其中wi指的是各評價函數所占的權重，所有權重之和（w1+ w2+w3）為1。因此，本文中的組卷目標就是使適應度函數盡可能大。

4.仿真實驗與分析

計算機的實驗平臺是：處理器Intel（R）Core（TM）Duo T5750 2.0GHz 2.0GHz，內存3.0GB，操作系統Windows xp。

表1 組卷的約束條件

總分 100 答題時間 90 期望得分率 0.7

題型分布 題數，題分 認知層次 卷面分值 知識點分布 卷面分值

填空題 10，2 了解 10 第一章 10

選擇題 10，2 識記 30 第三章 30

判斷題 10，2 理解 30 第四章 30

簡答題 2，5 應用 30 第五章 30

操作題 2，15 允許誤差 2 允許誤差 2

測試數據是340道《計算機文化基礎》試題組成的試題庫，共有5種題型、5個難度級別、4種認知層次、知識點分布4個章節，權重系數分別為0.7、0.2、0.1，允許的誤差均為2，總分100分，耗時約為90分種。組卷的具體約束條件見表1。

初始種群為20，迭代次數為100，交叉概率為0.68，變異概率為0.006。

在本文中，我們選取隨機組卷算法（Random）和標準遺傳算法（GA_random）作為對照算法，各算法組成試卷的適應度函數值、難度分布、知識點分布和認知層次的對比如圖2、圖3、圖4和圖5所示。其中，Random算法的種群數為20，GA_random算法的種群數為20，迭代次數為100，交叉概率為0.68，變異概率為0.006。由于各算法本身的參數具有不確定性，因此本文展示的是部分實驗結果。

圖2 各算法在適應度函數值對比

圖3 各算法在難度分布上的對比

圖4 各算法組成在知識點分布上的對比

圖5 各算法在認知層次分布上的對比

在適應度函數值的對比上，由圖2可知，Memetic算法在迭代26次后適應度函數值達到了1，從而能得出滿意的試卷，GA_random算法和Random算法的適應度函數值均不高。

在難度分布的對比上，Memetic算法的難度分布值為{10，29，34，21，6}，根據期望得分率0.7得出難度標準分布值為{12，30，32，19，7}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內。由圖3可見，Memetic算法的性能最優，GA_random算法次之，Random算法最差。

在知識點分布的對比上，Memetic算法的知識點分布值為{8，32，31，29}，知識點標準分布值為{10，30，30，30}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內。由圖4可見，Memetic算法的性能最優，GA_random算法次之，Random算法最差。

在認知層次分布的對比上，Memetic算法的認知層次分布值為{8，32，31，29}，知識點標準分布值為{10，30，30，30}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內。由圖5可見，Memetic算法的性能最優，GA_random算法次之，Random算法最差。

綜上所述，在相同條件下，Memetic算法在智能組卷過程中要優于GA_random算法和Random算法。在本次實驗中，Memetic算法策略生成了一套題號為（52，73，30，75，2，57，6，86，48，9，194，149，145，136，175，144，177，105，107，176，284，292，238，240，283，265，216，269，203，290，306，320，329，325），適應度函數值為1的最優試卷。

5.結語

本文介紹了如何設計編碼方案，適應度函數、遺傳算子和局部搜索策略來應用Memetic算法進行智能組卷工作。本文將Memetic算法應用到《計算機文化基礎》組卷過程中，實驗證明該算法方案可行，組卷效率高，試卷質量好。

參考文獻

[1]王琦.智能組卷算法研究比較[J].科技信息，2008（27）： 403-404.

[2]彭建偉.基于memetic 算法的個性化學習路徑推薦的研究與實現[D].長沙：湖南大學，2009：37-40.

[3]吳樹錦.基于遺傳算法智能組卷系統的研究與實現[J].天津職業院校聯合學報，2010（05）：34-37.

[4]周艷聰，劉艷柳.遺傳模擬退火智能組卷策略研究[J].計算機工程與設計，2011（03）：1066-1069.

[5]周艷聰，劉艷柳，顧軍華.小生境自適應遺傳模擬退火智能組卷策略研究[J].小型微型計算機系統，2011（02）：323-327.

基金項目：湖南省科技廳一般項目（2013PJ3066）。

作者簡介：

譚慧琳（1982—），湖南邵陽人，碩士研究生，邵陽醫學高等專科學校講師，研究方向：信息技術教育。

肖擎綱（1956—），男，湖南邵陽人，教授，湖南省邵陽市高等醫學專科學校副校長，主要研究方向：計算機教育。