基于遺傳算法的智能組卷系統的研究與實現

趙博，寧慧，張汝波

1. 哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001

2. 大連民族大學 機電工程學院，遼寧 大連 116600

隨著網絡的普及和信息技術的發展，利用計算機和網絡進行在線學習和考試已經成為一種趨勢。為了讓學生能夠及時檢驗自己的學習情況，在線考試系統應運而生。在在線考試系統的研究與實現中，如何能實現達到用戶滿意的組卷功能一直是研究的重點。

在傳統的組卷系統中，大多采用的是由教師人工組卷或者使用簡單的隨機法或回溯法進行組卷[1]。人工組卷不僅增加了教師的工作負擔，而且容易使組成的試卷主觀性太強，無法客觀考察學生對知識的掌握情況。而簡單的隨機組卷法和回溯法又具有隨機性太強的缺點，難以保證生成的試卷符合教師的期望。因此，本文提出采用遺傳算法來實現組卷系統。遺傳算法是一種全局優化搜索算法，具有自適應程度高、全局優化能力強等優點，適用于組卷系統的實現[2]。

1 遺傳算法

1.1 算法概述

遺傳算法(genetic algorithm，GA)最早是由美國的John holland 于20 世紀70 年代提出，該算法是根據大自然中生物體進化規律而設計提出的，是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法[3]。該算法通過數學的方式，用計算機仿真運算，將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時，相對一些常規的優化算法，通常能夠較快地獲得較好的優化結果。遺傳算法已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生智能領域[4]。

1.2 算法執行過程

1)初始化：設置進化代數計數器和最大進化代數，隨機生成若干個體作為初代種群。

2)計算適應度：計算種群中每個個體適應度。

3)選擇：從種群中以一定算法選擇若干個體。

4)交叉：將選擇得到的個體在一點或多點上交叉，得到新的種群。

5)變異：在種群中選若干個體，為每個體選擇變異點位并改變該點位的基因。

6)重復執行步驟2)～5)，直到適應度達到期望值或進化代數達到最大值。

2 系統設計與實現

本系統采用B/S 架構，教師只需要在網頁上輸入組卷的要求，如題目數量、分值，試卷難度，知識點覆蓋數等，系統調用組卷算法并即刻返回組卷結果。教師可以對所組試卷進行查看檢驗，通過實驗驗證，本系統所組試卷達到了要求，能很好地滿足課程考核的需求。

2.1 獲得初始種群

利用遺傳算法實現組卷系統時，首先要建立試卷和試題等實體與遺傳算法模型的映射關系。本系統將試題映射為個體上的基因，將試題組成的試卷映射為個體，并將一定數量的試卷組成的集合映射為種群[5]。

在設計獲得初始種群的方法時，首先要在方法的參數列表提供以下幾個參數：題目數量、題庫中所有試題的集合以及種群包含的個體數。

在生成初始種群的每個個體時，為了避免選到重復的試題，需要首先初始化一個集合A，用于保存該個體中的試題。每當從試題庫中選到一道題時，就判斷該試題是否已在集合A中。如果存在，說明該試題已被選擇，需要舍棄該試題并重新選擇；如果不存在，則將試題加入試卷并添加到集合A中。當題目數量達到要求時，一個個體就生成了。重復執行上述過程，直到種群中的個體數量達到要求。

此外，在設計生成初始種群的方法時，需要考慮種群包含的個體數這個參數。這個參數的大小對算法的性能有直接影響。如果設置得太小，則很難從種群中找到合適的個體；如果設置得太大，則在初始化、交叉和變異等過程會消耗太多時間。實驗表明，通常將這個值設置在20 左右較為合適。

2.2 計算適應度

在遺傳算法中，通常使用適應度來評價個體的優劣程度和對環境的適應程度。適應度的值則取決于具體的適應度函數。因此，設計一個好的適應度函數對于評價個體的優劣程度十分關鍵[6]。

在設計組卷系統的適應度函數時，需要同時考慮多個指標對試卷的影響，這樣才能全面地評價試卷的質量。為了使得適應度函數能夠全面評價試卷的難度、知識點覆蓋率和區分度等指標。本系統的適應度函數設計如下：

設一套試卷預期的難度系數為n0，而試卷的實際難度為n。 試卷難度n計算方式如下

式中：r是試卷的平均得分；R是試卷總分。因此n越大則試卷難度越大。

試卷預期的考察的知識點數為N0，而實際考察的知識點數為N。由于直接計算試卷的區分度較困難，因此本系統使用試卷中各題目難度的方差近似代替區分度，這樣可以保證取得的試卷既有簡單題，也有中等題和難題，不會出現所有題目難度接近而無法區分學生水平的問題。假設試卷預期的區分度為s0，而試卷的實際區分度為s。那么適應度函數如下

式中k1、k2、k3分別是難度、知識點覆蓋數、區分度這3 個指標在評價適應度時所占的權重，用戶可根據自己的需求設置這3 個參數，但要保證這3 個參數的和是1。

2.3 設計選擇算子

當某一代種群中沒有滿足適應度要求的個體時，就需要從這一代種群中選擇適應度高的個體，使其通過交叉和變異產生新一代種群。選擇算子就是選擇過程中使用的算法。

在選擇過程中，應當遵循的原則是優先選擇適應度高的個體。基于這一原則，有2 種常用的選擇算法：直接選擇法和輪盤賭選擇法。直接選擇法是將個體按照適應度降序排序，直接選擇前面的若干個體；而輪盤賭算法是一種概率算法，采用輪盤賭算法，每一個個體都有概率被選到，被選到的概率和他的適應度成正比，這樣，適應度越高的個體被選到的概率越大。

本系統選用的是輪盤賭算法[7]。假設種群共有n個個體，第i個個體的適應度為Ai，則第i個個體被選到的概率為

2.4 設計交叉算子

在遺傳算法中，交叉是產生后代的重要步驟。在交叉的過程，首先需要從選擇算法得到的個體中以某種方式選擇2 個個體，然后再選擇一個或多個交叉點位，接著就可以將2 個個體在該點位的試題進行互換，這樣就得到了2 個新的個體。重復執行上面過程若干次，使得到的新個體數等于上一代種群的個體數[8]。

在這個過程中，選擇個體和選擇交叉點位通常采用隨機選擇的方法。設計交叉算子時，確定交叉點位的數量是一個關鍵的問題。如果采用單點交叉，則算法執行速度較快，但是得到的后代和上一代區別不大；如果采用多點交叉則正好相反，選擇的點位越多，得到的后代和上一代區別越大，但同時執行算法需要的時間也越長[9]。本研究通過多次的實驗驗證，交叉點位的數量保持在3 個效果最好。

2.5 設計變異算子

在實際的遺傳過程中，變異發生的概率較小。因此本系統僅考慮在種群的每個個體上隨機選擇一個變異位置，而后從試題庫中隨機選擇一道相同題型的題目來替換該位置的題目[10]。

2.6 系統實現

本系統采用Java 語言開發，通過Servlet 處理用戶請求并返回響應，通過JSP 向用戶顯示結果，試題及其他數據保存在Mysql 數據庫中，題庫如圖1 所示。

圖1 試題庫信息界面

教師在登錄系統后，可以在系統上發布考試。發布考試時教師需要輸入與考試和試卷相關的信息，如考試名稱、考試時長、題目數量、每題分值、預期難度和預期知識點考察數等，輸入完成后點擊生成試卷，即可將考試發布到系統中。本次實驗中，教師將期望試卷難度設置為0.8，期望知識點考察數設置為50。發布考試界面如圖2 所示。

教師點擊發布考試之后，頁面將會跳轉到組卷結果頁，教師在此頁面可以查看組卷的結果，包括試題難度、知識點覆蓋數等信息和題目列表，查看組卷結果界面如圖3 和圖4 所示。根據圖3的組卷結果，試卷的實際難度為0.788，這與用戶輸入的期望難度0.8 接近，試卷考察的知識點數為56 個，多于用戶輸入的預期知識點數50 個。因此，可以認為該組卷算法生成的試卷能夠滿足用戶的要求，試卷的質量能夠得到保證。

圖2 發布考試界面

圖3 組卷結果界面

圖4 題目列表界面

3 結論

1)實驗結果表明，該算法的成功率和組卷效率較高，組成的試卷在難度、知識點覆蓋范圍等指標上能夠達到用戶的要求，試卷的質量能夠得到保證。

2)本文提出了一種高效的組卷策略，能夠有效克服傳統組卷算法存在的弊端，對于組卷算法的研究和智能組卷系統的設計與實現具有一定的參考價值。

本項目可以進一步擴展研究，通過增加試卷評價指標，進一步優化適應度函數，使組成的試卷令用戶更加滿意。