唐玲 尹珧人

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

關鍵詞：改進遺傳算法 智能組卷 數(shù)學模型

中圖分類號：TP18 文獻標識碼：A 文章編號：1674-098X（2013）03（c）-00-02

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

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

將智能組卷問題視為從一定題量的數(shù)據(jù)庫中抽取滿足組卷要求的一組試題組合，就能夠將組卷問題轉化為一個多重約束目標問題。求解一份由m道試題且每道試題有n個屬性的試卷，相即構建一個m×n的目標矩陣S。

S=

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

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

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

⑶答題總時間=（由用戶給定）；

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

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

組卷過程中，試題要根據(jù)數(shù)學模型中給出的各項指標來決定，即表示第i道試題中的第j項指標，其中i=1，2，…，m；j=1，2，…，n。

2 題庫建設

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

質量。

3 改進的遺傳算法在智能組卷中的

應用

3.1 編碼方案

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

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

3.2 生成初始種群p（0）

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

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

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

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

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

3.4 遺傳算子的改進

3.4.1 選擇算子

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

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

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

3.4.2 交叉算子和變異算子

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

pC=

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

pm=

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

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

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

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

3.5 終止條件

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

卷時。

4 仿真試驗結果分析

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

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

參考文獻

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

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

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

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

[5] 吳飛.自適應遺傳算法解決組卷問題的探討[J].重慶科技學院學報（自然科學版），2007（2）.