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

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

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

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

遺產(chǎn)算法；自動組卷；算法設(shè)計

0　引言

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

1　自動組卷算法分析

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

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

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

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

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

2.2 個體編碼的確定

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

2.3 種群初始化

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

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

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

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

2.5 組卷算法的選擇操作

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

2.6 組卷算法的交叉操作

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

2.7 組卷算法的變異操作

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

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

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

3　 結(jié)束語

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

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

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

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

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

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