王民川

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

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

1 自動(dòng)組卷算法研究

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

2 遺傳算法概述

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

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

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

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

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

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

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

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

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

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

1）選擇算子

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

2）交叉算子

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

3）變異算子

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

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

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

5）算法實(shí)現(xiàn)

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

接收用戶的組卷要求：

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

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

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

while（Gene

｛

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

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

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

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

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

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

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

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

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

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

7 結(jié)論

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

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

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