基于蟻群算法的智能測(cè)評(píng)系統(tǒng)開(kāi)發(fā)

文/蘇楠

1 國(guó)內(nèi)外智能測(cè)評(píng)系統(tǒng)的研究分析

國(guó)外研究現(xiàn)狀：西方教育對(duì)考試環(huán)節(jié)十分重視，測(cè)評(píng)系統(tǒng)的開(kāi)發(fā)起源于國(guó)外，在90年代初，就制定了相關(guān)的測(cè)評(píng)規(guī)則與辦法，在測(cè)評(píng)系統(tǒng)開(kāi)發(fā)領(lǐng)域中處于領(lǐng)先地位。在應(yīng)用領(lǐng)域，國(guó)外的很多部門(mén)與機(jī)構(gòu)都對(duì)測(cè)評(píng)系統(tǒng)給予關(guān)注，采用了在線測(cè)評(píng)的這種測(cè)試方式。被人們所熟知的有出國(guó)留學(xué)必須進(jìn)行的語(yǔ)言水平測(cè)試（例如雅思）就是通過(guò)在線測(cè)試的方式進(jìn)行的，計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)架構(gòu)師和思科認(rèn)證也是通過(guò)設(shè)置相應(yīng)考點(diǎn)，進(jìn)行在線測(cè)評(píng)完成的。這些都對(duì)測(cè)評(píng)系統(tǒng)的發(fā)展起到了促進(jìn)作用。在智能算法的測(cè)評(píng)系統(tǒng)開(kāi)發(fā)過(guò)程中，國(guó)外也只經(jīng)歷了不到二十年的發(fā)展時(shí)間，還存在著相應(yīng)的發(fā)展空間。

國(guó)內(nèi)發(fā)展現(xiàn)狀：國(guó)內(nèi)的在線測(cè)評(píng)系統(tǒng)，主要應(yīng)用于教育行業(yè)，尤其是在高等院校之中。高等院校受信息化技術(shù)影響，打造自身的網(wǎng)絡(luò)環(huán)境，并且實(shí)現(xiàn)了網(wǎng)絡(luò)平臺(tái)的教務(wù)工作管理和網(wǎng)絡(luò)平臺(tái)測(cè)試系統(tǒng)。高校每年都要進(jìn)行多門(mén)課程的考核，在線測(cè)評(píng)系統(tǒng)能夠滿足大多數(shù)課程的考核需求，也能節(jié)約資源開(kāi)銷(xiāo)。所以受到廣泛應(yīng)用。但是在其它行業(yè)中，測(cè)評(píng)系統(tǒng)應(yīng)用很少，在招聘中在素質(zhì)選拔技能選拔中，通過(guò)測(cè)評(píng)系統(tǒng)來(lái)完成的，更是寥寥無(wú)幾。從應(yīng)用領(lǐng)域來(lái)說(shuō)有待加強(qiáng)。從實(shí)現(xiàn)水平來(lái)講，很多高校的測(cè)評(píng)系統(tǒng)只能滿足簡(jiǎn)單的客觀化試題考試，沒(méi)有實(shí)現(xiàn)硬件擴(kuò)展也很少使用算法來(lái)體現(xiàn)自動(dòng)組卷的價(jià)值。

本文嘗試使用的蟻群算法和遺傳算法融合的方式，通過(guò)對(duì)試卷難度的控制，實(shí)現(xiàn)試卷的價(jià)值。同時(shí)利用建立區(qū)分度公式，來(lái)嘗試實(shí)現(xiàn)優(yōu)秀以及中等和偏弱學(xué)生的學(xué)習(xí)情況區(qū)分。而兩種算法融合方法的目的，是利用兩種算法各自的優(yōu)點(diǎn)，提升組卷速度提升成功率。因?yàn)橄伻核惴ㄔ诔跗诘穆窂竭x擇中，缺乏有效的選擇方式，選擇速度慢，（后文詳細(xì)介紹）而利用遺傳算法可以提升路徑選擇速度。通過(guò)兩種算法的融合，提升組卷質(zhì)量，實(shí)現(xiàn)組卷目標(biāo)。

2 蟻群算法與遺傳算法融合思想闡述

2.1 算法在智能測(cè)評(píng)系統(tǒng)中的作用

本文算法在智能測(cè)評(píng)系統(tǒng)中主要針對(duì)試卷的自動(dòng)生成產(chǎn)生作用，從淺入深的作用依次為：第一點(diǎn)，滿足試卷的最基本約束條件，也就是符合針對(duì)試卷而設(shè)計(jì)的總分、試題類(lèi)型、分?jǐn)?shù)數(shù)值、試題數(shù)量等等，最基本的設(shè)置要求。第二點(diǎn)，保證試題的難度覆蓋區(qū)域，使得試題難度更加具有價(jià)值，避免過(guò)于簡(jiǎn)單或者難度過(guò)大的題目集中的出現(xiàn)。第三點(diǎn)，增強(qiáng)試卷的區(qū)分度，在保證題目難度偏移不集中現(xiàn)象出現(xiàn)基礎(chǔ)上，體現(xiàn)試題的區(qū)分度，讓優(yōu)秀、中等、較差的學(xué)生通過(guò)智能測(cè)試，找到差距，教師對(duì)學(xué)生的學(xué)習(xí)狀態(tài)能夠很好的區(qū)分。第四點(diǎn)，保證試卷生成的成功率。

2.2 蟻群算法簡(jiǎn)介

2.2.1 蟻群算法基本思想

蟻群算法思想借鑒于生物學(xué)，人們發(fā)現(xiàn)螞蟻在尋覓食物并搬運(yùn)的過(guò)程中，總能找到相應(yīng)的優(yōu)選路徑，并且很少出現(xiàn)搬運(yùn)擁塞的現(xiàn)象。經(jīng)過(guò)研究發(fā)現(xiàn)，這是螞蟻可以分泌一種信息熵的緣故，這種特定的信息熵，具有特殊的氣味能夠被螞蟻所識(shí)別，同時(shí)這種信息熵會(huì)伴隨時(shí)間進(jìn)行揮發(fā)。

如圖1：起點(diǎn)為A，M,N代表不同選擇的路徑集合，即為選擇M處會(huì)經(jīng)過(guò)的所有路徑和從N處會(huì)經(jīng)過(guò)的所有路徑。設(shè)置時(shí)間t，則M處通過(guò)時(shí)間為t1，N處通過(guò)為t2，我們會(huì)發(fā)現(xiàn)t1，t2中較小者會(huì)逐漸被選中。初始狀態(tài)根據(jù)概率分析，假設(shè)兩邊路徑集合通過(guò)的數(shù)量相同，但經(jīng)過(guò)足夠長(zhǎng)時(shí)間單位tC后，時(shí)間短的路徑集合通過(guò)的螞蟻數(shù)量不斷增多。一方面時(shí)間短，說(shuō)明路徑短，多次循環(huán)通過(guò)的數(shù)量會(huì)形成倍數(shù)量級(jí)。另一方面，通過(guò)的螞蟻數(shù)量多，信息熵分泌多，揮發(fā)時(shí)間短會(huì)造成濃度的提升，從而成為優(yōu)選解。

圖1

2.2.2 蟻群算法優(yōu)缺點(diǎn)

從算法說(shuō)明處可以分析出算法具有以下優(yōu)點(diǎn)：第一點(diǎn)，從計(jì)算機(jī)算法實(shí)現(xiàn)角度來(lái)分析，蟻群算法優(yōu)選解的計(jì)算是一種分布式算法，從前文圖例說(shuō)明原理也可以看出。因此利于大規(guī)模運(yùn)算的實(shí)現(xiàn)。第二點(diǎn)，收斂速度快，正反饋機(jī)制：蟻群算法從信息熵的濃度來(lái)進(jìn)行辨別，濃度高，被選擇概率高，同時(shí)選擇概率高又不斷增強(qiáng)濃度，是一種正向的反饋機(jī)制。正反饋機(jī)制的特點(diǎn)就是收斂速度快。第三點(diǎn)，魯棒性能突出，這在蟻群算法在多個(gè)領(lǐng)域都得到應(yīng)用就可以看出，模型適用性強(qiáng)，便于修改與應(yīng)用。第四點(diǎn)，是以集合形式出現(xiàn)，利于求出優(yōu)選集合，便于實(shí)現(xiàn)全局化算法。

缺點(diǎn)：從算法思想闡述我們也可以看出，算法要嘗試實(shí)現(xiàn)的話，在算法初期，信息熵濃度的積累需要較長(zhǎng)時(shí)間，應(yīng)用于算法中也就是初期的算法搜索時(shí)間長(zhǎng)，算法時(shí)間復(fù)雜度高。同時(shí)也容易出現(xiàn)路徑選擇，問(wèn)題優(yōu)解針對(duì)個(gè)體難以區(qū)分，或者算法收斂過(guò)快，造成算法無(wú)法繼續(xù)。處于停止?fàn)顟B(tài)。

從思想實(shí)例出發(fā)，說(shuō)明可能存在的問(wèn)題，假設(shè)圖1中對(duì)于路徑的選擇，信息熵選擇方法重要權(quán)值為X，新路徑啟發(fā)重要權(quán)值為Y。也就是說(shuō)，當(dāng)路徑選擇或者最優(yōu)解中，X數(shù)值很高，則信息熵濃度為最重要。反之若Y數(shù)值高，則新路徑選擇優(yōu)先。我們考慮臨界狀態(tài)。如果Y數(shù)值高而X數(shù)值是0，那么就代表無(wú)論信息熵濃度多高，某路徑經(jīng)過(guò)多少螞蟻，這個(gè)解都會(huì)被放棄，而去尋求新路徑中，距離最近的解，這就等同于貪婪算法的實(shí)現(xiàn)。反之，如果X數(shù)值高，新路徑Y(jié)數(shù)值為0，那么就是一個(gè)完全的信息熵路徑選擇，高速的正反饋，極快的收斂，容易形成局部的錯(cuò)解，不適用于全局優(yōu)化的求解過(guò)程。

2.3 算法融合的分析

兩種算法進(jìn)行融合的目的明顯，是兩用兩種算法各自的優(yōu)點(diǎn)，實(shí)現(xiàn)降低試卷生成的時(shí)間復(fù)雜度，縮短試卷生成時(shí)間，并提升精度。蟻群算法的缺點(diǎn)是初期的信息熵的搜索時(shí)間長(zhǎng)，而通過(guò)遺傳算法隨機(jī)性，縮短初期的積累時(shí)間，獲得一個(gè)相對(duì)的前期優(yōu)解，再使用蟻群算法，發(fā)揮分布計(jì)算和正反饋機(jī)制的特點(diǎn)提升精度。

兩種算法都具有一定的融合性，那么融合位置的選擇較為重要，根據(jù)算法融合發(fā)揮的作用，可以用以下方法實(shí)現(xiàn)融合位置的計(jì)算。首先具體設(shè)置算法中的迭代次數(shù)臨界值（最大與最?。?，再進(jìn)行子代群體的最小進(jìn)化率的計(jì)算，并設(shè)置最小進(jìn)化率。如果在算法應(yīng)用過(guò)程中，發(fā)現(xiàn)實(shí)際進(jìn)化率大于我們的最小進(jìn)化率設(shè)置數(shù)值，則遺傳算法效率依然為較快，繼續(xù)進(jìn)行迭代計(jì)算，如果出現(xiàn)多次的一直連續(xù)的小于設(shè)置值現(xiàn)象，則遺傳算法作用完成，切入蟻群算法，利用正反饋機(jī)制提升精度，進(jìn)一步進(jìn)行計(jì)算。

3 算法融合智能測(cè)評(píng)系統(tǒng)試卷指標(biāo)

篇幅有限，這里進(jìn)行重要試卷指標(biāo)說(shuō)明，并簡(jiǎn)單介紹算法中的一些計(jì)算模型。

試卷難度指標(biāo)：

從難度指標(biāo)公式不難看出，這是每到試題的難度權(quán)值與分?jǐn)?shù)的乘積，再除以分?jǐn)?shù)和。其中，di為難度，si為分值，最終求得試卷的難度系數(shù)。

試卷區(qū)分度：試卷的區(qū)分度，體現(xiàn)試題的價(jià)值，通過(guò)學(xué)生對(duì)試卷的得分概率來(lái)體現(xiàn)，區(qū)分度用T代表：T=Hp-Lp，也就是高分成績(jī)獲得數(shù)量與低分成績(jī)獲得數(shù)量的得分率差值，一般情況下，區(qū)分度數(shù)值較大代表試卷區(qū)分度高，質(zhì)量佳。

試卷信度：也就是通過(guò)算法生成的試卷的質(zhì)量可信度，這是對(duì)算法生成的試卷能否穩(wěn)定的組卷成功，試卷能夠滿足考試要求，試卷質(zhì)量的一個(gè)總體評(píng)估指標(biāo)：

其中r為所求信度，n是具體的題目數(shù)量，P是該題得分率，s2為得分方差

4 算法融合組卷的算法模型與算法設(shè)計(jì)

4.1 蟻群算法數(shù)學(xué)模型

在蟻群算法模型中，P就是路徑選擇的相對(duì)概率，S就是引入的信息熵。從公式意義看出，S信息熵的數(shù)值決定了選擇新路徑的概率，也就是當(dāng)數(shù)值大的時(shí)刻，那么下一個(gè)路徑被選擇的概率很大，反之，就很小。當(dāng)螞蟻選擇的最優(yōu)路徑趨向相同，同時(shí)信息熵達(dá)到一個(gè)很小的臨界數(shù)值的時(shí)候，也就說(shuō)明了算法完成，解被求出。

4.2 遺傳算法與蟻群算法融合流程描述

初始化過(guò)程：確定試卷的基本約束條件以及簡(jiǎn)單參數(shù)以及試題模型

采用遺傳算法對(duì)試題進(jìn)行第一步優(yōu)解，并不斷是否達(dá)到融合臨界點(diǎn)。（融合臨界點(diǎn)確定方法前文有明確介紹），當(dāng)達(dá)到臨界點(diǎn)的時(shí)候，退出遺傳算法。

采用蟻群算法，并把遺傳算法的初步優(yōu)解應(yīng)用在初始信息分布中，解決初期信息熵搜素時(shí)間長(zhǎng)的問(wèn)題。

采用確定的蟻群算法模型，進(jìn)行相應(yīng)的數(shù)學(xué)運(yùn)算

最終輸出：成功試卷。

4.3 算法設(shè)計(jì)過(guò)程

4.3.1 遺傳算法設(shè)計(jì)

編碼設(shè)計(jì)：采用二進(jìn)制編碼模式，產(chǎn)生編碼矩陣，對(duì)染色體進(jìn)行編碼0代表未曾選中，1代表選中

選擇算子、交叉算子與變異算子：可以說(shuō)這三個(gè)算子的設(shè)計(jì)過(guò)程就是一個(gè)遺傳算法的簡(jiǎn)單過(guò)程。選擇算子的含義就是對(duì)染色體進(jìn)行挑選，選出適合算法的優(yōu)秀個(gè)體。目前流行的算法毫無(wú)疑問(wèn)是輪盤(pán)賭算法。這里不多做說(shuō)明。交叉算子，通過(guò)染色體隨機(jī)交叉的方式，通過(guò)數(shù)學(xué)方法產(chǎn)生下一代的算子，也就是繁衍優(yōu)秀下一代的方式。而算子交叉的方法很多，交叉算子的數(shù)值在0.5左右區(qū)間為適宜。變異算子，顧名思義，有遺傳就有變異，只有變異才可能發(fā)現(xiàn)更多的優(yōu)秀下一代群體。那么針對(duì)二進(jìn)制的染色體編碼方式，通過(guò)某些位置的邏輯反操作，可以實(shí)現(xiàn)變異。

參數(shù)考慮：也就是遺傳算法中各個(gè)參數(shù)的設(shè)置合理性。首先群體的數(shù)量，要根據(jù)題庫(kù)內(nèi)試題數(shù)量而定。迭代次數(shù)要適中，過(guò)大會(huì)產(chǎn)生大量消耗，過(guò)小難以產(chǎn)生真正的初期優(yōu)解。這里可以設(shè)置120次。同時(shí)設(shè)置交叉概率與變異概率。交叉概率建議為0.55。

4.3.2 蟻群算法設(shè)計(jì)

第一步，參數(shù)初始化。

第二步，將螞蟻分配到不同的路徑當(dāng)中，產(chǎn)生列表。

第三步，進(jìn)行螞蟻選擇下一路徑的概率計(jì)算，不同螞蟻對(duì)路徑的選擇不能重復(fù)。

第四步，群體走完路徑后，重新回到起點(diǎn)，通過(guò)蟻群算法數(shù)學(xué)模型進(jìn)行信息熵公式計(jì)算。

第五步，再次進(jìn)行第三步和第四步。

第六步，當(dāng)符合信息熵條件終止條件后，獲得優(yōu)解。