劉召華?李建良

摘 要：隨著計算機技術(shù)的發(fā)展，利用計算機存儲大量的試題信息并結(jié)合數(shù)據(jù)庫技術(shù)實現(xiàn)試題的自動組卷功能已成為一項實際可行且應(yīng)用性廣泛的課題。本文就試題組卷遺傳算法進行了論述和總結(jié)。

關(guān)鍵詞：自動組卷；遺傳算法；試題庫

隨著信息技術(shù)不斷發(fā)展，傳統(tǒng)考試方式已經(jīng)不能適應(yīng)現(xiàn)代化考試需求，設(shè)計開發(fā)和應(yīng)用計算機考試管理系統(tǒng)成為現(xiàn)代教育教學(xué)改革的一項重要任務(wù)。計算機技術(shù)不斷發(fā)展，并結(jié)合現(xiàn)有成熟的數(shù)據(jù)庫技術(shù)，為計算機考試管理系統(tǒng)開發(fā)提供了可靠保證?？荚嚬芾硐到y(tǒng)設(shè)計中，建立一個好的試題庫尤為重要，而良好的組卷方法卻是核心。如何保證生成的試卷能最大程度地滿足用戶的不同需求，并具有隨機性、科學(xué)性、合理性；尤其在交互環(huán)境下，對組卷速度要求較高，而一個在理論上能搜索到全局最優(yōu)的算法可能會以犧牲時間為代價，往往達不到預(yù)期的效果。因此，選擇一個高效、科學(xué)的算法是自動組卷的關(guān)鍵。以往具有自動組卷功能的考試系統(tǒng)大多采用隨機選取法和回溯試探法。在限制條件狀態(tài)空間的控制下，隨機選取法有時能夠抽取出一組令用戶滿意的試題，但由于它隨機選取試題的范圍太大，有可能在無法抽取合適試題的區(qū)域內(nèi)反復(fù)選題，進入死循環(huán)，最終導(dǎo)致組卷失敗。回溯試探法組卷成功率高，卻以犧牲大量的時間為代價。遺傳算法（Genetic Algorithms）以其全局尋優(yōu)和智能搜索技術(shù)，及收斂性好的特性能很好地滿足自動組卷的要求。

1. 遺傳算法原理

遺傳算法（Genetic Algorithm，GA）是模擬自然界自然選擇遺傳機制進行搜索尋優(yōu)的方法，通過模擬生物在染色體層面的各種遺傳優(yōu)化作用而設(shè)計人工尋優(yōu)方法，GA本質(zhì)上是一個群體迭代過程，從一個隨機的初始群體出發(fā)，依據(jù)優(yōu)勝劣汰原則.通過競爭、選擇、繁衍、變異等遺傳操作，產(chǎn)生性能更優(yōu)的下一代群體。直到滿足環(huán)境約束的優(yōu)良體或合乎具體的應(yīng)用準則為止。遺傳算法的這種特點使其很適合解決多重條件最優(yōu)解的問題。

2. 組卷問題的數(shù)學(xué)模型建立

通過實際組卷分析，組卷約束條件主要有知識點，題型，章節(jié)，認知層次，題量，分值，答題時間，難度，區(qū)分度，曝光度等10個方面。根據(jù)對上述組卷約束條件的分析，可以構(gòu)建組卷問題的數(shù)學(xué)模型。由于一張試卷存在10個約束變量，所以針對于整個試卷所有的題目構(gòu)成了一個10維度變量的空間：知識點，題型，章節(jié)，認知層次，題量，分值，答題時間，難度，區(qū)分度，曝光度。為了減小組卷算法的復(fù)雜度，提高組卷算法的效率，需要對這個10維空間進行化簡處理。一般而言，要出一份試卷，我們總是先確定試題難度、試卷的滿分值和所用的題型以及各種題型的題目和分數(shù)以及知識點分布，而且對一種考試而言，這種難度分布常保持相對穩(wěn)定。不同難度試題的分數(shù)分布通常成正態(tài)分布，我們可以根據(jù)難度系數(shù)、各知識點分數(shù)、各題型分數(shù)來約束將要被選中的試題個數(shù)以及試題難度分布，計算出不同難度級別的題目在試卷中所占的比例。再結(jié)合各知識點、各題型的分數(shù)在試卷中所占的比例，可將10維空間簡化為一個5維的空間——試卷（知識點，章節(jié)，題型，分值，難度），在這個5維空間里對試題進行操作來完成組卷。不同的計算機系統(tǒng)通常采用不同的二進制文件格式。

3. 遺傳算法在自動組卷中的應(yīng)用

遺傳算法模擬達爾文的自然界遺傳學(xué)：繼承（基因遺傳）、進化（基因突變）和優(yōu)勝劣汰（優(yōu)的基因大量被遺傳復(fù)制，劣的基因較少被遺傳復(fù)制）。其實質(zhì)就是一種把自然界有機體優(yōu)勝劣汰的自然選擇、適者生存的進化機制與同一群體中個體與個體間的隨機信息交換機制相結(jié)合的搜索算法。運用遺傳算法求解問題，首先需將所要求解的問題表示成二進制編碼，然后根據(jù)環(huán)境循環(huán)進行基本的操作：selection（選擇）、crossover（交叉）、mutation（變異），最后收斂到一個最適應(yīng)環(huán)境條件的個體上，得到問題的最優(yōu)解。算法步驟如下：

（1）染色體的編碼：假設(shè)試題庫中有m道題，可用一個m位的二進制串來表示，形式為：a1，a2，a3 ，...am，，其中若ai為1，則表示該題被選中；若ai 為0，則表示該題未被選中，即ai=1，第i道題被選中；ai=0，第i道題未被選中。

（2）初始化群體：通過隨機的方法生成初始化的串群體，在串群體中，串的長度是相同的，群體的大小按需要根據(jù)經(jīng)驗或?qū)嶒灲o出。

（3）計算當前種群每個個體的目標函數(shù)：本問題的目標函數(shù)可定義為

F=

Fi表示第i個屬性指標與用戶要求的誤差的絕對值，Wi表示第i個指標對組卷重要程度的權(quán)值，F(xiàn)是所有指標與用戶要求的誤差絕對值之和。該目標函數(shù)越大，則適應(yīng)度越小，被淘汰的概率越大。

（4）選擇：按照一定的選擇概率對種群進行復(fù)制，選擇較好的串生成下一代（個體的適應(yīng)度函數(shù)值越大，該串的性能越好，選擇概率越大），去掉較差的串。

（5）交叉：交叉是兩個串按照一定的概率（交叉概率P ），從某一位開始逐位互換。首先，對每個二進制串產(chǎn)生一個0～1范圍內(nèi)的隨機數(shù)；若該數(shù)小于P ，則選擇該串進行交叉，否則不予選擇。然后隨機地對被選擇的二進制串進行配對，并根據(jù)二進制串的長度 ，隨機產(chǎn)生交叉位置i，i為[1，n-1]上的一個整數(shù)。

（6）變異：變異是二進制串的某一位按照一定的概率（突變概率Pm）發(fā)生反轉(zhuǎn)，1變?yōu)?，0變?yōu)?。這里Pm 較小，Pm 可小于0.001。但在實踐中發(fā)現(xiàn)，在有些遺傳算子中，Pm為0.1時更好。

（7）終止：記錄進化的代數(shù)，并判斷是否滿足終止條件。若滿足，則輸出結(jié)果，否則轉(zhuǎn)向步驟3繼續(xù)執(zhí)行。終止條件如下：（a）出現(xiàn)種群滿足F=0；（b）某個個體目標函數(shù)值（個體適應(yīng)度值）達到指定要求；（c）達到指定的進化代數(shù)；（d）當前種群中最大目標函數(shù)值與以前各代中最大目標函數(shù)值相差不大，進化效果不顯著。

遺傳算法在試題組卷中的應(yīng)用可以將教師從繁重的考試出卷等工作中解放出來，最大限度地減少人為因素在組卷過程中的影響，最大程度地實現(xiàn)了組卷的自動化，有效提高試卷的質(zhì)量。我們也可以對簡單遺傳算法改進，利用組卷過程中的誤差對遺傳算法中的隨機性選擇進行誘導(dǎo)，保證產(chǎn)生的新個體的誤差相比對于同一個體的其他信息位的變異所產(chǎn)生的新個體而言，產(chǎn)生的誤差最小。理論分析與實驗結(jié)果表明，基于遺傳算法的試題組卷算法具有較好的智能組卷性能。

參考文獻

1.王小平.《遺傳算法——理論、應(yīng)用與軟件實現(xiàn)》西安交通大學(xué)出版社，2002

2.張文修，梁怡.《遺傳算法的數(shù)學(xué)基礎(chǔ)》西安交通大學(xué)出版社，2003

3.樂光學(xué)，彭小寧，曾志峰.試題庫自動組卷系統(tǒng)的算法與實現(xiàn)，計算機應(yīng)用，2001；21（8）：198-200

4.孫勇，柏云.基于遺傳算法的試題組卷策略.淄博學(xué)院學(xué)報（自然科學(xué)版），2002；（3）：27—28

5.劉彬，李勇，糜長軍.智能組卷系統(tǒng)中專家知識的表示與實現(xiàn).計算機工程與應(yīng)用，2002；38（17）：229— 231

6.王慧，劉寶坤，曹明，等.一種改進遺傳算法及應(yīng)用.天津理工學(xué)院學(xué)報，1998；14（4）：62—65