曹鑫+韓莉+韓紅彩+張亞娜

遺傳算法在考試系統(tǒng)的自動(dòng)組卷方面具有其他傳統(tǒng)組卷算法所不能比擬的優(yōu)點(diǎn)，通過交叉、變異等操作來產(chǎn)生新的個(gè)體，擴(kuò)大了搜索范圍，使得優(yōu)化的結(jié)果是全局最優(yōu)解而不是局部的最優(yōu)解，適合于大規(guī)模、復(fù)雜問題的求解，其計(jì)算簡(jiǎn)單但功能強(qiáng)大。

【關(guān)鍵詞】組卷；遺傳算法；操作

在線考試系統(tǒng)的設(shè)計(jì)與開發(fā)中，組卷是實(shí)現(xiàn)考試系統(tǒng)自動(dòng)化的核心問題之一。組卷是指由用戶先輸入對(duì)試卷試題的要求，然后系統(tǒng)自動(dòng)地從試題庫(kù)中選出符合用戶要求的試題，組成一份試卷的過程。

1 遺傳算法

遺傳算法是將孟德爾的遺傳變異理論與達(dá)爾文的“優(yōu)勝劣汰，適者生存”自然進(jìn)化學(xué)說進(jìn)行模擬，實(shí)現(xiàn)的一種迭代式的搜索算法。遺傳算法的步驟如下：

1.1 初始化

先產(chǎn)生足夠數(shù)量的個(gè)體，然后將這些個(gè)體組成一個(gè)種群。

1.2 迭代的執(zhí)行下面操作

在種群中，將每個(gè)個(gè)體的適應(yīng)度值計(jì)算出來，根據(jù)某個(gè)規(guī)則，選出一個(gè)能進(jìn)入到下一代的個(gè)體，產(chǎn)生一個(gè)新的種群。在這個(gè)新的種群中，按照交叉概率Pc進(jìn)行交叉操作，按照變異概率Pm進(jìn)行變異操作；如果不能滿足任何一個(gè)停止條件，那么就轉(zhuǎn)到第（1）步操作。

1.3 輸出適應(yīng)度值最優(yōu)的染色體作為最優(yōu)解

把問題的解用“染色體”來表示，把這染色體放到某個(gè)具體 “環(huán)境”中，根據(jù)適應(yīng)度函數(shù)值選出適應(yīng)度較高的“染色體”，并復(fù)制這些染色體，按照這個(gè)過程，將進(jìn)化工作一代一代的進(jìn)行下去，必將產(chǎn)生一個(gè)最適應(yīng)環(huán)境的 “染色體”，從而獲得問題的最優(yōu)解。

2 自動(dòng)組卷算法的實(shí)現(xiàn)

根據(jù)前面所介紹的有關(guān)遺傳算法的相應(yīng)知識(shí)，下面就對(duì)自動(dòng)組卷的算法進(jìn)行設(shè)計(jì)：

2.1 編碼

遺傳算法進(jìn)行優(yōu)化問題是通過編碼來實(shí)現(xiàn)的，因此編碼和解碼是遺傳算法的一個(gè)主題。首先是編碼算法的確定。由于標(biāo)準(zhǔn)化試卷每種題型所占的分?jǐn)?shù)、試題的個(gè)數(shù)和每題分?jǐn)?shù)的乘積是相同的，所以采用獨(dú)立的編碼策略。具體來講就是編碼的依據(jù)要結(jié)合題目的類型，在每種題型的內(nèi)部應(yīng)用常規(guī)編碼策略，也就是0-1編碼。這種方式的編碼使組與組之間的編碼是相互獨(dú)立，每一組的編碼都反映一種題型，試題庫(kù)中該題型的題目數(shù)量決定每一組編碼的長(zhǎng)度，一份試卷的編碼長(zhǎng)度就是總的編碼長(zhǎng)度，這是由試題庫(kù)中所含的試題總數(shù)決定。

2.2 生成初始群體

在初始群體產(chǎn)生的時(shí)候，首先將各個(gè)個(gè)體的所有位上均設(shè)置為“0”，然后參照每種題型題數(shù)的限制，隨機(jī)產(chǎn)生與試題數(shù)目相同的“1”位，這樣可以保證初始群體各個(gè)個(gè)體都滿足試卷的標(biāo)準(zhǔn)格式和滿分都為100分的特點(diǎn)。另外，這也解決了因試題數(shù)目過多而造成編碼長(zhǎng)度過長(zhǎng)的問題。種群規(guī)模n較大則進(jìn)化較慢，但是對(duì)全局最優(yōu)解的搜索會(huì)較為容易，而n較小時(shí)，則進(jìn)化速度快，但對(duì)全局的最優(yōu)解的搜索灰較為復(fù)雜。

2.3 計(jì)算初始群體適應(yīng)度

由于采用獨(dú)立編碼方式，所以在初始種群產(chǎn)生時(shí)，題型、題數(shù)和題分都是滿足要求的，因此在組卷過程的實(shí)際操作中，只需要考慮知識(shí)點(diǎn)的難度系數(shù)、范圍、試題區(qū)分度和教學(xué)要求等因素即可。在此可將知識(shí)單元的權(quán)值取1.0，試題區(qū)分度的權(quán)值取1.0，教學(xué)要求的權(quán)值取0.9，難度系數(shù)的權(quán)值取1.1。以上這些權(quán)值是在模擬組卷過程中使用的，而實(shí)際權(quán)值的確定應(yīng)該根據(jù)考試的要求或目標(biāo)進(jìn)行設(shè)定。

2.4 選擇

首先根據(jù)適應(yīng)度對(duì)群體中所有的個(gè)體進(jìn)行由小到大的排序，然后將排在最前面的一半染色體選取出，在對(duì)這些選取出的染色體進(jìn)行下面的操作。

2.5 交叉遺傳

交叉遺傳是針對(duì)編碼進(jìn)行的，此方法必須得保證試卷編碼中的各段1的位數(shù)恒定不變，否則將會(huì)引起試卷中每個(gè)題型的題數(shù)發(fā)生變化，導(dǎo)致生成的試卷不符合標(biāo)準(zhǔn)化試卷的要求。因此在組卷過程中，采用單親遺傳法，這種方法可以避免兩條染色體在進(jìn)行交叉時(shí)，所引起的試卷中不同類型的題數(shù)發(fā)生變化的情況。交叉操作是各段分別通過隨機(jī)數(shù)隨機(jī)產(chǎn)生交叉位，它是一種以染色體中點(diǎn)為軸心進(jìn)行的對(duì)稱交叉。

2.6 變異

為了使各題型組內(nèi)題目數(shù)量不會(huì)受變異操作而發(fā)生改變，可以采用一種一次變異操作，使組內(nèi)可同時(shí)變異兩位的方法，即一位0到1（1到0），而在該位所在的組內(nèi)，應(yīng)采用先向前、再向后的搜索方式，將與該位最近的1變?yōu)?（0到1）。

2.7 算法終止條件

遺傳算法中的優(yōu)化準(zhǔn)則，是一種依據(jù)問題的不同而有所不同的確定方式，可以采用如下準(zhǔn)則之一來作為判斷的條件：種群中個(gè)體的平均適應(yīng)度基本上達(dá)到了用戶預(yù)先設(shè)定的值；用戶輸入的值要大于種群中個(gè)體的最大適應(yīng)度；世代數(shù)超過預(yù)先設(shè)定的值。這里的終止條件是：設(shè)置遺傳最大代數(shù)為200，那么進(jìn)化到200后就會(huì)終止進(jìn)化過程。

為了防止組出相同的試卷，還需要對(duì)試題庫(kù)進(jìn)行一定的修改，即修改從試題庫(kù)中抽取的試題的使用次數(shù)和最近使用的時(shí)間，以便保證在連續(xù)生成的幾份試卷中或在某一段時(shí)間內(nèi)不會(huì)重復(fù)出現(xiàn)同一試題。

3 基于遺傳算法的組卷流程

在實(shí)現(xiàn)自動(dòng)選題時(shí)，可以采用父輩挑選與生存選擇兩種選題的方式。父輩挑選的方式是將每次選出的隨機(jī)抽樣不再返回，這種方式使得試題庫(kù)中的每道題目都有可能被選中；生存選擇的方式是指父輩與子代之間進(jìn)行競(jìng)爭(zhēng)，能進(jìn)入到下一輪競(jìng)爭(zhēng)環(huán)境的是二者中的優(yōu)良者，這是一種擇優(yōu)選擇。這兩種方法共同作用于試題的選擇，可以保證順利完成選題。在選題的過程中，題目的選擇是隨機(jī)的，而且哪一道題目被選中是一個(gè)非均勻的隨機(jī)事件，題目被選中的概率要依賴于上一次選題的過程。

遺傳算法在考試系統(tǒng)的自動(dòng)組卷方面具有其他傳統(tǒng)組卷算法所不能比擬的優(yōu)點(diǎn)，通過交叉、變異等操作來產(chǎn)生新的個(gè)體，擴(kuò)大了搜索范圍，使得優(yōu)化的結(jié)果是全局最優(yōu)解而不是局部的最優(yōu)解，適合于大規(guī)模、復(fù)雜問題的求解，其計(jì)算簡(jiǎn)單但功能強(qiáng)大。

參考文獻(xiàn)

[1]劉彬，金濤，陳太平.遺傳算法在試題組卷中的應(yīng)用[J].燕山大學(xué)學(xué)報(bào)，2002，26（03）：193-195.

[2]王娜.多目標(biāo)組卷模型及其算法研究[J].沈陽(yáng)師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，24（02）：189-191.

[3]管寶云，尹琦.基于混合智能算法的自動(dòng)組卷問題研究[J].天津工業(yè)大學(xué)學(xué)報(bào)，2006（04）：97-100.

[4]曾一，一冉忠，郭永林.試題庫(kù)中自動(dòng)組卷的算法及試卷測(cè)評(píng)策略[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（06）：3024-3027.

作者簡(jiǎn)介

曹鑫（1981-），女，現(xiàn)為石家莊信息工程職業(yè)學(xué)院講師，研究方向?yàn)樾畔⑾到y(tǒng)開發(fā)。

韓莉（1977-），女，現(xiàn)為石家莊信息工程職業(yè)學(xué)院講師，研究方向?yàn)閿?shù)據(jù)庫(kù)應(yīng)用于開發(fā)。

韓紅彩（1980-），女，現(xiàn)為石家莊信息工程職業(yè)學(xué)院講師，研究方向?yàn)閿?shù)據(jù)庫(kù)應(yīng)用于。

張亞娜（1979-），女，現(xiàn)為石家莊信息工程職業(yè)學(xué)院講師，研究方向?yàn)樾畔⑾到y(tǒng)開發(fā)。

作者單位

石家莊信息工程職業(yè)學(xué)院 河北省石家莊市 050035