基于粒子群遺傳算法的智能組卷策略

陳春燕，劉夢赤

(華南師范大學(xué)計(jì)算機(jī)學(xué)院,廣東 廣州 510631)

0 引 言

目前，計(jì)算機(jī)技術(shù)被廣泛應(yīng)用于各個(gè)領(lǐng)域，尤其是與教育模式的結(jié)合，大大彌補(bǔ)了傳統(tǒng)教學(xué)流程和學(xué)習(xí)方式上的缺陷，人們可通過互聯(lián)網(wǎng)遠(yuǎn)程在線學(xué)習(xí)，使學(xué)習(xí)不受空間和時(shí)間限制，降低了學(xué)習(xí)成本。相比起傳統(tǒng)教學(xué)模式，網(wǎng)絡(luò)教育也減少了學(xué)生與老師之間信息反饋的時(shí)間成本。因此，在線考試對網(wǎng)絡(luò)教育具有重大意義。與傳統(tǒng)考試模式相比，在線考試具有以下優(yōu)點(diǎn)：1)無需消耗人力資源管理試卷，避免了試卷丟失等現(xiàn)象；2)由于在線上完成命題、答題以及審題等流程，避免了大量紙張的浪費(fèi)，因此在線考試更加節(jié)能環(huán)保；3)教師只需設(shè)置組卷參數(shù)，系統(tǒng)即可采用智能算法自動(dòng)從題庫中抽題生成試卷；4)對于客觀題型，系統(tǒng)可自動(dòng)閱卷，減輕了教師的工作量[1]。

國外的教育信息化和在線考試系統(tǒng)得到了迅速的發(fā)展和廣泛的應(yīng)用。在現(xiàn)有計(jì)算機(jī)考試系統(tǒng)中，使用較多的有美國研究生入學(xué)考試(GRE)等系統(tǒng)。在構(gòu)建新的考試模式方面，國外已從傳統(tǒng)教學(xué)模式轉(zhuǎn)向信息化教學(xué)模式[2]。

國內(nèi)計(jì)算機(jī)技術(shù)發(fā)展雖然起步較晚，但近年來國內(nèi)高校通過努力研究與探索，開發(fā)了如“全國計(jì)算機(jī)等級(jí)考試”等功能完善的在線考試系統(tǒng)。另外，許多在線教育平臺(tái)也涵蓋了在線考試功能，著力為師生提供完善的教育資源[3]。

人工智能化考試組卷，是完成在線考試高效性的核心專業(yè)技術(shù)之一。人工智能考試組卷，就是根據(jù)已定的組卷要求，從題庫里抽取適合測試試題構(gòu)成試卷的過程。解決這類多目標(biāo)組合問題的策略，通常劃分為如下2大類：

1)傳統(tǒng)組卷策略。

①隨機(jī)抽取法[4]。隨機(jī)抽取法原理簡單，對單個(gè)題的抽取速度快，但因抽取時(shí)不控制試題參數(shù)，存在較大隨機(jī)性和不穩(wěn)定性等問題。文獻(xiàn)[5]提出了一種基于知識(shí)點(diǎn)與難度的隨機(jī)組卷算法，根據(jù)用戶設(shè)置的知識(shí)點(diǎn)與難度系數(shù)抽題，提高了組卷質(zhì)量，但存在重復(fù)抽取無效試題的現(xiàn)象，故組卷時(shí)間長，組卷成功率不高。

②回溯算法[6]。此算法組卷成功率比隨機(jī)抽取法高，但當(dāng)組卷試題題量大時(shí)，所需內(nèi)存大，時(shí)間冗余度高。文獻(xiàn)[7]提出了一種分類分段回溯試探算法，降低了試卷重復(fù)率，提高了組卷穩(wěn)定性，但由于其本質(zhì)仍是隨機(jī)抽取法，故組卷效率不高。

2)智能組卷策略。

①蟻群算法[8]。蟻群算法能夠并行處理且魯棒性較強(qiáng)，算法結(jié)果不太受初始路徑影響，組卷效率較高。缺點(diǎn)是計(jì)算量大，運(yùn)行效率低；參數(shù)設(shè)置不當(dāng)時(shí)，容易產(chǎn)生停滯、陷于局部最優(yōu)等問題。文獻(xiàn)[9]提出了一種蟻群優(yōu)化遺傳算法，通過實(shí)驗(yàn)表明此融合算法比蟻群算法性能更優(yōu)，但實(shí)現(xiàn)過程復(fù)雜，算法運(yùn)行時(shí)間長。

②遺傳算法[10]。該算法魯棒性強(qiáng)，組卷性能優(yōu)，但實(shí)現(xiàn)復(fù)雜，收斂速度慢。文獻(xiàn)[11]將遺傳算法進(jìn)行改進(jìn)，通過優(yōu)化遺傳算子提高最優(yōu)個(gè)體的適應(yīng)度，但在迭代初期優(yōu)化效果并不明顯，且算法中的交叉、變異概率為固定值，不利于快速找到最優(yōu)解，故算法收斂速度慢，組卷時(shí)間長。

③粒子群算法[12]。該算法無須許多參數(shù)調(diào)節(jié)，且個(gè)體能充分利用自身經(jīng)驗(yàn)和群體經(jīng)驗(yàn)快速調(diào)整自身狀態(tài)，搜索效率高。文獻(xiàn)[13-14]將粒子群算法和標(biāo)準(zhǔn)遺傳算法融合優(yōu)化，組卷效果明顯，但在迭代過程中，收斂速度較慢，收斂效率有待改進(jìn)。文獻(xiàn)[15]結(jié)合了粒子群算法和改進(jìn)后的遺傳算法，并利用貪心算法優(yōu)化初始種群，組卷成功率高，但其采用的二進(jìn)制編碼存在映射誤差，不利于算法得到最優(yōu)解。

經(jīng)過以上分析研究，結(jié)合粒子群算法和遺傳算法的優(yōu)劣勢，本文提出一種基于粒子群遺傳算法的智能組卷策略，在粒子群算法中融入遺傳操作。粒子群中的粒子不通過速度和位置更新自己，而采用交叉操作和自身的變異操作進(jìn)行更新。粒子進(jìn)行交叉操作的對象來自于每次迭代，根據(jù)目標(biāo)函數(shù)比較適應(yīng)度值而得出個(gè)體極值和群體極值。在對2種算法的結(jié)合進(jìn)行優(yōu)化的基礎(chǔ)上，本文還采用基于知識(shí)點(diǎn)、題型和分?jǐn)?shù)等參數(shù)，以不完全隨機(jī)方式對種群初始化，根據(jù)當(dāng)前種群中粒子的適應(yīng)度值采用動(dòng)態(tài)調(diào)節(jié)交叉概率、變異概率大小，以及分段實(shí)數(shù)編碼等方法，進(jìn)一步提高算法的可行性和高效性。最后，通過與標(biāo)準(zhǔn)遺傳算法、粒子群算法進(jìn)行對比實(shí)驗(yàn)來驗(yàn)證該算法的優(yōu)勢。

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

1.1 組卷問題分析

組卷問題實(shí)質(zhì)上是一個(gè)多約束條件的組合優(yōu)化問題。一份標(biāo)準(zhǔn)試卷，一般需緊跟測評考試大綱，試題難度適當(dāng)且具有一定的可區(qū)分性，能考查應(yīng)試者的知識(shí)儲(chǔ)備量[16]。因此試卷需包含試卷難度系數(shù)、區(qū)分度、信度與效度等特征指標(biāo)[17-18]。將組卷理論轉(zhuǎn)換成數(shù)學(xué)模型，設(shè)一份試卷總題量為m，每道試題有n個(gè)屬性，則一份試卷為一個(gè)m×n矩陣，矩陣中的aij表示第i題的第j個(gè)屬性，矩陣表示如式(1)所示：

(1)

在本文設(shè)計(jì)的模型中，選取n=5，表示試題的分值、題型、難度系數(shù)、知識(shí)點(diǎn)、教學(xué)能力層次等屬性。目標(biāo)矩陣S應(yīng)滿足的約束條件及其計(jì)算公式如下[19]：

1)試卷總分。M為總題量，ai1為第i題的分?jǐn)?shù)，如式(2)所示：

(2)

2)試卷題型與分?jǐn)?shù)。運(yùn)算方程式如公式(3)所示：

(3)

其中，Tk是第k題型的分?jǐn)?shù)，C是題型(含單選、多選、判定、填空、主觀題型)，具體題目類型和各題型分值由用戶設(shè)置。

3)試卷難度系數(shù)與分?jǐn)?shù)。f1i是每一題難度系數(shù)，如式(4)所示：

(4)

4)試卷能力層次及分?jǐn)?shù)。同一知識(shí)點(diǎn)下的不同能力層次的試題更能反映考生的能力水平。Ak代表第k級(jí)別，C是教學(xué)能力層次。每個(gè)知識(shí)點(diǎn)都有相應(yīng)的能力層次要求。具體試卷的能力層次等級(jí)分值由用戶設(shè)置。如式(5)所示：

(5)

5)知識(shí)點(diǎn)覆蓋率。r1指試卷含有知識(shí)點(diǎn)數(shù)，r2代表用戶希望的知識(shí)點(diǎn)數(shù)。知識(shí)點(diǎn)覆蓋率越大，表明越達(dá)到用戶期望。計(jì)算公式如式(6)所示：

(6)

1.2 目標(biāo)函數(shù)的建立

由于本文算法在抽取題目進(jìn)行組卷時(shí)，會(huì)保證試卷的各題型分?jǐn)?shù)和總分為用戶的期望分?jǐn)?shù)，因此只需要考慮其他約束條件。A代表試卷的能力層次分布，D代表試卷難度系數(shù)，R代表知識(shí)點(diǎn)覆蓋率。由于組卷結(jié)果往往與用戶期望存在偏差，設(shè)偏差值分別為EA、ED、ER，由式(7)～式(9)所示：

(7)

(8)

ER=1-R

(9)

式中，試卷能力層次的總個(gè)數(shù)用m1表示，能力層次為i的期望分?jǐn)?shù)用Ai表示。D、M、R分別由式(4)、式(2)與式(6)取得，UD是用戶希望的試卷難度參數(shù)。

因組卷問題是多約束問題，所以組卷約束條件不可能全滿足。應(yīng)根據(jù)實(shí)際情況忽略部分次要指標(biāo)，獲得近似最優(yōu)解即可。本文中智能組卷問題的目標(biāo)函數(shù)F，為所有約束條件的差值加權(quán)和的最小值函數(shù)(0≤F≤1)，即F越接近1，越達(dá)到用戶期望。如式(10)所示：

F=1-(w1×EA+w2×ED+w3×ER)

(10)

2 基于粒子群遺傳算法的智能組卷策略

2.1 算法主要思想

對于智能組卷算法，用戶不僅希望能夠生成符合要求的試卷，且算法運(yùn)行時(shí)間盡量短。

結(jié)合粒子群算法和遺傳算法優(yōu)勢與不足，本文提出一種基于粒子群遺傳算法的智能組卷策略，在粒子群算法中融入遺傳操作。粒子群中的粒子不通過速度和位置更新自己，而采用交叉操作和自身的變異操作進(jìn)行更新。粒子進(jìn)行交叉操作的對象來自于每次迭代，根據(jù)目標(biāo)函數(shù)比較適應(yīng)度值而得出的個(gè)體極值和群體極值。通過2種算法的結(jié)合來提高種群的收斂效率。另外，本文還采用基于知識(shí)點(diǎn)、題型和分?jǐn)?shù)等參數(shù)，以不完全隨機(jī)方式對種群初始化，在進(jìn)化過程中根據(jù)迭代情況和粒子群適應(yīng)度值自適應(yīng)改變交叉概率和變異概率，以及采用分段實(shí)數(shù)編碼等方法進(jìn)一步提高算法的可行性和高效性。

2.2 編碼方案和初始化種群

本文采用分段實(shí)數(shù)編碼機(jī)制對群體粒子進(jìn)行編碼。即試題按照題型分類后，分段歸置，也即同一段編碼上的試題為同一題型[20]。

在初始化種群階段，從題庫中抽取試題時(shí)，先根據(jù)期望的知識(shí)點(diǎn)從題庫中篩選試題構(gòu)成小題庫。另外，抽題過程中容易反復(fù)選取無效試題，為了解決這一問題，本文采用不重復(fù)隨機(jī)數(shù)列生成算法作為解決方案[5]。

另外，由上文中對智能組卷問題數(shù)學(xué)模型和目標(biāo)函數(shù)的建立，本文適應(yīng)度函數(shù)采用式(10)。在迭代更新過程里，每一代中適合度值最大的粒子為群體極值。個(gè)體極值就是個(gè)體在持續(xù)自動(dòng)更新調(diào)整過程里產(chǎn)生的適合度值最大的情況。

2.3 交叉操作

本文算法中個(gè)體粒子是和個(gè)體極值、群體極值展開交叉操作的。根據(jù)2.2節(jié)中所述個(gè)體極值和群體極值的特點(diǎn)，個(gè)體粒子與具有最優(yōu)良基因的極值粒子交叉，相比與其他個(gè)體交叉，此方式下的基因重組更能產(chǎn)生最優(yōu)粒子，因而利用交叉可迅速收斂到最優(yōu)解的鄰域區(qū)間中，減少收斂時(shí)間，提升收斂速度，逐漸接近最優(yōu)解[21]。

本文采取分段離散交叉，即在同一類型的編碼段中，當(dāng)隨機(jī)概率數(shù)低于交叉率的時(shí)候，子個(gè)體的每一個(gè)遺傳基因等概率隨機(jī)地選用父個(gè)體的遺傳基因。以個(gè)體與個(gè)體極值交叉為例，詳細(xì)步驟如下：

Step1設(shè)個(gè)體中某一類型編碼段長度為s1，當(dāng)隨機(jī)數(shù)R1小于交叉率時(shí)，依次選擇個(gè)體、個(gè)體極值的等位基因g1、g2。

Step2判斷g1、g2分值是否相等，以及個(gè)體粒子所有基因是否與g2存在重合現(xiàn)象。

Step3若g1、g2分值相等且不存在重合現(xiàn)象，當(dāng)隨機(jī)數(shù)R2>0.5時(shí)，新個(gè)體的基因來自于g2,否則來自于g1。以單選題為例，具體流程如圖1所示。

圖1 交叉過程圖

此方式可使生成的新個(gè)體的所有基因都唯一，即同一試卷的題目不存在重復(fù)現(xiàn)象。如果交叉操作應(yīng)用之后的粒子的適應(yīng)度值高于以前的適應(yīng)度值，則自動(dòng)更新粒子，否則不調(diào)整。

2.4 變異操作

變異操作注重于粒子群的局部搜索能力。本文采用分段變異模式，也就是變異操作在每一類題型與對應(yīng)的程序編碼段內(nèi)展開。具體流程如下：

Step1設(shè)個(gè)體中某一題型編碼段長度為s2，當(dāng)隨機(jī)數(shù)R3小于變異率時(shí)，確定變異位置。

Step2獲得Step1變異位置上的基因(即題號(hào))，進(jìn)一步得到題目信息，并獲取與該題目相同題型、分值且知識(shí)點(diǎn)為包含關(guān)系的題目集。

Step3在題目集中隨機(jī)選擇一個(gè)題目，用此題目的題號(hào)替換Step1被確定的題號(hào)。以單選題為例，該過程如圖2所示。

圖2 變異過程圖

2.5 自適應(yīng)交叉概率和變異概率

1)改進(jìn)思路。

近年來，相關(guān)學(xué)者提出了有關(guān)交叉概率、變異概率的自適應(yīng)策略[22]，雖提高了算法收斂速度，但沒有考慮到種群整體的情況，只是針對群體平均值與最優(yōu)值來調(diào)整概率，限制了算法的尋優(yōu)性能。

因此，對這2個(gè)概率的調(diào)整應(yīng)體現(xiàn)種群的相似程度。相似程度通過個(gè)體適應(yīng)度值來度量。當(dāng)粒子群相似度較小時(shí)，表明當(dāng)代粒子間的適應(yīng)度值相差較大，即種群的基因類型多樣，此時(shí)應(yīng)增大交叉概率，減小變異概率。反之，當(dāng)粒子群相似度較高時(shí)，表明當(dāng)前群體的基因類型較為單一，應(yīng)減小交叉概率，增大變異概率。并且隨著迭代次數(shù)的增加，交叉概率越來越小，變異概率越來越大，最終2個(gè)概率趨于穩(wěn)定值。本文根據(jù)此思想，結(jié)合Logistic函數(shù)和相似系數(shù)的概念來實(shí)現(xiàn)遺傳操作中2個(gè)概率的適應(yīng)性平衡調(diào)整。

2)Logistic函數(shù)。

Logistic函數(shù)在信息科學(xué)、生物學(xué)等領(lǐng)域中應(yīng)用廣泛，描述某些有界增長現(xiàn)象較準(zhǔn)確[23]。它表達(dá)形式不一，較常見的如式(11)所示：

(11)

由圖3可知，Logistic函數(shù)在區(qū)間中與變量呈正相關(guān)，而在兩端收斂。根據(jù)此特性，將函數(shù)融入到概率的自適應(yīng)策略中，能夠得出符合改進(jìn)需求的算式。

圖3 Logistic函數(shù)圖像

3)相似系數(shù)。

群體中個(gè)體間的相似程度通過相似系數(shù)來反映。本文引入期望EX和方差DX來計(jì)算得到相似系數(shù)，以適應(yīng)度值為變量，得到種群平均值，以及偏離平均值的離散程度，如式(12)、式(13)所示：

(12)

(13)

式中，favg為群體平均適應(yīng)度值，M為種群規(guī)模，fi(i=1,2,…,M)表示個(gè)體適應(yīng)度值。

理論上群體中粒子隨著進(jìn)化，優(yōu)良程度越來越高，粒子適應(yīng)度值逐漸增大，粒子群相似程度也越來越高。即EX逐漸增大，而DX則逐漸減小。據(jù)此，λ的計(jì)算公式如式(14)所示：

(14)

4)交叉概率和變異概率調(diào)節(jié)公式。

結(jié)合相似系數(shù)的定義,給出改進(jìn)的自適應(yīng)交叉概率pc、變異概率pm，調(diào)節(jié)公式如式(15)、式(16)所示：

(15)

(16)

其中，u1、u2為2個(gè)常數(shù)，其取值范圍分別為(0,+∞)、(0,1)。

由式(15)、式(16)可知，將u1設(shè)為10，u2設(shè)為0.1，則改進(jìn)后的交叉概率pc、遺傳概率pm的意義在于：

①隨著相似系數(shù)λ的增大，pc越來越小，pm越來越大。

②pc的變化范圍始終在(0.4,0.9)區(qū)間內(nèi)，pm變化范圍始終在(0,0.1)區(qū)間內(nèi)。

2.6 算法流程

算法流程如圖4所示。當(dāng)?shù)螖?shù)達(dá)到規(guī)定的值時(shí)，算法結(jié)束。

圖4 算法流程圖

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)部分采用仿真方式驗(yàn)證本文算法的優(yōu)勢。本文采用大數(shù)據(jù)教育平臺(tái)Weblearn的某課程題庫作為數(shù)據(jù)集來源。該系統(tǒng)采用MongoDB數(shù)據(jù)庫，其題庫按照題型分為4張表。選取該課程在題庫中的500道題，其中5種題型各為100道。在主機(jī)操作系統(tǒng)為Windows7，CPU為Intel Core i5，8 GB內(nèi)存環(huán)境下，在IntelliJ IDEA2019平臺(tái)上進(jìn)行實(shí)驗(yàn)。根據(jù)分析設(shè)置組成一套試卷的約束條件要求如下：

1)試卷的題型及其分?jǐn)?shù)分布如表1所示。

表1 試卷題型及分值參數(shù)表

2)能力層次分布在試卷中的比重如表2所示。

3)試卷知識(shí)點(diǎn)為特定的一組知識(shí)點(diǎn)，在每次實(shí)驗(yàn)中都保持不變。

4)試卷難度系數(shù)為0.6。

5)交叉、變異概率的調(diào)整公式中u1設(shè)為10，u2設(shè)為0.1。

6)種群規(guī)模為30，最高迭代更新數(shù)目設(shè)為150。

本文采用改進(jìn)遺傳算法[24]、粒子群算法[25]以及本文算法進(jìn)行對比實(shí)驗(yàn)，并在上述實(shí)驗(yàn)環(huán)境下進(jìn)行。3種算法在相同的組卷參數(shù)條件下進(jìn)行50次重復(fù)組卷實(shí)驗(yàn)，并根據(jù)組卷的主要約束條件及其性能等方面進(jìn)行對比分析。

3.1 組卷主要約束條件對比分析

1)針對難度系數(shù)的對比分析。

組卷基于不同算法，由式(4)計(jì)算難度系數(shù)，把實(shí)驗(yàn)數(shù)據(jù)取平均有效數(shù)值，3類算法下的難度系數(shù)對照如表3所示：

表3 3種算法下的難度系數(shù)及誤差率對比表

誤差率是指期望值與實(shí)際值的差值占期望值的百分比。由表3可知，本文算法在3個(gè)算法中誤差率最小，最能滿足用戶對于試卷難度方面的需求。

2)針對知識(shí)點(diǎn)覆蓋率的對比分析。

由式(6)計(jì)算知識(shí)點(diǎn)覆蓋率，表4展示了3種算法下的知識(shí)點(diǎn)覆蓋率取平均值后的數(shù)據(jù)對比。

表4 3種算法下的知識(shí)點(diǎn)覆蓋率對比表 單位：%

由表4可知，相較于遺傳算法和粒子群算法，本文算法生成的試卷的知識(shí)點(diǎn)覆蓋率最高，最能達(dá)到用戶期望。

3)在能力層次分布上的對比分析。

由式(5)計(jì)算能力層次分布分值，表5展示了3種算法下的能力層次分布取平均數(shù)后的數(shù)據(jù)對比。為了直觀地展示在不同組卷策略的作用下，能力層次分布的實(shí)際數(shù)據(jù)與期望值的偏差，本文給出了3種算法下的能力層次誤差對比圖，如圖5所示。

表5 3種算法下的能力層次分布對比表

由圖5可知，對于本文算法生成的試卷，能力層次分布的誤差絕對值曲線整體上都低于其他2種算法下的誤差。即本文算法下的能力層次分布的實(shí)際數(shù)據(jù)更接近于期望值。

圖5 3種算法下的能力層次分布誤差圖

由難度系數(shù)、知識(shí)點(diǎn)覆蓋率和能力層次分布的實(shí)驗(yàn)數(shù)據(jù)對比可知，相較于遺傳算法和粒子群算法，本文算法生成的試卷的參數(shù)實(shí)際值更接近于用戶期望的參數(shù)值。即在相同的實(shí)驗(yàn)環(huán)境下，本文算法生成的試卷更具有實(shí)用性。

3.2 算法性能分析

為了驗(yàn)證本文算法的優(yōu)勢，算法性能采取參數(shù)多批量對比分析，即題庫規(guī)模劃分為500、1000、1500、2000題，迭代次數(shù)分別取50、100、150次，統(tǒng)計(jì)3種算法在不同參數(shù)值下的運(yùn)行時(shí)間和最優(yōu)個(gè)體適應(yīng)度數(shù)據(jù)。

1)運(yùn)行效率對比分析。

把3類算法在不同題庫規(guī)模、進(jìn)化次數(shù)下的運(yùn)行時(shí)間取平均有效數(shù)值，測試實(shí)驗(yàn)數(shù)據(jù)信息如表6所示。為了形象地比較，把運(yùn)行時(shí)間數(shù)據(jù)表按照題庫規(guī)模轉(zhuǎn)換成柱形圖，如圖6～圖9所示。

圖6 題庫規(guī)模為500下的算法耗時(shí)圖

圖7 題庫規(guī)模為1000下的算法耗時(shí)圖

圖8 題庫規(guī)模為1500下的算法耗時(shí)圖

圖9 題庫規(guī)模為2000下的算法耗時(shí)圖

表6 運(yùn)行時(shí)間數(shù)據(jù)表 單位：s

根據(jù)圖6～圖9和表6可知，在同一題庫規(guī)模下，迭代更新數(shù)目相同時(shí)，本算法運(yùn)行時(shí)間在三者中最少，且隨著迭代次數(shù)增加，優(yōu)勢越來越明顯；而在同一迭代次數(shù)下，隨著題庫規(guī)模的增加，3種算法耗時(shí)都有不同程度的增加，但本文算法增加的運(yùn)行時(shí)間最少，即本文算法運(yùn)行效率在三者中最高。

2)最優(yōu)個(gè)體適應(yīng)度值對比分析。

為比較算法的收斂速度以及生成的試卷的質(zhì)量高低，將迭代次數(shù)進(jìn)行細(xì)分，并將不同題庫規(guī)模下生成的最優(yōu)個(gè)體的適應(yīng)度值取平均有效數(shù)值，測試實(shí)驗(yàn)數(shù)據(jù)信息如表7所示。為了形象地比較，把表7根據(jù)題庫規(guī)模轉(zhuǎn)換成折線圖，如圖10～圖13所示。

表7 最優(yōu)個(gè)體適應(yīng)度值數(shù)據(jù)表

圖10 題庫規(guī)模為500下的最優(yōu)對比圖

圖11 題庫規(guī)模為1000下的最優(yōu)對比圖

圖12 題庫規(guī)模為1500下的最優(yōu)對比圖

圖13 題庫規(guī)模為2000下的最優(yōu)對比圖

由圖10～圖13和表7可知，當(dāng)?shù)螖?shù)相同時(shí)，3種算法的最優(yōu)個(gè)體平均適應(yīng)度值都隨著題庫規(guī)模的擴(kuò)大而增加，但本文算法的最優(yōu)個(gè)體適應(yīng)度值增量最多，即本文想法相較于其他兩者，更適用于題庫較大的組卷問題。當(dāng)題庫規(guī)模相同時(shí)，粒子群算法和遺傳算法雖然起初最優(yōu)個(gè)體的平均適應(yīng)度值較高，整個(gè)組卷過程收斂速度較快，但最優(yōu)個(gè)體適應(yīng)度值較低，即這2種算法可能陷入了局部最優(yōu)解。而本文算法雖然收斂速度較慢，但是最優(yōu)個(gè)體的適應(yīng)度值一直呈現(xiàn)增長趨勢，說明相較于其他2種算法，本文算法的種群個(gè)體在尋找全局最優(yōu)解時(shí)呈均勻移動(dòng)趨勢，這在一定程度上克服了收斂“早熟”現(xiàn)象。另外，隨著迭代次數(shù)的增加，本文算法的最優(yōu)個(gè)體平均適應(yīng)度值逐漸優(yōu)于其他算法，表明本文算法生成試卷的整體質(zhì)量也高于其他算法生成試卷的質(zhì)量。

通過以上實(shí)驗(yàn)數(shù)據(jù)的對比分析，粒子群遺傳算法實(shí)用性更強(qiáng)、性能更優(yōu)、組卷效率更高，是一種有效解決組卷問題的策略。本文的基于粒子群遺傳算法的組卷策略相比基于遺傳算法的組卷策略和基于粒子群算法的組卷策略，生成的試卷質(zhì)量更高，試卷內(nèi)容也更科學(xué)、規(guī)范。

4 結(jié)束語

本文分析了當(dāng)前主流的智能組卷算法，并結(jié)合組卷的數(shù)學(xué)模型，提出了基于粒子群遺傳算法的智能組卷策略，粒子同個(gè)體極值及群體極值進(jìn)行交叉操作，與粒子本身展開變異操作，同時(shí)應(yīng)用交叉、變異概率的自適應(yīng)調(diào)節(jié)、分段實(shí)數(shù)編碼機(jī)制等方法提高算法性能。最后由實(shí)驗(yàn)對比表明，該算法具備較強(qiáng)實(shí)用性，組卷效率高，基于此算法生成的試卷質(zhì)量高，試卷內(nèi)容也更符合用戶需求。但本算法仍有收斂速度慢、迭代初期種群適應(yīng)度值低等不足之處，后期會(huì)進(jìn)一步優(yōu)化。