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

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

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

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

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

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

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

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

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

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

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

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

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

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

題型ai2表示試題的題型（判斷題、單選題、多選題、填空題、問答題），用戶可指定各類題型的分?jǐn)?shù)。，其中當(dāng)試題i為第j種題型時(shí)，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ù)總分。

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

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

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

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

2.1量子粒子群算法

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

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

2.2遺傳算法

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

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

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

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

2.3算法描述

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

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

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

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

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

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

7）按種群的進(jìn)化方程生成新的粒子；

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

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

3　實(shí)驗(yàn)結(jié)果與分析

本文針對(duì)《WEB技術(shù)》課程試題庫進(jìn)行了實(shí)驗(yàn)分析，題庫中有判斷題300道，選擇題400道，填空題200道題，編程題100道，試題共分為5個(gè)章節(jié)，測(cè)試等級(jí)分為初、中、高3個(gè)等級(jí)。組卷約束條件設(shè)置為總分：100分；測(cè)試等級(jí)分?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種算法來解組卷問題，從而比較這些算法在求解組卷問題時(shí)的性能。結(jié)合算法和組卷的效率綜合考慮，并經(jīng)多次測(cè)試，交叉概率為0.8，變異概率為0.2；QPSO算法的學(xué)習(xí)率為C1= C2=0.2，慣性權(quán)重從0.9到0.5線性減少，最大迭代次數(shù)為600，每種組卷模型進(jìn)行100次組卷實(shí)驗(yàn)，對(duì)這100次實(shí)驗(yàn)結(jié)果求平均，實(shí)驗(yàn)的結(jié)果如表1所示。

表1　4種算法實(shí)驗(yàn)結(jié)果對(duì)比

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

4　結(jié)論

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

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

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

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

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

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

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

［7］武仁杰.蟻群算法在自動(dòng)組卷建模中的應(yīng)用研究［J］.計(jì)算機(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ù)測(cè)模型［J］.農(nóng)業(yè)工程學(xué)報(bào)，2010，26（2）：88－93.

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

［11］許永達(dá)．基于改進(jìn)遺傳算法的智能組卷研究［J］．計(jì)算機(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稿件編號(hào)：201507164

2010年云南省高等學(xué)校教學(xué)改革研究項(xiàng)目（201010）；云南農(nóng)業(yè)大學(xué)2013年校級(jí)教學(xué)改革立項(xiàng)項(xiàng)目（ZNJG201306）

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