基于遺傳算法的開放教育在線考試系統組卷實現

[摘 要]文章利用遺傳算法，實現開放教育在線考試系統組卷，教師只需設置部分常規的試卷題型、題量、總分等約束條件，其它如試卷難易度、章節覆蓋率、試題曝光度等約束條件由系統自動生成，實現自動化、智能化組卷。

[關鍵詞]開放教育;在線考試;遺傳算法;組卷

[中圖分類號]G434 [文獻標識碼]A [文章編號]1008-7656（2019）02-0024-03

由于開放教育在職成人學生存在分布分散、工學矛盾等特點，全部課程都集中在期末統一時間進行紙質考試，容易造成考試安排時間長、學生參考成本高、缺考率高、考務管理難度大等問題。為此，國家開放大學及各省級電大都在探索開展在線考試改革工作，通過采用網絡在線考試，讓基層考點能靈活組織課程考試，使學生隨時隨地考試，把考試融入到平時學習中，充分調動學生參與學習的積極性。對于開放教育在線考試而言，如何設計組卷策略是關鍵之一，要考慮開放教育多層級管理模式及基層考點數量多、技術力量相對薄弱的特點，盡量減少人工設置組卷參數，使組卷方式自動化、智能化，組卷生成的試卷具有隨機性、科學性和合理性。

一、遺傳算法

遺傳算法（Genetic Algorithm）是一種模擬自然界生物進化規律的優勝劣汰規則演化而來的隨機搜索算法，它模擬生物界從一個隨機初始種群開始，通過對種群中個體不斷進行選擇、交叉、變異等操作，使種群中的優秀個體經過進化后保留下來，淘汰劣質的個體，通過不斷的進化得到越來越優秀的種群，其在解決多種約束條件下的最優解這類問題上具有優秀的表現，算法主要步驟如下。

（一）初始化：設置問題編碼方式，生成初始種群。

（二）計算個體適應度：對種群中的每個個體進行評價，計算個體的優劣程度。

（三）選擇：根據個體適應度從種群中選擇個體生成新種群。

（四）交叉：對種群中的個體進行叉交配對生成新種群。

（五）變異：對種群中個體的染色體進行變異生成新的種群。

（六）結束：通過不斷進行選擇、交叉、變異操作達到截止條件后，從種群中選擇最優個體即作為問題最優解。

二、組卷原理

組卷是根據用戶給定的約束條件（試卷總分、難度系數、考試時長、考試章節、題型、題量、曝光度等），從試題庫中依據一定的策略（算法）選取與約束條件相匹配的試題組成試卷的過程。試題庫中的約束條件試題通常包括：題號、題型、所屬知識點、難度、區分度、題干、操作說明、作答時間、分數、曝光次數、上次使用時間等特征參數。

利用遺傳算法組卷，首先將組卷過程中涉及的試卷庫、試卷、試題、試題特征參數等相關概念映射為遺傳算法中的種群、個體、染色體、基因等相關概念，其對應關系為：種群—試卷庫，個體—試卷，染色體—試題，基因—試題特征參數。然后根據組卷約束條件建立遺傳算法組卷數學模型，對組卷問題“解”（試卷）的染色體（試題）進行編碼，確定數學模型的數據結構。最后通過對試卷庫（種群）中的試卷（個體）不斷執行選擇、交叉、變異等遺傳操作，當遺傳操作達到設定的條件后，選擇試卷庫（種群）中最優的試卷（個體）完成遺傳算法組卷操作。

三、遺傳算法組卷實現

（一）適應度函數設計

雖然組卷涉及的約束條件較多，有總分、總時長、題型、題量、題目分值、難度系數、知識點覆蓋率、曝光度等，但在本系統的開發中，為保證每科目試卷規格的統一，試卷的題型、題目分值、總分數、總時長等常規約束條件由教師在組卷時統一設置，因此算法需處理的約束條件僅包括試卷難度、知識點覆蓋率和曝光度。

其中N表示試卷預期難度與實際難度的偏差值，NP表示試卷預期難度，取值范圍為[0，1]，取值越大，試卷預期難度越大，k表示試卷題量，ni表示第i題的難度，ni取值范圍為[0，1]，ti表示第i題的分數，Z表示試卷總分，可推算出N的取值范圍為[0，1]，取值越小，試卷難度越接近預期難度，試卷質量越好。

其中P表示試卷曝光度，即試卷中出現已曝光的試題分數占試卷總分的比例，且該值與試題曝光次數相關，k表示試卷題量，pi表示第i題是否曝光，取值為0或1，0表示該題還未被使用過，1表示該題已被其它試卷使用過，ti表示第i題的分數，Z表示試卷總分，spi表示第i題的曝光次數，m表示題庫總題量，當題庫中無試題曝光時，P=0，可推算出P的取值范圍為[0，1]， 取值越小，試卷曝光度越低，試卷質量越好。

其中F表示題庫中各章節題量在題庫所占比例與所生成的試卷中對應章節題量在試卷中所占比例的偏差之和，k表示題庫章節數，tki表示題庫中第i章題量，TK表示題庫總題量，sji表示試卷中第i章題量，SJ表示試卷總題量，可推算出F的取值范圍為[0，2]，取值越小，試卷章節題量與題庫章節題量越對應，試卷質量越好。

4.對于遺傳算法適應度函數來說，取值必須為非負，且取值越大越好，綜合考慮式1、2、3取值范圍，本系統試卷適應度函數設計為：

當N、P、F值越小時，S值越大，表示該試卷質量越好，其繁殖能力越強，有更大的幾率參與下一代遺傳。

（二）數據結構設計

遺傳算法通過不斷迭代計算求解最優解，雖然它具有良好的全局尋優和收斂速度快等特點，但也應結合實際應用及程序語言，做好編碼方案和數據結構設計，以便提高算法執行速度。本系統采用vbscript作為程序語言，試題存儲在數據庫中，為了避免算法迭代過程中頻繁讀取數據庫影響速度，對染色體采用字符串編碼方式，將需要參與遺傳計算的試題特征參數全部以基因形式存儲在染色體編碼中，即每道試題編碼如下：試題編號-分數-難度-曝光次數-章節號，并利用二維數組存儲種群，如式（5）所示。

二維數組S中每一行即表示一套試卷，dij表示第i套試卷第j道試題的編碼（0≤i

（三）算法結構

1.種群初始化

設置初始種群規模大小為m，本系統m取值為50。設試卷共有k種題型，每種題型題目數量為Tk，每種題型每題分數為Sk，則試卷總題量為∑ki =1Tk，試卷總分為∑ki =1Sk，定義二維數組S[m，n+1]。從數據庫中根據試卷題型及題型題量隨機選取m套試卷的試題信息（試題編號-分數-難度-曝光次數-章節號）存入二維數組S中，利用公式（4），計算每套試卷適應度值，存入二維數組S最后一列。

2.選擇

采用輪盤賭選擇法，將種群中質量較好的試卷以較大的概率選擇出來遺傳至下一代，其原理為：利用種群中試卷的適應度值來劃分輪盤區域，適應度越大，所占輪盤的區域就越大，被選取的概率就越大。設第i套試卷被選取的概率為Pi，則

每次從種群中選取試卷時，先隨機生成一個在區間[0，1]之間的數R，若∑ki=0 Pi≥R（k<m），則第k套試卷被選取，重復該方法選取m套試卷存放在新數組St[m，n+1]中。

3.交叉

因試卷由多種題型組成，本系統采用按題型分段單點交叉法，即對試卷每種題型都進行交叉操作，每次采用隨機法從數組St [m，n+1]隨機選取兩套試卷進行交叉，生成的下一代試卷存放回原數組S[m，n+1]中。同時為使部分試卷保留原始基因遺傳到下一代，本系統設置交叉概率Pc=0.75，交換前先隨機生成一個在區間[0，1]之間的數R，如R≤Pc，則對選取的試卷進行交叉，否則不交叉，選取的兩套試卷原樣遺傳至下一代，對于執行了交叉的試卷，需重新計算試卷適應度值。交叉后，如試卷中存在重復的題目，則應將其替換為未重復的題目。

4.變異

變異屬于小概率事件，本系統取變異概率Pm=0.08，依次選取數組S[m，n+1]的每套試卷，先隨機生成一個在區間[0，1]之間的數R，如R≤Pm，則對該套試卷進行變異操作，隨機生成一個小于試卷總題量的正整數作為需變異題目序號，將該題目替換成其它題型相同且不與當前試卷題目重復的題目。

5.結束

遺傳算法通過不斷迭代運行公式，使其解盡可能接近最優解，同時也要考慮算法運行時間，并不是迭代次數越多越好，本系統設置為300，同時設置最優試卷期望適應度值為3.8，在迭代過程中，滿足任一條件即中止迭代，種群中適應度值最高的試卷即作為成功組卷的試卷。

四、總結

文章結合廣西遠程開放教育在線考試系統開發工作，重點研究針對開放教育特點，采用遺傳算法實現系統組卷功能的原理及算法過程。系統測試結果表明，通過使用遺傳算法對開放教育在線考試進行組卷，能夠便捷、快速、隨機且較為科學地實現考點考試組卷。

[參考文獻]

[1]實例講解遺傳算法——基于遺傳算法的自動組卷系統[EB/OL]. https：//www.Cnblogs.com/artwl/archive/2011/05/19/2051556.html，2011.

[2]余勝泉，姚顧波，何克抗.通用試題庫組卷策略算法[M/CD].1999.

[3]胡木林. 基于遺傳算法的在線考試系統組卷設計[J].中國教育技術裝備，2018（12）.

[4]韓蕾. 基于遺傳算法的自動組卷系統的研究與實現[D].青島：中國海洋大學，2010.

[5]王軍偉.基于遺傳算法的組卷系統的研究與應用[D].南昌：南昌大學，2010.

[6]黃國政.基于遺傳算法的組卷系統的設計與實現[D].南京：南京理工大學，2008.

[7]靳國興，文漢云.試題庫中自動組卷算法的設計[J].長江大學學報（自然科學版），2008（4）.

[作者簡介]鄧明學（1981-），男，江西宜春人，廣西大學計算機與電子信息學院在讀工程碩士，廣西廣播電視大學教務處副處長，工程師，研究方向：計算機網絡與并行分布計算技術、遠程教育管理。

[責任編輯 韋書令]