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

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

[中圖分類號]G434 [文獻(xiàn)標(biāo)識碼]A [文章編號]1008-7656（2019）02-0024-03

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

一、遺傳算法

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

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

（二）計算個體適應(yīng)度：對種群中的每個個體進(jìn)行評價，計算個體的優(yōu)劣程度。

（三）選擇：根據(jù)個體適應(yīng)度從種群中選擇個體生成新種群。

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

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

（六）結(jié)束：通過不斷進(jìn)行選擇、交叉、變異操作達(dá)到截止條件后，從種群中選擇最優(yōu)個體即作為問題最優(yōu)解。

二、組卷原理

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

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

三、遺傳算法組卷實現(xiàn)

（一）適應(yīng)度函數(shù)設(shè)計

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

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

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

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

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

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

（二）數(shù)據(jù)結(jié)構(gòu)設(shè)計

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

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

（三）算法結(jié)構(gòu)

1.種群初始化

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

2.選擇

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

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

3.交叉

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

4.變異

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

5.結(jié)束

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

四、總結(jié)

文章結(jié)合廣西遠(yuǎn)程開放教育在線考試系統(tǒng)開發(fā)工作，重點(diǎn)研究針對開放教育特點(diǎn)，采用遺傳算法實現(xiàn)系統(tǒng)組卷功能的原理及算法過程。系統(tǒng)測試結(jié)果表明，通過使用遺傳算法對開放教育在線考試進(jìn)行組卷，能夠便捷、快速、隨機(jī)且較為科學(xué)地實現(xiàn)考點(diǎn)考試組卷。

[參考文獻(xiàn)]

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

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

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

[4]韓蕾. 基于遺傳算法的自動組卷系統(tǒng)的研究與實現(xiàn)[D].青島：中國海洋大學(xué)，2010.

[5]王軍偉.基于遺傳算法的組卷系統(tǒng)的研究與應(yīng)用[D].南昌：南昌大學(xué)，2010.

[6]黃國政.基于遺傳算法的組卷系統(tǒng)的設(shè)計與實現(xiàn)[D].南京：南京理工大學(xué)，2008.

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

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

[責(zé)任編輯 韋書令]