基于遺傳算法的組卷方法研究

王民川

鄭州廣播電視大學，河南鄭州 450007

考試是一項“測量工程”。從統(tǒng)計學的角度來看，考試是一種抽樣測量，通常我們告訴學生的應考內容是考查的總體，而試題實際考查到的內容則是我們從總體中抽取的樣本。要提高考試質量，在實施考試之前，先要進行設計。為了更好地普及計算機命題，有必要研究一種采用科學、先進的組卷方法來實現(xiàn)快速、高效、科學組卷。本文著重對遺傳算法在自動組卷中的應用研究，通過對遺傳算法理論的研究，探討一下遺傳算法以解決智能選題成卷的問題。

1 自動組卷算法研究

國內外的許多科研單位、學校機構都在對組卷系統(tǒng)進行研究[1]。雖然組卷系統(tǒng)是一個被探討了很長時間的問題，但至今還沒有一個很好的解決其自動出題的算法方案。以前所采用的算法大多是隨機選取和回溯試探法，他們雖然都能最終組出試卷，但是在實際的操作過程中，卻發(fā)現(xiàn)他們不是耗費的時間很大就是容易進入死循環(huán)。

2 遺傳算法概述

遺傳算法GA[2]（Genetic Algorithm）是一種新型的、模擬自然界生物進化過程的隨機搜索、優(yōu)化方法。他是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是由美國Michigan大學的JohnH.Honlland教授于1975年首先提出來的。他采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。由于他采用種群的方式組織搜索，這使得他可以同時搜索解空間內的多個區(qū)域。而且用種群組織搜索方式使得遺傳算法特別適合大規(guī)模并行。

3 基于遺傳算法的組卷方法

首先，確定考試時間KSSJ、試卷的滿分值MFZ和所用的題型以及各種題型的題目和分數，而且對一種考試而言，這種題型一一分數分布曲線LT常保持相對穩(wěn)定，如英語等級考試、各種計算機等級考試等都是這樣。

其次，獲取難度一一分數分布曲線LD、內容一一分數分布曲線LC，教學要求度一一分數分布曲線LR及其各自允許的誤差，曲線LC，LR及其允許的誤差均由用戶給出。曲線LD在很大程度上決定了考試成績的分布，是很重要的一條曲線。

4 自動組卷的遺傳算法設計與實現(xiàn)

4.1 染色體編碼及群體的初始化

經典遺傳算法采用二進制編碼，用1表示該題被選中，0表示該題未被選中，這種編碼簡單明了，但是進行交換等遺傳操作時，各題型的題目數難以精確控制，而且，當題庫中題量很大時，編碼很長。

4.2 適應度函數

在遺傳算法中，以適應值大小來區(qū)分群體中個體的優(yōu)劣。一般情況下適應值越大的個體越好，適應值越小的個體越差。

4.3 遺傳算子設計

1）選擇算子

采用期望值模型選擇機制，即先用公式1計算群體中各個個體期望被選中的次數：

2）交叉算子

將以上選出的個體進行兩兩隨機配對，對每一對相互配對的個體采用有條件的“均勻交叉”，即兩個配對個體的每一個基因座上的基因都按設定的交叉概率Pc和一定的條件（確保交換后個體仍是有意義的組合）進行交換，產生兩個新個體。

3）變異算子

由于普通的變異操作可能會使用戶指定范圍外的題目出現(xiàn)在染色體中，也會使各題型的題目數難以保證，本文采用有條件的變異算子，即每個個體的每一個基因座上的基因都按設定的變異概率Pm在一定范圍內變異。

4）最優(yōu)保存策略

進行了選擇、交叉、變異操作后，比較新一代的最好個體與上一代的最好個體的適應值，如下降，則以上一代最好個體替換新一代的最差個體。

5）算法實現(xiàn)

確定參數：最大代數MaxGene，群體規(guī)模Pop Size，交叉概率Pc，變異概率Pm；

接收用戶的組卷要求：

產生初始群體；

當前代數Gene=0；

計算群體中各個體的適應值；

while（Gene

｛

根據個體適應值及選擇策略從當前群體中選擇生成下一代的父體；

執(zhí)行交換操作和變異操作生成新一代群體；

計算新一代群體中各個體的適應值；

比較新一代的最好個體與上一代的最好個體的適應值，如下降，則以上一代最好個體替換新一代的最差個體：

輸出當前代數，群體的平均目標函數，最好個體的目標函數值；

輸出最好個體的編碼，計算各難度級別的分數等指標，輸出這些指標的值并與用戶的要求值相比較。

5 成卷的技術指標

從難度、區(qū)分度、信度、效度是評介成卷合理性的有效指標，盡管這些指標是利用試卷的應試結果進行分析，我們在組卷時沒有應試結果，但我們應當了解其計算方法，以便指導我進行科學、合理性組卷。試卷分析涉及的理論如下所述[3]。

6 組卷系統(tǒng)分析

本系統(tǒng)要求所開發(fā)的組卷功能體現(xiàn)遺傳算法的應用,其技術指標，如：難度、所用時間等，存放在試題庫中，而試題庫管理系統(tǒng)則采用合理的選題算法，對題庫中的題目從難度進行控制選題，從而生成符合測試要求的試卷。

7 結論

隨著計算機考試系統(tǒng)的不斷普及,基于遺傳算法的自動組卷技術越來越成為計算機輔助測試中人們研究的一個熱點。文章基于對遺傳算法的研究，只應用了組卷系統(tǒng)的幾個變量，至于要自動生成完全符合標準化考試的試卷，則算法中應用加入更多的組卷系統(tǒng)變量，才能高效、科學地滿足組卷要求。由于計算量大，所以在運行過程中程序出現(xiàn)了假死現(xiàn)象，這個問題值得繼續(xù)研究。

[1]王小平，曹立明.遺傳算法[M].西安:西安交通大學出版社，2002，6.

[2]李敏強，等著.遺傳算法的基本理論與應用[M].北京：科學出版社，2003，3.