一種改進(jìn)的多目標(biāo)粒子群組卷算法*

馬躍亮，靳志強(qiáng)，孫晨霞

(河北農(nóng)業(yè)大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 保定 071001)

利用計(jì)算機(jī)按照一定的組卷算法從試題庫(kù)抽取試題組成符合要求的試卷，是實(shí)現(xiàn)考試規(guī)范化和科學(xué)化的手段。在各種計(jì)算機(jī)輔助考試系統(tǒng)、試題庫(kù)系統(tǒng)軟件中，自動(dòng)組卷一直是該類系統(tǒng)的一個(gè)難點(diǎn)，其解決方法也一直是算法研究熱點(diǎn)。可以說(shuō)一個(gè)自動(dòng)組卷系統(tǒng)的效率和組卷質(zhì)量主要取決于組卷算法。以往的組卷算法多采用隨機(jī)抽題法、回溯試探法及遺傳算法。

隨機(jī)抽題法根據(jù)狀態(tài)空間的控制指標(biāo)，隨機(jī)抽選一道試題加入試卷中，不斷重復(fù)直到組卷完畢或失敗為止。該算法簡(jiǎn)單，但是當(dāng)題庫(kù)龐大時(shí)，時(shí)間復(fù)雜度大，而且常由于約束條件的局部滿足而導(dǎo)致組卷失敗。回朔試探法是將隨機(jī)選取產(chǎn)生的每一狀態(tài)記錄下來(lái)，搜索失敗時(shí)，釋放上次記錄的狀態(tài)類型，然后再依據(jù)一定的規(guī)律變換一種新的狀態(tài)進(jìn)行試探，通過(guò)不斷地回朔試探直到試題生成完畢或回到出發(fā)點(diǎn)為止。當(dāng)試卷總題量較大時(shí)，時(shí)間和空間復(fù)雜度都很大。可以看出，隨機(jī)抽題法和回溯試探法都具有較大的缺點(diǎn)，而且不具有智能性。

遺傳算法[1](GA)模仿自然界的適者生存法則，根據(jù)遺傳的變異交叉等操作進(jìn)行重復(fù)迭代，直到滿足某些收斂指標(biāo)。GA最初用于函數(shù)優(yōu)化及組合優(yōu)化。現(xiàn)已廣泛用于生產(chǎn)調(diào)度問(wèn)題、圖像處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等領(lǐng)域。其在計(jì)算機(jī)輔助教學(xué)方面的應(yīng)用也是一大亮點(diǎn)，如在組卷應(yīng)用中遠(yuǎn)優(yōu)于以往算法，但也存在粒子速度控制等問(wèn)題。

1 組卷問(wèn)題數(shù)學(xué)模型

1.1 組卷問(wèn)題描述

組卷問(wèn)題即計(jì)算機(jī)根據(jù)要求從題庫(kù)中自動(dòng)抽取符合條件的分?jǐn)?shù)、難度、章節(jié)、知識(shí)點(diǎn)等要求的試題組成試卷，因此，組卷問(wèn)題包括了多個(gè)重要指標(biāo)，如分?jǐn)?shù)、難度、題型、章節(jié)、知識(shí)點(diǎn)等。每道題在錄入時(shí)已經(jīng)被賦予了相應(yīng)的指標(biāo)。在本庫(kù)中，試題分為1、2、3、4四個(gè)難度等級(jí)；試卷難度從難到易分為 A、B、C、D、E五個(gè)等級(jí)，每種級(jí)別的試卷中四種級(jí)別的試題所占比例不同。試題其他屬性，如題型、章節(jié)、知識(shí)點(diǎn)等也都相應(yīng)賦值。

1.2 數(shù)學(xué)模型

本文引用了王一萍[2]選用的關(guān)于粒子群算法設(shè)計(jì)的目標(biāo)函數(shù)數(shù)學(xué)模型：

其他限制函數(shù)如下：

其中 xik表示試題，cik表示知識(shí)點(diǎn)，hik表示知識(shí)點(diǎn)覆蓋率，dik表示難度系數(shù)，D表示目標(biāo)難度系數(shù)，si表示主觀題，ui為主觀題最小比例。

在上面各式中，式(1)為目標(biāo)函數(shù)，式(2)為主觀題比例函數(shù)，式(3)為知識(shí)點(diǎn)覆蓋率函數(shù)，式(4)為題型分布函數(shù)。

2 改進(jìn)的粒子群優(yōu)化算法

2.1 簡(jiǎn)單粒子群優(yōu)化算法

假設(shè)在一個(gè)M維的目標(biāo)搜索空間[3]中有n個(gè)粒子，每個(gè)粒子的位置表示一個(gè)潛在的解。用 xi=(xi1，xi2……xiM)表示第 i個(gè)粒子的位置向量。 用 νi=(νi1，νi2……νiM)表示第i個(gè)粒子飛行的速度向量。將xi帶入適應(yīng)度函數(shù)f(x)就可以計(jì)算出其適應(yīng)值 f(xi)，根據(jù)適應(yīng)值的大小即可衡量 xi的優(yōu)劣。 用 pi=(pi1，pi2……piM)表示第 i個(gè)粒子迄今為止搜索到的最好位置，也稱為個(gè)體極值pbest。用pg=(pg1，pg2……pgM)表示整個(gè)粒子群迄今為止搜索到的最優(yōu)位置，也稱為全局極值gbest。第i個(gè)粒子第m個(gè)分量根據(jù)下面公式來(lái)更新自己的速度和位置：

其中，νim(k)表示第 i個(gè)粒子在第k次迭代中第 d維的速度分量；xim(k)表示第i個(gè)粒子在第k次迭代中第m維的位置分量；c1和 c2為加速度系數(shù)；r1和 r2是介于[0，1]之間的隨機(jī)數(shù)；ω稱為慣性因子；ωνim(k)表示第 i個(gè)粒子在第k次迭代中第m維的慣性速度；pim(k)-xim(k)表示第i個(gè)粒子當(dāng)前位置與自己最好位置之間的距離，作為第k+1次迭代源于第i個(gè)粒子本身的加速度；pgm(k)-xim(k)表示第i個(gè)粒子當(dāng)前位置與群體最佳位置之間的距離，作為第k+1次迭代源于整個(gè)群體的加速度。據(jù)上式知，第i個(gè)粒子在第k+1次迭代中的位置和速度根據(jù)第k次迭代的位置 xi(k)、第k次迭代的速度 νi(k)、個(gè)體極值pbest、全局極值 gbest等生成。

由式(5)可見(jiàn)，粒子的速度進(jìn)化方程由個(gè)體認(rèn)知和社會(huì)信息共享兩部分組成。

式(5)中的第一項(xiàng) νim(k)為粒子更新前的速度，第二項(xiàng)c1r1(pim(k)-xim(k))為粒子本身的個(gè)體認(rèn)知部分；第三項(xiàng)c2r2(pgm(k)-xgm(k))為粒子間的社會(huì)信息共享部分。如果進(jìn)化方程只有個(gè)體認(rèn)知部分，則因粒子間缺少信息交流，得到最優(yōu)解的概率非常小；如果只有社會(huì)信息共享部分，則粒子因無(wú)自身的認(rèn)知能力，雖然收斂速度較快，但粒子速度難以得到更理想的控制。

2.2 改進(jìn)的粒子群算法

在整個(gè)粒子群尋優(yōu)過(guò)程中，粒子飛行速度大小直接影響算法的全局收斂性。飛行速度大，則粒子到達(dá)全局最優(yōu)解所需時(shí)間短，但容易飛越最優(yōu)解；飛行速度小，則粒子到達(dá)全局最優(yōu)解的時(shí)間長(zhǎng)，故必需對(duì)粒子的飛行速度進(jìn)行有效控制，使粒子在先期以較快速度飛行到全局最優(yōu)區(qū)域，進(jìn)而以較小的步長(zhǎng)對(duì)最優(yōu)區(qū)域進(jìn)行局部搜索以獲得高精度解。筆者將粒子群優(yōu)化過(guò)程分為三個(gè)階段。首先利用遺傳算法的交叉操作對(duì)粒子群進(jìn)行前期攪動(dòng)，使得初始種群能夠迅速地均勻遍布整個(gè)搜索空間；然后用變異操作進(jìn)行局部尋優(yōu)的微調(diào)攪動(dòng)，使得種群更快地向目標(biāo)移動(dòng)靠攏；最后利用粒子群優(yōu)化得出結(jié)果。

改進(jìn)粒子群優(yōu)化算法的實(shí)現(xiàn)步驟如下。

(1)隨機(jī)生成初始群體

在粒子群算法中，每個(gè)粒子均表示一個(gè)可行解，以二進(jìn)制編碼形式表示。

在矩陣中，行表示試題，如：a2i為1表示試題 Qi在第2套試卷中被選擇，每行表示一套試卷。每列依次表示題分、題型、章節(jié)、難度系數(shù)。

(2)計(jì)算并評(píng)價(jià)每個(gè)粒子的適應(yīng)值

模型最初目標(biāo)函數(shù)值用來(lái)衡量滿足式(2)～式(4)候選解的質(zhì)量。然而，基于粒子群優(yōu)化算法的粒子可能不滿足其中一個(gè)或多個(gè)限制條件。為解決此問(wèn)題，評(píng)估粒子質(zhì)量時(shí)，如果不滿足某限制條件則要考慮懲罰函數(shù)，懲罰函數(shù)對(duì)應(yīng)各限制條件。

①b罰值是關(guān)于不滿足知識(shí)點(diǎn)限制范圍：

這個(gè)值是彌補(bǔ)所選擇試題知識(shí)點(diǎn)覆蓋率的不足。

②d罰值是違反多試卷同試題數(shù)量的限制：

當(dāng)兩套試卷具有相同的試題數(shù)量超閾值S時(shí)使用。

③函數(shù)J(x)是計(jì)算粒子x適應(yīng)值

J(x)=Z當(dāng)滿足所有限制條件

其中w1、w2和w3是相關(guān)的權(quán)重，同樣粒子x的適應(yīng)值要考慮目標(biāo)值和罰值。根據(jù)組卷的實(shí)際問(wèn)題，適應(yīng)值越小，粒子越好。

(3)個(gè)體極值pbest和全局極值 gbest計(jì)算

使用限制標(biāo)準(zhǔn)確定pbest和gbest的值在原來(lái)的粒子群優(yōu)化算法中，粒子的pbest和gbest最費(fèi)時(shí)間，因此提出限制標(biāo)準(zhǔn)來(lái)加速確定粒子pbest和gbest的進(jìn)行。根據(jù)分析得知，一個(gè)粒子的適應(yīng)值是為了確定粒子pbest和gbest，但不能直接用于粒子速度的更新。因?yàn)閆和J(x)都能單獨(dú)提高作用，可用當(dāng)前pbest的適應(yīng)值作為適應(yīng)值的界限，當(dāng)中間適應(yīng)值超過(guò)此界限時(shí)則終止對(duì)第i個(gè)粒子適應(yīng)值的計(jì)算。將第i個(gè)粒子的當(dāng)前適應(yīng)值與pbest值比較，如果優(yōu)于它原來(lái)的pbest則用這個(gè)適應(yīng)值更新其pbest，這種限制能節(jié)省計(jì)算時(shí)間。

(4)若個(gè)體極值pbest和全局極值 gbest滿足條件或其他終止條件，則退出。

(5)將個(gè)體按照適應(yīng)度排序，取適應(yīng)度較差的50%進(jìn)行交叉或變異操作，遺傳操作計(jì)數(shù)器加1。

為加速粒子群初期的尋優(yōu)速度，在前期加入遺傳算法的交叉和變異操作。將排序后的50%粒子復(fù)制一遍，并與原型隨機(jī)進(jìn)行交叉或變異操作，然后再按適應(yīng)度排序，取適應(yīng)度值前50%放入原種群，保持種群規(guī)模不變。在總循環(huán)次數(shù)的前25%次，交叉率取0.8進(jìn)行交叉操作，使群體迅速均勻地進(jìn)行全局搜索；接下來(lái)的15%次以變異率為0.2進(jìn)行變異操作，使得群體能更加快速地進(jìn)行局部搜索。

①染色體的交叉。采用雙點(diǎn)交叉運(yùn)算[4]，隨機(jī)選取兩個(gè)雙親染色體確定兩個(gè)隨機(jī)交叉點(diǎn)進(jìn)行交叉運(yùn)算得出新個(gè)體，如：

設(shè)每?jī)晌粸橐粋€(gè)交叉單位，隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)4和7，則交叉之后變成：

②染色體的變異。隨機(jī)產(chǎn)生若干個(gè)變異位置，然后在相應(yīng)的位置隨機(jī)選取一道試題。如變異前的染色體為：1010 1101 0001 1110，隨機(jī)產(chǎn)生了3個(gè)變異位置，分別為：(2，5，8)， 則變異后的染色體為：1011 1101 0101 1100。

(6)若個(gè)體極值pbest和全局極值 gbest滿足條件或其他終止條件，則退出。

(7)生成 νim(k+1)和 xim(k+1)構(gòu)成下一代群體，循環(huán)次數(shù)加 1。

每個(gè)粒子的速度和位置的更新要遵循粒子群的離散方法，如通過(guò)轉(zhuǎn)換函數(shù) S(·)和粒子中取值為 1的位表示概率的速度變化，尺度為[0.0，1.0]。采用線性內(nèi)插函數(shù)：S(νij)=νij/2νmax+0.5，將速度轉(zhuǎn)換成概率。

(8)檢查終止條件

如果最優(yōu)解不再變化或者達(dá)到最大迭代次數(shù)GenMax便終止迭代，否則返回(2)。

3 實(shí)驗(yàn)測(cè)試及結(jié)果分析

本實(shí)驗(yàn)在具有海量試題的題庫(kù)內(nèi)進(jìn)行測(cè)試。本算法中每個(gè)題目含題分、題型、章節(jié)、難度系數(shù)四個(gè)屬性(如表1)，其他屬性從略。設(shè)試卷總分為100分，各種題型比例為 1∶1∶1∶2∶5，章節(jié)比例 2∶2∶2∶4，難度分布 為 2∶3∶7∶8，粒子群規(guī)模為3，最大迭代次數(shù)為600。

表1 題庫(kù)數(shù)據(jù)示例

使用改進(jìn)粒子群算法進(jìn)行測(cè)試，運(yùn)行10次的一組結(jié)果為(試題編號(hào))：17，22，27，34，39，42，44，49，51，55，57，57，60，61,64，65，67，68，71，73，75，78，80，81，82，84，86，90，92，99。

分別使用遺傳算法、粒子群算法和改進(jìn)粒子群算法進(jìn)行組卷實(shí)驗(yàn)。迭代記錄如表2。

表2 三種算法運(yùn)行10次的迭代記錄比較

試驗(yàn)結(jié)果表明，當(dāng)試題庫(kù)中的試題具有一定規(guī)模時(shí)，此改進(jìn)粒子群算法生成試卷的速度能達(dá)到較理想的效果，而且題庫(kù)越大，效果越明顯。此改進(jìn)的粒子群算法和遺傳算法在同樣的迭代次數(shù)條件下，相對(duì)于遺傳算法和基本粒子群算法能更快地收斂于全局最優(yōu)解。

本文利用遺傳算法的優(yōu)點(diǎn)，對(duì)粒子群優(yōu)化算法(PSO)的組卷方法加以改進(jìn)，從而設(shè)計(jì)出一種更加智能和高效的自動(dòng)組卷算法，使智能組卷的速度得到了明顯的提高，使組卷系統(tǒng)更加具有使用價(jià)值和現(xiàn)實(shí)意義。多數(shù)算法中提高速度都是以犧牲更多尋優(yōu)目標(biāo)實(shí)現(xiàn)的，增加尋優(yōu)目標(biāo)和提高速度是個(gè)兩難問(wèn)題，有待于進(jìn)一步解決。

[1]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[2]王一萍，曲偉建，潘海珠.一種基于粒子群優(yōu)化的組卷算法[J].兵工自動(dòng)化，2008(8).

[3]田民格.改進(jìn)的粒子群優(yōu)化算法實(shí)現(xiàn)多目標(biāo)智能組卷[D].三明學(xué)院學(xué)報(bào)，2009(10)：404-405.

[4]徐清振，肖成林.遺傳算法成卷策略的編碼實(shí)例[J].現(xiàn)代計(jì) 算 機(jī) ，2006(6)：40-41.