盛 魁，馬 健，董 輝

(亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽亳州 236800)

?

SA-PSO算法在智能組卷中的應(yīng)用研究

盛 魁，馬 健，董 輝

(亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽亳州 236800)

通用、健壯、高效的組卷算法是實現(xiàn)考試智能化、規(guī)范化、科學(xué)化的重要保障。本文在分析智能組卷數(shù)學(xué)模型及各種組卷算法的基礎(chǔ)上，針對目前組卷算法存在組卷時間長、組卷效率低等缺陷，提出了一種基于模擬退火粒子群優(yōu)化算法(SA-PSO)。將其應(yīng)用于智能組卷實驗，并與RANDOM和PSO算法作比較。實驗結(jié)果表明，SA-PSO算法使得組卷效率、組卷成功率和組卷滿足度等方面均有顯著的提高，并且保證了組卷的質(zhì)量。

模擬退火法；粒子群；智能組卷

“互聯(lián)網(wǎng)+”教育開啟了教育新模式，推動了教育信息化和智能化的快速發(fā)展，智能化考試系統(tǒng)因其客觀、便捷、準(zhǔn)確、安全等特點在各種考試中應(yīng)用。而在智能化考試系統(tǒng)設(shè)計中，組卷算法是保證組卷質(zhì)量的關(guān)鍵技術(shù)，對整個考試系統(tǒng)起著決定性作用。因此，快捷、高效、科學(xué)的組卷算法日益成為教育領(lǐng)域和人工智能領(lǐng)域共同關(guān)注的熱點問題[1]。

智能組卷是按照課程標(biāo)準(zhǔn)和課程教學(xué)大綱的要求，運用人工智能技術(shù)，由計算機來設(shè)計試卷內(nèi)容，并使生成試卷內(nèi)容符合設(shè)定的各項指標(biāo)。目前廣泛被采用的組卷算法有隨機抽取組卷算法、回溯試探組卷算法、遺傳算法和定性映射法四類[2]。其中，隨機抽取法[3]邏輯結(jié)構(gòu)較簡單，易于實現(xiàn)單道試題的快速抽取，但存在很大的不確定性和隨意性，無法滿足題庫多變的要求，不具有智能性?；厮菰囂椒╗4]在狀態(tài)類型和試卷總題量少的試題庫系統(tǒng)中組卷效果比較理想，但程序結(jié)構(gòu)較復(fù)雜，選取試題隨機性差，重題率高，組卷時間長。遺傳算法[5]解決了抽題的隨機性問題，滿足智能組卷系統(tǒng)對于大型試題庫與復(fù)雜結(jié)構(gòu)組卷的要求，但自動出題的收斂速度比較慢且算法操作比較復(fù)雜。定性映射方法[6]能夠合理分配不同難度的試題，提高了組卷的效率和成功率，但其結(jié)構(gòu)程序較復(fù)雜，數(shù)學(xué)基礎(chǔ)要求較高，實現(xiàn)起來難度大。

本文在分析組卷數(shù)學(xué)模型、模擬退火算法和粒子群算法的基礎(chǔ)上，將模擬退火算法的降溫思想和Metropolis準(zhǔn)則引入粒子群算法中,提出了一種基于模擬退火和粒子群算法的優(yōu)化算法(SA-PSO)，用該算法處理智能組卷問題，并通過實例進(jìn)行驗證。

1 智能組卷問題的數(shù)學(xué)模型

1.1 約束條件

在智能組卷時需要考慮試卷的約束條件，常見的主要約束有試卷總分、試卷總時間、試卷難度、題型分布、知識點分布等。假設(shè)一份試卷所包含的試題數(shù)為m，每道試題題型有n個約束條件，一份試卷可用一個m×n的矩陣來表示：

(1)

其中，矩陣S中aij表示第i道題的第j個屬性，ai1為第i道試題的編號，即試題的唯一標(biāo)識；ai2為第i道試題的分?jǐn)?shù)；ai3為第i道試題的難度值；ai4為第i道試題對應(yīng)的知識點編號；ai5為第i道試題對應(yīng)的認(rèn)知分類；ai6為第i道試題題型；ai7為第i道試題對應(yīng)的答題時間；ai8為第i道試題的區(qū)分度。目標(biāo)矩陣滿足的約束條件如下：

除上述約束條件外，還可以指定試卷的期望值、使用頻度和使用信度等約束條件，在實際組卷過程中,約束條件過多會增加組卷的難度，影響組卷的成功率。

1.2 目標(biāo)函數(shù)

組卷的目標(biāo)就是從試題庫中搜索到滿足各項約束分布的試題集，智能組卷本質(zhì)上是一種多目標(biāo)尋優(yōu)問題[7]。本文采用權(quán)重系數(shù)法對智能組卷建模，組卷問題的目標(biāo)函數(shù)為：

(2)

其中，i為第i個約束的權(quán)重；ei為第i約束因素對組卷目標(biāo)的誤差，且目標(biāo)函數(shù)越小越好。

2 模擬退火粒子群優(yōu)化算法

2.1 粒子群優(yōu)化算法

粒子群算法(Particle Swarm Optimization，PSO)是一種在模擬鳥類捕食行為的基礎(chǔ)上發(fā)展起來的啟發(fā)式全局優(yōu)化技術(shù)[8-9]。設(shè)在D維空間中，有N個粒子，粒子i的位置Xi=(xi1,xi2，…,xiD)；粒子i速度Vi=(vi1,vi2，…,viD)；粒子i的局部極值向量為pbest=(pi1,pi2，…,piD)；群種的全局極值向量為pbest=(pg1,pg2，…,pgD)。粒子的速度和位置依據(jù)如下方程變化，

(3)

(4)

2.2 模擬退火算法(SA)

模擬退火算法(Simulated Annealing，SA)，其基本思想就是用一個物理系統(tǒng)的退火過程來模擬優(yōu)化問題的尋優(yōu)過程，是一種解決組合優(yōu)化問題的有效近似算法[10-11]，適合于大規(guī)模組合優(yōu)化問題求解。接受最優(yōu)解的概率可由Metropolis準(zhǔn)則來確定，

(5)

其中，T表示控制參數(shù)，xi表示當(dāng)前解，xj表示新產(chǎn)生的解，f(x)表示問題目標(biāo)函數(shù)。

2.3 模擬退火粒子群算法(SA-PSO)

模擬退火粒子群算法(SA-PSO)，是PSO算法中每個粒子在更新速度和位置的過程中引入SA思想而形成的一種新的優(yōu)化算法。SA-PSO算法先利用PSO的快速搜索能力得到一個較優(yōu)的群體，然后利用SA的突跳能力實現(xiàn)全局尋優(yōu)。SA-PSO算法優(yōu)化實現(xiàn)步驟如下：

Step1 初始化參數(shù)：學(xué)習(xí)因子c1，c2,慣性權(quán)重，退火起始溫度T和終止后溫度T0，迭代次數(shù)k，退火速度a。搜索空間的下限Xmin和上限Xmax，粒子運動時速度的最小值Vmin與最大值Vmax；

3 實驗結(jié)果與分析

3.1 組卷要求和參數(shù)設(shè)置

為了驗證SA-PSO算法的可行性和有效性，以及確定部分算法參數(shù)對算法的影響，以數(shù)據(jù)結(jié)構(gòu)課程為例，進(jìn)行組卷實驗分析。試題庫題型表中題量分布為：291道選擇題、238道填空題、241道算法分析題、281道算法設(shè)計題。模擬退火中退火起始溫度T=8000，終止溫度T0=0.03，退火速度α=0.9。最大迭代次數(shù)為10000，群體粒子數(shù)為50。組卷過程中的要求如下：總分為100，估計用時為120分鐘，試題難度為0.4900；試卷區(qū)分度為0.4050。用戶設(shè)置參數(shù)的各種分布如表1至表3所示，根據(jù)AHP方法[12]計算智能組卷各目標(biāo)權(quán)重，結(jié)果如表4所示。

表1 題型——分?jǐn)?shù)分布

表2 知識點——分?jǐn)?shù)分布

表3 認(rèn)知層次——分?jǐn)?shù)分布

表4 試卷的各種約束權(quán)重

3.2 組卷效率比較

為了檢驗SA-PSO算法組卷效果，在實驗環(huán)境相同的情況下，將隨機抽取法(RANDOM)和粒子群算法(PSO)作對比，組卷花費時間如圖1所示?？梢钥闯?，RANDOM算法的組卷速度較慢，PSO算法的速度也相對較慢，而SA-PSO算法進(jìn)行全局搜索和局部尋優(yōu)的平衡搜索，不斷趨于最優(yōu)解，收斂速度快，提高了組卷效率。

圖1 組卷效率對比圖

3.3 組卷成功率比較

表5表示3種算法組卷成功率的對比結(jié)果。SA-PSO算法組卷的成功率高于RANDOM和PSO算法，這說明運用SA-PSO算法進(jìn)行組卷不但成功率高，而且速度快，具有較好的實用性，為智能組卷提供了一種新的方法。

表5 組卷成功率對比表

3.4 組卷滿足度平均值比較

不同組卷算法滿足度平均值對比結(jié)果如表6所示。運用SA-PSO算法進(jìn)行組卷試卷難度滿足度、區(qū)分度滿足度和知識點滿足度的平均值均高于RANDOM和PSO組卷的滿足度平均值。這說明SA-PSO算法是一種有效、實用、科學(xué)的組卷算法。

表6 組卷滿足度平均值對比表

4 結(jié)語

智能考試是教育信息化的一種重要體現(xiàn)，而組卷算法是提高組卷效率、組卷成功率的基本保障。本文將模擬退火思想融入粒子化算法，提出一種基于SA-PSO優(yōu)化算法。SA-PSO算法不但能以較大的概率挑出局部極值點而且收斂速度快，實現(xiàn)了SA算法和POS算法的優(yōu)勢互補。針對智能組卷的具體應(yīng)用表明，SA-PSO算法在組卷時不但提高了組卷的效率和成功率，而且滿足了組卷的要求，具有很強的實用性，使得生成試卷更加科學(xué)、規(guī)范。

[1]梁海麗.基于通用試題庫的智能組卷系統(tǒng)的開發(fā)與實現(xiàn)[D].石家莊:河北科技大學(xué),2011.

[2]夏愛月.基于遺傳算法的自動組卷系統(tǒng)研究與實現(xiàn)[J].電腦編程技巧與維護(hù),2009(2):94-95.

[3]張振國,楊柯.新型組卷策略的研究與實現(xiàn)[J].計算機工程與設(shè)計,2008(20):5348-5353.

[4]龔?fù)耆?基于最小回溯代價的智能組卷算法[D].長沙:湖南大學(xué),2005.

[5]周艷聰,劉艷柳.遺傳模擬退火智能組卷策略研究[J].計算機工程與設(shè)計,2011(3):1066-1069.

[6]邵紅青,馮嘉禮,甘棠儀,等.一種基于定性映射的自動組卷算法[J].計算機輔助工程,2005(2):26-29.

[7]李欣然,樊永生.改進(jìn)量子行為粒子群算法智能組卷策略研究[J].計算機科學(xué),2013(4):263-239.

[8]Parsopoulos K E,Vrahatis M N.Recent approach to global optimization problem through particle swarm optimization[J].Natural Computing,2002(2):235-256.

[9]Kennedy J,Eberhart R C.Particle swarm optimization[C].IEEE Intrmationa1Conference on Neural Networks Perth,Australia,1995.

[10]王夢蘭.智能優(yōu)化算法的比較與改進(jìn)[J].中國水運,2012(12):48-49.

[11]刁鳴,鄒麗.模擬退火遺傳禁忌搜索的多用戶檢測算法[J].哈爾濱工程大學(xué)學(xué)報,2014(3):373-377.

[12]張志強,徐斌,何勇靈,等.基于AHP評價方法的發(fā)動機性能評價[J].兵工學(xué)報,2008(5):625-628.

Research on Application of SA-PSO Algorithm in Intelligent Test Paper

SHENG Kui,MA Jian,DONG Hui

(Department of Information Engineering,Bozhou Vocational and Technical College,Bozhou Anhui 236800,China)

The general,robust and efficient test paper generation algorithm is an important guarantee for the intelligent,standardized and scientific test.In the analysis of intelligent composing mathematical model and algorithm of generating test paper based,according to the generating set of algorithms exist long time of the test paper,test paper efficiency and low defects,puts forward a method based on simulated annealing particle swarm optimization algorithm (SA-PSO).Its application in intelligent test paper composition experiment,and random and PSO algorithm as the comparison experiment results show that,SA-PSO algorithm in efficiency of composing,the success rate of test and the test paper meet degree are increased significantly,and to ensure the quality of the test paper.

simulated annealing;particle swarm;intelligent test paper

2016-03-28

2015年安徽省高等學(xué)校省級自然科學(xué)研究重點基金項目“物聯(lián)網(wǎng)技術(shù)在中藥材種植環(huán)境信息采集中的研究與應(yīng)用”(KJ2015A417)；2015年安徽省高校振興計劃優(yōu)秀青年人才支持計劃(gxyqZD2016529)；2015年安徽省科技攻關(guān)計劃項目“基于OTO模式的中藥材誠信平臺研究”(1501zc03031)。

盛 魁(1981- )，男，副教授，碩士，從事農(nóng)業(yè)物聯(lián)網(wǎng)、數(shù)據(jù)挖掘和電子商務(wù)研究。

TP311

A

2095-7602(2016)10-0042-05