遺傳算法在智能組卷中的實現

肖衡 龍草芳 潘玉霞

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

遺傳算法在智能組卷中的實現

肖衡 龍草芳 潘玉霞

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

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

智能組卷 遺傳算法 交叉算子 變異算子 適應度

1 引言

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

2 遺傳算法簡述

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

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

2.1 編碼

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

2.2 選擇

選擇是根據個體的相對適應值,計算個體的再生次數,確定系統重組或系統的交叉個體,選擇父代個體,產生子代個體。常用的系統選擇算法有輪盤賭選擇、隨機遍歷抽樣、局部選擇等。

2.3 交叉或重組基因

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

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

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

2.4 變異

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

2.5 適應度函數

可以直接引用目標函數或是變異后的目標函數作為適應度函數,利用適應度函數搜索空間內的解,并計算個體的適應度。

3 智能組卷算法研究

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

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

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

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

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

Q約束,區分度約束,體現考生對知識掌握的水平的高低。

B約束,曝光度結束,控制試題反復出現的次數。

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

4 組卷數學模型型

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

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

章節 題型 分值 難度 區分度次數 時間

0001 選擇 2 容易 差 1 2

…… …… … …… …… … …

0012 計算10 難 良 1 10

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

5 遺傳算法設計

5.1 確定編碼方案

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

5.2 確定適應度函數

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

5.3 確定遺傳算子

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

5.3.1 交叉算子

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

F1＝A11A12A13A14A15A16|B11B12B13B14B15|C11C12C13|D11D12

F2＝A21A22A23A24A25A16|B21B22B23B24B25|C21C22C23|D21D22

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

S1＝A11A12A13A14A25A26|B11B12B23B24B25|C11C12C23|D11D22

S2＝A21A22A23A24A15A16|B21B22B13B14B15|C21C22C13|D21D12

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

5.3.2 變異算子

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

通常為避免遺傳算法中“早熟收斂”現象,加快搜索效率和防止局部最優,需要根據種群的遺傳進化情況來動態地調整交叉概率和變異概率。

6 實驗數據

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

表1 變異率對算法的影響

從實現結果看出變異率在0.002－0.004時,能產生適量的新個體,適當地擴大解空間,得到的適應度值最低,當變異率過小,不易產生新個體,過大,產生過多新個體,適應度值偏大,容易丟失優良個體。

7 結語

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

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

[2]虞耀君,等.基于遺傳算法的網絡考試系統.計算機仿真,2010.

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

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

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

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

肖衡(1979－),女,碩士,三亞學院,講師,研究方向為計算機網絡與安全。龍草芳(1983－),女,碩士,三亞學院,助教,研究方向為計算機網絡與數據庫應用。潘玉霞(1983－),碩士,三亞學院,講師,研究方向智能計算與應用。