Memetic算法智能組卷策略研究

【摘要】智能組卷是一個(gè)多約束條件的組合優(yōu)化問(wèn)題，算法的效率是決定智能組卷算法是否能獲得高質(zhì)量試卷的核心。Memetic算法組卷策略采用整數(shù)編碼的形式、單點(diǎn)交叉策略、隨機(jī)變異策略和爬山算法，以難度、知識(shí)點(diǎn)分布和認(rèn)識(shí)層次設(shè)計(jì)適應(yīng)度函數(shù)，以期達(dá)到快速生成高質(zhì)量試卷的目的。文章的最后用隨機(jī)組卷算法（Random）和標(biāo)準(zhǔn)遺傳算法（GA_random）作為對(duì)照算法，以詳細(xì)的實(shí)驗(yàn)結(jié)果證明了Memetic算法的有效性。綜上所述，Memetic算法是一種有效實(shí)用的組卷策略。

【關(guān)鍵詞】智能組卷;算法;適應(yīng)度函數(shù);數(shù)學(xué)模型

1.引言

隨著計(jì)算機(jī)輔助教學(xué)的不斷發(fā)展，智能組卷系統(tǒng)已成為教育學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域研究的熱點(diǎn)。如何根據(jù)教學(xué)的需要自動(dòng)生成考卷是計(jì)算機(jī)考試系統(tǒng)中的關(guān)鍵。智能組卷實(shí)質(zhì)上是一個(gè)基于對(duì)試卷約束條件求解的多目標(biāo)參數(shù)優(yōu)化問(wèn)題。目前常見(jiàn)的解決辦法有：隨機(jī)抽取、回溯試探、遺傳算法、粒子群算法等[1]，但都存在一定的局限性。Memetic算法結(jié)合了遺傳算法和局部搜索算法的優(yōu)點(diǎn)，既具有全局尋優(yōu)能力，又能通過(guò)局部搜索優(yōu)化種群分布，保證了較高收斂性能[2]，是求解多目標(biāo)優(yōu)化問(wèn)題的最有效方法之一。本文嘗試用Memetic算法來(lái)解決智能組卷的問(wèn)題，以期達(dá)到高可靠性和實(shí)用性的組卷目的。

2.組卷約束模型

2.1 指導(dǎo)思想

組卷的主要依據(jù)是教學(xué)大綱，系統(tǒng)生成的試卷必須全面反映大綱的廣度和深度[3];系統(tǒng)生成的試卷要利于考核考生的知識(shí)水平和促進(jìn)考生智力發(fā)展;試題要有總分和時(shí)間限制。

2.2 試卷的屬性指標(biāo)

試卷的屬性指標(biāo)指試卷必須達(dá)到的用戶需求，由試題本身的屬性來(lái)體現(xiàn)，是建立組卷系統(tǒng)的核心。試卷的屬性越貼近用戶的需求，試卷的質(zhì)量越高。一般來(lái)說(shuō)，試卷的屬性指標(biāo)由以下部分組成：分?jǐn)?shù)（Score）、難度（Degree of Difficulty）、認(rèn)知層次（Cognitive Level）、知識(shí)點(diǎn)（Knowledge Point）、題型（Item Topic）及時(shí)間（Answer Time ） [4] [5]。假設(shè)一張?jiān)嚲碛蒻道試題組成，每道題有n個(gè)屬性，則一張?jiān)嚲砜梢杂蒻×n的矩陣R來(lái)表示。

矩陣的每行表示一道試題，列表示該題的屬性。每道試題的屬性amn所代表的含義如下：am1表示題目的分?jǐn)?shù)、am2表示難度系數(shù)、am3表示對(duì)應(yīng)的認(rèn)知層次、am4表示所屬的知識(shí)點(diǎn)章節(jié)、am5表示題型及am6表示估計(jì)答題時(shí)間。

2.3 組卷約束模型

（1）試卷總分，即計(jì)算試卷矩陣所有題目的分?jǐn)?shù)（第一列所有元素）之和。

（2）試卷難度系數(shù)，即計(jì)算試卷矩陣中每一道試題的分?jǐn)?shù)與其對(duì)應(yīng)的難度系數(shù)乘積之和，再除以試卷總分，則得出該試卷的難度系數(shù)。

（3）認(rèn)知層次為x的題目分?jǐn)?shù)，其中，即計(jì)算試卷矩陣中認(rèn)知層次為x的試題的分?jǐn)?shù)之和。

（4）知識(shí)點(diǎn)為y的題目分?jǐn)?shù)，其中，即計(jì)算試卷矩陣中知識(shí)點(diǎn)為y的試題的分?jǐn)?shù)之和。

（5）題型為z的題目分?jǐn)?shù)，其中，即計(jì)算試卷矩陣中題型為z的試題的分?jǐn)?shù)之和。

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

組卷約束模型可以分為簡(jiǎn)單目標(biāo)約束（即：試卷總分和估計(jì)總答題時(shí)間）和曲線分布約束（即：由試題相應(yīng)屬性所占的分?jǐn)?shù)總和來(lái)體現(xiàn)）組成。為了簡(jiǎn)化試卷的約束模型，我們可以根據(jù)實(shí)際情況通過(guò)指定總分、時(shí)間、試卷總難度系數(shù)和各知識(shí)點(diǎn)所占的分?jǐn)?shù)等措施降低算法的搜索空間。

3.Memetic算法描述

3.1 算法流程

Memetic算法就是在遺傳算法中通過(guò)局部搜索使個(gè)體達(dá)到局部最優(yōu)，算法流程如圖1所示。

圖1 Memetic算法流程

3.2 算法模型

3.2.1 染色體編碼

為便于理解和計(jì)算適應(yīng)度函數(shù)，本文采用整數(shù)編碼的方式。試卷可以表示成染色體的形式，染色體的長(zhǎng)度代表了試卷的題量，染色體每位基因的數(shù)值代表組成該試卷的題號(hào)。

3.2.2 試卷初始化

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

3.2.3 選擇算子

采用輪盤(pán)賭策略來(lái)完成選擇操作。

3.2.4 交叉算子

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

3.2.5 變異算子

采用隨機(jī)變異策略作為變異操作的方式，即： 根據(jù)變異概率，在需進(jìn)行變異操作的染色體中隨機(jī)選擇交叉點(diǎn);然后在相應(yīng)的題型庫(kù)中選擇不與當(dāng)前染色體基因重復(fù)的一道滿足要求的試題基因來(lái)替代當(dāng)前交叉點(diǎn)所存在的基因，從而形成新的染色體。

3.2.6 局部搜索策略

本文采用爬山算法對(duì)遺傳算子產(chǎn)生的新個(gè)體進(jìn)行爬山操作，從而獲得最優(yōu)解。

3.2.7 適應(yīng)度函數(shù)

為了降低算法的搜索空間，提高算法的效率，本文在初始化試卷矩陣時(shí)就已經(jīng)滿足了試卷估計(jì)答題時(shí)間、題型分布和試卷總分的要求，因此適應(yīng)度函數(shù)只考慮難度分布、認(rèn)知層次分布和知識(shí)點(diǎn)分布的要求，具體構(gòu)建如下：

設(shè)生成的試卷各難度級(jí)別占的分?jǐn)?shù)用sds表示，預(yù)期各難度級(jí)別占的分?jǐn)?shù)用yds表示，各難度級(jí)別允許的誤差用es表示，則難度分布的誤差函數(shù)可用下式表示：

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

同理可得到認(rèn)知層次分布的誤差函數(shù)f2和知識(shí)點(diǎn)分布的誤差函數(shù)f3：

設(shè)生成的試卷各認(rèn)知層次占的分?jǐn)?shù)用scs表示，預(yù)期各難度級(jí)別占的分?jǐn)?shù)用ycs表示，各難度級(jí)別允許的誤差用ec表示，則認(rèn)知層次分布的誤差函數(shù)可用下式表示：

（8）其中，f2越小，說(shuō)明試卷越接近認(rèn)知層次分布的要求。

設(shè)生成的試卷各知識(shí)點(diǎn)所占的分?jǐn)?shù)用sks表示，預(yù)期各難度級(jí)別占的分?jǐn)?shù)用yks表示，各難度級(jí)別允許的誤差用ek表示，則知識(shí)點(diǎn)分布的誤差函數(shù)可用下式表示：

（9）試卷的誤差函數(shù)是f1 、f2 和f3的加權(quán)和。試卷的誤差函數(shù)越小，則試卷的質(zhì)量越高。為了便于計(jì)算，讓試卷的質(zhì)量與適應(yīng)度函數(shù)成正比，本文用試卷誤差函數(shù)的倒數(shù)來(lái)設(shè)計(jì)適應(yīng)度函數(shù)，同時(shí)為了防止出現(xiàn)分母為0的現(xiàn)象，本文用試卷誤差函數(shù)加1作為分母，即：

（10），其中wi指的是各評(píng)價(jià)函數(shù)所占的權(quán)重，所有權(quán)重之和（w1+ w2+w3）為1。因此，本文中的組卷目標(biāo)就是使適應(yīng)度函數(shù)盡可能大。

4.仿真實(shí)驗(yàn)與分析

計(jì)算機(jī)的實(shí)驗(yàn)平臺(tái)是：處理器Intel（R）Core（TM）Duo T5750 2.0GHz 2.0GHz，內(nèi)存3.0GB，操作系統(tǒng)Windows xp。

表1 組卷的約束條件

總分 100 答題時(shí)間 90 期望得分率 0.7

題型分布 題數(shù)，題分 認(rèn)知層次 卷面分值 知識(shí)點(diǎn)分布 卷面分值

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

選擇題 10，2 識(shí)記 30 第三章 30

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

簡(jiǎn)答題 2，5 應(yīng)用 30 第五章 30

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

測(cè)試數(shù)據(jù)是340道《計(jì)算機(jī)文化基礎(chǔ)》試題組成的試題庫(kù)，共有5種題型、5個(gè)難度級(jí)別、4種認(rèn)知層次、知識(shí)點(diǎn)分布4個(gè)章節(jié)，權(quán)重系數(shù)分別為0.7、0.2、0.1，允許的誤差均為2，總分100分，耗時(shí)約為90分種。組卷的具體約束條件見(jiàn)表1。

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

在本文中，我們選取隨機(jī)組卷算法（Random）和標(biāo)準(zhǔn)遺傳算法（GA_random）作為對(duì)照算法，各算法組成試卷的適應(yīng)度函數(shù)值、難度分布、知識(shí)點(diǎn)分布和認(rèn)知層次的對(duì)比如圖2、圖3、圖4和圖5所示。其中，Random算法的種群數(shù)為20，GA_random算法的種群數(shù)為20，迭代次數(shù)為100，交叉概率為0.68，變異概率為0.006。由于各算法本身的參數(shù)具有不確定性，因此本文展示的是部分實(shí)驗(yàn)結(jié)果。

圖2 各算法在適應(yīng)度函數(shù)值對(duì)比

圖3 各算法在難度分布上的對(duì)比

圖4 各算法組成在知識(shí)點(diǎn)分布上的對(duì)比

圖5 各算法在認(rèn)知層次分布上的對(duì)比

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

在難度分布的對(duì)比上，Memetic算法的難度分布值為{10，29，34，21，6}，根據(jù)期望得分率0.7得出難度標(biāo)準(zhǔn)分布值為{12，30，32，19，7}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內(nèi)。由圖3可見(jiàn)，Memetic算法的性能最優(yōu)，GA_random算法次之，Random算法最差。

在知識(shí)點(diǎn)分布的對(duì)比上，Memetic算法的知識(shí)點(diǎn)分布值為{8，32，31，29}，知識(shí)點(diǎn)標(biāo)準(zhǔn)分布值為{10，30，30，30}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內(nèi)。由圖4可見(jiàn)，Memetic算法的性能最優(yōu)，GA_random算法次之，Random算法最差。

在認(rèn)知層次分布的對(duì)比上，Memetic算法的認(rèn)知層次分布值為{8，32，31，29}，知識(shí)點(diǎn)標(biāo)準(zhǔn)分布值為{10，30，30，30}，在允許誤差為2的情況下，Memetic算法的難度誤差均在允許范圍內(nèi)。由圖5可見(jiàn)，Memetic算法的性能最優(yōu)，GA_random算法次之，Random算法最差。

綜上所述，在相同條件下，Memetic算法在智能組卷過(guò)程中要優(yōu)于GA_random算法和Random算法。在本次實(shí)驗(yàn)中，Memetic算法策略生成了一套題號(hào)為（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），適應(yīng)度函數(shù)值為1的最優(yōu)試卷。

5.結(jié)語(yǔ)

本文介紹了如何設(shè)計(jì)編碼方案，適應(yīng)度函數(shù)、遺傳算子和局部搜索策略來(lái)應(yīng)用Memetic算法進(jìn)行智能組卷工作。本文將Memetic算法應(yīng)用到《計(jì)算機(jī)文化基礎(chǔ)》組卷過(guò)程中，實(shí)驗(yàn)證明該算法方案可行，組卷效率高，試卷質(zhì)量好。

參考文獻(xiàn)

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

[2]彭建偉.基于memetic 算法的個(gè)性化學(xué)習(xí)路徑推薦的研究與實(shí)現(xiàn)[D].長(zhǎng)沙：湖南大學(xué)，2009：37-40.

[3]吳樹(shù)錦.基于遺傳算法智能組卷系統(tǒng)的研究與實(shí)現(xiàn)[J].天津職業(yè)院校聯(lián)合學(xué)報(bào)，2010（05）：34-37.

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

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

基金項(xiàng)目：湖南省科技廳一般項(xiàng)目（2013PJ3066）。

作者簡(jiǎn)介：

譚慧琳（1982—），湖南邵陽(yáng)人，碩士研究生，邵陽(yáng)醫(yī)學(xué)高等專(zhuān)科學(xué)校講師，研究方向：信息技術(shù)教育。

肖擎綱（1956—），男，湖南邵陽(yáng)人，教授，湖南省邵陽(yáng)市高等醫(yī)學(xué)專(zhuān)科學(xué)校副校長(zhǎng)，主要研究方向：計(jì)算機(jī)教育。