基于遺傳算法的在線考試系統的研究

蘇小兵 李天平

山東師范大學傳播學院 濟南 250014

近年來，計算機技術和人工智能得到快速發展，隨著教育測量理論研究的不斷深入，基于遺傳算法組卷系統的研究與開發得到越來越多的專家學者的關注。本文從教學要求出發，結合項目反應理論，以遺傳算法為基礎，提出基于項目反應理論的數學模型。用此組卷算法實現的在線考試系統的數據表明，算法能夠有效解決自動組卷問題，有效提高組卷的質量和速度。

1 教育測量理論

試題庫是按照一定的教育測量理論利用計算機技術構成的某學科試題的集合。目前常用的教育測量理論主要有兩種，一種是經典測量理論（Classical Test Theory，CTT），另一種是項目反應理論（Item Response Theory，IRT）。

項目反應理論是克服經典測量理論的各種局限性而發展起來的一種全新的測量學理論[1]。項目測量理論在20世紀50年代初正式確立，它的基本思想是：確定考生的心理特質值和他們對于項目反映之間的關系，這種關系的數學形式就是“項目反映模型”。這種模型不是確定性模型，而是概率模型，其原因是考生對于測驗項目的反映除了受到某種特定的“能力”的支配外，還受到許多隨機因素的影響，如焦慮、動機、考試技能等。項目反映模型是表示考生能力和考生對考試項目正答概率之間關系的數學形式，主要有拉希模型、Logistic雙參數模型，還有探索使用的等級積分模型、分布評分模型等。

2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一類借鑒生物界的進化規律（適者生存、優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它由美國的J.Holland教授于1975年首次提出[2]，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定，具有內在的隱含并行性和更好的全局尋優能力。采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳算法的這些性質已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域，是現在有關智能計算的關鍵技術之一[3]。

以Holland1975年提出的稱為傳統的GA為例，簡述它的主要步驟。

編碼：GA在進行搜索之前先將解空間的解數據表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合便構成不同的點。

初始群體的生成：隨機產生N個初始串結構數據，每個串結構數據稱為一個個體。N個個體構成一個群體。GA以這N個串結構數據作為初始點開始迭代。

選擇：選擇的目的是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。判斷個體優良與否的標準是各自的適應度值的大小。

交換：交換操作是遺傳算法中最主要的遺傳操作。通過交換操作可以得到新一代的個體，新個體組合了其父輩的個體特性。交換體現了信息交換的思想。

變異：變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結構數據中某個串的值。同生物界一樣，GA中變異發生的概率很低，通常取值在0.001～0.01。變異為新個體的產生提供了機會。

3 遺傳算法在在線考試系統中的應用

基于IRT的組卷問題可以描述為一個最大化模型，此模型滿足測試條件的同時，匹配公式（1）中對目標測驗信息函數指定的形式，最大化測驗信息函數[4]：

其中Xi表示試題是否被選進試卷中。若被選中，Xi＝1；否則，Xi＝0。Ii是能力θk點的項目信息函數值，而rk是測驗目標信息量，系數qin是題目i具有屬性n的參數值，Qn代表測驗中包含屬性n的題目數。cim是題目i的類別決策值，即如果題目i屬于類別m則其值為l，否則為0。Cmn代表測驗中允許包含的某一類別m的題目數范圍。而Lip是題目間約束關系的系數，Lp是約束邊界值。公式（1）用于表示題目之間的互斥或包含關系。

1）染色體編碼及初始種群的生成。染色體編碼就是對試題庫的某道題目進行標示，當第i題被選中時，xi＝l；當第i題未被選中時，xi＝0。初始化串群體就是隨機生成含有N個串的群體。在串群體中，串長度都是相同的，群體大小根據需要給出，一般取個體編碼長度數的一個線性倍數。

2）適應度函數的確定。在遺傳算法中，適應度函數的大小區分群體中個體的優劣。通常，適應度函數是通過目標函數轉化而來，其值越大個體越好。通過對公式（1）的分析，適應度函數定義為：

其中對于函數t(x)，當x＞0時，函數值為x；當x≤0時，函數值為0。

3）遺傳操作。選擇：常用的選擇算法為按比例的適應度分配，主要包括繁殖池選擇、輪盤賭選擇等方法。本文采用的選擇算法是輪盤賭算法。交換：交換又叫基因重組，對于不同的編碼方式，交換算子是不同的。本文采用的是二進制編碼的單點式交換算子，即在兩個父代個體上隨即產生一個交換點，再間接交換兩個父代個體的對應片段，從而得到兩個子代個體。變異：變異是遺傳算法中保持物種種群多樣性的重要途徑。在二進制編碼中就是將隨機選擇出來的基因座上的基因值由1變0，由0變1。

4 結束語

本文以項目反應理論為理論基礎，使試題本身的參數與考生樣本無關，測試更加真實，評價更加合理。將遺傳算法應用于在線考試系統，實現試題庫的自動組卷，有效地提高組卷的質量和速度。

[1]余嘉元.教育和心理測量[M].南京:江蘇教育出版社,1987

[2]Holland J. Adaptation in Natural and Artificial Systems[M].Ann Arbor: University of Michigan Press,1975

[3]張文修,梁怡.遺傳算法的數學基礎[M].西安:西安交通大學出版社,2000

[4]董敏,霍劍青,王曉蒲.基于IRT智能組卷的模型管理系統[J].中國科學技術大學學報,2004,10(5):612-617