基于基因表達(dá)式編程的計(jì)算機(jī)組卷算法研究

韓 嘯，畢 波，唐錦萍

(1.東北石油大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，黑龍江 大慶 163000;2.黑龍江大學(xué) 數(shù)據(jù)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080)

0 引 言

隨著當(dāng)代教育技術(shù)及科學(xué)技術(shù)的迅速發(fā)展，傳統(tǒng)的教學(xué)與考試方式已漸漸無法適應(yīng)現(xiàn)代化的教學(xué)要求，因此網(wǎng)絡(luò)化的教學(xué)考試已漸漸步入人們的視野。網(wǎng)絡(luò)化的教學(xué)考試的關(guān)鍵在于能夠快速智能地組成試卷，即在計(jì)算機(jī)上設(shè)置試題庫，并通過適當(dāng)?shù)乃惴ㄌ暨x出試題并構(gòu)成試卷，這類算法相較于傳統(tǒng)的人工組卷來說更為高效[1]。

通過網(wǎng)絡(luò)化的考試模式，不僅可以減輕教師及學(xué)校的工作量，而且更能激發(fā)學(xué)生的學(xué)習(xí)熱情、提高學(xué)生的學(xué)習(xí)效率。

目前的在線考試系統(tǒng)已經(jīng)可以實(shí)現(xiàn)智能組卷、在線答題、在線閱卷等一系列功能。但由于一些現(xiàn)實(shí)條件的約束，各類在線考試系統(tǒng)在智能組卷方面還不夠成熟；大批量產(chǎn)生試卷時(shí)速度慢、質(zhì)量差是現(xiàn)階段組卷算法的主要缺點(diǎn)。

針對現(xiàn)階段在線考試系統(tǒng)組卷速度慢、質(zhì)量差、題型不均衡等不合理的問題[2]，文中首先給出了組卷問題的數(shù)學(xué)模型，將組卷問題歸結(jié)為一個(gè)約束非線性優(yōu)化問題，并提出了基于基因表達(dá)式編程的自動組卷算法，將該算法用于求解組卷優(yōu)化問題，實(shí)驗(yàn)證明該算法有著較高的計(jì)算效率和良好的實(shí)用性。

1 常見智能組卷算法

常見的智能組卷算法包括以下4種：

(1)基于隨機(jī)算法的組卷算法。

隨機(jī)組卷算法是依據(jù)已經(jīng)確定的試卷標(biāo)準(zhǔn)進(jìn)行隨機(jī)抽取試題[3]，在組卷時(shí)，利用二項(xiàng)分布函數(shù)建立數(shù)學(xué)模型，按照試題的類型、試題的難度、知識點(diǎn)等約束條件進(jìn)行選擇。

該算法結(jié)構(gòu)簡單、易于理解，常常應(yīng)用于容量較小的試題庫組卷系統(tǒng)中[4]。當(dāng)系統(tǒng)中試題過多時(shí)，組卷的時(shí)間會變長且成功率低。

(2)基于回溯算法的組卷算法。

回溯算法實(shí)際上是一個(gè)類似于枚舉的搜索嘗試過程[5]，是一種選優(yōu)搜索的方法，按選優(yōu)條件向前搜索以達(dá)到目標(biāo),在搜索嘗試的過程中尋找問題的解，當(dāng)不滿足求解條件時(shí)就進(jìn)行“回溯”[6]，嘗試別的路徑，重新抽取試題。

在試題種類少、數(shù)量少的情況下，回溯算法優(yōu)于隨機(jī)算法[7]。但當(dāng)試題種類增多、試題量增加后，使用回溯算法生成試卷的速度明顯變慢[8]，且選取的試題不能保證是最優(yōu)的，所以在智能組卷中回溯算法很少被使用。

(3)基于遺傳算法的組卷算法。

遺傳算法(genetic algorithm，GA)是一類借鑒生物界的“適者生存，優(yōu)勝劣汰”的遺傳機(jī)制演化而來的隨機(jī)化搜索方法[9]。該算法采用簡單的編碼技術(shù)對試題庫中的試題進(jìn)行編碼，生成初始的種群。然后通過復(fù)制、交換、突變?nèi)N操作產(chǎn)生下一代新的種群。并且一代一代朝向適應(yīng)度函數(shù)的方向發(fā)展，直至產(chǎn)生滿足出卷要求的試卷。

遺傳算法在智能組卷中是比較靈活的方法，適用于具有多約束條件的組卷問題[10]。但在組卷過程中由于試題量的增加，“早熟”的問題逐漸顯現(xiàn)出來，所以如何提高算法執(zhí)行效率，解決“早熟”問題成為了重要的研究問題。

(4)基于粒子群優(yōu)化算法的組卷算法。

粒子群優(yōu)化算法是模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法[11]。粒子群算法首先從試題庫中隨機(jī)抽取若干套試卷，構(gòu)成最初的粒子群(每個(gè)粒子代表一套試卷)。然后，運(yùn)用適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的值，判斷其是否符合要求。如果不符合繼續(xù)迭代，直至選取到符合要求的試卷。

粒子優(yōu)化種群算法在計(jì)算大規(guī)模試題庫系統(tǒng)時(shí)編碼簡單，搜索速度更快，效率更高，但是不適宜處理離散的優(yōu)化問題，且在選擇遺傳算子時(shí)比較麻煩。

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

組卷是指從一個(gè)試題庫中在滿足給定規(guī)則的情況下，根據(jù)確定的參數(shù)及算法，從試題庫中篩選組合出一套滿足要求的、科學(xué)的、合理的試卷。

進(jìn)行組卷時(shí)需要給定以下的約束條件：試題數(shù)量、總分、題型個(gè)數(shù)、題型分?jǐn)?shù)等。首先用xn來表示題型，用yn來表示章節(jié)，ki=1表示選擇某題，ki=0表示不選擇某題，如表1所示。

表1 試卷的約束條件

根據(jù)表1，可列出約束條件：

①試題數(shù)量約束。

(1)

②總分約束。

(2)

式(2)表示試卷總分為100分。

③題型個(gè)數(shù)約束。

(3)

(4)

(5)

(6)

式(3)表示被選中的試題中選擇題的個(gè)數(shù)為10個(gè)，式(4)表示被選中的試題中填空題的個(gè)數(shù)為10個(gè)，式(5)表示被選中的試題中判斷題的個(gè)數(shù)為10個(gè)，式(6)表示被選中的試題中大題的個(gè)數(shù)為4個(gè)。

④每章所有題型的總分約束。

(7)

(8)

(9)

(10)

其中，yim表示第i題在第m章，

式(7)表示第一章被選中的所有試題的總分，第一章試題占20分。式(8)表示第二章被選中的所有試題的總分，第二章試題占20分。式(9)表示第三章被選中的所有試題的總分，第三章試題占20分。式(10)表示第四章被選中的所有試題的總分，第四章試題占40分。

⑤某章必有某種數(shù)量題型約束。

(11)

(12)

(13)

式(11)表示第一章被選中的題必須包含1個(gè)大題，式(12)表示第二章選中的題必須包含2個(gè)選擇題，式(13)表示第三章選中的題必須包含1個(gè)判斷題。

3 基因表達(dá)式編程算法在組卷算法中的應(yīng)用

3.1 基因表達(dá)式編程算法的介紹

基因表達(dá)式編程算法(gene expression programming，GEP)是融合和遺傳算法(GA)和遺傳規(guī)劃(genetic programming，GP)的特點(diǎn)演化而成的算法[12]。

首先，在基因型上(句法上)，基因表達(dá)式編程算法繼承了GA的定長線性編碼的特點(diǎn)，以K-表達(dá)式的形式表示[13]。GEP的染色體可以由單個(gè)或多個(gè)GEP基因組成。GEP的基因是由基因的頭部h和尾部t組成，基因的頭部既可以包含函數(shù)符又可以包含終結(jié)符，而基因的尾部只能包含終結(jié)符。其中頭部的長度是根據(jù)具體的問題來決定的，基因尾部的數(shù)量由頭部數(shù)量決定，公式為：

t=h×(n-1)+1

(14)

其中，n表示所需變量數(shù)量最多的函數(shù)的參數(shù)個(gè)數(shù)(例如在常見的數(shù)學(xué)運(yùn)算中，絕對值和三角函數(shù)運(yùn)算n=1，而大多數(shù)的算數(shù)運(yùn)算如加減乘除n=2)。GEP采用這種將頭部和尾部分開的基因形式，一方面整個(gè)基因的結(jié)構(gòu)在設(shè)定了函數(shù)集合和頭部長度之后就能夠確定；另一方面，整個(gè)基因在該公式的前提下一定能夠保證結(jié)構(gòu)上的正確性，而不用擔(dān)心會產(chǎn)生任何非法的個(gè)體。

其次，在表現(xiàn)型上(語義上)，GEP繼承了GP的樹形結(jié)構(gòu)，稱為表達(dá)式樹。表達(dá)式樹上的葉節(jié)點(diǎn)表示運(yùn)算數(shù)，也就是終結(jié)符。分支節(jié)點(diǎn)表示運(yùn)算符，也就是函數(shù)符。盡管GEP采用固定長度的基因，但其對應(yīng)的表達(dá)式樹形式卻千差萬別。但無論染色體怎樣變異，這些表達(dá)式樹都是有效的。GEP的基本流程框架如圖1所示[14],具體步驟如下:

①設(shè)置控制參數(shù),選擇函數(shù)集合并設(shè)置終結(jié)符；

②創(chuàng)建初始種群,包含若干個(gè)代表不同解答方案的個(gè)體；

③解析GEP的基因解碼,計(jì)算每個(gè)個(gè)體的適應(yīng)度值用以評價(jià)種群；

④若達(dá)到設(shè)定最大進(jìn)化代數(shù)或計(jì)算精度,則進(jìn)化結(jié)束,否則執(zhí)行步驟⑤；

⑤根據(jù)“適者生存”原則，實(shí)施最優(yōu)化保存策略；

⑥遺傳操作產(chǎn)生下一代：分別利用選擇、變異、倒串、插串(包括IS插串、RIS插串、基因插串)、重組(包括單點(diǎn)重組、兩點(diǎn)重組、基因重組)、隨機(jī)變量變異對群體實(shí)施遺傳操作；

⑦生成新種群，并計(jì)算各個(gè)個(gè)體的適應(yīng)度函數(shù)值，然后返回步驟④。

圖1 GEP算法流程

3.2 基因表達(dá)式編程的適應(yīng)度函數(shù)

基因表達(dá)式編程的適應(yīng)度函數(shù)是進(jìn)化算法與現(xiàn)實(shí)問題的接口，同時(shí)也是算法演化過程的主要驅(qū)動源泉。適當(dāng)?shù)倪m應(yīng)度函數(shù)可以評價(jià)算法所求得的問題解的優(yōu)劣。適應(yīng)度函數(shù)的計(jì)算一般按照以下步驟進(jìn)行：

①對個(gè)體的編碼串解碼，得到個(gè)體的表現(xiàn)型；

②由個(gè)體的表現(xiàn)型計(jì)算出相應(yīng)個(gè)體的目標(biāo)函數(shù)值；

③依據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按照一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度函數(shù)。

通過上述組卷問題的數(shù)學(xué)模型可以得到組卷問題關(guān)于基因表達(dá)式編程算法的適應(yīng)度函數(shù)為：

W=1 000-(N+Q+M+P)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

3.3 基因表達(dá)式編程的遺傳算子

GEP采用的是線性等長的編碼方式，所以基因表達(dá)式編程的遺傳操作類似于遺傳算法[15]。GEP在進(jìn)行各種遺傳操作時(shí)滿足“保持基因的長度不變，尾部只能出現(xiàn)終結(jié)符”的原則，因此，經(jīng)過遺傳操作后的子代染色體仍然是合法的。GEP區(qū)別于遺傳編程的一個(gè)特點(diǎn)是：GEP的一個(gè)染色體可以多次進(jìn)行不同的遺傳操作，也可以不進(jìn)行任何的遺傳操作。

GEP的遺傳算子包括：選擇、變異、倒串、插串(包括IS插串、RIS插串、基因插串)、重組(包括單點(diǎn)重組、兩點(diǎn)重組、基因重組)等算子[16]。對于組卷算法，只可用到變異和重組(單點(diǎn)重組、兩點(diǎn)重組)。

①變異。

在GEP中，變異是維持種群多樣性的主要方法，變異可以發(fā)生在染色體上的任何位置，染色體的變異過程如圖2所示，3-8位為尾部，變異位置用下劃線表示：

圖2 GEP染色體變異過程

②重組。

重組包括了單點(diǎn)重組、兩點(diǎn)重組和基因重組[17]。單點(diǎn)重組，顧名思義是在組卷染色體中尋找到兩個(gè)父代染色體，然后在兩個(gè)父代染色體中隨機(jī)選取一個(gè)交換位置，然后互相交換交換位置后面的染色體部分，從而形成兩個(gè)新的子代染色體。染色體的單點(diǎn)重組過程如圖3所示，3-8位為尾部，重組部分用下劃線表示。

圖3 GEP染色體單點(diǎn)重組過程

圖3中選擇父代1與父代2的4號基因位置為交換點(diǎn)，子代1是父代1交換父代2中的部分得到的，子代2是父代2交換父代1中的部分得到的。

兩點(diǎn)重組就是首先尋找到兩個(gè)組卷父代染色體，然后在兩個(gè)染色體上隨機(jī)選擇兩個(gè)交換位置，然后互相交換兩個(gè)位置間的部分，以達(dá)到產(chǎn)生兩個(gè)新的子代染色體的目的。染色體的兩點(diǎn)重組過程如圖4所示，3-8位為尾部，重組部分用下劃線表示。

圖4中子代1、子代2是父代1、父代2以2號位置和4號位置為重組點(diǎn)交換中間部分得到的。

4 仿真結(jié)果與分析

文中構(gòu)造了一個(gè)題目總數(shù)為1 000道題的題庫進(jìn)行實(shí)驗(yàn)，其中1～300題為選擇題，301～600題為填空題，601～800題為判斷題，801～1 000題為大題。

圖4 GEP染色體兩點(diǎn)重組過程

實(shí)驗(yàn)環(huán)境為：Windows7操作系統(tǒng)，CPU為i5-4210 M，內(nèi)存為4 G，使用python3.7編程實(shí)現(xiàn)。

程序中變異、單點(diǎn)重組、兩點(diǎn)重組的概率為P=(0.28,0.41,0.31)，則實(shí)驗(yàn)使用參數(shù)如表2所示。適應(yīng)度函數(shù)越接近1 000則得到的結(jié)果越好，當(dāng)適應(yīng)度函數(shù)為1 000時(shí)，達(dá)到最佳組卷效果。

表2 進(jìn)化中使用的參數(shù)

迭代次數(shù)與適應(yīng)度函數(shù)的變化如圖5所示。通過圖5可以看出，由于初始化種群時(shí)得到的種群比較理想，故開始時(shí)最佳適應(yīng)度函數(shù)就已經(jīng)在980～1 000的范圍內(nèi)波動，試卷的平均適應(yīng)度則在870～950的范圍內(nèi)波動，經(jīng)過496次迭代后，最佳適應(yīng)度函數(shù)達(dá)到1 000，即組卷達(dá)到最好效果。

通過試驗(yàn)輸出的試卷中的試題在題庫中的編號為[538，61，748，683，275，330，50，979，510，774，705，168，945，759，471，589，27，77，835，798，679，454，53，682，663，177，321，158，273，68，691，219，215，806]，也就是說這套試題符合給定的約束條件，該組卷算法成功地完成了組卷任務(wù)。

圖5 最佳適應(yīng)度與平均適應(yīng)度

5 結(jié)束語

通過試驗(yàn)驗(yàn)證，基于基因表達(dá)式編程算法的智能組卷算法在給定試卷約束條件的前提下，構(gòu)建出組卷問題的數(shù)學(xué)模型及相應(yīng)的適應(yīng)度函數(shù)，便可以很快地計(jì)算得到理想的結(jié)果，即滿足條件的試卷，能有效地防止“早熟”，且簡單快捷，具有較高的實(shí)用價(jià)值。