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

邱靖,郭睿南,浦濤文,于學(xué)媛,張海濤

（云南農(nóng)業(yè)大學(xué) 教務(wù)處，云南 昆明 650201）

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

邱靖,郭睿南,浦濤文,于學(xué)媛,張海濤

（云南農(nóng)業(yè)大學(xué) 教務(wù)處，云南 昆明 650201）

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

QPSO；遺傳算法；權(quán)重系數(shù)；智能組卷；模型研究

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

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

1　組卷數(shù)學(xué)模型

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

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

分?jǐn)?shù) ai1表示試題的分值，M為用戶給定的試卷總分ai1=M。

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

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

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

測試層次ai5表示測試層次，測試層次分為初級、中級及高級。用戶可以指定各類層次所占分?jǐn)?shù)。，其中當(dāng)試題i為第j種層次時，cj=1，否則為cj=0，Nj為第j個測試層次級別對應(yīng)的總分。

時間ai6表示整套試卷完成的預(yù)計時間，

2　QPSO算法與遺傳算法融合在智能組卷系統(tǒng)的應(yīng)用

2.1量子粒子群算法

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

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

2.2遺傳算法

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

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

Wi為第i個約束條件的權(quán)重系數(shù)，滿足。適應(yīng)度函數(shù)值越小，說明實際組卷與用戶需求的試卷指標(biāo)相異度最小，因此目標(biāo)函數(shù)表示為：

在算法中設(shè)定一個標(biāo)志f來判定種群中是否有粒子仍在迭代，是否能搜尋到更優(yōu)解。如f=1，則種群仍在進化，否則，種群已經(jīng)找到最優(yōu)解，程序結(jié)束。

2.3算法描述

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

2）根據(jù)迭代次數(shù)動態(tài)調(diào)整收縮擴張系數(shù)，使組卷尋優(yōu)空間由全局調(diào)整到局部；

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

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

5）計算粒子群全局最優(yōu)解平均位置mbest。

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

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

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

9）輸出全局最優(yōu)解（最佳組卷），算法結(jié)束。

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

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

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

表1　4種算法實驗結(jié)果對比

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

4　結(jié)論

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

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

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

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

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

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

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

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

［8］SUN J，XU W，F(xiàn)ENG 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網(wǎng)絡(luò)融合的稻瘟病預(yù)測模型［J］.農(nóng)業(yè)工程學(xué)報，2010，26（2）：88－93.

［10］邱靖,楊毅,秦西云,等.QPSO優(yōu)化BP網(wǎng)絡(luò)預(yù)測煙蚜發(fā)生量［J］.云南農(nóng)業(yè)大學(xué)學(xué)報（自然科學(xué)）,2013,28（4）:561-564.

［11］許永達．基于改進遺傳算法的智能組卷研究［J］．計算機與數(shù)字工程，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年云南省高等學(xué)校教學(xué)改革研究項目（201010）；云南農(nóng)業(yè)大學(xué)2013年校級教學(xué)改革立項項目（ZNJG201306）

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