一種基于ＣＨＣ算法的自動組卷方法

（西安電子科技大學 a.網(wǎng)絡(luò)教育學院; b.計算機學院， 西安 710071）



摘 要：利用改進的遺傳算法——跨世代異物種重組大變異(cross generation heterogeneous recombination cataclysmic mutation，CHC)算法提出了一種自動組卷方法。初始種群即初始試卷集利用具有啟發(fā)式信息的搜索算法產(chǎn)生；適應(yīng)度函數(shù)是用戶指定的試卷總體指標與試卷實際指標絕對誤差的加權(quán)和；選擇操作群體為當前群體與上世代群體的群體總和，因為大個體群操作可以更好地保持遺傳多樣性；交叉操作采用單點交叉方法。變異操作的步驟是：從上世代個體中挑選適應(yīng)度較差的個體，對其中的若干個個體選擇一定比例的基因座，隨機地決定它們的位值。由于考慮到了約束條件的限制，從而避免了盲目性且加快了收斂速度。實驗結(jié)果表明該方法比基本遺傳算法要快而且滿足最優(yōu)條件。

關(guān)鍵詞：自動組卷； 跨世代異物種重組大變異算法； 遺傳算法

中圖分類號：TP301.6 文獻標志碼：A

文章編號：10013695(2009)01013403



Approach of auto generating examination paper based on CHC algorithm

DING Zhenguoa， GUO Haiyanb



(a.School of Network Education， b.School of Computer Science Technology， Xidian University， Xi’an 710071， China)



Abstract:An approach of auto generating examination paper based on the improved genetic algorithm CHC algorithm was proposed．The initial population was produced by the searching algorithms containing heuristic information． The fitness function was the weighted sum of the absolute error of the paper entire index andactual index．The select operating population was summation of current and previous one，for the operating population was big，the genetic diversity could be kept better．The single node crossover was used in cross operating．The mutate operating process was that some individuals of bad fitness were chosenfrom last generation first，then locas in proportion with these individuals were picked up，these place values were determined randomly．Due to the restrict of the capability，the algorithm can avoid blindness and can speed up the constringency． Simulation results show that the planning algorithm is faster than the basal genetic algorithms and meet the optimal requirements．

Key words：auto generating examination paper； cross generation heterogeneous recombination cataclysmic mutation(CHC)algorithms； genetic algorithm



0 引言

自動組卷就是根據(jù)用戶輸入的組卷要求，計算機自動從試題庫中選擇試題組成一份符合用戶要求的試卷。自動組卷的效率與質(zhì)量完全取決于組卷算法的設(shè)計。如何設(shè)計一個算法從題庫中既快又好地抽出一組最佳解或是抽出一組非常接近最佳解的實體，涉及到一個全局尋優(yōu)和收斂速度快慢的問題。目前比較流行的自動組卷的方法是根據(jù)用戶輸入的試卷總體要求，分別匹配試卷的知識分布、題型分布、認知分類分布、難度分布、區(qū)分度分布、時間分布、分數(shù)分布，形成組卷參數(shù)表，然后根據(jù)該參數(shù)表從試題庫中選題。這類方法在形成最終的組卷參數(shù)表時，沒有考慮知識分布、題型分布、難度分布等各種參數(shù)之間的相互制約關(guān)系，因此在組卷時題庫中經(jīng)常會出現(xiàn)找不到滿足所有屬性的試題，只好用具有近似屬性的試題替代，最終會降低組卷的指標。針對這個問題，選題時可以采取一些策略，如優(yōu)先權(quán)策略、補償策略、回溯策略等，但這樣會使算法很復雜，效果也有限。

基于此，本文提出一種利用跨世代異物種重組大變異(CHC)算法來進行自動組卷的方法。CHC算法是遺傳算法的一種改進，它是由Eshelman于1991年提出的。該算法與基本遺傳算法（SGA）的不同點在于：SGA的遺傳操作比較單純，簡單地實現(xiàn)并行處理；CHC算法犧牲這種單純性，換取遺傳操作的較好效果，并強調(diào)優(yōu)良個體的保留。

1 CHC算法概述

遺傳算法是從代表問題可能潛在解集的一個種群開始的，一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應(yīng)度大小挑選個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后代種群比前代更加適應(yīng)環(huán)境，末代種群的最優(yōu)個體經(jīng)過解碼，可以作為問題的近似最優(yōu)解。CHC算法是簡單遺傳算法的改進，它強調(diào)優(yōu)良個體的保留，其改進之處首先表現(xiàn)在選擇上。通常，遺傳算法是依據(jù)個體的適應(yīng)度復制個體完成選擇操作的；而在CHC算法中，上世代種群與通過新的交叉方法產(chǎn)生的個體種群混合起來，從中按一定的概率選擇較優(yōu)的個體。這一策略稱為跨世代精英選擇。其明顯特征表現(xiàn)在：

a)健壯性。這一選擇策略，即使當交叉操作產(chǎn)生較劣個體偏多時，由于原種群大多數(shù)個體殘留，不會引起個體的評價值降低。

b)遺傳多樣性保持。由于大個體群操作，可以更好地保持進化過程中的遺傳多樣性。

c)排序方法。克服了比例適應(yīng)度計算的尺度問題。

d)在交叉操作上很靈活，根據(jù)不同的應(yīng)用領(lǐng)域采取不同的交叉方法。自動組卷由于通常采用符號編碼方案，可以利用單點交叉、雙點交叉及均勻交叉等。變異操作上CHC算法在進化前期不采取變異操作，當種群進化到一定的收斂時期，從優(yōu)秀的個體中選擇一部分個體進行初始化。初始化的方法是選擇一定比例的基因座，隨機地決定它們的位值。這個比例值稱為擴散率，一般取0.35。

2 組卷問題的數(shù)學模型

組卷問題實際上是一個多條件的約束優(yōu)化問題，這個問題通常被定義為一個目標函數(shù)和多個約束條件的組合。

為了考核學生對所學內(nèi)容的掌握情況，每道試題一般需具備如下九個屬性:試題編號、題目類型、試題所屬知識點、難度、區(qū)分度、認知分類、估計答題時間、分值、曝光度。所以在組卷中生成一份試卷，就是得到一個m×9的矩陣。其中：m是該試卷中試題量總數(shù)；每道試題的九個屬性決定矩陣S一行元素的值。S可表示為如下形式:

S=

a11a12…a18a19

a21a22…a28a29

 

am1am2…am8am9

這是一個問題求解中的目標狀態(tài)矩陣，它應(yīng)盡量滿足如下多個約束條件:

a)總答題時間f1(由用戶給出) = ∑mi=1ai，7。

b)試卷總分f2(由用戶給出)=∑mi=1ai，8。

c)試卷難度系數(shù)f3(由用戶給出)= ∑mi=1ai，4/m。

d)區(qū)分度f4(由用戶給出)=∑mi=1ai，5/m。

e)試卷題型分布及各題型試題量分布f5(由用戶給出)=∑ki=1bi=m。其中：k為試卷題型數(shù)；bi為各題型試題量。

f)試卷認知分類分布f6(由用戶給出)=∑pi=1ci=f2。其中：p為認知分類類型數(shù)；ci為各認知分類的題目所占的分值。

g)曝光度f7=∑mi=1ai，9盡可能地小。

在實際應(yīng)用中設(shè)定整卷指標來綜合反映這個指標與用戶要求的誤差。由于它們的重要程度不同，整卷的指標就是幾個指標的加權(quán)和；同時為了不至于各個誤差相互抵消，這幾個指標與用戶要求的誤差都取絕對值。可以用下式表示:f=∑fiwi。其中：fi表示第i個指標與用戶要求的誤差的絕對值；wi表示第i個指標的權(quán)值。組卷的目標就是使整卷指標f最小，或者盡可能小。

3 自動組卷的算法實現(xiàn)

3.1 編碼方法

問題解的編碼表示采用基因分段式編碼，在編碼時可以解決組卷中題型及各題型題量分布這些約束條件，簡化求解問題。具體編碼方式如下:首先根據(jù)各題型獨立編碼成基因段，基因段的數(shù)量由題型的數(shù)量決定，用k來表示；每一基因段內(nèi)基因數(shù)由試題庫內(nèi)該題型的題量決定。因此，試題庫有n道試題時編碼為b1，b2，…，bn。

bi=1 當?shù)趇道題被選中時0 當?shù)趇道題被選中時；i=1，2，…，n

且滿足條件∑ni=1bi=m， m是實際組卷中試卷所需題量

∑r1i=1bi=m1，∑r2i=r1+1bi=m2，…，∑rki=r(k-1)+1bi=mk，∑ki=1mi=m，rk=n

rk-r(k-1)為試題庫中各題型的題量;m1，…，mk分別為實際組卷中各題型所需題量。

3.2 初始化群體的產(chǎn)生

初始試卷集是整個遺傳算法迭代的起點，本文采取如下策略產(chǎn)生初始試卷集：對每一基因段隨機選擇m個位置，將它們的位值置1，其他位值置0。這樣就生成一個初始試卷個體，如此反復生成包含n個個體的初始試卷集。在初始試卷集中，串長度都是相同的，群體大小根據(jù)需要，按經(jīng)驗或?qū)嶒灲o出。在實際組卷中，設(shè)群體規(guī)模為N，每一個體的基因段都是通過random()這個函數(shù)在該類題型的最小題號與該類題型的最大題號之間隨機選擇mi道題。其中mi表示第i種題型所需題量。

在生成初始群體的個體時，每產(chǎn)生一個滿足條件的隨機數(shù)時，都要把題庫中對應(yīng)試題選題標記置1。同時把題庫中具有相同知識點的試題的選題標記置1，這樣就可以避免相同知識點試題在同一試卷生成時重復出現(xiàn)，從而優(yōu)化了初始群體。

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

首先通過解碼得到個體的組卷參數(shù)矩陣S。具體過程如下：根據(jù)串b1，b2，…，bn的值，可知試卷中包含的試題題號；然后把這些試題的屬性寫到組卷參數(shù)矩陣S中(由此可以看到：組卷參數(shù)矩陣S的值是由題庫中的試題屬性組成的，這就保證了按照矩陣S來選題時不會出現(xiàn)找不到題的情況)；最后調(diào)用評估函數(shù)得到每個個體的適應(yīng)度。在實際應(yīng)用中，通過計算個體的整卷指標f來反映個體的適應(yīng)度，整卷指標f越小，個體的適應(yīng)度越高。所以可取適應(yīng)度函數(shù)為整卷指標f的倒數(shù)，即F=1/f。適應(yīng)度函數(shù)反映了個體與成卷要求之間的差別，算法在優(yōu)化搜索中以適應(yīng)度函數(shù)為尋優(yōu)依據(jù)。

3.4 遺傳算子的設(shè)計

1）選擇算子

根據(jù)適應(yīng)度的大小按照比例選擇方法來求取個體遺傳到下一代的概率，方法如下：a)首先計算出當前群體P(k)和通過交叉方法產(chǎn)生的個體群體C′(k)中每個個體的適應(yīng)度Fi；b)計算每個個體的相對適應(yīng)度的大小，即Fi/∑nj=1Fj，它就是被遺傳到下一代的概率；c)利用輪盤賭選擇方法來確定每個個體被選中的次數(shù)；d)對當前群體P(k)和通過交叉產(chǎn)生的群體C′(k)中的個體按照適應(yīng)度進行大小排序，選取前面N個適應(yīng)度大的個體作為遺傳到下一代的個體，這樣群體規(guī)模又恢復為原來的規(guī)模。

2)交叉算子

對當前群體P(k)與上世代群體P(k-1)混合后產(chǎn)生混合種群C(k)中的個體進行配對，即分成N對個體對，然后計算配對個體間的海明距離。當該距離大于海明距離閾值時，對該配對個體實行交叉策略；否則將該配對個體從種群C(k)中消除。這里采用單點交叉方法，即首先找出每對的兩個個體中在同一基因段內(nèi)距離最近的兩個點，這就是需要交叉的點，交換這兩個點的編碼即產(chǎn)生了兩個新個體。交叉后的種群記為C′(k)。

3)變異算子

在進化前期不進行變異操作，當進化到一定收斂時期時才采取變異操作。變異的方法是從P(k)中選擇適應(yīng)度較差的N1個個體進行初始化。初始化的方法是選擇一定比例的基因座，隨機地決定它們的位值。

采用沒有重串的穩(wěn)態(tài)繁殖技術(shù)，即在形成新一代種群時，使其中的種群均不重復。在將child1′、child2′加入到新的一代種群之前，先檢查它們是否與種群中現(xiàn)有的個體重復；若重復，則舍棄，重新進行變異，甚至重新進行交叉。

4 實驗結(jié)果與結(jié)論

利用J2EE平臺進行實驗分析，將500道試題按要求分別賦予各項特征值存于試題庫中， 給出要生成的試卷要求，為了比較CHC算法與基本遺傳算法，仿真時分別采用了這兩種算法進行對比分析。這里，群體規(guī)模選為20。表1為兩種算法的仿真結(jié)果。利用基本遺傳算法時的平均迭代次數(shù)為354.4次，利用CHC算法時的平均迭代次數(shù)為24次。可見利用CHC算法得到的結(jié)果比基本遺傳算法有較優(yōu)的性能指標。

表1 兩種算法的性能比較

迭代次數(shù) 實驗次數(shù)

遺傳算法CHC算法迭代次數(shù)

實驗次數(shù)遺傳算法CHC算法

121126446118

233317540931

335828平均354.424

5 結(jié)束語

智能組卷是一個典型的多條件約束優(yōu)化問題，本文針對該問題，采用CHC算法進行求解，提高了遺傳算法的搜索速度、簡化了雜交運算，具有很好的性能和實用性。

參考文獻：

［1］魏平，熊偉清.用遺傳算法解組卷問題的設(shè)計與實現(xiàn)[J].微電子學與計算機，2002，19(4):4850.

[2]閉應(yīng)洲，蘇德富，陳寧江.基于矩陣編碼的遺傳算法及其在自動組卷中的應(yīng)用[J ].計算機工程，2003，29(6):7376.

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

[4]陸億紅，柳紅.基于整數(shù)編碼和自適應(yīng)遺傳算法的自動組卷[J].計算機工程，2005，31(23):232233.

[5]朱黎明，林亞平，陳治平，等.基于單親遺傳算法的智能組卷研究[J].科學技術(shù)與工程，2005，5(15):10641066.

[6]張振理，王英勛.基于CHC算法的無人機航跡規(guī)劃方法[J].北京航空航天大學學報，2007，33（6）:690693.

[7]張辰，張艷群.基于遺傳和模擬退火算法的自動組卷系統(tǒng)設(shè)計與實現(xiàn)[J]. 計算機工程與科學，2004，26(11):6568.

[8]周文舉.一種基于知識點的遺傳算法組卷的改進應(yīng)用[J].山東師范大學學報:自然科學版， 2006，21(3):3942.