肖衡 龍草芳 潘玉霞

(三亞學(xué)院,海南三亞 572022)

遺傳算法在智能組卷中的實現(xiàn)

肖衡 龍草芳 潘玉霞

(三亞學(xué)院,海南三亞 572022)

遺傳算法是智能化考試系統(tǒng)的最常用的一種組卷算法。本文介紹了遺傳算法的特點及操作過程,依據(jù)組卷時各種約束建立了數(shù)學(xué)模型,提出使用改進的遺傳算法解決組卷中一些問題。最后以實驗證明,使用動態(tài)調(diào)整交叉概率和變異概率可避免遺傳算法的一些弊端。

智能組卷 遺傳算法 交叉算子 變異算子 適應(yīng)度

1 引言

隨著人工智能的發(fā)展和網(wǎng)絡(luò)的普及,無紙化考試系統(tǒng)已成為各種教育平臺的一大熱點。實現(xiàn)智能組卷,可以避免大量的重復(fù)勞力,提高工作效率。而要實現(xiàn)智能組卷主要在于組卷算法的研究。在組卷算法的設(shè)計中,試題庫系統(tǒng)的建設(shè)是非常重要的一個環(huán)節(jié),要想生成的試卷具有高質(zhì)量,在對題庫設(shè)計中對難度,總分,區(qū)分度,章節(jié)百分比,題型百分比,層次百分比等參數(shù)的設(shè)定非常重要。智能組卷是從題庫中隨機抽取題實現(xiàn)組合,其本質(zhì)是典型的多約束問題求解的過程。而想讓每次組卷的效率與質(zhì)量都盡量接近用戶的期望值,模擬自然進化過程群體搜索自適應(yīng)調(diào)整策略的遺傳算法能為多目標優(yōu)化提供非常合適的解決方案。

2 遺傳算法簡述

遺傳算法是一種并行的、能夠有效優(yōu)化的算法,以Morgan的基因理論及Eldridge與Gould間斷平衡理論為依據(jù),同時融合了Mayr的邊緣物種形成理論和Bertalanffv一般系統(tǒng)理論的一些思想,模擬達爾文的自然界遺傳學(xué):繼承(基因遺傳)、進化(基因突變)優(yōu)勝劣汰(優(yōu)的基因大量被遺傳復(fù)制,劣的基因較少被遺傳復(fù)制)。其實質(zhì)就是一種把自然界有機體的優(yōu)勝劣汰的自然選擇、適者生存的進化機制與同一群體中個體與個體間的隨機信息交換機制相結(jié)合的搜索算法。運用遺傳算法求解問題首先需將所要求解的問題表示成二進制編碼,然后根據(jù)環(huán)境進行基本的操作:選擇selection,交叉或重組基因crossover,變異mutation,適應(yīng)度函數(shù)fitness operation……這樣進行不斷的所謂“生存選擇”,最后收斂到一個最適應(yīng)環(huán)境條件的個體上,得到問題的最優(yōu)解。

遺傳算法求解過程的主要操作如下:

2.1 編碼

遺傳算法在求解過程,先將問題進行二進制編碼,形成基因型串結(jié)構(gòu)數(shù)據(jù),體現(xiàn)種群的多樣性,提高算法的搜索能力。該過程需要兩大問題,一是編碼的長短對數(shù)據(jù)精度和搜索空間的影響;二是選擇性的隨機特,造成局部搜索能力弱小的問題。

2.2 選擇

選擇是根據(jù)個體的相對適應(yīng)值,計算個體的再生次數(shù),確定系統(tǒng)重組或系統(tǒng)的交叉?zhèn)€體,選擇父代個體,產(chǎn)生子代個體。常用的系統(tǒng)選擇算法有輪盤賭選擇、隨機遍歷抽樣、局部選擇等。

2.3 交叉或重組基因

交叉操作是種群之間的交叉,隨機選擇兩個群體,隨機確定交叉處,按一定概率進行基因交換,再互換形成新的種群。

交叉有二進制交叉、單點交叉、多點交叉、洗牌交叉等

基因重組是結(jié)合繼承父代交配信息產(chǎn)生個體,常有離散重組、擴展性重組、中間重組、線性重組等。

2.4 變異

變異是隨機選擇種群中一個染色體,按一定概率進行基因變異。

2.5 適應(yīng)度函數(shù)

可以直接引用目標函數(shù)或是變異后的目標函數(shù)作為適應(yīng)度函數(shù),利用適應(yīng)度函數(shù)搜索空間內(nèi)的解,并計算個體的適應(yīng)度。

3 智能組卷算法研究

在智能組卷中,抽題樣本希望能合理全面考察學(xué)生的綜合能力,題型應(yīng)涉及幾個方面:題目、題型、章節(jié)覆蓋、區(qū)分度、難度系數(shù)、分值、時間。而要得出期望效果,事先需給出理想試卷的評估標準,以評估標準組成一個MxN的矩陣,將組卷問題變成求解空間的過程。在實踐證明中發(fā)現(xiàn),約束條件越多,要求越嚴格,組卷的難度就越大,而且過多的約束條件會降低組卷的成功率。一般情況組卷約束有:

K約束,知識點約束,涉及章節(jié)覆蓋和分值比例。

TP約束,題型約束,指明試卷中的題型,如選擇題、簡答題、判斷題等。

M約束,題數(shù)約束,表示該試卷中各題型的數(shù)量總和。

D約束,難度約束,針對考試對象選擇不同的難度。

Q約束,區(qū)分度約束,體現(xiàn)考生對知識掌握的水平的高低。

B約束,曝光度結(jié)束,控制試題反復(fù)出現(xiàn)的次數(shù)。

T約束,考試時間約束,一般與題量成正比。

4 組卷數(shù)學(xué)模型型

將以上七種約束結(jié)合起來構(gòu)建數(shù)學(xué)模型,在這些約束中找出若干個可行性解的過程就是組卷的過程。如果用n表示一套試卷的題數(shù),則mx7的矩陣表示一套試卷

多個解中的某個候選解可以如下

章節(jié) 題型 分值 難度 區(qū)分度次數(shù) 時間

0001 選擇 2 容易 差 1 2

…… …… … …… …… … …

0012 計算10 難 良 1 10

組卷是一個多目標規(guī)劃求解問題,如果將所有約束都考慮進去是不切實際的,約束過多,會影響遺傳算法的組卷效率,還可能找不到可行解。要盡量減少約束,縮小模型的維數(shù)。

5 遺傳算法設(shè)計

5.1 確定編碼方案

在遺傳算法中任何一種編碼方案都是為了更好地得到優(yōu)良種群。若采用二進制編碼,會使遺傳算法算子的操作簡單易用。但試題庫信息量較大時,染色體會過長,則會產(chǎn)生許多不利因素,需要改進編碼方案,采用十進制編碼。因而要根據(jù)種群的大小和多樣性來確定最優(yōu)的編碼方案。

5.2 確定適應(yīng)度函數(shù)

遺傳算法中評價個體的優(yōu)劣,是由適應(yīng)度值決定的。設(shè)計適應(yīng)度函數(shù)對各約束條件所產(chǎn)生的偏差進行記錄,適應(yīng)度值最高,種群越優(yōu)。通常在遺傳算法中引用權(quán)重對各約束條件進行不同側(cè)重點的定理分配,然后將各約束條件產(chǎn)生的實際偏差與各權(quán)重之積進行累加,來設(shè)計適應(yīng)度函數(shù)。

5.3 確定遺傳算子

遺傳算法選擇算子有許多種,選擇依據(jù)都是適應(yīng)度值,選擇適應(yīng)度值高的個體進入下一代。目前最經(jīng)典的是輪盤方式,輪盤任意旋轉(zhuǎn)后停下來時,指針所指區(qū)域則被選中。這種選擇算子中個體適應(yīng)度值越高,被選中的概率越高,能很好地保護優(yōu)良個體,將適應(yīng)度大的種群進行復(fù)制。

5.3.1 交叉算子

本文采用了段間交叉算子,也稱為群體內(nèi)交叉,表現(xiàn)為整個染色體多點交叉。由編碼方案中確定了每一種題型的染色體都是獨立的,假設(shè)A表示選擇題,則A11、A12、A13都是單選題,B、C、D分別表示填空題、判斷題、計算題。交叉之前隨機產(chǎn)生兩個父代個體,兩個父代個體進行段間交叉。假設(shè)兩個父代個體如下:

F1＝A11A12A13A14A15A16|B11B12B13B14B15|C11C12C13|D11D12

F2＝A21A22A23A24A25A16|B21B22B23B24B25|C21C22C23|D21D22

再隨機產(chǎn)生一個0到1之間的數(shù)字,當這個數(shù)字小于等于交叉概率時,確定交叉點。假設(shè)四種題型的交叉點分別是4、2、2、1,產(chǎn)生的子代則是:

S1＝A11A12A13A14A25A26|B11B12B23B24B25|C11C12C23|D11D22

S2＝A21A22A23A24A15A16|B21B22B13B14B15|C21C22C13|D21D12

為了保證種群數(shù)量不變,F1與S1,F2與S2分別進行比較,適應(yīng)度值高的保留,值低淘汰。

5.3.2 變異算子

變異操作是在種群中隨機選中一個變異位,將該位置的編碼取反,使算法具有局部隨楊搜索功能,增加群體多樣性。本文采用單個染色體單點變異。選隨機產(chǎn)生隨機數(shù),與變異概率進行比較,若小于等于變異概率則變異。假如該題是選中狀態(tài),變異后則變成未被選中,再隨機選取一個未被選中的置為選中狀態(tài)。

通常為避免遺傳算法中“早熟收斂”現(xiàn)象,加快搜索效率和防止局部最優(yōu),需要根據(jù)種群的遺傳進化情況來動態(tài)地調(diào)整交叉概率和變異概率。

6 實驗數(shù)據(jù)

將5個章節(jié)的500道題分別賦予各種特征值,給出生成試卷的要求,分別使用遺傳算法進行實驗。成批生成10套試卷,要求任兩套間的重復(fù)率不超過5%,每題被抽的最大次數(shù)是3次?？偡?00分,用時90分鐘,種群大小50,試卷區(qū)分度為0.5,難度0.5,最大迭代次數(shù)100,交叉率為0.6。(如表1)

表1 變異率對算法的影響

從實現(xiàn)結(jié)果看出變異率在0.002－0.004時,能產(chǎn)生適量的新個體,適當?shù)財U大解空間,得到的適應(yīng)度值最低,當變異率過小,不易產(chǎn)生新個體,過大,產(chǎn)生過多新個體,適應(yīng)度值偏大,容易丟失優(yōu)良個體。

7 結(jié)語

使用動態(tài)地調(diào)整交叉概率和變異概率,不僅能避免遺傳算法的“早熟早收斂”現(xiàn)象,在收斂速度、算法成功率和算法效率方面也具有一定的優(yōu)勢。

[1]賀榮,陳爽.在線組卷策略的研究與設(shè)計.計算機工程與設(shè)計,2011,32(6).

[2]虞耀君,等.基于遺傳算法的網(wǎng)絡(luò)考試系統(tǒng).計算機仿真,2010.

[3]楊秀梅.基于遺傳算法的組卷系統(tǒng)的研究[碩士學(xué)位論文].上海:上海交通大學(xué),2007.

[4]張超群,等.遺傳算法編碼方案比較.計算機應(yīng)用研究,2011年28卷3期.

[5]葛宇,梁靜.基于免疫遺傳算法的智能組卷系統(tǒng)設(shè)計.計算機應(yīng)用與軟件,2011,28(1).

專業(yè)智能性試題庫建設(shè)—以三亞學(xué)院為例(項目編號:Syxyjy120404)。三亞市院地科技合作項目(2012YD42)。

肖衡(1979－),女,碩士,三亞學(xué)院,講師,研究方向為計算機網(wǎng)絡(luò)與安全。龍草芳(1983－),女,碩士,三亞學(xué)院,助教,研究方向為計算機網(wǎng)絡(luò)與數(shù)據(jù)庫應(yīng)用。潘玉霞(1983－),碩士,三亞學(xué)院,講師,研究方向智能計算與應(yīng)用。