基于遺傳算法的自動組卷技術(shù)

楊巍巍，宋海峰，高巍巍，馬憲敏，李 放，張麗明

（1.黑龍江外國語學(xué)院，黑龍江 哈爾濱150025；2.黑龍江工程學(xué)院，黑龍江 哈爾濱150050；3.吉林華僑外國語學(xué)院，吉林 長春130117）

自動組卷是依據(jù)用戶指定的約束條件（查詢參數(shù)）抽取出符合要求的試題并組合成試卷。組卷模塊是整個網(wǎng)絡(luò)考試系統(tǒng)設(shè)計(jì)中重要的組成部分。遺傳算法（Genetic Algorithm，GA）是由生物進(jìn)化論中的“適者生存，優(yōu)勝劣汰”進(jìn)化規(guī)律和遺傳機(jī)制演化來的一類隨機(jī)搜索方法。遺傳算法借用生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、交叉、變異等作用機(jī)制，實(shí)現(xiàn)個體適應(yīng)性的提高，從而體現(xiàn)了自然界中“物競天擇、適者生存”的進(jìn)化過程［1］。

1 智能組卷技術(shù)

1.1 試題庫結(jié)構(gòu)

在數(shù)據(jù)庫設(shè)計(jì)中，為單個試題設(shè)置題號、知識點(diǎn)、題型、預(yù)計(jì)用時、分值、難度、區(qū)分度、最近被選時間等多個屬性描述［2］，以便于組卷時對整份試卷進(jìn)行條件約束。

1.2 建立組卷數(shù)學(xué)模型

將自動組卷生成的試題，量化為包含題號、知識點(diǎn)、題型、答題時間、分值、難度和區(qū)分度等屬性的一個n維向量（a1，a2，…，an），假設(shè)1份試卷中包含m道試題，則將生成的試卷表示為m×n的目標(biāo)矩陣S［3］。

目標(biāo)矩陣S主要滿足以下約束條件［4］：

1）知識點(diǎn)約束。

式中：ZF 為試卷總分，zk（k＝1，2，…，n）為第k個知識點(diǎn)的總分，zpk為第k個知識點(diǎn)的分值占整個試卷的分值比例。

2）試卷題型約束。

式中：tk（k＝1，2，…，n）為第k種題型的總分值，tpk為第k種題型占整個試卷的分值比例。

3）試卷答題總時間。

式中：f4為試卷題型分布指標(biāo)中的ZF。

5）難度系數(shù)。

式中：wi為該試題的權(quán)值，較簡單的題型權(quán)值比重分配較小，較難的題型權(quán)值比重分配較大。難度劃分為5個等級：易［0.0～0.2）、較易［0.2～0.4）、中等［0.4～0.6）、較難［0.6～0.8）、難［0.8～1.0），默認(rèn)值為0.6，也可由用戶自行指定。難度系數(shù)越小，試卷越簡單。

6）試卷區(qū)分度。

區(qū)分度值一般在－1～＋1之間，值越大區(qū)分度越好，說明試題設(shè)計(jì)得也越好。

2 遺傳算法的改進(jìn)及應(yīng)用

2.1 染色體編碼

將1份試卷映射成1個染色體，其中的各試題映射成基因，按照題型與知識點(diǎn)排序，生成試卷。在1份試卷中，染色體包含的編碼個數(shù)即為試卷中試題的個數(shù)。將染色體表示為一維向量：（G1，G2，G3，…，Gn），其中Gi（i＝1，…，n，n為試卷中包含的總題目數(shù)）為試題的編號［5］。

傳統(tǒng)的使用二進(jìn)制編碼存在搜索空間過大和編碼長度過長等缺點(diǎn)，本系統(tǒng)中采用整數(shù)編碼策略［6－7］，試題的每個屬性值用整數(shù)來表示，如表1所示。

表1 試題編碼

2.2 產(chǎn)生初始種群

根據(jù)預(yù)先設(shè)定的條件隨機(jī)生成初始種群，種群規(guī)模需要根據(jù)實(shí)際情況來確定，一般來說在30～80之間較好。

2.3 適應(yīng)度函數(shù)的設(shè)置

適應(yīng)度函數(shù)在遺傳算法中決定著個體的優(yōu)勝劣汰，是群體進(jìn)化的驅(qū)動力。在生成初始種群時，已對試卷總分?jǐn)?shù)、總時間、所含題型和所含知識點(diǎn)進(jìn)行約束，在設(shè)計(jì)適應(yīng)度函數(shù)時，使用試卷的難度、題型分布和知識點(diǎn)分布的誤差進(jìn)行衡量。為了避免誤差正負(fù)值之間互相抵消，使用誤差的絕對值進(jìn)行計(jì)算。設(shè)ei為第i個指標(biāo)與用戶要求之間誤差的絕對值，wi為第i個指標(biāo)對組卷重要程度的權(quán)值，設(shè)適應(yīng)度函數(shù)f＝ ，當(dāng)f的值達(dá)到最小時，組卷成功［4］。

2.4 遺傳算子的改進(jìn)

1）選擇算子。采用按適應(yīng)值排序擇優(yōu)的方法選擇個體是被復(fù)制到下一代還是被淘汰。具體做法是：在父代中，對個體按照適應(yīng)值排序，然后按照一定的概率來選擇，將適應(yīng)度高的部分個體遺傳到下一代，其余部分個體或者進(jìn)行交叉，或者進(jìn)行變異。通過對算法進(jìn)行試驗(yàn)，將適應(yīng)度高的30%個體復(fù)制到下一代，形成子代種群。

2）交叉算子。交叉有單點(diǎn)交叉、雙點(diǎn)交叉和多點(diǎn)交叉等，它使得群體形態(tài)多樣化。因?yàn)槌跏挤N群已經(jīng)按設(shè)定的組卷?xiàng)l件產(chǎn)生，因此，本系統(tǒng)采用單點(diǎn)交叉。在群體中，將個體按適應(yīng)度值進(jìn)行排序，選擇適應(yīng)度低的個體，兩兩配對，并在同一題型內(nèi)，隨機(jī)產(chǎn)生交叉位置，按照交叉概率Pc進(jìn)行單點(diǎn)交叉操作，生成兩個新的個體，如圖1所示［9］。如果知識點(diǎn)重復(fù)，則重新產(chǎn)生交叉位置。將產(chǎn)生的新的個體適應(yīng)度與群體中其他個體適應(yīng)度進(jìn)行比較，若適應(yīng)度值高于其他個體中適應(yīng)度最小的，則保留。對最終產(chǎn)生的新的種群，再按個體適應(yīng)度值進(jìn)行排序，適應(yīng)度高的復(fù)制到子代。

圖1 單點(diǎn)交叉操作

圖1 中，Xi表示選擇題，Ti表示填空題，Wi表示問答題，Bi表示編程題。

3）變異算子。當(dāng)兩個個體相似度很高時，采用交叉操作很難產(chǎn)生新個體，采用變異操作可以抑制早熟。變異概率Pm值大，搜索范圍大，群體多樣性好，可以較好地抑制早熟，避免產(chǎn)生局部最優(yōu)解；但Pm值太大，會失去從父代繼承的優(yōu)良個體，并導(dǎo)致算法收斂速度慢［10］。本文采用自適應(yīng)函數(shù)動態(tài)調(diào)整交叉概率Pc和變異概率Pm，當(dāng)種群中個體的適應(yīng)度差別較大時，增大Pc的值，減小Pm的值，加快進(jìn)化速度；反之，減小Pc的值，增大Pm的值，本文采用基本位變異算子，在個體中選擇任意的位置進(jìn)行基因的變異操作。

2.5 算法的停止標(biāo)準(zhǔn)

算法在遇到下列情況之一時，終止迭代：①達(dá)到最大的迭代次數(shù)；②當(dāng)前群體的平均適應(yīng)度值與期望適應(yīng)度值的誤差小于ε，ε為給定的期望誤差；③算法在經(jīng)過連續(xù)的若干代進(jìn)化后，種群中最佳個體的適應(yīng)度值或平均適應(yīng)度值沒有發(fā)生改進(jìn)。

3 測 試

使用《JAVA語言程序設(shè)計(jì)》試題庫進(jìn)行測試，共有600道題，其中選擇題、填空題、問答題和編程題各150道，初始種群規(guī)模N取值50，試卷總分為100min，答題時間為120min。經(jīng)算法測試后得到如表2所示的結(jié)果。

表2 測試結(jié)果

由表2結(jié)果可以看出，使用改進(jìn)遺傳算法組卷的成功率及組卷效率都比較高。

4 結(jié)束語

組卷工作是一項(xiàng)復(fù)雜而繁重的工作，本文針對學(xué)生的知識水平和特點(diǎn)以及考試要求，對組卷流程、遺傳算法中染色體編碼、適應(yīng)度函數(shù)、各種遺傳算子以及算法的停止標(biāo)準(zhǔn)等進(jìn)行了深入的研究，提高了組卷的質(zhì)量和效率，較適合在平時測驗(yàn)和期末考試中進(jìn)行應(yīng)用和推廣。

［1］殷霖.遺傳算法在自動組卷中的應(yīng)用［J］.廊坊師范學(xué)院學(xué)報，2011（6）：26－28.

［2］李霞婷，宋榮.改進(jìn)型遺傳算法在組卷系統(tǒng)中的研究與設(shè)計(jì)［J］.電腦知識與技術(shù)，2011（7）：4947－4948.

［3］邵明珠，李偉峰.基于遺傳算法的組卷技術(shù)研究與實(shí)踐［J］.煤炭技術(shù)，2011（9）：253－254.

［4］楊巍巍.網(wǎng)絡(luò)考試系統(tǒng)中關(guān)鍵技術(shù)的研究與應(yīng)用［D］.哈爾濱：哈爾濱工程大學(xué)，2010.

［5］丁知平.基于改進(jìn)遺傳算法的自動組卷問題的研究［J］.軟件，2011（9）：9－11.

［6］蔡娟.改進(jìn)遺傳算法在組卷中的應(yīng)用［J］.吉林廣播電視大學(xué)學(xué)報，2011（10）：9.

［7］徐新華.基于分段的自然數(shù)編碼的遺傳算法在自動組卷問題中的應(yīng)用［J］.廊坊師范學(xué)院學(xué)報：自然科學(xué)版，2011（10）：24－26.

［8］化莉.基于遺傳算法的組卷策略［J］.蘇州科技學(xué)院學(xué)報：自然科學(xué)版，2011（9）：58－61.

［9］李建勛，文海玉.一類模擬退火算法與遺傳算法混合優(yōu)化策略［J］.黑龍江工程學(xué)院學(xué)報：自然科學(xué)版，2010，24（2）：69－71.

［10］葉長芳，雷繼呈，高衛(wèi)斌.自適應(yīng)遺傳算法在智能組卷中的應(yīng)用［J］.信息安全與技術(shù)，2011（7）：64－66.