摘  要： 針對(duì)遺傳算法組卷易陷入早熟、難以收斂的問(wèn)題進(jìn)行研究，結(jié)合進(jìn)化環(huán)境對(duì)進(jìn)化過(guò)程的影響和引導(dǎo)，對(duì)動(dòng)態(tài)進(jìn)化環(huán)境進(jìn)行建模，提出了一種基于動(dòng)態(tài)變異池的策略。該策略的種群不共享變異池，在每次變異前，根據(jù)每個(gè)個(gè)體的弱點(diǎn)動(dòng)態(tài)生成該個(gè)體的變異基因庫(kù)，以此改善當(dāng)前變異環(huán)境，實(shí)施引導(dǎo)性變異，提高解質(zhì)量。該策略能加速收斂，并在很大程度上提高收斂精度。實(shí)驗(yàn)數(shù)據(jù)表明，采用了該策略的組卷算法能快速生成各項(xiàng)指標(biāo)都與約束條件十分貼近的試卷，具有很好的實(shí)用價(jià)值。

　　關(guān)鍵詞： 組卷；進(jìn)化環(huán)境；遺傳算法；動(dòng)態(tài)變異池；收斂精度；題庫(kù)系統(tǒng)

0 引言

　　隨著信息技術(shù)的不斷發(fā)展應(yīng)用，考試模式將面臨著巨大的變化。在線學(xué)習(xí)、考試系統(tǒng)層出不窮，如何自動(dòng)實(shí)時(shí)地從題庫(kù)中隨機(jī)抽取合適的試題是這類(lèi)系統(tǒng)要解決的首要問(wèn)題，同時(shí)這也是一個(gè)多約束的NP難題。目前常用的組卷方法主要有隨機(jī)抽取法、回溯試探法、最大權(quán)法和遺傳算法[1-6]。其中，遺傳算法[7-8]因其內(nèi)在并行性和全局尋優(yōu)能力被廣泛應(yīng)用于傳統(tǒng)搜索方法難于解決的非線性、多約束等復(fù)雜問(wèn)題。

　　然而，實(shí)際應(yīng)用中發(fā)現(xiàn)，遺傳算法生成試卷經(jīng)常會(huì)出現(xiàn)早熟、收斂慢等問(wèn)題，特別是當(dāng)試卷約束較復(fù)雜時(shí)，算法會(huì)更加難以收斂，其結(jié)果往往是生成試卷的時(shí)間長(zhǎng)、與客戶要求的偏差大等。為解決這些問(wèn)題，本文對(duì)動(dòng)態(tài)進(jìn)化環(huán)境進(jìn)行設(shè)計(jì)和建模，提出了一種稱(chēng)為動(dòng)態(tài)變異池的策略，該策略一方面監(jiān)測(cè)試卷性能指標(biāo)；另一方面根據(jù)試卷性能指標(biāo)監(jiān)測(cè)結(jié)果，結(jié)合客戶偏好，為每個(gè)個(gè)體生成不同的變異池實(shí)施引導(dǎo)性變異。實(shí)驗(yàn)表明，動(dòng)態(tài)變異池策略能加速收斂，提高收斂精度，生成滿意度比較高的試卷。

1 遺傳算法解組卷問(wèn)題

　　1.1 編碼設(shè)計(jì)

　　采用分題型段編碼。取題號(hào)為染色體基因，一張?jiān)嚲淼念}目數(shù)量決定了試卷個(gè)體的染色體長(zhǎng)度。同時(shí)對(duì)染色體進(jìn)行分段，一個(gè)題型對(duì)應(yīng)一段，段的長(zhǎng)度即根據(jù)題型約束計(jì)算而來(lái)的每種題型的題目數(shù)量。

　　分題型段編碼有以下兩點(diǎn)好處：

　　（1）編碼長(zhǎng)度適中，進(jìn)化過(guò)程快。

　?。?）個(gè)體初始即滿足題型題量和卷面分約束，這使得試卷個(gè)體具有“合法性”，并且這種“合法性”不會(huì)被進(jìn)化操作所打亂，無(wú)論如何交叉和變異，個(gè)體均能滿足題型題量的約束。

　　1.2 適應(yīng)度函數(shù)設(shè)計(jì)

　　設(shè)組卷的題量要求為n，卷面分約束為G。采用分題型段編碼后對(duì)應(yīng)的題號(hào)分別為m1、m2、m3、…、mn。根據(jù)組卷的各項(xiàng)約束參數(shù)為每張?jiān)嚲斫×6的目標(biāo)狀態(tài)矩陣A=[A1 A2 A3 A4 A5 A6]，如式（1）所示，該目標(biāo)狀態(tài)矩陣決定著試卷個(gè)體的優(yōu)劣。

　　其中，A1為題目分?jǐn)?shù)指標(biāo)，A2為課程指標(biāo)，A3為難度指標(biāo)，A4為章節(jié)指標(biāo)，A5為知識(shí)點(diǎn)指標(biāo)，A6為已抽過(guò)的頻度指標(biāo)。

　　可用式（2）計(jì)算第j門(mén)課程實(shí)際所占比例與理想百分比的誤差：

　　其中，IPcj為第j門(mén)課程所占試卷總分的理想百分比，ai1為第i道題的分值。如果ai2為第j門(mén)課程，則δij為1，否則為0。式（2）還可以用來(lái)計(jì)算難度約束誤差和章節(jié)約束誤差?？捎檬剑?）來(lái)計(jì)算試卷是否命中第j號(hào)知識(shí)點(diǎn)的誤差：

　　其中，Nk為總共需要命中的知識(shí)點(diǎn)個(gè)數(shù)；IPkj為j號(hào)知識(shí)點(diǎn)的理想比例，一般為1/NK。如果ai5為j號(hào)知識(shí)點(diǎn)，則δij=1，否則δij=0。另外，組卷時(shí)，為保障隨機(jī)性和多樣化，盡可能每次能夠優(yōu)先抽取被抽中次數(shù)較少的“新鮮”題，可以用式（4）來(lái)計(jì)算整張?jiān)嚲淼男迈r程度：

　　其中，ai6為mi已被抽中的次數(shù)，min和max為題庫(kù)中的題被抽中最少和最多的次數(shù)。設(shè)所有誤差之和為E，適應(yīng)度函數(shù)可表示為1/（E+1）。如有其他的約束，也可計(jì)算之后加入總計(jì)誤差E中。誤差越小，適應(yīng)值越大，表明試卷個(gè)體與理想試卷偏差越小，競(jìng)爭(zhēng)能力越強(qiáng)。

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

　　采用標(biāo)準(zhǔn)遺傳算法的賭輪選擇、兩點(diǎn)交叉、單點(diǎn)變異和精英保留策略[7]。單點(diǎn)變異時(shí)選取與變異位置同題型的題目進(jìn)行變異替換。值得一提的是，交叉和變異操作可能導(dǎo)致個(gè)體出現(xiàn)重題。如下所示，父代個(gè)體P1、P2在位置3~7處進(jìn)行交叉，產(chǎn)生子代個(gè)體S1、S2。

　　P1=3 5 |1 6 9 10 12| 15 18 19

　　P2=2 4 |3 7 9 11 10| 13 19 20

　　S1=3 5 |3 7 9 11 10| 15 18 19

　　S2=2 4 |1 6 9 10 12| 13 19 20

　　交叉以后，S1個(gè)體出現(xiàn)了重題3，若繼續(xù)對(duì)S2在位置8進(jìn)行變異，取與13題同題型的12題進(jìn)行替換，變異后的S2也將出現(xiàn)重題。

　　對(duì)于重題現(xiàn)象，一般有兩種處理方法：進(jìn)化操作后檢查子代個(gè)體是否有重題并進(jìn)行簡(jiǎn)單替換[9]；或者放棄本次進(jìn)化，重新進(jìn)化[10]。這兩種處理方式都將耗費(fèi)大量時(shí)間。本文的處理是在整個(gè)進(jìn)化迭代結(jié)束后只對(duì)最優(yōu)解進(jìn)行重題優(yōu)化。所謂重題優(yōu)化是指找到與重題同題型并且各項(xiàng)約束指標(biāo)最接近的題去替換重題，將去重題操作對(duì)個(gè)體適應(yīng)度的影響減到最小。重題優(yōu)化策略比前兩種處理方式更節(jié)省進(jìn)化時(shí)間，并且在題庫(kù)規(guī)模越大時(shí)優(yōu)勢(shì)更明顯[11]。

2 動(dòng)態(tài)進(jìn)化環(huán)境建模

　　“孟母三遷”的故事告訴人們環(huán)境因素不容忽視，同樣，源于生物進(jìn)化的遺傳算法也不能忽視進(jìn)化環(huán)境的影響。組卷問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，其約束很多，若忽略進(jìn)化環(huán)境的引導(dǎo)性作用，進(jìn)化過(guò)程會(huì)顯得異常緩慢，其結(jié)果是出現(xiàn)早熟現(xiàn)象并且最優(yōu)解的質(zhì)量無(wú)法達(dá)標(biāo)。表現(xiàn)在具體應(yīng)用上，生成的試卷可能會(huì)與用戶要求存在嚴(yán)重的偏差，比如某次生成試卷要求某重點(diǎn)章節(jié)占總題量的30%，然而實(shí)際抽出的題卻只占5%，這樣一些非重點(diǎn)章節(jié)（如選學(xué)章節(jié)）卻抽出了嚴(yán)重過(guò)剩的題，這樣的偏差是用戶無(wú)法接受的，考生也無(wú)法適應(yīng)。當(dāng)組卷約束比較苛刻時(shí)，這種偏差會(huì)更明顯。

　　進(jìn)化環(huán)境對(duì)進(jìn)化過(guò)程的影響主要體現(xiàn)在“優(yōu)勝劣汰”和“基因突變”上，可歸結(jié)為偏好一詞。歸根結(jié)底，這會(huì)指引進(jìn)化個(gè)體產(chǎn)生和保留更好的基因。伴隨進(jìn)化過(guò)程的進(jìn)行，這種偏好也在動(dòng)態(tài)變化著，該如何對(duì)動(dòng)態(tài)的偏好信息進(jìn)行建模，引導(dǎo)進(jìn)化過(guò)程更快地找到缺失基因呢？

　　改進(jìn)變異算子的研究源于變異算子在進(jìn)化計(jì)算中起主導(dǎo)作用的認(rèn)識(shí)[12]。遺傳算法進(jìn)行組卷具有全局收斂性，但也有一定概率的不穩(wěn)定性，特別是當(dāng)組卷約束參數(shù)比較復(fù)雜和苛刻時(shí)，這種不穩(wěn)定的概率就會(huì)增加。造成不穩(wěn)定性的主要原因之一是有效基因的缺失，變異可有效解決這一問(wèn)題。

　　目前應(yīng)用的遺傳算法的變異池是通用的，一般直接選取可用題庫(kù)作為變異池。在組卷約束參數(shù)較為復(fù)雜時(shí)，這種通用變異池就會(huì)放慢有效基因恢復(fù)的步伐。為此，對(duì)變異算子做出改進(jìn)，在每次變異前先改善當(dāng)前的變異環(huán)境，設(shè)計(jì)了動(dòng)態(tài)變異池策略，使每次變異都會(huì)產(chǎn)生比父輩更優(yōu)秀的個(gè)體。

　　動(dòng)態(tài)變異池的具體建模過(guò)程如下：

　　（1）取通用變異池（可用題集）作為舊變異池。

　?。?）根據(jù)組卷約束參數(shù)計(jì)算并記錄當(dāng)前個(gè)體嚴(yán)重缺失的基因。具體為：依次取約束參數(shù)（如章節(jié)約束），計(jì)算當(dāng)前試卷與該類(lèi)約束各項(xiàng)指標(biāo)的實(shí)際誤差，即計(jì)算該試卷各章節(jié)比例相對(duì)于約束參數(shù)要求的各章節(jié)比例的實(shí)際誤差，并記錄實(shí)際誤差最大的指標(biāo)項(xiàng)（章節(jié)編號(hào)）。

　　（3）重復(fù)步驟（2），直至各類(lèi)約束都計(jì)算完畢。

　?。?）生成空的新變異池。

　　（5）根據(jù)步驟（2）、（3）中記錄的指標(biāo)項(xiàng)集合，對(duì)當(dāng)前變異池進(jìn)行優(yōu)化。依次從舊變異池中挑出屬于該指標(biāo)項(xiàng)的題集加入到新的變異池中。每次挑選不改變舊變異池的內(nèi)容。

　?。?）重復(fù)步驟（5），直至所有指標(biāo)項(xiàng)都處理完畢，當(dāng)前試卷“急缺基因庫(kù)”形成，即當(dāng)前個(gè)體此次變異的新變異池生成。

　　這種每個(gè)個(gè)體每次變異前都根據(jù)個(gè)體的缺點(diǎn)重新生成變異池的策略稱(chēng)為動(dòng)態(tài)變異池策略。這樣一來(lái)，算法的變異池很大程度上引導(dǎo)著變異朝著好的方向進(jìn)行，從而改進(jìn)個(gè)體質(zhì)量，加速收斂。

　　需重點(diǎn)說(shuō)明的是，動(dòng)態(tài)變異池的生成過(guò)程中，對(duì)舊變異池的每次篩選都不能改變舊變異池的內(nèi)容，這使得同時(shí)具有多個(gè)有效基因的題有可能重復(fù)進(jìn)入變異池，增加被選中的概率，即增加了缺失的有效基因進(jìn)入下一代的概率。實(shí)驗(yàn)表明，這能有效強(qiáng)化缺失基因，加大搜索力度和精度。

3 實(shí)驗(yàn)

　　對(duì)采用通用變異池的遺傳算法（算法1）和采用動(dòng)態(tài)變異池的遺傳算法（算法2）進(jìn)行實(shí)驗(yàn)對(duì)比，兩個(gè)算法均采用了重題優(yōu)化策略[11]。數(shù)據(jù)庫(kù)總題量為10 977，題型15種，難度級(jí)別5個(gè)。根據(jù)多次實(shí)驗(yàn)，算法進(jìn)化代數(shù)設(shè)置為2倍題量約束，下限為100，種群規(guī)模設(shè)置為2倍題量約束，下限為200。表1~表4為兩種遺傳算法按4組方案運(yùn)行10次所得的平均性能詳細(xì)對(duì)比。4組方案涉及3門(mén)課程，其中課程1（方案1）的題量為  1 773，課程2（方案2）的題量為1 424，課程3（方案3和方案4）的題量為1 811。

　　表中數(shù)據(jù)表明，算法2對(duì)不同的組卷方案都能比算法1更快更好地收斂。特別對(duì)較復(fù)雜的約束參數(shù)，算法2的優(yōu)勢(shì)能得到更好的體現(xiàn)。如方案2中出現(xiàn)的知識(shí)點(diǎn)包含要求，算法2能比算法1更多地命中，如表2所示。再如方案4中的章節(jié)分布約束，由于課程3各章節(jié)題目在數(shù)據(jù)庫(kù)中存在比例較為均衡，面對(duì)組卷過(guò)程中常常出現(xiàn)的各章節(jié)要求比例偏頗的情況，一般算法很難得到與要求比例很貼近的解，但如表4所示，算法2找到的最優(yōu)解滿意程度很高，不僅章節(jié)比例，其他各項(xiàng)指標(biāo)都與試卷約束參數(shù)很貼近，并且效率比算法1好。

　　目前該策略已經(jīng)集成于主要用于期考出卷的教務(wù)助手系統(tǒng)，運(yùn)行穩(wěn)定，經(jīng)統(tǒng)計(jì)，50道題最差10 s能完成組卷，100道最差30 s能完成組卷，且抽取試卷質(zhì)量好，滿意度高。

4 結(jié)論

　　試卷自動(dòng)生成問(wèn)題是一個(gè)多約束優(yōu)化問(wèn)題，同時(shí)也是一個(gè)NP難問(wèn)題，它的約束參數(shù)很難用數(shù)學(xué)形式表達(dá)，所以傳統(tǒng)算法無(wú)法對(duì)其求解，遺傳算法因其優(yōu)秀的搜索能力廣泛應(yīng)用于求解這類(lèi)問(wèn)題。為克服遺傳算法易陷入早熟、難以收斂的問(wèn)題，本文提出了基于動(dòng)態(tài)變異池的遺傳算法，該算法已經(jīng)集成于教務(wù)系統(tǒng)運(yùn)行，實(shí)驗(yàn)數(shù)據(jù)表明，加入了進(jìn)化環(huán)境和偏好設(shè)計(jì)的遺傳算法具有更好的魯棒性和收斂性，能更早更好地找到滿足條件的最優(yōu)解，并在很大程度上提高求解精度，加速算法收斂，具有很好的實(shí)用價(jià)值。

　　基于動(dòng)態(tài)變異池的研究只是基于環(huán)境的進(jìn)化算法的一個(gè)小的著眼點(diǎn)，研究更復(fù)雜的進(jìn)化環(huán)境從而避免算法陷入局部最優(yōu)，跳出進(jìn)化停滯是日后工作一個(gè)重要的開(kāi)展方向。另外，如何一次產(chǎn)生n套高質(zhì)量的不重復(fù)的試卷也是一個(gè)重要的后續(xù)實(shí)驗(yàn)課題。

參考文獻(xiàn)

　　[1] 龔?fù)耆?基于最小回溯代價(jià)的智能組卷算法[D].長(zhǎng)沙：湖南大學(xué)，2005.

　　[2] 李大輝.基于廣度優(yōu)先回溯算法的試題搜索算法[J].大慶石油學(xué)院學(xué)報(bào)，2006，30（3）：100-102.

　　[3] 金漢均，鄭世玨，吳明武.分段隨機(jī)抽選法在智能組卷中的研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2003，20（9）：102-126.

　　[4] Yan Song， Yang Guoxing. Item bank system and the test paper generation algorithm[C]. 2012 7th International Conference on Computer Science & Education（ICCSE）， IEEE， 2012：491-495.

　　[5] 尹常治，楊皓，趙立族.最大權(quán)法試卷組卷算法[J].工程圖學(xué)學(xué)報(bào)，2004，25（3）：106-110.

　　[6] Huang Wei， Wang Zhaohui. Design of examination paper generating system from item bank by using genetic algorithm[C]. International Conference on Computer Science and Software Engineering（CSSE）， Wuhan， 2008：1323-1325.

　　[7] 陳國(guó)良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

　　[8] 鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2007.

　　[9] 黃寶玲.自適應(yīng)遺傳算法在智能組卷中的應(yīng)用[J].計(jì)算機(jī)工程，2011，14（37）：161-163.

　　[10] 周艷聰，劉艷柳，顧軍華.小生境自適應(yīng)遺傳模擬退火智能組卷策略研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32（2）：323-327.

　　[11] 肖桂霞，趙武初，朱偉，等.基于遺傳算法智能組卷的去重題方法[J].計(jì)算機(jī)工程，2012，11（38）：150-152.

　　[12] 霍紅衛(wèi)，許進(jìn)，保錚.選擇和變異算子的作用分析[J].電子學(xué)報(bào)，2000，28（2）：31-34.