基于定向變異遺傳算法的智能組卷算法研究

胡新源，趙當(dāng)麗，李 輝，張向波，韓振興

（1.中國(guó)科學(xué)院國(guó)家授時(shí)中心，陜西 西安 710600；2.中國(guó)科學(xué)院大學(xué)，北京 100049；3.中國(guó)人民解放軍63768部隊(duì)，陜西 西安 710600）

隨著在線(xiàn)考核在現(xiàn)代教學(xué)方式中占比逐漸增大，實(shí)現(xiàn)準(zhǔn)確、高效的智能組卷算法已成為現(xiàn)代教育研究的一個(gè)熱點(diǎn)。文獻(xiàn)[1-2]對(duì)幾種智能算法應(yīng)用在組卷問(wèn)題上的性能做出了比較，目前解決組卷問(wèn)題主要依賴(lài)遺傳算法[3-4（]Genetic Algorithm，GA），但是由于組卷問(wèn)題數(shù)學(xué)模型較復(fù)雜，導(dǎo)致基于標(biāo)準(zhǔn)遺傳算法（Standard Genetic Algorithm，SGA）的組卷算法存在明顯尋優(yōu)能力弱、易早熟收斂陷入局部最優(yōu)等GA常見(jiàn)問(wèn)題。文獻(xiàn)[5]根據(jù)組卷約束條件人為選取初始種群，提高初始種群的適應(yīng)度。文獻(xiàn)[6-8]提出混合遺傳算法以提升算法性能，文獻(xiàn)[9]提出一種自適應(yīng)遺傳算法（Adaptive Genetic Algorithm，AGA），通過(guò)自適應(yīng)調(diào)整交叉變異概率提升組卷效率。但是以上優(yōu)化對(duì)于遺傳算法的性能提升均有限。文獻(xiàn)[10]提出一種定向變異遺傳算法（Directional Variation Genetic Algorithm，DVGA）的思想，對(duì)算法性能提升取得較好的效果。為進(jìn)一步改善GA的尋優(yōu)能力，該文基于以上研究基礎(chǔ)，結(jié)合組卷模型進(jìn)一步加強(qiáng)算法的定向?qū)?yōu)能力，同時(shí)降低了組卷時(shí)間，具有良好的性能。

1 智能組卷數(shù)學(xué)模型構(gòu)建

組卷算法的目的在于根據(jù)給出的限制條件，從題庫(kù)中自動(dòng)抽選符合條件的試題組卷，其數(shù)學(xué)本質(zhì)是在多維約束條件下求全局最優(yōu)解問(wèn)題[11],。解決此類(lèi)問(wèn)題需要確定一個(gè)目標(biāo)函數(shù)及多個(gè)約束條件，在組卷問(wèn)題中，約束條件即為題目的各項(xiàng)屬性，因此每道試題可以通過(guò)一維向量Q=(a1,a2,a3,…,an)來(lái)描述，n表示每道試題需要被約束的屬性總數(shù)。包含m道試題的題庫(kù)則構(gòu)成一個(gè)m×n的矩陣D[12]，如下所示：

組卷的過(guò)程即為從題庫(kù)矩陣D中選取一個(gè)滿(mǎn)足各約束條件的子集矩陣的過(guò)程，該組卷模型將以難度、章節(jié)、曝光時(shí)間、題型、分?jǐn)?shù)5個(gè)屬性作為約束條件，各屬性約束和目標(biāo)函數(shù)的選取如下所示。

1）難度：試卷的難度約束應(yīng)為試卷各試題的平均難度，用于區(qū)分考生水平。

式（2）中，ai1表示第i題的難度值，d表示預(yù)期的試卷整體難度，n表示該試卷中題目總數(shù)。

2）章節(jié)：章節(jié)用于約束試卷考察知識(shí)范圍，需對(duì)試卷逐題判斷是否屬于目標(biāo)章節(jié)。

式（3）中，ai2代表第i題的考察章節(jié)，S代表指定的章節(jié)范圍。

3）曝光時(shí)間：曝光時(shí)間表示該題目距離上次被抽取用于組卷的間隔時(shí)長(zhǎng)，需逐題判斷，用于避免題目頻繁出現(xiàn)。

式（4）中，ai3表示第i題的曝光時(shí)間，T代表最低未被組卷使用的間隔次數(shù)。

4）題型：通常試卷的題型結(jié)構(gòu)是固定且可枚舉的，需逐題判斷整卷的各題型是否符合指定數(shù)量。

式（5）中，t代表試卷中總題型數(shù)，tn代表每個(gè)題型的預(yù)設(shè)數(shù)量，tj為形如f2的函數(shù)，用于統(tǒng)計(jì)試卷中各題型數(shù)量，tj中以ai4代表第i題的題型。

5）分?jǐn)?shù)：分?jǐn)?shù)屬性需要統(tǒng)計(jì)整卷所有試題分?jǐn)?shù)求和，且應(yīng)允許一定的誤差。

式（6）中，ai5代表第i題分?jǐn)?shù)，其中P為預(yù)設(shè)試卷總分?jǐn)?shù)，δ為可接受的誤差范圍。

2 基于遺傳算法的組卷

GA被廣泛應(yīng)用在組卷問(wèn)題中，具體思路為：針對(duì)組卷問(wèn)題進(jìn)行基因編碼、適應(yīng)度函數(shù)的設(shè)計(jì)，選取合適的遺傳算子后即可抽取一定數(shù)量的試卷作為初始種群，進(jìn)行選擇交叉變異，直到種群中最優(yōu)個(gè)體滿(mǎn)足指定條件。種群中最優(yōu)個(gè)體即為滿(mǎn)足約束的目標(biāo)試卷。

2.1 基因編碼

GA中種群中的個(gè)體需用基因編碼表示，通常采用二進(jìn)制編碼來(lái)描述個(gè)體[13]。當(dāng)應(yīng)用在組卷問(wèn)題時(shí)，個(gè)體的基因編碼即為試卷所包含的試題編號(hào)，若采用二進(jìn)制編碼時(shí)，題庫(kù)中的每個(gè)題都需要出現(xiàn)在編碼中，極大地浪費(fèi)了編碼效率。其次，在每次交叉變異的過(guò)程中需對(duì)試題題型進(jìn)行判斷，引入了大量計(jì)算。文獻(xiàn)[14]提出一種實(shí)數(shù)分段式編碼，以試題編號(hào)實(shí)數(shù)為基因，按試題題型分段編碼，如下所示。

式（7）中，Qi表示試卷中的第i種題型，共計(jì)t種題型，每種題型ni道。采用實(shí)數(shù)分段式編碼時(shí)，基因編碼長(zhǎng)度僅為試卷試題總數(shù)，極大提升了編碼效率，且各題型在試卷染色體中位置固定，因此在交叉操作中可省略對(duì)題型的判斷[15]，如圖1所示。

圖1 采用實(shí)數(shù)分段式編碼的交叉操作

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來(lái)評(píng)判個(gè)體的優(yōu)劣性，應(yīng)滿(mǎn)足單值、非負(fù)及合理反映個(gè)體優(yōu)劣程度等要求，根據(jù)已建立的組卷模型可知適應(yīng)度應(yīng)為各項(xiàng)約束條件求加權(quán)和。

上式中，c用于保證目標(biāo)函數(shù)的非負(fù)性，ωi表示各項(xiàng)約束條件在目標(biāo)函數(shù)中的權(quán)重。其中，。

2.3 初始種群選取

根據(jù)已建立的組卷模型可知，組卷約束條件分為難度、題型、分?jǐn)?shù)等需要統(tǒng)計(jì)整卷判斷和章節(jié)、曝光時(shí)間等逐題判斷兩種類(lèi)型。由于目標(biāo)試卷中每道試題必定滿(mǎn)足第二類(lèi)需逐題判斷的約束條件，因此當(dāng)確定約束條件后，可根據(jù)指定的章節(jié)及曝光時(shí)間對(duì)題庫(kù)進(jìn)行篩選形成基因庫(kù)G。結(jié)合編碼結(jié)構(gòu)的題型設(shè)置，從中抽取一定數(shù)量的試卷作為初始種群，可使得初始種群有一個(gè)較高的適應(yīng)度，加速算法收斂。

2.4 遺傳算子設(shè)計(jì)

GA中的遺傳算子分為選擇算子、交叉算子、變異算子三部分。

選擇算子控制著進(jìn)化過(guò)程中的篩選作用，為了符合優(yōu)勝劣汰的規(guī)律同時(shí)又不喪失種群物種多樣性，通常采用輪盤(pán)賭方法。同時(shí)為了避免最優(yōu)個(gè)體在進(jìn)化過(guò)程中丟失，采用精英策略保留當(dāng)代最優(yōu)個(gè)體，使最優(yōu)個(gè)體無(wú)需經(jīng)過(guò)選擇交叉及變異直接進(jìn)入下一代。

交叉算子用于模擬種群進(jìn)化過(guò)程中的繁衍過(guò)程，通常采用單點(diǎn)交叉的方式，通過(guò)選擇算子選取父母?jìng)€(gè)體以交叉概率Pc進(jìn)行交叉。

變異算子用來(lái)模擬種群進(jìn)化過(guò)程中個(gè)體產(chǎn)生基因突變的情況，用于維持種群的多樣性，決定了算法的搜索能力，通常采用單點(diǎn)變異，種群中個(gè)體以概率Pm進(jìn)行變異，由于組卷模型存在題型約束，因此變異結(jié)果應(yīng)從同題型試題中抽取。

2.5 終止條件

組卷即為求適應(yīng)度函數(shù)最大值的過(guò)程，當(dāng)種群中最優(yōu)個(gè)體達(dá)到指定要求或達(dá)到指定的進(jìn)化次數(shù)后停止進(jìn)化，最優(yōu)個(gè)體即為滿(mǎn)足預(yù)設(shè)目標(biāo)的試卷。

3 基于定向變異遺傳算法的組卷

3.1 遺傳算子的改進(jìn)

GA中交叉概率Pc和變異概率Pm對(duì)于算法尋優(yōu)能力和收斂速度有著重要影響，自AGA被提出以來(lái)，眾多優(yōu)秀的改進(jìn)自適應(yīng)遺傳算法陸續(xù)被提出[16]，該文采用基于Sigmoid曲線(xiàn)改進(jìn)的自適應(yīng)遺傳算子來(lái)進(jìn)一步提升算法尋優(yōu)能力。

上式中，A=9.903 438，Pcmax、Pcmin表示交叉概率最大值及最小值，Pmmax、Pmmin表示變異概率最大值及最小值，f′表示進(jìn)行交叉的父母?jìng)€(gè)體中較大的適應(yīng)度，favg表示當(dāng)代種群平均適應(yīng)度，fmax表示當(dāng)代種群最大適應(yīng)度，f表示發(fā)生變異個(gè)體的適應(yīng)度。

3.2 變異操作的改進(jìn)

根據(jù)前文實(shí)數(shù)分段式編碼結(jié)構(gòu)及GA流程可知，在一次完整的組卷過(guò)程中，交叉操作只會(huì)改變各試卷的試題組合，而不會(huì)從總題庫(kù)中抽取新的試題，僅在變異操作過(guò)程中會(huì)引入新的試題。因此，從基因庫(kù)G中抽取試題作為變異結(jié)果，可確保由變異操作產(chǎn)生的新試題，在章節(jié)及曝光時(shí)間等需逐題判斷的約束條件下直接滿(mǎn)足目標(biāo)。且由于初始種群也在基因庫(kù)G中選取，因此在一次完整的組卷過(guò)程中，種群個(gè)體的基因即各試題始終滿(mǎn)足章節(jié)及曝光時(shí)間等需逐題判斷的約束條件，適應(yīng)度函數(shù)中關(guān)于章節(jié)及曝光時(shí)間的權(quán)重系數(shù)ω2、ω3可置為0，從而可以使得該組卷模型從五維約束條件簡(jiǎn)化為三維約束條件。

由于GA基于優(yōu)勝劣汰的法則，當(dāng)種群進(jìn)化到中后期往往存在嚴(yán)重同化現(xiàn)象即陷入局部最優(yōu)，此時(shí)由于種群同化嚴(yán)重，交叉操作已幾乎不能產(chǎn)生新試卷個(gè)體，主要依賴(lài)變異產(chǎn)生優(yōu)良試卷個(gè)體跳出局部最優(yōu)，而隨機(jī)變異會(huì)使得種群在長(zhǎng)時(shí)間內(nèi)無(wú)法跳出局部最優(yōu)。因此需對(duì)變異方向加以控制，使其只能朝著更優(yōu)定向變異。定向變異是指當(dāng)發(fā)生變異時(shí)，計(jì)算發(fā)生變異個(gè)體變異前的適應(yīng)度f(wàn)(x)與變異后的適應(yīng)度f(wàn)′(x)，僅當(dāng)f(x)

基于以上約束目標(biāo)屬性及適應(yīng)度的DVGA的組卷算法，不僅縮小了組卷過(guò)程尋優(yōu)的搜索空間，同時(shí)還限定了變異方向，使得個(gè)體只能朝著全局最優(yōu)發(fā)生變異，種群更易跳出局部最優(yōu)，極大地提升了算法的尋優(yōu)能力，同時(shí)簡(jiǎn)化了組卷過(guò)程的計(jì)算量，從而提升了組卷效率。

3.3 改進(jìn)遺傳算法

基于上述對(duì)遺傳算子和變異操作過(guò)程的改進(jìn)，可得到基于DVGA的組卷算法流程如圖2所示。

圖2 基于DVGA的組卷算法流程

4 仿真驗(yàn)證

為了驗(yàn)證文中提出的基于DVGA的組卷算法對(duì)組卷性能的提升，進(jìn)行如下實(shí)驗(yàn)，設(shè)置參數(shù)如表1所示。

表1 參數(shù)設(shè)置

結(jié)合上述流程圖進(jìn)行編程仿真，可以得到在相同條件下，各算法最大適應(yīng)度如圖3所示。

圖3 3種算法種群最大適應(yīng)度比較

同時(shí)，以表1條件進(jìn)行20次試驗(yàn)，分別對(duì)SGA、AGA、DVGA平均組卷準(zhǔn)確率、收斂代數(shù)及運(yùn)行時(shí)間進(jìn)行比較，可得到表2及圖4結(jié)果。

表2 3種算法組卷準(zhǔn)確率比較

圖4 3種算法收斂代數(shù)及算法耗時(shí)

從圖3可以看出，該文提出的DVGA相比于A(yíng)GA及SGA，具有更強(qiáng)的尋優(yōu)及跳出局部最優(yōu)的能力。表2及圖4表明，該文提出的DVGA準(zhǔn)確率及組卷效率相較于SGA及AGA均取得較大的提升。

5 結(jié)束語(yǔ)

智能組卷問(wèn)題本質(zhì)是對(duì)多約束多目標(biāo)的問(wèn)題尋求最優(yōu)解。該文充分利用組卷模型中約束條件的特性，優(yōu)先篩選出帶有部分最優(yōu)特性的優(yōu)良基因庫(kù)，使變異從中產(chǎn)生且定向只可朝著最優(yōu)變異，極大地縮短了組卷時(shí)間，提高了組卷效率。