基于遺傳算法的智能組卷系統(tǒng)的研究與實(shí)現(xiàn)

趙博，寧慧，張汝波

1. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

2. 大連民族大學(xué) 機(jī)電工程學(xué)院，遼寧 大連 116600

隨著網(wǎng)絡(luò)的普及和信息技術(shù)的發(fā)展，利用計(jì)算機(jī)和網(wǎng)絡(luò)進(jìn)行在線學(xué)習(xí)和考試已經(jīng)成為一種趨勢(shì)。為了讓學(xué)生能夠及時(shí)檢驗(yàn)自己的學(xué)習(xí)情況，在線考試系統(tǒng)應(yīng)運(yùn)而生。在在線考試系統(tǒng)的研究與實(shí)現(xiàn)中，如何能實(shí)現(xiàn)達(dá)到用戶滿意的組卷功能一直是研究的重點(diǎn)。

在傳統(tǒng)的組卷系統(tǒng)中，大多采用的是由教師人工組卷或者使用簡(jiǎn)單的隨機(jī)法或回溯法進(jìn)行組卷[1]。人工組卷不僅增加了教師的工作負(fù)擔(dān)，而且容易使組成的試卷主觀性太強(qiáng)，無(wú)法客觀考察學(xué)生對(duì)知識(shí)的掌握情況。而簡(jiǎn)單的隨機(jī)組卷法和回溯法又具有隨機(jī)性太強(qiáng)的缺點(diǎn)，難以保證生成的試卷符合教師的期望。因此，本文提出采用遺傳算法來(lái)實(shí)現(xiàn)組卷系統(tǒng)。遺傳算法是一種全局優(yōu)化搜索算法，具有自適應(yīng)程度高、全局優(yōu)化能力強(qiáng)等優(yōu)點(diǎn)，適用于組卷系統(tǒng)的實(shí)現(xiàn)[2]。

1 遺傳算法

1.1 算法概述

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

1.2 算法執(zhí)行過(guò)程

1)初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器和最大進(jìn)化代數(shù)，隨機(jī)生成若干個(gè)體作為初代種群。

2)計(jì)算適應(yīng)度：計(jì)算種群中每個(gè)個(gè)體適應(yīng)度。

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

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

5)變異：在種群中選若干個(gè)體，為每個(gè)體選擇變異點(diǎn)位并改變?cè)擖c(diǎn)位的基因。

6)重復(fù)執(zhí)行步驟2)～5)，直到適應(yīng)度達(dá)到期望值或進(jìn)化代數(shù)達(dá)到最大值。

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

本系統(tǒng)采用B/S 架構(gòu)，教師只需要在網(wǎng)頁(yè)上輸入組卷的要求，如題目數(shù)量、分值，試卷難度，知識(shí)點(diǎn)覆蓋數(shù)等，系統(tǒng)調(diào)用組卷算法并即刻返回組卷結(jié)果。教師可以對(duì)所組試卷進(jìn)行查看檢驗(yàn)，通過(guò)實(shí)驗(yàn)驗(yàn)證，本系統(tǒng)所組試卷達(dá)到了要求，能很好地滿足課程考核的需求。

2.1 獲得初始種群

利用遺傳算法實(shí)現(xiàn)組卷系統(tǒng)時(shí)，首先要建立試卷和試題等實(shí)體與遺傳算法模型的映射關(guān)系。本系統(tǒng)將試題映射為個(gè)體上的基因，將試題組成的試卷映射為個(gè)體，并將一定數(shù)量的試卷組成的集合映射為種群[5]。

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

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

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

2.2 計(jì)算適應(yīng)度

在遺傳算法中，通常使用適應(yīng)度來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣程度和對(duì)環(huán)境的適應(yīng)程度。適應(yīng)度的值則取決于具體的適應(yīng)度函數(shù)。因此，設(shè)計(jì)一個(gè)好的適應(yīng)度函數(shù)對(duì)于評(píng)價(jià)個(gè)體的優(yōu)劣程度十分關(guān)鍵[6]。

在設(shè)計(jì)組卷系統(tǒng)的適應(yīng)度函數(shù)時(shí)，需要同時(shí)考慮多個(gè)指標(biāo)對(duì)試卷的影響，這樣才能全面地評(píng)價(jià)試卷的質(zhì)量。為了使得適應(yīng)度函數(shù)能夠全面評(píng)價(jià)試卷的難度、知識(shí)點(diǎn)覆蓋率和區(qū)分度等指標(biāo)。本系統(tǒng)的適應(yīng)度函數(shù)設(shè)計(jì)如下：

設(shè)一套試卷預(yù)期的難度系數(shù)為n0，而試卷的實(shí)際難度為n。 試卷難度n計(jì)算方式如下

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

試卷預(yù)期的考察的知識(shí)點(diǎn)數(shù)為N0，而實(shí)際考察的知識(shí)點(diǎn)數(shù)為N。由于直接計(jì)算試卷的區(qū)分度較困難，因此本系統(tǒng)使用試卷中各題目難度的方差近似代替區(qū)分度，這樣可以保證取得的試卷既有簡(jiǎn)單題，也有中等題和難題，不會(huì)出現(xiàn)所有題目難度接近而無(wú)法區(qū)分學(xué)生水平的問(wèn)題。假設(shè)試卷預(yù)期的區(qū)分度為s0，而試卷的實(shí)際區(qū)分度為s。那么適應(yīng)度函數(shù)如下

式中k1、k2、k3分別是難度、知識(shí)點(diǎn)覆蓋數(shù)、區(qū)分度這3 個(gè)指標(biāo)在評(píng)價(jià)適應(yīng)度時(shí)所占的權(quán)重，用戶可根據(jù)自己的需求設(shè)置這3 個(gè)參數(shù)，但要保證這3 個(gè)參數(shù)的和是1。

2.3 設(shè)計(jì)選擇算子

當(dāng)某一代種群中沒(méi)有滿足適應(yīng)度要求的個(gè)體時(shí)，就需要從這一代種群中選擇適應(yīng)度高的個(gè)體，使其通過(guò)交叉和變異產(chǎn)生新一代種群。選擇算子就是選擇過(guò)程中使用的算法。

在選擇過(guò)程中，應(yīng)當(dāng)遵循的原則是優(yōu)先選擇適應(yīng)度高的個(gè)體?；谶@一原則，有2 種常用的選擇算法：直接選擇法和輪盤賭選擇法。直接選擇法是將個(gè)體按照適應(yīng)度降序排序，直接選擇前面的若干個(gè)體；而輪盤賭算法是一種概率算法，采用輪盤賭算法，每一個(gè)個(gè)體都有概率被選到，被選到的概率和他的適應(yīng)度成正比，這樣，適應(yīng)度越高的個(gè)體被選到的概率越大。

本系統(tǒng)選用的是輪盤賭算法[7]。假設(shè)種群共有n個(gè)個(gè)體，第i個(gè)個(gè)體的適應(yīng)度為Ai，則第i個(gè)個(gè)體被選到的概率為

2.4 設(shè)計(jì)交叉算子

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

在這個(gè)過(guò)程中，選擇個(gè)體和選擇交叉點(diǎn)位通常采用隨機(jī)選擇的方法。設(shè)計(jì)交叉算子時(shí)，確定交叉點(diǎn)位的數(shù)量是一個(gè)關(guān)鍵的問(wèn)題。如果采用單點(diǎn)交叉，則算法執(zhí)行速度較快，但是得到的后代和上一代區(qū)別不大；如果采用多點(diǎn)交叉則正好相反，選擇的點(diǎn)位越多，得到的后代和上一代區(qū)別越大，但同時(shí)執(zhí)行算法需要的時(shí)間也越長(zhǎng)[9]。本研究通過(guò)多次的實(shí)驗(yàn)驗(yàn)證，交叉點(diǎn)位的數(shù)量保持在3 個(gè)效果最好。

2.5 設(shè)計(jì)變異算子

在實(shí)際的遺傳過(guò)程中，變異發(fā)生的概率較小。因此本系統(tǒng)僅考慮在種群的每個(gè)個(gè)體上隨機(jī)選擇一個(gè)變異位置，而后從試題庫(kù)中隨機(jī)選擇一道相同題型的題目來(lái)替換該位置的題目[10]。

2.6 系統(tǒng)實(shí)現(xiàn)

本系統(tǒng)采用Java 語(yǔ)言開發(fā)，通過(guò)Servlet 處理用戶請(qǐng)求并返回響應(yīng)，通過(guò)JSP 向用戶顯示結(jié)果，試題及其他數(shù)據(jù)保存在Mysql 數(shù)據(jù)庫(kù)中，題庫(kù)如圖1 所示。

圖1 試題庫(kù)信息界面

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

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

圖2 發(fā)布考試界面

圖3 組卷結(jié)果界面

圖4 題目列表界面

3 結(jié)論

1)實(shí)驗(yàn)結(jié)果表明，該算法的成功率和組卷效率較高，組成的試卷在難度、知識(shí)點(diǎn)覆蓋范圍等指標(biāo)上能夠達(dá)到用戶的要求，試卷的質(zhì)量能夠得到保證。

2)本文提出了一種高效的組卷策略，能夠有效克服傳統(tǒng)組卷算法存在的弊端，對(duì)于組卷算法的研究和智能組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)具有一定的參考價(jià)值。

本項(xiàng)目可以進(jìn)一步擴(kuò)展研究，通過(guò)增加試卷評(píng)價(jià)指標(biāo)，進(jìn)一步優(yōu)化適應(yīng)度函數(shù)，使組成的試卷令用戶更加滿意。