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

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

0 引言

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

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

1 遺傳算法解組卷問題

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

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

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

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

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

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

　　設(shè)組卷的題量要求為n，卷面分約束為G。采用分題型段編碼后對應(yīng)的題號分別為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)矩陣決定著試卷個體的優(yōu)劣。

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

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

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

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

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

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

　　采用標(biāo)準(zhǔn)遺傳算法的賭輪選擇、兩點(diǎn)交叉、單點(diǎn)變異和精英保留策略[7]。單點(diǎn)變異時選取與變異位置同題型的題目進(jìn)行變異替換。值得一提的是，交叉和變異操作可能導(dǎo)致個體出現(xiàn)重題。如下所示，父代個體P1、P2在位置3~7處進(jìn)行交叉，產(chǎn)生子代個體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個體出現(xiàn)了重題3，若繼續(xù)對S2在位置8進(jìn)行變異，取與13題同題型的12題進(jìn)行替換，變異后的S2也將出現(xiàn)重題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　表中數(shù)據(jù)表明，算法2對不同的組卷方案都能比算法1更快更好地收斂。特別對較復(fù)雜的約束參數(shù)，算法2的優(yōu)勢能得到更好的體現(xiàn)。如方案2中出現(xiàn)的知識點(diǎn)包含要求，算法2能比算法1更多地命中，如表2所示。再如方案4中的章節(jié)分布約束，由于課程3各章節(jié)題目在數(shù)據(jù)庫中存在比例較為均衡，面對組卷過程中常常出現(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é)論

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

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

參考文獻(xiàn)

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

　　[2] 李大輝.基于廣度優(yōu)先回溯算法的試題搜索算法[J].大慶石油學(xué)院學(xué)報，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é)報，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] 陳國良，王煦法，莊鎮(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é)報，2000，28（2）：31-34.