肖桂霞（常德職業(yè)技術(shù)學(xué)院　現(xiàn)代教育技術(shù)中心，湖南　常德 415000）

動(dòng)態(tài)進(jìn)化環(huán)境在組卷中的建模與應(yīng)用

肖桂霞
（常德職業(yè)技術(shù)學(xué)院現(xiàn)代教育技術(shù)中心，湖南常德 415000）

針對(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à)值。

組卷；進(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ò)程快。

（2）個(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=［A1A2A3A4A5A6］，如式（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）取通用變異池（可用題集）作為舊變異池。

（2）根據(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ì)算完畢。

（4）生成空的新變異池。

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

（6）重復(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。

表1　組卷約束為方案1的兩種遺傳算法性能對(duì)比表

表2　組卷約束為方案2的兩種遺傳算法性能對(duì)比表

表3　組卷約束為方案3的兩種遺傳算法性能對(duì)比表

表4　組卷約束為方案4的兩種遺傳算法性能對(duì)比表

表中數(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)課題。

［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.

Modeling and application of dynamic evolutionary environment in test paper generating problem

Xiao Guixia
（Modern Education Technology Center，Changde Vocational Technical College，Changde 415000，China）

Consideringtheeffectsandguidanceofenvironmentontheevolutionaryprocess，thedynamicevolutionary environment is modeled and a Dynamic Mutation Pool（DMP）method is proposed to overcome premature and slow convergence defects of genetic algorithms when generating a test paper intelligently.In DMP，the mutation pool of the population is not shareable. Every individual has its own mutation pool，and it is generated dynamically according to the performance before each mutation operation.DMP can improve the mutation environment，thus it significantly improves the quality of solutions，and further enhances the convergence of the algorithm.The comparative experiment shows that an algorithm which adopts this dynamic mutation strategy can generate a satisfying test paper quickly.

test paper generating；evolutionary environment；genetic algorithms；Dynamic Mutation Pool（DMP）；convergent accuracy；item bank system

TP391.9；TP301.6

A

1674-7720（2015）02-0077-03

（2014-08-28）

肖桂霞（1983），通信作者，女，碩士，高級(jí)工程師，主要研究方向：進(jìn)化計(jì)算，智能算法，E-mail：89714262@qq.com。