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

肖衡 龍草芳 潘玉霞

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

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

肖衡 龍草芳 潘玉霞

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

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

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

1 引言

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

2 遺傳算法簡述

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

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

2.1 編碼

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

2.2 選擇

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

2.3 交叉或重組基因

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

交叉有二進(jìn)制交叉、單點(diǎn)交叉、多點(diǎn)交叉、洗牌交叉等

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

2.4 變異

變異是隨機(jī)選擇種群中一個(gè)染色體,按一定概率進(jìn)行基因變異。

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

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

3 智能組卷算法研究

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

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

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

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

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

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

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

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

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

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

多個(gè)解中的某個(gè)候選解可以如下

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

0001 選擇 2 容易 差 1 2

…… …… … …… …… … …

0012 計(jì)算10 難 良 1 10

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

5 遺傳算法設(shè)計(jì)

5.1 確定編碼方案

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

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

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

5.3 確定遺傳算子

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

5.3.1 交叉算子

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

F1＝A11A12A13A14A15A16|B11B12B13B14B15|C11C12C13|D11D12

F2＝A21A22A23A24A25A16|B21B22B23B24B25|C21C22C23|D21D22

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

S1＝A11A12A13A14A25A26|B11B12B23B24B25|C11C12C23|D11D22

S2＝A21A22A23A24A15A16|B21B22B13B14B15|C21C22C13|D21D12

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

5.3.2 變異算子

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

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

6 實(shí)驗(yàn)數(shù)據(jù)

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

表1 變異率對(duì)算法的影響

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

7 結(jié)語

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

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

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

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

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

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

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

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