基于改進遺傳算法的試卷生成算法研究

摘 要:針對應用傳統遺傳算法在組卷中出現的早熟和收斂速度慢等問題，提出基于改進遺傳算法的試卷生成算法。詳細介紹改進的遺傳算法應用于組卷的步驟，包括編碼方法、適應度函數、交叉算子和變異算子的確定等關鍵內容。該算法采用分組自然數形式進行個體編碼，同時，一改傳統交叉方法，采用自適應交叉概率和遺傳概率的方法進行運算。仿真實驗表明，該算法有效提高了組卷的效率。

關鍵詞:題庫;組卷;遺傳算法;自適應交差概率

中圖分類號:TP31文獻標識碼:A

文章編號:1004-373X(2010)06-143-02

Generation Algorithm of Test Paper Based on Improved Genetic Algorithm

XUE Fang，SU Yulei

(Computer Teaching Room，Xi′an Medical University，Xi′an，710021，China)

Abstract:In response to the phenomena of premature manner and low speed in convergence as traditional genetic algorithm is applied in generating test papers，an improved genetic-algorithm-based generating style is proposed.Meanwhile，it also elaborates process of the improved style in generating test papers，including the confirmation of encoding method，fitness function，crossover operator and mutation operator.Group method of positive integer has been adopted in this improved algorithm in individual coding.Furthermore，the improved algorithm manages to make use of crossover probability and genetic probability in the operating process.From the proof in a series of simulation tests，the improved algorithm enhances efficiency in generating test papers to a great extent.

Keywords:item bank;test-paper;genetic algorithm;adaptive crossover probability

0 引 言

教學中的最后一個環節，也是最能體現學生學習情況、教師授課效果的環節就是考試。但面對各高校每年大量擴招的現狀，考試命題、閱卷等工作越來越繁重，這無疑使得命題效率、試卷質量、閱卷差錯率受到或多或少的影響。同時，傳統命題方式，可能產生不同教師命題，內容側重點、難點有所差異，無法更客觀、公正地反映學生的學習效果及教師的教學質量，無法對教師的教學改革提供更積極有益的理論指導。因此，推行無紙化考試，采用高效智能算法自動生成試題成為對學生考核手段變革的必然。

組卷問題是一個全局尋優的問題，在尋優過程中需要綜合考慮章節(ch)、題型(ty)、知識點(Kn)、難度系數(Di)、區分度(De)、答題時間(Ti)、分數(Sc)等各種約束條件。則每道題目可用一個形如:(Ch，Ty，Kn，Di，De，Ti，Sc)的7維向量描述。設題庫中題目數量為n，則n道題目可用式(1)所示的7×n階矩陣描述。

Ch1Kn1Di1De1Ti1Ti2Tin

Ch2Kn2Di2De2Sc1Sc2Scn



ChnKnnDinDenTy1Ty2Tyn〗(1)

式(1)中:七種參數既可由用戶手工輸入，也可利用之前的模板自動產生。試卷生成算法可轉化為如何在已有n道題目的題庫中選擇m道題目，使這m道題目在章節、知識點、難度系數、區分度等方面滿足或最接近用戶的需求，即在該7×n階矩陣中選則最優的7×m階子矩陣。

1 傳統試卷生成算法

經過20多年的發展，目前主要采用的試卷生產算法有以下三種:

1.1 隨機選取法

根據用戶輸入的考試要求，隨機從試題庫中選取滿足條件的試題組成試卷，直到整份試卷組成或已搜索到題庫末尾。該方法具有很大的隨機性和不確定性，無法從整體上把握教學的要求，不具有智能性[1]，且組卷效率低下。

1.2 回溯試探法

即將隨機選取法產生的每一個狀態類型記錄下來，當搜索失敗時釋放上次的狀態類型，再按照一定的變換規律重新選取，直到滿足要求的整份試卷自動生成[2]。

1.3 傳統遺傳算法

遺傳算法(Genetic Algorithm)是模擬達爾文進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法從代表問題可能潛在的解集的一個種群(Population)開始，而一個種群則由經過基因(Gene)編碼的一定數目的個體(Individual)組成。每個個體實際上是染色體(Chromosome)帶有特征的實體。應用于組卷中，種群即初始交配池中試卷的集合，個體即每一套試卷而染色體即組成該試卷的每道試題。傳統遺傳算法生成試卷的思路如圖1所示。

圖1 遺傳算法應用于組卷問題流程圖

首先按特定方法對試題進行編碼，然后從原始題庫中抽取出一定數量的試題生成n份初始試卷，作為遺傳算法的交配池。計算其中每份試題的適應度值，并按照預先設置好的復制、交叉、變異原則進行相應運算，衡量適應度值是否滿足要求。如果滿足則解碼生成試卷，否則繼續進行交叉變異等各項運算，直至適應度值滿足要求或達到預先設定好的代數要求為止。

2 基于改進遺傳算法的試卷生成算法設計

遺傳算法具有內在的并行性，全局尋優和收斂速度快的特點，這些都易于處理試題庫自動組卷問題[3]。但基于傳統的遺傳算法的組卷方法易發生早熟、收斂速度慢等問題，針對這些問題，魏平等[4]采用穩態策略的單親遺傳算法求解組卷問題，通過突變算子的引入，使整個種群保持在最有可能獲得成功的狀態，加快算法向全局最優值的逼近速度。王淑佩等[5]提出了一種自適應調整種群適應值分布的基于小生境技術的遺傳算法并將之應用于求解組卷問題。

本文采用一種新的基于改進遺傳算法的試卷生成算法，具體設計如下:

2.1 編碼設計及初始種群的生成

試題編碼采用分組自然數編碼方式。按照題型將其分為不同組，組內采用自然數按照題目錄入的先后順序編碼。在系統生成試卷前，首先需要用戶提供期望的難度、章節、及命題藍圖。如:用戶期望的試卷難度為0.8，命題范圍為1~6章，并選用1號命題藍圖，即:整份試卷滿分100，其中選擇題20×2分、填空題10×1分、判斷題10×1分、簡答題4×5分、程序設計題2×10分。運用石中盤[6]的理論，根據用戶輸入的期望難度值自動生成各種難度試題占整份試卷的百分比，再在遵從章節分配和命題藍圖等約束條件的前提下，隨機生成初始種群。表現形式如表1，表2所示。

表1 試卷A

選擇填空判斷 簡答程序設計

3 78 122 1 … 9 2 54 … 88…… 5 1

表2 試卷B

選擇填空 判斷 簡答程序設計

6 32 99 2 … 142 65 42 … 1 ……6 2

2.2 適應度函數

適應度函數用于衡量個體性能的優略程度，他的設計對遺傳算子有很大影響，是優化個體的依據[7]。本文采用實際屬性值和用戶期望值之差作為適應度函數，差值越小說明個體適應度越高，越符合用戶的期望，反之，適應性越低。

試卷難度:Di(x)=Dih-g(x)。式中:Dih為用戶期望的難度系數;g(x)=(∑ni=1ai)/n為當前試卷難度;ai為每道試題的難度。

同理可得出區分度的適應度函數De(x)。

章節:C(xi)=Ch-Ci。式中C(xi)為第i章的值，Ch為用戶期望該章節試題占整份試卷的比例;Ci為該章節題目實際所占比例。

整份試卷的適應度:

F(x)=max[Di(x)，De(x)，C(x)]

2.3 選擇算子

對原種群中的個體按適應度值的大小排序，取值最小的前20%個體直接進入下一代種群，余下的個體兩兩配對，按交叉、變異概率進行相應運算。

2.4 交叉算子及變異算子

為了避免早熟及收斂速度慢等問題，在交叉算子和變異算子的設計上采用自適應方法，根據不同個體的適應度值選取適合自己的交叉和變異算子。給定標準交叉、變異概率(j，b)，當適應度函數的值較大時，個體的交叉、變異概率增大。

交叉概率:

Pj=j，F(x)≤Favg

j[F(x)/Favg]，F(x)>Favg

變異概率:

Pb=b，F(x)≤Favg

b[F(x)/Favg]，F(x)>Favg

3 結 語

經試驗，該算法在交叉概率j為0.78～0.82，變異概率b=0.3，種群大小Popsize=80，固定最大代數Maxgen=150時可快速、高效得到有用解。

參考文獻

[1]全惠云，范國闖.基于遺傳算法的試題庫智能組卷系統研究[J].武漢大學學報:自然科學版，1999，45(5):758-760.

[2]楊青.基于遺傳算法的試題庫自動組卷問題的研究[J].濟南大學學報:自然科學版，2004，18(3):228-230.

[3]王淑佩，易葉青.基于改進自適應遺傳算法的組卷研究[J].科學技術與工程，2006，6(4):469-473.

[4]魏平，干海光，熊偉清.基于進化穩定策略的單親遺傳算法求解組卷問題[J].微電子學與計算機，2005，21(2):105-109.

[5]王淑佩.一種新的基于小生境的自適應遺傳算法[D].蘭州:蘭州理工大學，2006.

[6]石中盤，韓衛.基于概率論和自適應遺傳算法的智能抽題算法[J].計算機工程，2002(1):141-143.

[7]周文舉.基于遺傳算法的自動組卷系統研究與實現[D].濟南:山東師范大學，2006.

[8]肖成林，徐清振.基于遺傳算法的成卷策略的設計與實現[J].現代計算機，2003(8):39-41.