基于遺傳算法的開(kāi)放教育在線考試系統(tǒng)組卷實(shí)現(xiàn)

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

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

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

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

一、遺傳算法

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

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

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

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

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

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

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

二、組卷原理

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

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

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

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

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

其中N表示試卷預(yù)期難度與實(shí)際難度的偏差值，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表示該題還未被使用過(guò)，1表示該題已被其它試卷使用過(guò)，ti表示第i題的分?jǐn)?shù)，Z表示試卷總分，spi表示第i題的曝光次數(shù)，m表示題庫(kù)總題量，當(dāng)題庫(kù)中無(wú)試題曝光時(shí)，P=0，可推算出P的取值范圍為[0，1]， 取值越小，試卷曝光度越低，試卷質(zhì)量越好。

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

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

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

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

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

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

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

1.種群初始化

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

2.選擇

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

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

3.交叉

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

4.變異

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

5.結(jié)束

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

四、總結(jié)

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

[參考文獻(xiàn)]

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

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

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

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

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

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

[7]靳國(guó)興，文漢云.試題庫(kù)中自動(dòng)組卷算法的設(shè)計(jì)[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版），2008（4）.

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

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