改進(jìn)的遺傳算法在智能組卷中的應(yīng)用研究

唐玲 尹珧人

摘 要：該文提出分段二進(jìn)制編碼，對(duì)遺傳算法的選擇過(guò)程進(jìn)行改進(jìn)，并采用獨(dú)立題型題庫(kù)存放的方法來(lái)求解組卷問(wèn)題。實(shí)驗(yàn)結(jié)果表明，新方法的組卷成功率和收斂速度都得到明顯提高，較好的克服了早熟收斂現(xiàn)象，組卷質(zhì)量明顯提高。

關(guān)鍵詞：改進(jìn)遺傳算法 智能組卷 數(shù)學(xué)模型

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2013）03（c）-00-02

隨著我國(guó)信息技術(shù)的飛速發(fā)展，計(jì)算機(jī)在教學(xué)領(lǐng)域有了廣泛應(yīng)用，用計(jì)算機(jī)進(jìn)行網(wǎng)上考試已經(jīng)成為一種趨勢(shì)，因此怎么才能快速?gòu)脑囶}庫(kù)中選出一份滿足用戶各項(xiàng)要求的試卷成為一個(gè)問(wèn)題。目前常用的組卷方法有隨機(jī)選題法、回溯試探法、遺傳算法三種，而傳統(tǒng)的遺傳算法主要通過(guò)交叉算子繁衍后代，容易造成早熟收斂現(xiàn)象。因此目前已經(jīng)有很多人為提高組卷效率，將遺傳算法的算子改進(jìn)后再應(yīng)用到智能組卷系統(tǒng)中。該文為加快算法的收斂速度，將遺傳算法的算子進(jìn)行了改進(jìn)，并應(yīng)用于智能組卷系統(tǒng)中。

1 智能組卷的數(shù)學(xué)模型

將智能組卷問(wèn)題視為從一定題量的數(shù)據(jù)庫(kù)中抽取滿足組卷要求的一組試題組合，就能夠?qū)⒔M卷問(wèn)題轉(zhuǎn)化為一個(gè)多重約束目標(biāo)問(wèn)題。求解一份由m道試題且每道試題有n個(gè)屬性的試卷，相即構(gòu)建一個(gè)m×n的目標(biāo)矩陣S。

S=

試題常有如下屬性：⑴難度系數(shù)a1、⑵分?jǐn)?shù)a2、⑶能力層次a3、⑷預(yù)計(jì)答題時(shí)間a4、⑸題型a5、⑹已出題次數(shù)a6。目標(biāo)矩陣應(yīng)滿足以下約束條件：

⑴試卷難度系數(shù)=1-/總分（由用戶給定）；

⑵試卷總分=（一般為100分）；

⑶答題總時(shí)間=（由用戶給定）；

⑷（為第p能力層次題分），能力層次類型和所占分?jǐn)?shù)由用戶給定，即能力層次約束，其中

⑸題型題分=，第j題型題分，其中：c={，j為題型要求約束。題型分別為：判斷、單選、填空、多選等，具體組卷題型類別和每題分值由用戶給定。

組卷過(guò)程中，試題要根據(jù)數(shù)學(xué)模型中給出的各項(xiàng)指標(biāo)來(lái)決定，即表示第i道試題中的第j項(xiàng)指標(biāo)，其中i=1，2，…，m；j=1，2，…，n。

2 題庫(kù)建設(shè)

該文試題在存儲(chǔ)時(shí)采用各題型獨(dú)立試題庫(kù)的存儲(chǔ)方法，為了避免經(jīng)常抽取同一道試題，我們將各題型題庫(kù)中試題根據(jù)已出題次數(shù)（a6）排序（初次抽取試題時(shí)，試題順序隨機(jī)產(chǎn)生），使a6小的試題下次被抽中的機(jī)率更大，以提高每次組卷產(chǎn)生的試卷

質(zhì)量。

3 改進(jìn)的遺傳算法在智能組卷中的

應(yīng)用

3.1 編碼方案

將二進(jìn)制數(shù)分段編碼，每段代表一個(gè)題型，k表示題型數(shù)量，題庫(kù)中試題數(shù)量決定了編碼的長(zhǎng)度。設(shè)各題型題庫(kù)中共有t道試題，則編碼形式為b1b2…bt，隨機(jī)產(chǎn)生初始化種群（假設(shè)串長(zhǎng)度是相同的）。

其中：bi={ i=1，2，…，t，且滿足=m，其中m是試題所含的題目數(shù)。=m1，=m2，…，=mk，=m，=t其中m1，m2，…，mk表示在試卷中各題型的試題數(shù)量，r1、…、rk表示各題庫(kù)中該題型的試題數(shù)量。

3.2 生成初始種群p（0）

為了降低問(wèn)題難度，提高求解效率，我們隨機(jī)產(chǎn)生試卷的初始種群p（0），使初始種群滿足試卷總分的要求。

3.3 確定適應(yīng)度函數(shù)

我們采用以下形式的適應(yīng)度函數(shù)[1]：

F=1/（1+） i = 1，…，n

其中ei表示第i組卷因素對(duì)組卷目標(biāo)造成的誤差，ki表示權(quán)值系數(shù)，且ki>0。

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

3.4.1 選擇算子

該文中每個(gè)個(gè)體的適應(yīng)度值由適應(yīng)度函數(shù)計(jì)算得來(lái)，并將種群代數(shù)t的初始值設(shè)置為0，將每代種群按其適應(yīng)度值的降序進(jìn)行排序，依次計(jì)算相鄰個(gè)體之間的廣義海明距離H，廣義海明距離[2]是指相同長(zhǎng)度的兩個(gè)串中對(duì)應(yīng)位不相同的數(shù)量，例如，某種群的某代進(jìn)化種群中第i個(gè)個(gè)體和第j個(gè)個(gè)體分別為：

xi（t）=1111001010001，xj（t）=1100101011001

它們間的廣義海明距離H（x（t），xj（t））==4。比較H和參數(shù)d的大小，若H小于d，則依次用父代群體中的優(yōu)秀個(gè)體替換適應(yīng)度小的個(gè)體；否則保留這兩個(gè)個(gè)體，將其加入到新一代群體中，執(zhí)行交叉操作。

3.4.2 交叉算子和變異算子

該文的交叉概率和變異概率是根據(jù)種群的進(jìn)化情況用自適應(yīng)函數(shù)來(lái)控制的，這樣可以加快遺傳算法搜索效率，有效防止算法陷入局部最優(yōu)，從而保護(hù)優(yōu)良試卷個(gè)體，所使用的適應(yīng)度函數(shù)如下[3]：

pC=

式中：f取參與交叉的兩個(gè)個(gè)體中適應(yīng)度值較大的一個(gè)；fmax、favg為上代群體中個(gè)體的最大適應(yīng)度值、群體的平均適應(yīng)度值；pc1=0.9，pc2=0.6。

pm=

式中：fmax、favg分別取上代群體中個(gè)體的最大適應(yīng)度值、群體平均適應(yīng)度值；f為要變異個(gè)體的適應(yīng)度值；pm1=0.1，pm2=0.001。

該文交叉操作過(guò)程如下：隨機(jī)產(chǎn)生交叉位置i，該位置由挑選出的兩個(gè)個(gè)體的長(zhǎng)度t決定，其中i取整數(shù)且1≤i≤t-1，按下面方式交叉：

為了避免交叉在基因段內(nèi)進(jìn)行導(dǎo)致同一題型試題重復(fù)的情況，我們限定交叉點(diǎn)位于第i個(gè)基因段內(nèi)，前i個(gè)基因段保持不變，從第i+1個(gè)基因段開(kāi)始逐位進(jìn)行交換。并且在交叉后立刻評(píng)價(jià)新產(chǎn)生個(gè)體的適應(yīng)度，將其與父代兩個(gè)體比較，如果適應(yīng)度值相同，則將新個(gè)體視為無(wú)效個(gè)體刪除；否則將其連同父帶個(gè)體保留，使新個(gè)體直接執(zhí)行變異操作。

為了保證各個(gè)題型、題數(shù)的要求，變異過(guò)程我們利用變異率決定隨機(jī)到哪位并將該位的值取反，同時(shí)在該位所在的基因段內(nèi)，向前或向后搜索與該位最近并且值相反的位，將該位值也取反。

3.5 終止條件

我們將種群規(guī)模設(shè)置為200，算法執(zhí)行的最大代數(shù)設(shè)置為500，當(dāng)出現(xiàn)如下情況時(shí)算法終止：①達(dá)到要求的進(jìn)化代數(shù)；②當(dāng)進(jìn)化中種群最大適應(yīng)度值與之前各代種群最大適應(yīng)度值近似時(shí)；③得到滿足用戶的組卷約束要求的種群或得到用戶滿意的試

卷時(shí)。

4 仿真試驗(yàn)結(jié)果分析

為了驗(yàn)證本算法可行，我們分別采用該文算法和傳統(tǒng)遺傳算法針對(duì)智能組卷系統(tǒng)進(jìn)行了仿真。針對(duì)《C語(yǔ)言程序設(shè)計(jì)》的1000道試題進(jìn)行組卷實(shí)驗(yàn)，將試題按照單選、多選、填空、判斷題型分別建立4個(gè)庫(kù)文件，并規(guī)定每個(gè)庫(kù)中有250題，每類題型有5種難度。試卷滿分設(shè)置為100分；預(yù)計(jì)答題時(shí)間為120 min；試卷總體難度系數(shù)設(shè)置為0.8。仿真結(jié)果如圖1、圖2所示。

通過(guò)上面比較可以看出，該文算法能夠得到最優(yōu)解，并且在進(jìn)化代數(shù)和收斂速度上明顯優(yōu)于傳統(tǒng)遺傳算法，提高了問(wèn)題的求解效率，能有效地解決智能組卷問(wèn)題，充分驗(yàn)證了本算法可行。

參考文獻(xiàn)

[1] 楊路明，陳大鑫.改進(jìn)遺傳算法在試題自動(dòng)組卷中的應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2004（5）：77-78.

[2] 王麗芳，王楠，李新華.基于一種改進(jìn)遺傳算法的智能組卷的研究[J].中北大學(xué)學(xué)報(bào)（自然科學(xué)版），2006（4）.

[3] 王小平，曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[4] 路景，周春艷.基于遺傳算法的混合優(yōu)化策略研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（3）：144-146.

[5] 吳飛.自適應(yīng)遺傳算法解決組卷問(wèn)題的探討[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2007（2）.