QPSO和GA相融合的智能組卷模型研究

邱靖,郭睿南,浦濤文,于學媛,張海濤

（云南農業大學 教務處，云南 昆明 650201）

QPSO和GA相融合的智能組卷模型研究

邱靖,郭睿南,浦濤文,于學媛,張海濤

（云南農業大學 教務處，云南 昆明 650201）

為簡化模型結構，改善算法全局搜索性能和組卷模型成功率，本研究提出利用QPSO中的全局和局部最優位置優化遺傳算法中交叉、變異算子，粒子群編碼采用實數編碼，交叉、變異操作均在功能塊內部進行，目標函數增加了權重系數判定是否更新粒子群，以此建立了智能組卷模型，并進行了相關實驗分析。實驗結果表明：改進的模型與其他三種組卷模型相比，該模型運行效率、全局搜尋性能、組卷成功率都有較大的提高，說明該組卷模型更穩定有效。

QPSO；遺傳算法；權重系數；智能組卷；模型研究

隨著信息技術、網絡技術、計算機輔助教學和人工智能的發展，網絡考試越來越受到廣泛地應用，因此建立一個好的自動組卷系統尤為重要，而組卷模型的好壞直接關系到對學生所學知識的評估以及能否達到預期效果的關鍵因素。由此可見，組卷算法的研究成為智能組卷系統的核心。

組卷實際上是在一定約束條件下的多目標優化求最優解問題，保證自動生成的試卷能滿足用戶的組卷指標，具有隨機性、客觀性、合理性及科學性等特點。目前，組卷方法包括：隨機選取法、回溯法、遺傳算法、PSO算法、QPSO算法及蟻群算法等［1-7］。這些組卷算法在一定時期內對網絡組卷起到了積極作用，但隨機選取法結構簡單，組卷的成功率低，很難滿足用戶的需求；回溯法其程序結構較復雜，但缺乏隨機性，組卷速度較低；遺傳算法雖具有全局尋優性、算法簡單、并行性及通用性等特點，但因其算法本身有許多參數需要調整，搜索不夠精確；粒子群算法簡單易實現，參數不需大量調整，但因其算法本身易陷入局部極值，致使組卷結果不是全局最優。針對這些不足，本研究提出將量子粒子群算法（QPSO）和遺傳算法相融合運用到智能組卷模型，并分析其組卷效率。

1　組卷數學模型

智能組卷即在試題庫系統中，自動生成滿足用戶需求的試卷。題庫中每道試題包括許多屬性（分數、題型、難度系數、知識點、測試層次等），當用戶抽取一份試卷時，設定總分值、題型數量、知識點、難度系數及題型分值。用戶抽取n道題時，就決定了一n×m的參數矩陣A。

矩陣A每一列代表試題的一個屬性，m為試題屬性個數，每一行代表一道試題的屬性值，n為所生成試卷的總題數。組卷的約束條件為：

分數 ai1表示試題的分值，M為用戶給定的試卷總分ai1=M。

題型ai2表示試題的題型（判斷題、單選題、多選題、填空題、問答題），用戶可指定各類題型的分數。，其中當試題i為第j種題型時，cj=1，否則為cj=0，Sj為第j種題型的總分。

難度系數ai3表示難度系數（0-1），用戶規定試題難度系數范圍。，其中當試題i的難度系數屬于用戶規定的難度系數cj=1，否則cj=0，Mj為用戶規定的難度系數總分。

知識點ai4表示試題對應的知識點，用戶可根據考察需要來確定各章節的分值。，其中當試題i為第j個知識點時，cj=1，否則cj=0，zj為第j個知識點對應的總分。

測試層次ai5表示測試層次，測試層次分為初級、中級及高級。用戶可以指定各類層次所占分數。，其中當試題i為第j種層次時，cj=1，否則為cj=0，Nj為第j個測試層次級別對應的總分。

時間ai6表示整套試卷完成的預計時間，

2　QPSO算法與遺傳算法融合在智能組卷系統的應用

2.1量子粒子群算法

Sun［8］等人于2004年提出了量子粒子群算法（QPSO）。該算法可以在整個解空間進行搜索，具有較強的全局搜索性能。QPSO算法主要由以下3個進化方程［9-10］完成粒子群的更新迭代：

其中α1，α2，w為 （0,1）間的隨機數，β為收縮擴張系數，β的選擇和控制決定整個算法的收斂效率，N為粒子群數目，pi為第i次迭代的局部最優位置，pg為粒子群最優位置,mbest為粒子群的全局最優解平均位置。

2.2遺傳算法

遺傳算法（GA）［11］是通過選擇、交叉、變異等操作，利用生物進化論思想，采用優勝劣汰理論，使種群進化逐步接近目標函數。本研究交叉及變異操作都采用在功能塊內部進行。即在同題型內部進行交叉及變異操作，保證了組卷時各目標參數的正確匹配，簡化了優化目標，同時能更好地滿足用戶的需求。

遺傳算法的優劣，主要是粒子編碼方式及適應度函數如何確定。本研究采用整型編碼，而不是二進制編碼（1和0），粒子長度由試卷題目數決定，粒子編碼由所選取試題在試題庫中的題號決定。這種編碼方式大大縮短了粒子長度，也不存在頻繁編碼和解碼變化而導致優化搜索空間急劇增大，從而降低算法搜索性能。適應度函數引入了組卷約束條件對應的權重系數，如公式（5）。

Wi為第i個約束條件的權重系數，滿足。適應度函數值越小，說明實際組卷與用戶需求的試卷指標相異度最小，因此目標函數表示為：

在算法中設定一個標志f來判定種群中是否有粒子仍在迭代，是否能搜尋到更優解。如f=1，則種群仍在進化，否則，種群已經找到最優解，程序結束。

2.3算法描述

1）初始化粒子群，按組卷目標中各種題型的題量、知識點、難度系數、測試層次、分值等要求，提取N套試題（種群為N），并初始化所有粒子的局部最優位置pi和全局最優位置pg；

2）根據迭代次數動態調整收縮擴張系數，使組卷尋優空間由全局調整到局部；

3）選擇，計算粒子群所有粒子的適應度值，從當前種群中選取適應度函數值最小兩個個體的直接進入下一代，而最大的兩個個體淘汰，其余的個體進行交叉變異操作，并判斷pi和pg是否更新；

4）交叉，根據交叉概率pc的值判定粒子是否進行交叉操作，交叉時采用功能塊內部（同類題型）交叉，從種群中隨機選取兩個粒子，將該兩個粒子中第i個功能塊的所有試題進行交叉操作；

5）計算粒子群全局最優解平均位置mbest。

6）變異 根據變異概率pm的值判定是否對mbest進行變異操作，變異操作同樣采用在功能塊內部進行變異；

7）按種群的進化方程生成新的粒子；

8）判斷是否滿足算法的終止條件，若滿足則轉到下一步，否則轉到步驟2）；

9）輸出全局最優解（最佳組卷），算法結束。

3　實驗結果與分析

本文針對《WEB技術》課程試題庫進行了實驗分析，題庫中有判斷題300道，選擇題400道，填空題200道題，編程題100道，試題共分為5個章節，測試等級分為初、中、高3個等級。組卷約束條件設置為總分：100分；測試等級分數比例為初：20分，中：60分，高：20分；難度系數分布比例：0.0-0.3占20分，0.3-0.7占60分，0.7-1占20分；章節分數所占分值從第一章到第五章分別為：20分、20分、20分、20分、20分；題型數量為判斷題15題、選擇題20題、填空題10題、編程題5題。

分別用GA、PSO、QPSO以及GA和QPSO融合的算法等4種算法來解組卷問題，從而比較這些算法在求解組卷問題時的性能。結合算法和組卷的效率綜合考慮，并經多次測試，交叉概率為0.8，變異概率為0.2；QPSO算法的學習率為C1= C2=0.2，慣性權重從0.9到0.5線性減少，最大迭代次數為600，每種組卷模型進行100次組卷實驗，對這100次實驗結果求平均，實驗的結果如表1所示。

表1　4種算法實驗結果對比

實驗中，通過計算4種算法的平均進化次數、最大完成時間、最小完成時間、平均完成時間及組卷成功率來驗證GA和QPSO融合算法的有效性，組卷成功率為算法進行100次實驗得到的平均值。由表1可知，本文研究的算法無論從運行次數，還是最大、最小、平均完成時間均比其他3種算法小，但組卷成功率卻比其他3種算法高。說明采用QPSA算法優化BP算法中的粒子群，使搜尋最優解空間的范圍更大，提高了組卷算法的收斂速度，簡化了智能組卷模型，克服了搜索空間易陷入局部極值，且搜索精度得到了提高。

4　結論

本研究針對目前組卷算法的不足，提出了將遺傳算法和量子粒子群算法融合運用到智能組卷中，研究表明該方法相比遺傳算法、粒子群算法等計算簡單，收斂速度快，相比于量子粒子群算法有利于更快地收斂到全局最優解，且組卷的成功率也遠高于其他算法。從組卷的結果來看，該算法組卷的穩定性好，可信度高，證明了該算法的有效性。

［1］劉貝貝,肖明,馬曉敏.基于推理的組卷數學建模及其應用［J］.計算機工程，2010,36（4）：195-197.

［2］周偉.隨機抽題任意組卷智能閱卷的無紙化考試方法研究［J］.軟件,2014,35（3）:11-16,19.

［3］冶劍鋒,張學良.基于Stirling數的多條件約束組卷算法的研究與實現［J］.數理醫藥學雜志，2013,26（3）：264-266.

［4］張敏輝.基于改進遺傳算法智能組卷的研究［J］.計算機與數字工程，2012,40（3）：18-20.

［5］李俊,張建國.多目標粒子群算法在智能組卷中的應用研究［J］.河南大學學報：自然科學版，2013,43（6）：697-702.

［6］李欣然,樊永生.改進量子行為粒子群算法智能組卷策略研究［J］.計算機科學,2013,40（4）:236-239.

［7］武仁杰.蟻群算法在自動組卷建模中的應用研究［J］.計算機仿真,2011,28（8）:380-384.

［8］SUN J，XU W，FENG B．A global search strategy of quantum-behaved particle swarm optimization［C］//Cybernetics and Intelligent Systems，2004 IEEE Conference on．IEEE，2004：111-116．

［9］邱靖，吳瑞武，黃雁鴻，等.混沌理論與BP網絡融合的稻瘟病預測模型［J］.農業工程學報，2010，26（2）：88－93.

［10］邱靖,楊毅,秦西云,等.QPSO優化BP網絡預測煙蚜發生量［J］.云南農業大學學報（自然科學）,2013,28（4）:561-564.

［11］許永達．基于改進遺傳算法的智能組卷研究［J］．計算機與數字工程，2013,41（2）：176-178，207.

Design of intelligent test paper constructing model based on QPSO and GA

QIU Jing,GUO Rui-nan,PU Tao-wen,YU Xue-yuan,ZHANG Hai-tao
（Teaching Affairs Office，Yunnan Agriculture University，Kunming 650201,China）

In order to simplify the model structure,improve the algorithm global search performance and the success rate of test paper model,this study proposes to use the global QPSO and local optimal location optimization GA crossover,mutation operator,the real number coding using particle swarm coding,crossover,mutation operation is performed in the inner functional block,the objective function increases the weight coefficient of determination whether to update the particle swarm,establishes the intelligent test paper model,and relevant experimental analysis.The experimental results show that:compared with other three kinds of test paper model,the model efficiency,the global search performance,and the success rate was higher,indicating that the test paper model is more stable and effective.

Quantum-behaved Particle Swarm Optimization（QPSO）；Genetic Algorithm（GA）；weight coefficient；intelligentpaper constructing；model research

TN01

A

1674－6236（2016）13-023-03

2015-07-24稿件編號：201507164

2010年云南省高等學校教學改革研究項目（201010）；云南農業大學2013年校級教學改革立項項目（ZNJG201306）

邱 靖（1979—），女，四川達州人，碩士，講師。研究方向：人工智能。