蔣　哲(湖北工業(yè)大學(xué), 武漢430068)

基于遺傳算法的自動(dòng)組卷系統(tǒng)的分析與設(shè)計(jì)

蔣哲
(湖北工業(yè)大學(xué), 武漢430068)

自動(dòng)組卷系統(tǒng)中的關(guān)鍵環(huán)節(jié)在于組卷算法的選擇，算法的好換直接關(guān)系著組卷的質(zhì)量以及效率。本文對(duì)三種常用的組卷算法進(jìn)行了分析，并將改進(jìn)的遺傳算法應(yīng)用于自動(dòng)組卷問題中，有效提高了組卷質(zhì)量和效率。本文詳細(xì)闡述了基于遺傳算法的自動(dòng)組卷算法的實(shí)現(xiàn)流程。

遺產(chǎn)算法；自動(dòng)組卷；算法設(shè)計(jì)

0　引言

自動(dòng)組卷指的是計(jì)算機(jī)考試系統(tǒng)自動(dòng)從預(yù)先設(shè)定的題庫(kù)中按照用戶的特點(diǎn)需求抽取試題從而組成一套完整的試卷。自動(dòng)組卷得到的試卷既要滿足用戶設(shè)定的要求，同時(shí)也需要具有合理性、隨機(jī)性，這對(duì)組卷算法提出了很高的要求。目前已經(jīng)有了一些自動(dòng)組卷系統(tǒng)，然而由于科目眾多、各專業(yè)的課程重點(diǎn)不同等因素的影響，這些自動(dòng)組卷系統(tǒng)還無法有效滿足用戶的需求。

1　自動(dòng)組卷算法分析

組卷算法的設(shè)計(jì)是影響組卷系統(tǒng)組卷質(zhì)量的關(guān)鍵因素，目前現(xiàn)有的自動(dòng)組卷系統(tǒng)采用的組卷算法主要包括三種類型：回溯試探法、隨機(jī)算法以及遺傳算法。

回溯試探法的思想是：首先隨機(jī)抽取一個(gè)試題，對(duì)該試題進(jìn)行分析，判斷是否滿足抽題要求，若滿足條件則抽出該試題進(jìn)入試卷，否則重新選題。當(dāng)組卷未完成時(shí)，采用回溯的方法試探之前的操作進(jìn)行繼續(xù)組卷?；厮莘ú僮鲝U棄的頻率較低，有效減少了無效組卷操作。因此，回溯試探法的組卷成功率很高，但需要花費(fèi)大量的時(shí)間作為代價(jià)。隨機(jī)組卷法是指計(jì)算機(jī)根據(jù)預(yù)先設(shè)定的隨機(jī)函數(shù)從題庫(kù)中抽取符合條件的試題組成一套完整的試卷。這種方法實(shí)現(xiàn)起來比較簡(jiǎn)單方便，在實(shí)踐中得到了廣泛的應(yīng)用。然而隨機(jī)組卷法組成的試卷一旦某個(gè)條件達(dá)不到要求時(shí)（如試卷的預(yù)期答題時(shí)間超標(biāo)），則整套試卷作廢，從而導(dǎo)致出現(xiàn)大量的無效試卷，極大地降低了組卷的成功率和效率。遺傳算法是一種基于自然界進(jìn)化理論的優(yōu)化算法，它遵循優(yōu)勝劣汰的自然法則。遺傳算法中的編碼技術(shù)可以表示各種復(fù)雜的現(xiàn)實(shí)問題，它通過對(duì)編碼的遺傳操作即可確定算法的學(xué)習(xí)方向和策略。遺傳算法是以種群為操作對(duì)象的，對(duì)種群中的每個(gè)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)、篩選、交叉和變異操作，從而實(shí)現(xiàn)個(gè)體的優(yōu)勝劣汰。

2 　基于改進(jìn)的遺傳算法的組卷算法設(shè)計(jì)

2.1目標(biāo)函數(shù)的確定

試卷組織過程中應(yīng)綜合考慮題目類型、知識(shí)點(diǎn)分布、試題難度等因素，用戶給定這些指標(biāo)的參考值后，對(duì)自動(dòng)組卷系統(tǒng)得到的試卷的指標(biāo)值進(jìn)行比較，將指標(biāo)誤差加權(quán)求和，得到目標(biāo)函數(shù)。

2.2 個(gè)體編碼的確定

確定好遺傳算法的目標(biāo)函數(shù)后，需要對(duì)自動(dòng)組卷問題進(jìn)行編碼。組卷問題的求解就是篩選試題組成合理的試卷。因此，首先將試題根據(jù)進(jìn)行分類，如分為選擇題、填空題、計(jì)算題等，然后將試題按題型分段編碼，不同題型的編碼相互獨(dú)立。試卷個(gè)體則按照分庫(kù)編號(hào)進(jìn)行染色體編碼，所選中的試題按照順序排列好后，其試題代碼則為試卷個(gè)體的代碼。

2.3 種群初始化

遺傳算法是基于種群的方法，因此需要設(shè)定初始種群，然后在初始種群的基礎(chǔ)上不斷進(jìn)化。種群是所有試卷個(gè)體的集合，初始試卷個(gè)體通過計(jì)算機(jī)隨機(jī)生成。隨機(jī)生成初始試卷個(gè)體時(shí)，試卷總分、題型、均滿足要求。

2.4 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是遺傳算法中個(gè)體進(jìn)化操作的依據(jù)，因此在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，應(yīng)當(dāng)使得遺傳算法的群體位于解空間內(nèi)，同時(shí)方便其搜索方向接受指導(dǎo)。一個(gè)良好的適應(yīng)度函數(shù)應(yīng)當(dāng)能反應(yīng)每個(gè)個(gè)體本身質(zhì)量的好壞。在組卷算法中，適應(yīng)度函數(shù)可通過目標(biāo)函數(shù)轉(zhuǎn)換得到，本文采用的適應(yīng)度函數(shù)如下：

式中，f為目標(biāo)函數(shù)，F(xiàn)為適應(yīng)度。從上式可知，f越小，則適應(yīng)度值越高，即試卷評(píng)價(jià)指標(biāo)的誤差越校，試卷個(gè)體的適應(yīng)度越高，即試卷更符合組卷要求。

2.5 組卷算法的選擇操作

遺傳算法以試卷個(gè)體為遺傳操作的對(duì)象，具體過程為：首先計(jì)算種群中每個(gè)試卷個(gè)體的適應(yīng)度值，并找出適應(yīng)度最高的個(gè)體，用它直接替代本代群體遺傳操作后生產(chǎn)的適應(yīng)度最小的個(gè)體，即遵循“精英保留”原則。其他的試卷個(gè)體則使用輪盤法完成選擇工作。將種群中每個(gè)個(gè)體的適應(yīng)度值求和得到種群的整體適應(yīng)值，然后計(jì)算每個(gè)試卷個(gè)體的選擇概率，同時(shí)生產(chǎn)一個(gè)0~1之間的隨機(jī)數(shù)，若選擇概率小于隨機(jī)數(shù)，則該試卷個(gè)體不選擇。

2.6 組卷算法的交叉操作

個(gè)體交叉的概率使用自適應(yīng)交叉概率。由于試卷個(gè)體最終應(yīng)該符合題量以及題型的規(guī)定，因此試卷個(gè)體在完成交叉操作時(shí)應(yīng)當(dāng)在各自的編碼組中進(jìn)行，例如A個(gè)體與B個(gè)體進(jìn)行交叉時(shí)，選擇題只能與選擇題交叉，而不同的題型不能混合交叉。對(duì)上一步篩選出的個(gè)體進(jìn)行兩兩交叉操作。在進(jìn)行交叉時(shí)，各題型編碼段隨機(jī)生成一個(gè)交叉點(diǎn)，然后將交叉點(diǎn)之后的編碼互相交換，當(dāng)各題型均完成交叉后，則表示兩個(gè)個(gè)體之間的交叉操作完成。由于交叉之后可能出現(xiàn)編碼重復(fù)的情況，因此需要將重復(fù)的編碼替換為隨機(jī)抽取非重復(fù)編碼。

2.7 組卷算法的變異操作

個(gè)體變異的概率使用自適應(yīng)變異概率。由自然法則可知，變異是小概率事件，其發(fā)生的情況較少，只有少部分個(gè)體會(huì)發(fā)生變異，每個(gè)試卷個(gè)體的變異概率決定了個(gè)體是否發(fā)生變異。每個(gè)個(gè)體隨機(jī)產(chǎn)生一個(gè)0~1之間的隨機(jī)數(shù)，若個(gè)體變異概率大于隨機(jī)數(shù)，則該個(gè)體進(jìn)行變異操作。變異操作具體如下：每個(gè)題型段隨機(jī)產(chǎn)生一個(gè)變異位置，移除該位置上原有的試題編碼，并補(bǔ)入新的未被選中的試題編碼。當(dāng)各題型均完成變異后，即產(chǎn)生新的變異個(gè)體。

2.8 組卷算法的迭代終止條件

本算法迭代終止判定：（1）平均適應(yīng)度達(dá)到最高適應(yīng)度值的95%；（2）迭代次數(shù)達(dá)到預(yù)定最大次數(shù)，則結(jié)束迭代循環(huán)。

3　 結(jié)束語(yǔ)

我們研究的熱點(diǎn)和難點(diǎn)，遺傳算法本身具有全局尋優(yōu)和智能搜索的特性，將遺傳算子自適應(yīng)改進(jìn)后的遺傳算法應(yīng)用于組卷中，能夠很好地解決組卷的多重目標(biāo)尋優(yōu)問題。

[1]李玲.基于遺傳算法的自動(dòng)組卷系統(tǒng)設(shè)計(jì)[J].軟件導(dǎo)刊,2013,04:52-54.

[2]劉慧梅.基于遺傳算法的自動(dòng)組卷算法的設(shè)計(jì)[J].價(jià)值工程,2012,20:223-224.

[3]董園.基于改進(jìn)遺傳算法的自動(dòng)組卷系統(tǒng)的研究[J].三明學(xué)院學(xué)報(bào),2012,06:17-22.

[4]施俊,繆勇.基于遺傳算法的自動(dòng)組卷研究與應(yīng)用[J].電腦知識(shí)與技術(shù),2014,34:8160-8162.

蔣哲(1986-)，男,江蘇常州人，本科,研究方向：計(jì)算機(jī)方向。