方俊

摘 要： 遺傳算法組卷存在收斂速度慢和未成熟收斂問(wèn)題，難以滿足考核要求。已有較多算法采用了分段編碼、分段進(jìn)化的策略，以降低算法的復(fù)雜度，提高算法的性能，但均未實(shí)現(xiàn)分段組卷，沒(méi)能從根本上提高算法的性能。為此提出分段偽并行組卷的方法，即：分段組成符合要求的試卷段，再組合成一份完整的符合用戶需求的試卷。實(shí)驗(yàn)證明，該方法能夠大大加快收斂速度，提高組卷質(zhì)量。

關(guān)鍵詞： 遺傳算法； 適應(yīng)度； 組卷； 種群多樣性； 偽并行

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）07-37-03

Abstract： There exist problems of slow convergence speed and premature convergence in genetic algorithm， making it hard to meet the inspection requirements. Hence the block coding， and segmented evolution strategy are adopted in many algorithms in order to reduce the complexity of the algorithm， and improve the performance of the algorithm. However， none of them can realize composing test paper piecewise. The performance of the algorithm is failed to fundamentally be improved. To solve the above problems， a method of pseudo-parallel group volume is proposed. Test paper is composed individually， and assembled into a complete test paper. It meets the demand of the users. Experiments show that this method can greatly speed up the convergence and improve the quality of composing test paper.

Key words： genetic algorithm； fitness value； composing test paper； diversity of population； pseudo-parallel

0 引言

隨著人工智能技術(shù)的發(fā)展，出現(xiàn)了基于智能的計(jì)算機(jī)輔助教學(xué)系統(tǒng)。智能組卷是智能計(jì)算機(jī)輔助教學(xué)系統(tǒng)的重要組成部分，它的研究目的是使計(jì)算機(jī)代替人工出卷。能否快速地組成科學(xué)的、合理的和具有隨機(jī)性的高質(zhì)量試卷取決于組卷算法的設(shè)計(jì)。20世紀(jì)80年代中后期，國(guó)內(nèi)外研究者根據(jù)組卷問(wèn)題的特點(diǎn)進(jìn)行了組卷算法的研究，相繼產(chǎn)生了多種組卷方法。其中具有代表性的有隨機(jī)抽題法、回溯試探法和遺傳算法等[1]。①隨機(jī)抽題法是根據(jù)組卷時(shí)定義的控制指標(biāo)，不斷從試題庫(kù)中隨機(jī)選取試題加入試卷中，直到組卷完成。該方法簡(jiǎn)單，單次運(yùn)行速度快，但成功率低。②回溯試探法的基本思想：判斷隨機(jī)抽取的試題是否滿足指定的約束條件，當(dāng)滿足約束條件時(shí)繼續(xù)向前搜索，并保存待生成試卷的狀態(tài)空間。當(dāng)組卷失敗時(shí)，則返回上次記錄，再按照預(yù)定策略進(jìn)行新的搜索試探，直到生成試卷或回到出發(fā)點(diǎn)為止。該方法組卷耗時(shí)長(zhǎng)，且內(nèi)存空間占用量也較大。③遺傳算法作為一種優(yōu)秀的算法，已在很多領(lǐng)域得到應(yīng)用，與傳統(tǒng)的搜索算法不同，它是模仿自然選擇和遺傳進(jìn)化過(guò)程來(lái)搜索最優(yōu)解，特別適于處理傳統(tǒng)的搜索方法無(wú)法解決的復(fù)雜問(wèn)題和非線性問(wèn)題。智能組卷是一種多目標(biāo)約束問(wèn)題[2]，受多種因素的影響，如總分、題型，每種題型的題量，每種題型所占的分值、時(shí)間、難度、區(qū)分度等，但遺傳算法利用適應(yīng)度值來(lái)指導(dǎo)搜索方向，使得采用遺傳算法解決多目標(biāo)約束的組卷問(wèn)題具有明顯的應(yīng)用優(yōu)勢(shì)。它具有所組試卷隨機(jī)性強(qiáng)，質(zhì)量高的特點(diǎn)，但由于約束條件多，易出現(xiàn)未成熟收斂和收斂慢，多個(gè)目標(biāo)方向在收斂速度上存在不一致的現(xiàn)象，容易向一個(gè)方向上側(cè)重。在采用遺傳算法進(jìn)行組卷時(shí)，較多算法采用了分段編碼、分段進(jìn)化的策略[3-4]，以降低算法的復(fù)雜度，提高算法的性能，但并未實(shí)現(xiàn)分段組卷，沒(méi)能從根本上提高算法的性能。本文提出分段偽并行組卷的方法，即按題型分段成子群體，各子群體獨(dú)立進(jìn)行遺傳進(jìn)化。按題型組成符合要求的試卷段，再將其組合成一份完整的符合用戶需求的試卷。由于各子群體的進(jìn)化計(jì)算是在同一臺(tái)計(jì)算機(jī)上串行進(jìn)行的，所以稱為偽并行遺傳算法。該算法由于簡(jiǎn)化了關(guān)系，使得進(jìn)化速度明顯提高，只需經(jīng)過(guò)幾代進(jìn)化即可取得符合用戶要求的試卷，而且精度也有較大的提高。

1 試題的屬性與試卷的約束條件

1.1 試題的屬性

1.2 試卷的約束條件

一份試卷往往要求同時(shí)滿足多個(gè)約束條件，但過(guò)多的約束條件增加了組卷的難度。本文采用分段偽并行組卷的方法，要求按題型分段組卷，按段組成滿足要求的試卷段，再組合成一份符合用戶要求的試卷。試卷及各段必須滿足下面的約束條件。

⑴ 試卷總分要求：試卷的各試題的分值之和與用戶設(shè)定的試卷總分相等。

⑵ 試卷難度要求：試卷的各段、整份試卷的難度值與用戶設(shè)定的試卷難度值相等。

⑶ 試卷區(qū)分度要求：試卷的各段、整份試卷的區(qū)分度值與用戶設(shè)定的試卷區(qū)分度值相等。

⑷ 考試時(shí)間：整份試卷的各試題的答題用時(shí)之和與用戶設(shè)定的試卷時(shí)長(zhǎng)相等。

⑸ 各題型題量：各題型中的題目數(shù)量與用戶設(shè)定的每種題型的題目數(shù)量相等。

⑹ 各題型所占的分值：各題型所占的分值與用戶設(shè)定的每種題型占試卷總分值的百分比相等。

⑺ 各題型答題用時(shí)：各題型答題用時(shí)與用戶設(shè)定的每種題型答題用時(shí)相等。

2 分段組卷偽并行遺傳算法

對(duì)于分段組卷偽并行遺傳算法，給出相應(yīng)的算法步驟。

步驟1 染色體編碼及種群初始化

編碼是應(yīng)用遺傳算法時(shí)首先需要解決的問(wèn)題，對(duì)于組卷來(lái)說(shuō)常用編碼的有兩種，基于二進(jìn)制的編碼[5]和基于實(shí)數(shù)的編碼[6]。與實(shí)數(shù)編碼相比， 二進(jìn)制編碼的搜索效率更高，且二進(jìn)制編碼具有操作簡(jiǎn)單易行，交叉、變異便于實(shí)現(xiàn)的特點(diǎn)，故本文采用二進(jìn)制編碼的方式。編碼按題型分段進(jìn)行，假設(shè)題庫(kù)中某一題型共有m道試題，則可用一個(gè)m位的二進(jìn)制串來(lái)表示，如果其中的題目被選中，則用“1”表示，未被選中，則用“0”表示。

初始化群體采用隨機(jī)方式產(chǎn)生。通常，種群規(guī)模將影響算法的性能，種群設(shè)置越大可以提供處理的模式越多，群體中個(gè)體多樣性越高，可以防止早熟收斂，但會(huì)增加計(jì)算量；種群設(shè)置過(guò)小則使遺傳算法的搜索空間受到限制，不能提供足夠的采樣點(diǎn)，一般可通過(guò)實(shí)驗(yàn)確定。

步驟4 選擇運(yùn)算

選擇是采用某一選擇策略挑選父代中的優(yōu)良個(gè)體進(jìn)行復(fù)制，以繁殖后代。選擇的方法有輪盤賭選擇、最優(yōu)保存策略、確定式采樣選擇、無(wú)回放隨機(jī)選擇、無(wú)回放余數(shù)隨機(jī)選擇、排序選擇、隨機(jī)聯(lián)賽選擇[9]。本文算法采用基于目標(biāo)函數(shù)值的排序選擇方法和最優(yōu)保存策略。選擇運(yùn)算在各題型段內(nèi)獨(dú)自進(jìn)行，將目標(biāo)函數(shù)值按照從小到大的順序排列，目標(biāo)函數(shù)值越小，所對(duì)應(yīng)的個(gè)體越優(yōu)良。本文選取前面20%的優(yōu)良個(gè)體直接復(fù)制進(jìn)入下一代。

分段選擇運(yùn)算相對(duì)于整條染色體的選擇運(yùn)算具有更高的性能。比如，一條染色體由于某一染色體段的目標(biāo)函數(shù)值偏大就可能被丟棄，不會(huì)被復(fù)制進(jìn)入下一代。而分段選擇只是將目標(biāo)函數(shù)值大的染色體段淘汰，其他目標(biāo)函數(shù)值小的染色體段將被復(fù)制進(jìn)入下一代，從而減少了無(wú)效迭代，能夠提高選擇運(yùn)算的效率。

步驟5 交叉運(yùn)算

交叉操作是遺傳算法中最主要的操作，是產(chǎn)生新的優(yōu)良個(gè)體的主要方法。交叉操作要求既不破壞染色體中基因的優(yōu)良性狀，又能有效地產(chǎn)生出一些好的新個(gè)體。常用的交叉方式有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉和算術(shù)交叉[9]。本文采用單點(diǎn)交叉，在各自的題型段內(nèi)，隨機(jī)選取兩個(gè)相互配對(duì)的染色體段，隨機(jī)確定交叉點(diǎn)，在交叉點(diǎn)位置后面部分字符串相互交換而形成二個(gè)新的染色體段。具體的交叉方式如下。

由于交叉操作后生成的新染色體段中所包含的“1”的個(gè)數(shù)可能發(fā)生改變，為了確保題型段內(nèi)所包含的題目數(shù)與用戶設(shè)定的一致，因此需要檢查字符串中所包含的“1”的個(gè)數(shù)。這里只檢查交叉點(diǎn)后“1”的數(shù)目是否改變，如果增加了就隨機(jī)選擇其中的“1”將其反轉(zhuǎn)為“0”，如果減少了就隨機(jī)選擇其中的“0”將其反轉(zhuǎn)為“1”，以保證在題型段內(nèi)所包含的題目數(shù)與用戶設(shè)定一致。本文采用雜交產(chǎn)生子代60%的新個(gè)體。

步驟6 變異運(yùn)算

遺傳算法中的變異算子是生物體進(jìn)化過(guò)程中染色體上的基因位發(fā)生突變的現(xiàn)象，它使染色體的結(jié)構(gòu)和性狀發(fā)生改變。它能改善遺傳算法的局部搜索能力和維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。在遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子，對(duì)于二進(jìn)制編碼而言，變異操作就是把某些基因位的值取反[9]。具體是在各題型段內(nèi)隨機(jī)確定變異點(diǎn)的位置，將其值取反。如果是“0”變?yōu)椤?”，則該題型段的題目數(shù)量增加了1題，因此需要隨機(jī)選取其他位置的“1”將其變?yōu)椤?”以保持該題型的題目數(shù)量與用戶設(shè)定的數(shù)量一致。如果是“1”變?yōu)椤?”，則該題型段的題目數(shù)量減少了1題，因此需要隨機(jī)選取該段其他位置的“0”值將其變?yōu)椤?”以保持該題型的題目數(shù)量與用戶設(shè)定的數(shù)量一致。實(shí)際編程可以隨機(jī)選取一個(gè)“1”和一個(gè)“0”，再分別變?yōu)椤?”和“1”，本文采用變異產(chǎn)生子代20%的新個(gè)體。

在執(zhí)行完以上步驟后，返回到第2步驟，對(duì)個(gè)體進(jìn)行評(píng)價(jià)。如果滿足終止條件，即可輸出結(jié)果；如果不滿足終止條件，則繼續(xù)向下執(zhí)行，循環(huán)往復(fù)，使各染色體段向最優(yōu)解方向移動(dòng)，從而使整條染色體逐漸接近最優(yōu)解。

3 實(shí)驗(yàn)條件和結(jié)果

表2數(shù)據(jù)為本文方法與排序方法的比較，此處的排序算法與本文算法惟一的不同是未采用偽并行的計(jì)算策略，其他條件相同。從表2可以看出，組卷50次，采用分段組卷偽并行遺傳算法時(shí)，在組卷約束條件較多的情況下，本文算法迭代次數(shù)明顯減少，算法的效率有了較大的提高。

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

組卷是一個(gè)多目標(biāo)約束問(wèn)題，由于約束條件多、題量大，用原始遺傳算法進(jìn)行組卷易出現(xiàn)未成熟收斂和收斂速度慢問(wèn)題。本文給出分段組卷偽并行遺傳算法，對(duì)于約束條件多的組卷問(wèn)題，采用分段組成符合要求的試卷段，再組合成一份完整的符合用戶需求的試卷，該方法有明顯的優(yōu)勢(shì)。在進(jìn)化過(guò)程中，利用目標(biāo)函數(shù)值排序的選擇方法和最優(yōu)保存策略，保證了優(yōu)質(zhì)個(gè)體能夠被復(fù)制進(jìn)入下一代。利用較大的雜交、變異概率補(bǔ)充新個(gè)體，保持了種群多樣性。對(duì)在雜交、變異運(yùn)算過(guò)程中所引起的題目數(shù)量的變化進(jìn)行檢查，并進(jìn)行處理，使其與用戶設(shè)定的數(shù)量相等。實(shí)驗(yàn)證明，分段偽并行遺傳算法能夠大大加快收斂速度，提高組卷質(zhì)量，并可同時(shí)生成多份滿足要求的試卷。

參考文獻(xiàn)：

[1] 彭雪蓮.基于多策略改進(jìn)遺傳算法的智能組卷研究[D].廣西大學(xué)，2010.

[2] 張琨，楊會(huì)菊，宋繼紅，趙學(xué)龍.基于遺傳算法的自動(dòng)組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué)，2012.5（34）：178-183

[3] 魏平熊，偉清.用遺傳算法解組卷問(wèn)題的設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2002.4：48-50

[4] 孟朝霞.基于自適應(yīng)免疫遺傳算法的智能組卷[J].計(jì)算機(jī)工程，2008.34（18）：203-205

[5] 于淼，王日宏.改進(jìn)遺傳算法在智能組卷中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2008.44（25）：236-238

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

[7] 饒樂(lè)三，王曉柳.教育統(tǒng)計(jì)學(xué)[M].南京大學(xué)出版社，1990.

[8] 魯萍，王玉英.多約束分級(jí)尋優(yōu)結(jié)合預(yù)測(cè)計(jì)算的智能組卷策略[J].計(jì)算機(jī)應(yīng)用，2013.33（2）.

[9] 陳國(guó)良，王煦法，莊鎮(zhèn)泉，王東生.遺傳算法及其應(yīng)用[M].人民郵電出版社，2001.