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

王民川

鄭州廣播電視大學(xué)，河南鄭州 450007

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

1 自動組卷算法研究

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

2 遺傳算法概述

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

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

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

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

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

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

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

4.2 適應(yīng)度函數(shù)

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

4.3 遺傳算子設(shè)計

1）選擇算子

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

2）交叉算子

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

3）變異算子

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

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

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

5）算法實現(xiàn)

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

接收用戶的組卷要求：

產(chǎn)生初始群體；

當(dāng)前代數(shù)Gene=0；

計算群體中各個體的適應(yīng)值；

while（Gene

｛

根據(jù)個體適應(yīng)值及選擇策略從當(dāng)前群體中選擇生成下一代的父體；

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

計算新一代群體中各個體的適應(yīng)值；

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

輸出當(dāng)前代數(shù)，群體的平均目標(biāo)函數(shù)，最好個體的目標(biāo)函數(shù)值；

輸出最好個體的編碼，計算各難度級別的分?jǐn)?shù)等指標(biāo)，輸出這些指標(biāo)的值并與用戶的要求值相比較。

5 成卷的技術(shù)指標(biāo)

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

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

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

7 結(jié)論

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

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

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