朱郭峰

摘要：為了減輕考試系統(tǒng)中老師出卷的工作量，并使出卷更加合理與科學(xué)化，此文通過遺傳算法設(shè)計(jì)了一種新型的自動組卷系統(tǒng)，該系統(tǒng)首先介紹了遺傳算法的基本思想與優(yōu)勢，其次利用隨機(jī)搜索方法對自動組卷系統(tǒng)中各個功能模塊進(jìn)行了詳細(xì)的設(shè)計(jì)，其中主要包括自動組卷系統(tǒng)中的編碼方案的確定、自適應(yīng)度函數(shù)的創(chuàng)建、選擇交叉變異算子以及控制參數(shù)計(jì)算，最后，我們對基于遺傳算法的自動組卷系統(tǒng)進(jìn)行了成功的實(shí)現(xiàn)，整個系統(tǒng)運(yùn)行正常。

關(guān)鍵詞：遺傳算法；自動組卷；成卷技術(shù)指標(biāo)

中圖分類號：P315.69 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）07-1626-04

1 概述

考試是用來考查人們學(xué)習(xí)程度的一種常見方式，傳統(tǒng)的出試題的方式讓老師有很大的負(fù)擔(dān)，由于每個老師的理解不同，使其對學(xué)生的學(xué)習(xí)掌握程度的認(rèn)識也有所不一樣，這樣就使得知識的覆蓋面和試題難度難以被控制。為了達(dá)到考查的目的，提高老師的工作效率，避免不必要的重復(fù)勞動，我們有必要采用一種科學(xué)的組卷方式實(shí)現(xiàn)科學(xué)，高效，快速組卷。該文主要探討遺傳算法在自動組卷中的應(yīng)用，研究遺傳算法解決自動選題成卷的問題。

2 遺傳算法

遺傳算法起源于達(dá)爾文的進(jìn)化理論與孟德爾的遺傳學(xué)理論，它是一種新型的，模擬自然界生物進(jìn)化過程的隨機(jī)搜索方法。借鑒生物遺傳學(xué)的方法，經(jīng)過選擇、遺傳、變異等生物過程，提高個體的適應(yīng)性，從而達(dá)到優(yōu)勝劣汰的淘汰機(jī)制。遺傳算法已經(jīng)在搜索、優(yōu)化、機(jī)器學(xué)習(xí)、圖像識別等領(lǐng)域得到了廣泛的應(yīng)用，已經(jīng)成為智能計(jì)算的重要技術(shù)。與傳統(tǒng)的優(yōu)化算法相比較，遺傳算法具有如下優(yōu)勢：1） 遺傳算法從解集中的串集開始搜索，不同于傳統(tǒng)優(yōu)化算法從單個初始值開始迭代得到最優(yōu)解的方法。遺傳算法搜索覆蓋面大，容易搜索到全局最優(yōu)解。2） 遺傳算法通過適應(yīng)度函數(shù)值來評價個體的優(yōu)劣從而得到最優(yōu)解，不涉及搜索空間的知識和其它輔助信息。由于適應(yīng)度函數(shù)可以取任意的定義域，并且不受連續(xù)可微的約束。這樣大大擴(kuò)展了遺傳算法的應(yīng)用范圍。3） 遺傳算法根據(jù)概率的改變來確定搜索方向，經(jīng)過比較得到最優(yōu)解集，其概率并不是確定的。有效地防止了組卷失敗的狀況。4） 遺傳算法遺傳算法在進(jìn)化過程中利用獲得的信息進(jìn)行自主搜索，使得優(yōu)質(zhì)個體能夠以更高的概率被選中，從而得到更優(yōu)質(zhì)的基因結(jié)構(gòu)。遺傳算法的主要工作流程，如圖1所示。

3 自動組卷

3.1 自動組卷的發(fā)展

在自動組卷試題庫的創(chuàng)建方面，我們可以不斷的更新與完善試題庫的內(nèi)容，在組卷時，對每題的內(nèi)容進(jìn)行分析，對出現(xiàn)過的缺點(diǎn)與不規(guī)范可以進(jìn)一步修改，從而避免了傳統(tǒng)出試卷時，考試結(jié)束后沒有時間來進(jìn)行總結(jié)與記錄的缺點(diǎn)。自動組卷的產(chǎn)生，使得試題的內(nèi)容具有了繼承性，規(guī)范性，可以不斷地積累出試卷的經(jīng)驗(yàn)，并做好相應(yīng)的記錄與分析，豐富與規(guī)范試題庫的內(nèi)容，達(dá)到了開放性，實(shí)用性與交流性的特點(diǎn)?；厮菰囂椒ㄅc隨機(jī)抽取法是自動組卷中最常用的算法，回溯試探法記錄每次操作的狀態(tài)類型，然后分別與設(shè)定的條件進(jìn)行對比，抽取滿足條件的類型，一直循環(huán)到自動生成試卷或者重新開始組卷，它是基于隨機(jī)抽取法基礎(chǔ)上的。隨機(jī)抽取法不考慮最優(yōu)化，自動組卷生成的試卷只需要滿足預(yù)先提出的各種約束條件，此試卷就為可用的了。隨機(jī)抽取法算法結(jié)構(gòu)簡單，選取單一的試題時有較快的運(yùn)行速度，但是應(yīng)用于組卷的整個過程中，其抽取空間較大，會使得組卷時間很長，或者最后選取的試題不能滿足要求，組卷失敗。

3.2 自動組卷的技術(shù)指標(biāo)與系統(tǒng)分析

試卷的評比中，會通過有幾種曲線來考核試卷的好壞，如獲取難度分?jǐn)?shù)分布曲線LD，教學(xué)要求度分?jǐn)?shù)分布曲線LR，題型分?jǐn)?shù)分布曲線LT，內(nèi)容分?jǐn)?shù)分布曲線LC及其各自允許的誤差，其中LR，LC及允許的誤差都是用戶給出的。曲線LD是很重要的曲線，大大地決定了最終成績的分布。成卷的技術(shù)指標(biāo)有難度，區(qū)分度，信度，效度這些方面，我們通常是用試卷的考試結(jié)果進(jìn)行分析，但是在組卷時，我們了解這些指標(biāo)的計(jì)算方法，然后進(jìn)行科學(xué)合理地組卷。組卷系統(tǒng)中的試題庫需要進(jìn)行難度控制，能夠生成符合測試要求，達(dá)到真正考查學(xué)生目的的試卷。

3.3 自動組卷試題屬性

為了保證試題的質(zhì)量，更好地考查學(xué)生對知識的掌握情況，我們通過控制以下屬性來讓試題規(guī)范化，科學(xué)化，最優(yōu)化。

1）難度系數(shù)D：學(xué)生掌握試題內(nèi)容的難易程度，D公式1確定

[Di=SiFi] （1）

其中，Di是指第i道題的難易系數(shù)值；Si是指所有考生在第i題的平均分?jǐn)?shù)；Fi是i題的滿分值。只有當(dāng)Di適中，才能使得試卷達(dá)到檢測學(xué)生對知識的真實(shí)掌握情況，當(dāng)Di為0，則意味著，沒有一個學(xué)生可以答對第i題，則該題的難度太大；當(dāng)Di為1時，則意味著所有的學(xué)生都能答對第i題，則該題難度太低，這樣的題目不能達(dá)到檢測學(xué)生的目的。一份理想的試卷的難度系數(shù)應(yīng)該在0.4—0.6之間，這樣考試的成績分布能夠滿足正態(tài)分布，也具有實(shí)際的參考價值。

2）區(qū)分度Q：為了區(qū)分考生的水平與能力，更好地考查考生各方面，試題需要設(shè)定一個區(qū)分度標(biāo)準(zhǔn)。區(qū)分度是根據(jù)考生的前35%高分組與后35%低分組計(jì)算出來的。如公式2

[Qi=Hi-LiFi] （2）

其中，Qi 為 第i題的區(qū)分度；Hi是前35%高分組在第i題的平均分?jǐn)?shù)；Li是后35%高分組在第i題的平均分?jǐn)?shù)；Fi是i題的滿分值。當(dāng)Qi = 0，表明低分組和高分組的平均分?jǐn)?shù)相等，從而本試卷不能區(qū)分考生能力；當(dāng)Qi < 0；則說明此試卷太難，考生都是胡亂猜測做題的；Qi > 0 ，才是正常的，但最好要大于0.3，這樣才能有效區(qū)分考生能力。

3）時間T：是確定所有考生做完整套題所需要的平均時間。

4）分?jǐn)?shù)S：確定此試卷的滿分值。

5）曝光度E：曝光度是用來描述一道試題在前后兩份試卷中出現(xiàn)的時間間隔。通過對曝光度值的大小來決定是否選用該題。

[Ei=Sa-SbG] （3）

其中，Ei 為第i題的曝光度；Sa 為第i道題在最近的那份試卷的出卷時間；Sb為第i道題在此次試卷的出卷時間；G為用戶允許前后兩份試卷出卷時間的最小間隔值。

4 基于遺傳算法自動組卷的設(shè)計(jì)與實(shí)現(xiàn)

遺傳算法應(yīng)用于自動組卷中，首先要生成初始群體然后按照各約束條件對其中的個體進(jìn)行選擇與復(fù)制，再對其以一定的概率進(jìn)行交叉與變異的操作，從而實(shí)現(xiàn)個體結(jié)構(gòu)之間新的重組，不斷迭代，知道搜索到符合條件的全局最優(yōu)解。遺傳算法應(yīng)用于自動組卷中的算法如下：

1） 確定編碼方案

自動組卷最終需要得到一份滿足各約束條件的可行試卷，根據(jù)生物遺傳學(xué)，我們可以將一份試卷對應(yīng)一個染色體，而試卷中的每個試題對應(yīng)染色體中的每個基因，我們可以用試題的題號來表示標(biāo)記基因的值。染色體中的每個基因編碼可以表示為：（R1，R2，R3，……Rn），其中Ri（n為試卷中的總題型數(shù)目，i = n -1）是試題的題號。

2） 建立適應(yīng)度函數(shù)

在遺傳算法中，群體中個體的優(yōu)劣是通過適應(yīng)值的大小來區(qū)分的。通常來說，適應(yīng)值越大，就判斷該個體越優(yōu)秀，反之，則判斷該個體越差勁。適應(yīng)度函數(shù)就相當(dāng)于是求解一個問題的評價標(biāo)準(zhǔn)函數(shù)。我們設(shè)某個體的適應(yīng)度函數(shù)為f（x），在建立函數(shù)之前，我們要保證目標(biāo)函數(shù)與適應(yīng)度函數(shù)建立映射后，使得f（x）是非負(fù)的，并使其越大越好。

3） 設(shè)計(jì)遺傳算子

Step 1選擇算子。選擇算子是用來確定進(jìn)行交叉的個體，本身并不具有產(chǎn)生個體的能力，主要是為了達(dá)到提高群體平均適應(yīng)度值的目的。通過選擇算子，我們選擇優(yōu)異的個體，使其直接遺傳給下一代或者讓其通過交配產(chǎn)生新個體然后再遺傳下一代，從而就淘汰了適應(yīng)度值低的個體，也就是劣質(zhì)個體被淘汰了。個體i在初始群體為n的情況下，其被選中的概率為

[Psi=fi/i=1nfi] （4）

其中n為初始群體的大小，fi 為第i個個體的適應(yīng)值。

Step 2 交叉算子。交叉算子能夠產(chǎn)生新個體，它主要操作是將父代個體的部分結(jié)構(gòu)進(jìn)行兩兩替換重組，從而產(chǎn)生新個體，這主要是在相同題型段內(nèi)操作的?；镜倪z傳算法中，交叉概率是固定的。自適應(yīng)的交叉概率是可以自己調(diào)整的，交叉概率越大，則搜索過程中更加容易保證群體的多樣性。所以，在粗略搜索時，其交叉概率越大越好，最后細(xì)搜時，其交叉概率越小越好，這樣能夠加快其收斂速度。

Step 3 變異算子。變異算子也能夠產(chǎn)生新個體，是產(chǎn)生新個體的一種輔助方法。它決定遺傳算法在局部的搜索能力。采取最小的概率對滿足約束條件的相同題型段的單點(diǎn)進(jìn)行變異操作，并且先進(jìn)行交叉操作再以變異概率Pm來進(jìn)行操作。在確定每個題型的題號范圍后，需要考慮該個體基因與其他基因是否被多次選中，有沒有重復(fù)，如果被選中，就要重新開始產(chǎn)生，直到?jīng)]有被選中的隨機(jī)數(shù)，用它來代替此題型段中的任意一個題號。變異算子可以保證種群的多樣性，防止出現(xiàn)早熟現(xiàn)象。

Step 4 選擇算法的控制參數(shù)指標(biāo)。遺傳算法中需要考慮的參數(shù)有，群體規(guī)模n，交叉概率為Pe，變異概率為Pm。當(dāng)群體規(guī)模過小時，能夠提高運(yùn)算速度，但是降低了種群的多樣性，比較難得到最優(yōu)解。但是當(dāng)群體規(guī)模過大時，運(yùn)算速度會下降，n的取值范圍一般大于30且小于150。交叉概率決定了個體的更新與算法的全局搜索能力，當(dāng)Pe取值過大時，容易導(dǎo)致群體的高適應(yīng)度值得到破壞，取值過小時，其退化為簡單的隨機(jī)搜索，所以其取值范圍為0.35～0.85之間。變異概率Pm過小時，會使產(chǎn)生的新個體較少，若過大，則會使其退化為簡單的隨機(jī)搜索，所以其取值范圍為0.01～0.2之間較合適。P的值是經(jīng)過多次的實(shí)驗(yàn)確定的。

Step 5 確定算法的終止條件。我們通過限制最大的迭代次數(shù)與既定的目標(biāo)適應(yīng)度值來判斷是否終止算法，分別將個體的最大適應(yīng)度值與目標(biāo)適應(yīng)度值進(jìn)行比較，當(dāng)期望值不大于最大適應(yīng)度值時就停止迭代，否則對上述遺傳操作進(jìn)行反復(fù)循環(huán)，直到達(dá)到期望適應(yīng)度值時，組卷才成功。

Step 6算法的實(shí)現(xiàn)

參數(shù)的確定，群體規(guī)模n，交叉概率為Pe，變異概率為Pm，最大迭代次數(shù)為MaxGene，實(shí)際迭代次數(shù)Gene；

確定用戶的約束條件；

建立初始群體；

初始迭代的次數(shù)Gene = 0；

確定群體中每個個體的適應(yīng)度值；

確定最好個體的編號，輸出的指標(biāo)值分別與用戶的約束條件值進(jìn)行比較。

5 結(jié)束語

隨著計(jì)算機(jī)的普及，信息知識的發(fā)展，使得自動組卷技術(shù)被大家追捧。自動組卷技術(shù)能夠減輕老師的負(fù)擔(dān)，使老師們將更多的時間投入到科學(xué)研究中；使試題的形式更加規(guī)范化，能夠更好地進(jìn)行總結(jié)與分析，使試題更加科學(xué)化，更好地考查學(xué)生各方面的素質(zhì)。該文主要是基于遺傳算法在自動組卷中的應(yīng)用，設(shè)置了幾個變量，設(shè)計(jì)了遺傳算法自動組卷的基本步驟，實(shí)現(xiàn)了簡單的自動組卷功能。由于時間與能力有限，其運(yùn)行過程中的細(xì)節(jié)問題還需得到完善。

參考文獻(xiàn)：

[1] 王明川.基于遺傳算法的組卷方法研究[J].基礎(chǔ)科學(xué)，2011，35（2）：65-81.

[2] 朱大茗，馬紹漢.算法設(shè)計(jì)與分析[M].北京：高等教育出版社，2009.

[3] 李敏強(qiáng).遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2003.

[4] 宋芝蘭.基于遺傳算法自動組卷問題的設(shè)計(jì)研究[J].商業(yè)科技，2011，2（上）：9-10.

[5] 王棟.自適應(yīng)遺傳算法的研究[J].科技前沿，2011，2（646）：175.

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

[7] 鐘寧，劉連浩.遺傳算法在在線考試系統(tǒng)中自動組卷的優(yōu)化設(shè)計(jì)[J].電腦知識與科技，2010，7（2）：397-398.

[8] 謝興，秦前清.遺傳算法在醫(yī)學(xué)圖像自適應(yīng)融合中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（3）：181-183.

[9] Xiao Han-peng.Research of Test Paper System Base on Genetic Al-gorithm[J].Computer Knowledge and Technology，2010，27（056）：65-81.

[10] Guo Xiaolei.Design and Implementation of Paper System based onAGA[J].Computer Development &Applications，2010，8（027）：7569-7570.