SA-PSO算法在智能組卷中的應用研究

盛 魁，馬 健，董 輝

(亳州職業技術學院信息工程系，安徽亳州 236800)

?

SA-PSO算法在智能組卷中的應用研究

盛 魁，馬 健，董 輝

(亳州職業技術學院信息工程系，安徽亳州 236800)

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

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

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

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

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

1 智能組卷問題的數學模型

1.1 約束條件

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

(1)

其中，矩陣S中aij表示第i道題的第j個屬性，ai1為第i道試題的編號，即試題的唯一標識；ai2為第i道試題的分數；ai3為第i道試題的難度值；ai4為第i道試題對應的知識點編號；ai5為第i道試題對應的認知分類；ai6為第i道試題題型；ai7為第i道試題對應的答題時間；ai8為第i道試題的區分度。目標矩陣滿足的約束條件如下：

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

1.2 目標函數

組卷的目標就是從試題庫中搜索到滿足各項約束分布的試題集，智能組卷本質上是一種多目標尋優問題[7]。本文采用權重系數法對智能組卷建模，組卷問題的目標函數為：

(2)

其中，i為第i個約束的權重；ei為第i約束因素對組卷目標的誤差，且目標函數越小越好。

2 模擬退火粒子群優化算法

2.1 粒子群優化算法

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

(3)

(4)

2.2 模擬退火算法(SA)

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

(5)

其中，T表示控制參數，xi表示當前解，xj表示新產生的解，f(x)表示問題目標函數。

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

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

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

3 實驗結果與分析

3.1 組卷要求和參數設置

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

表1 題型——分數分布

表2 知識點——分數分布

表3 認知層次——分數分布

表4 試卷的各種約束權重

3.2 組卷效率比較

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

圖1 組卷效率對比圖

3.3 組卷成功率比較

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

表5 組卷成功率對比表

3.4 組卷滿足度平均值比較

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

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

4 結語

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

[1]梁海麗.基于通用試題庫的智能組卷系統的開發與實現[D].石家莊:河北科技大學,2011.

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

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

[4]龔完全.基于最小回溯代價的智能組卷算法[D].長沙:湖南大學,2005.

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

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

[7]李欣然,樊永生.改進量子行為粒子群算法智能組卷策略研究[J].計算機科學,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]王夢蘭.智能優化算法的比較與改進[J].中國水運,2012(12):48-49.

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

[12]張志強,徐斌,何勇靈,等.基于AHP評價方法的發動機性能評價[J].兵工學報,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年安徽省高等學校省級自然科學研究重點基金項目“物聯網技術在中藥材種植環境信息采集中的研究與應用”(KJ2015A417)；2015年安徽省高校振興計劃優秀青年人才支持計劃(gxyqZD2016529)；2015年安徽省科技攻關計劃項目“基于OTO模式的中藥材誠信平臺研究”(1501zc03031)。

盛 魁(1981- )，男，副教授，碩士，從事農業物聯網、數據挖掘和電子商務研究。

TP311

A

2095-7602(2016)10-0042-05