基于模擬退火遺傳算法的自動(dòng)組卷系統(tǒng)的研究

摘要:從題庫(kù)中抽出一組滿足多項(xiàng)要求的試題是一組合優(yōu)化問題，針對(duì)該問題，比較了目前幾種組卷的特點(diǎn)，提出把一種實(shí)數(shù)編碼的模擬退火遺傳算法應(yīng)用在自動(dòng)組卷問題中。為了對(duì)群體中每個(gè)個(gè)體進(jìn)行調(diào)整并改善單一遺傳算法的性能，該算法以遺傳算法流程作為主體流程，在主流程中嵌入模擬退火算法，與現(xiàn)有遺傳算法相比，該算法能較好地克服未成熟收斂現(xiàn)象，并且組卷的成功率和速度有明顯的提高。

關(guān)鍵詞:組合優(yōu)化;實(shí)數(shù)編碼;自動(dòng)組卷;模擬退火

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)11-2719-02

Research and Implementation on Composition Papers System Based on Improved Genetic Algorithms

CHEN Ying-qi， ZHAO Lei， DENG Lin

(Department of Computer， Aviation University of Air Force， Changchun 130022， China)

Abstract: Auto generating a test paper from a test database， which satisfies multiple requirements is a combinatorial optimization problem. The characteristics of some existing algorithms of auto generating a test paper is investigated and using a real code based simulating annealing genetic algorithm to address this problem is proposed. In order to adjust each individual of the group and improve the performance of a single genetic algorithm， the proposed algorithm combines the genetic algorithm with the simulating annealing method. Compared with the existing genetic algorithms， the proposed algorithm overcomes the premature convergence phenomenon more easily and it im-proves the success rate and the efficiency of auto generating a test paper as well.

Key words: combinatorial optimization; genetic algorithm; real code; test paper auto generation; simulating annealing

現(xiàn)在許多學(xué)校都已建立了試題庫(kù)，如何從試題庫(kù)中抽出一組同時(shí)滿足難度合理、知識(shí)點(diǎn)分布全面、時(shí)間合理等多項(xiàng)要求的試題組成一份科學(xué)的試卷是我們研究的問題。本文提出用融入模擬退火思想的遺傳算法進(jìn)行自動(dòng)組卷，能較好地克服遺傳算法的早熟問題，進(jìn)一步提高算法的搜索效率，并采用實(shí)數(shù)編碼方案，能更好地配合模擬退火遺傳算法的具體實(shí)現(xiàn)。

1 模擬退火遺傳算法的基本思想

模擬退火遺傳算法的基本思想遺傳算法(GA)是一種模擬自然選擇和遺傳變異機(jī)制的全局概率尋優(yōu)算法。通過對(duì)當(dāng)前群體實(shí)施選擇、交叉、變異等遺傳操作，產(chǎn)生下一代群體，逐步逼近最優(yōu)解狀態(tài)。

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

每個(gè)試題包含如下屬性信息:難度(I1)、認(rèn)知分類(I2)、章節(jié)知識(shí)點(diǎn)(I3)、分?jǐn)?shù)(I4)、時(shí)間(I5)，因此一道試題可由如下向量描述:Item=(I1，I2，I3，I4，I5)，而一份有m道試題的試卷將包含m個(gè)Item向量，可用如下矩陣表示:D=[Itemij](其中，i=1～m，j=1～5)。

組卷問題就是在題庫(kù)中尋找一組滿足難度、時(shí)間、知識(shí)點(diǎn)分布等多重條件約束的試題集，每一個(gè)約束條件都可以用一個(gè)基于以上二維矩陣的公式表示:①要滿足試卷的總分100分、整卷難度為d的公式為:;②時(shí)間為120分鐘:;③知識(shí)點(diǎn)為K的試題分值占總分的x%的約束條件:;④認(rèn)知分類為R的試題分值占總分的y%的約束條件為:。

3 基于模擬退火遺傳算法的組卷系統(tǒng)的設(shè)計(jì)

3.1 組卷系統(tǒng)的后臺(tái)數(shù)據(jù)庫(kù)設(shè)計(jì)

試題庫(kù)的結(jié)構(gòu)應(yīng)能很好地配合遺傳算法實(shí)現(xiàn)智能組卷。本系統(tǒng)中，每個(gè)科目對(duì)應(yīng)一個(gè)試題數(shù)據(jù)庫(kù)文件，科目題庫(kù)中再分題型建立對(duì)應(yīng)的表。表結(jié)構(gòu)中除了定義基本的表示試題內(nèi)容和答案的字段外，還增加用于參與組卷約束條件計(jì)算的試題屬性字段，如表示試題知識(shí)點(diǎn)分布、試題難度、估計(jì)所需時(shí)間等。

3.2 模擬退火遺傳組卷算法設(shè)計(jì)

3.2.1 染色體編碼

本系統(tǒng)用分段實(shí)數(shù)編碼，將一份試卷映射成一個(gè)染色體，避免了編碼和解碼的過程。有利于提高計(jì)算效率。假設(shè)用戶要求有n個(gè)題型，則采用n段編碼，m為各題型要抽取的試題題目，則各段編碼由m個(gè)元素組成，每個(gè)元素用被抽題目在試題庫(kù)中的試題序號(hào)表示。

3.2.2 初始群體的產(chǎn)生

標(biāo)準(zhǔn)遺傳算法的初始群體是完全隨機(jī)產(chǎn)生的，但完全由隨機(jī)函數(shù)產(chǎn)生隨機(jī)數(shù)序列往往分布不均勻，且易產(chǎn)生重復(fù)的隨機(jī)數(shù)，增加算法的復(fù)雜度。因此，本系統(tǒng)初始種群的產(chǎn)生用約瑟夫算法[3]進(jìn)行了改進(jìn)。

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

適應(yīng)度函數(shù)一般采用對(duì)各種約束條件進(jìn)行重要性的衡量，以求取綜合指標(biāo)誤差最小，可用如下公式表示:f(x)=1/(x+1)，其中，x表示第項(xiàng)指標(biāo)的重要性權(quán)重，表示第項(xiàng)指標(biāo)相對(duì)于組卷目標(biāo)的誤差的絕對(duì)值。根據(jù)實(shí)際組卷經(jīng)驗(yàn)，對(duì)不同的約束條件可給定不同的允許誤差(1%～5%)，只要試卷個(gè)體滿足第項(xiàng)組卷要求的誤差在容許范圍內(nèi)，即可認(rèn)為=0，這樣可加快搜索到合理解的速度。

3.2.4 遺傳操作

1) 選擇算子:采用最佳個(gè)體保存法和比例選擇法相結(jié)合的選擇方法。即在群體交叉、變異之前，先選出最佳個(gè)體，直接復(fù)制到下一代中;其余個(gè)體的選擇采用最基本的比例選擇法，即各個(gè)體被選擇的概率與其適應(yīng)度成比例。

2) 交叉和變異算子:簡(jiǎn)單遺傳算法的交叉和變異的概率均采用固定值，這并不利于進(jìn)化朝著有利于算法收斂的方向發(fā)展，所以本文采用了自適應(yīng)調(diào)整交叉概率和變異概率的方法，使概率隨著解的適應(yīng)值而自適應(yīng)地改變。

4 結(jié)束語

本文把結(jié)合了模擬退火思想的遺傳算法應(yīng)用在智能組卷系統(tǒng)中，針對(duì)具體問題設(shè)計(jì)了組卷問題的染色體編碼、適應(yīng)度函數(shù)和遺傳操作。所設(shè)計(jì)的組卷系統(tǒng)由于使用了混合的遺傳算法，能以較快的搜索速度獲得科學(xué)、滿意的試卷。

參考文獻(xiàn):

[1] 余有明.遺傳算法的編碼理論與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(3):86-89.

[2] 賈艷萍.一種應(yīng)用于負(fù)載均衡的模擬退火遺傳算法[J].空軍工程大學(xué)學(xué)報(bào):自然科學(xué)版，2007(2):59-62.

[3] 陳海山.josephus問題的算法設(shè)計(jì)與應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(1):61-64.