改進(jìn)遺傳算法在自動組卷中的應(yīng)用

1、改進(jìn)遺傳算法在自動組卷中的應(yīng)用摘要：針對傳統(tǒng)遺傳算法在種群編碼方案、初始種群生成、動態(tài)概率、多點(diǎn)交叉操作等方面做了一些改進(jìn)，改進(jìn)后的算法明顯提高了組卷的成功率和收斂速度，取得了滿意的組卷效果。關(guān)鍵詞：遺傳算法；自動組卷；適應(yīng)度；約束0引言隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，在線考試模式日趨成熟，計算機(jī)自動組卷成為一個熱點(diǎn)問題。如何快速生成最大程度滿足用戶的不同需要，并具有隨機(jī)性、科學(xué)性、合理性，這涉及到一個在題庫中尋優(yōu)和收斂速度的問題。遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它是用來解決多約束條件下的最優(yōu)問題。遺傳算法提供了一種求解復(fù)雜系統(tǒng)

2、優(yōu)化問題的通用框架。它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。1遺傳算法的基本操作遺傳算法有3個基本操作：選擇操作、交叉操作、變異操作。這些操作又有各不相同的方法來實現(xiàn)。（1）選擇操作。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇過程的第一步是計算適應(yīng)度，個體選擇概率的常用計算方法有：按比例的適應(yīng)度計算，基于排序的適應(yīng)度計算。適應(yīng)度計算之后是進(jìn)行選擇操作，按照適應(yīng)度進(jìn)行父代個體的選擇?？梢赃x擇的算法有：輪盤賭選擇、隨機(jī)遍歷抽樣、錦標(biāo)賽選擇、截斷選擇、局部選擇。（2）交叉操作。交叉是把兩個父個體的部分結(jié)構(gòu)加以替換重組而

3、生成新個體的操作。根據(jù)個體編碼的表示方法不同，可以分為實值重組和二進(jìn)制交叉，實值重組有：離散重組、中間重組、線性重組、擴(kuò)展線性重組；二進(jìn)制交叉有：單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、洗牌交叉、縮小代理交叉。（3）變異操作。變異是對群體中的個體串的某些基因座上的基因值作變動。實際上是子代基因按小概率擾動產(chǎn)生的變化。根據(jù)個體編碼的表示方法不同，可以有以下的算法：實值變異、二進(jìn)制變異。2自動組卷的算法實現(xiàn)一份質(zhì)量好的試卷，應(yīng)該是在知識點(diǎn)分布、題型分布、認(rèn)知分類分布、難度分布、區(qū)分度分布、分?jǐn)?shù)分布、時間分布等試卷指標(biāo)之間的極大平衡。由此可見，自動組卷問題是一個具有多重約束的組合優(yōu)化問題。傳統(tǒng)的遺傳算法可以從

4、很差的個體逐漸搜索到較好的個體，對領(lǐng)域知識的要求也很少，是一種通用的有效的方法，但它存在搜索后期效率低和易形成末成熟收斂的情況。為提高遺傳操作在組卷算法中的搜索能力，本系統(tǒng)從“種群編碼方案、初始種群生成、動態(tài)概率、多點(diǎn)交叉操作”等方面對其加以改進(jìn)，使其功能更為強(qiáng)大，效果更好。具體解決方案如下。2.1染色體編碼及初始群體的設(shè)計在傳統(tǒng)的遺傳算法中采用二進(jìn)制編碼，假設(shè)題庫里有N道題，從N道題中選出滿足約束條件的試題生成試卷，可用長為N的二進(jìn)制字串來表示，1表示該題選中，0表示該題未被選中。這樣就形成了染色體編碼，但這樣的二進(jìn)制位串較長，且在進(jìn)行交叉和變異遺傳算子操作時，各種題型的題目數(shù)量不好控制，算

5、法對不同問題的適應(yīng)性較差、尋優(yōu)過程易陷入局部最優(yōu)而出現(xiàn)早熟收斂。為克服二進(jìn)制編碼的缺點(diǎn)，采用實數(shù)編碼方案，將一份試卷映射為一個染色體，組成該試卷的每道題的題號作為基因，基因的值直接用試題號表示，每種題型的題號放在一起，按題型分段，在后面的遺傳算子操作中也按段操作，這樣保證了各題型的題目數(shù)不變。例如，要生成一份.NET程序設(shè)計試卷，其中單項選擇題10道，多項選擇題5道，程序填空題6道，編程題2道，則染色體編碼是：（10、63、13、12、19、84、8、25、2、45|7、36、43、1、23|31、95、48、52、99、14|6&74）單項選擇題多項選擇題程序填空題編程題為了使遺傳算法更快地

6、到達(dá)最優(yōu)解，試卷初始種群的生成是根據(jù)總題數(shù)、題型比例、總分等指標(biāo)的要求隨機(jī)產(chǎn)生，使得初始種群一開始就滿足了題數(shù)、總分等指標(biāo)的要求。采用分段實數(shù)編碼，既可以克服以往采用二進(jìn)制編碼搜索空間過大和編碼長度過長的缺點(diǎn)，又取消了個體的解碼時間，提高了求解速度。2.2適應(yīng)度函數(shù)的設(shè)計遺傳算法在進(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，以種群中每個個體的適應(yīng)值大小來區(qū)分個體的優(yōu)劣。一般情況下適應(yīng)值越大的個體越好，適應(yīng)值越小的個體越差。而影響適應(yīng)度函數(shù)依賴于目標(biāo)函數(shù)，而目標(biāo)函數(shù)就是要使實際得到的試卷中的各指標(biāo)分布與理論要求分布的分值偏差最小，因為題數(shù)、總分等要求在初始化種群時已經(jīng)考慮，剩下的還有知識

7、點(diǎn)分布、難度分布、區(qū)分度分布、認(rèn)知度分布等指標(biāo)要考慮。為簡單起見，本系統(tǒng)選擇了平常主要考慮的試卷難度系數(shù)和知識點(diǎn)分布兩個指標(biāo)。因此，目標(biāo)函數(shù)可以簡化為：g(x)=w1*|EP-P|+w2*(1-D)(1)其中，w1、w2分別為難度、知識點(diǎn)指標(biāo)的權(quán)重，且w1+w2=1;EP為期望難度系數(shù)，P為試卷難度系數(shù)，P=Epixsi/刀si，其中i=1,2,N,N是試卷所含的題目數(shù)，pi、si分別是第i題的難度系數(shù)和分?jǐn)?shù)；D為知識點(diǎn)覆蓋率，D二M/N,N為期望本試卷包含的知識點(diǎn)個數(shù)，M為一個個體中所有題目知識點(diǎn)個數(shù)(M二N):用戶的期望難度系數(shù)EP與試卷難度系數(shù)P之差越小越好，知識點(diǎn)覆蓋率越大越好，由上式

8、可以看出g(x)越小越好。而適應(yīng)度函數(shù)可以通過以下轉(zhuǎn)換得到：f(x)=i-g(x)或g(x)v10其它(2)2.3遺傳算子的設(shè)計（1）選擇算子。選擇算子的作用在于根據(jù)個體的優(yōu)劣程度決定它在下一代是被淘汰還是被復(fù)制。通過選擇，將使適應(yīng)度高的個體有較大的生存機(jī)會。本系統(tǒng)采用了適應(yīng)度比例方法（賭輪選擇方法）。該方法是利用各個體的適應(yīng)度值的概率來決定其后代遺傳的可能性，設(shè)群體大小為n，個體i的適應(yīng)度值為Fi,則個體i被選中的概率Pi為：Fi/刀Fi（i=1,2,n）；（2）交叉算子。由于在編碼時采用的是分段（題型）實數(shù)編碼，所以在交叉時采用了分段單點(diǎn)交叉，整個個體就表現(xiàn)為多點(diǎn)交叉。交叉概率Pc的取值直

9、接影響算法的收斂性，Pc越大，產(chǎn)生新個體的速度就越快，而遺傳模式被破壞的可能性也就越大，這樣具有高適應(yīng)度的個體結(jié)構(gòu)可能就被破壞；Pc過小，使得搜索過程緩慢，以致停滯不前。本系統(tǒng)采用了動態(tài)調(diào)整交叉概率的方法。交叉概率Pc公式為：Pc=k*ffmaxfvfavgkfvfavg（3）其中，fmax為樣體適應(yīng)度函數(shù)的最大伯，favg為娜休適用度函數(shù)的T-均值：f為兩個交叉?zhèn)€體中的適應(yīng)度函數(shù)值較大的一個，k為概率系數(shù)（k1）,本系統(tǒng)k=0.9）交叉過程的實現(xiàn)：將群體中的染色體任意進(jìn)行兩兩配對，對每對染色體產(chǎn)生一個0,1的隨機(jī)數(shù)r,若rPc（交叉概率），則分段隨機(jī)產(chǎn)生一個交叉點(diǎn)，然后分段從交叉點(diǎn)進(jìn)行后半段

10、互換（確保交換后個體仍是有意義的組合）以得到下一代。交叉后生成的子代的新段有可能是非法的，因為有可能存在重復(fù)的題號，出現(xiàn)這種情況要將出現(xiàn)的題號換成該段中沒有出現(xiàn)過的題號，這樣重新得到新子代。（3）變異算子。因為變異概率一般較小，所以本系統(tǒng)沒有采用分段變異，而是只對個體上的某個基因進(jìn)行變異；雖然變異概率Pm的選取也會影響算法的收斂性，但考慮Pm一般在0.0010.1范圍內(nèi)取值，所以本系統(tǒng)采用Pm=0.015。對某個體，隨機(jī)產(chǎn)生一個0,I的隨機(jī)數(shù)r,若rPm,則對該個體進(jìn)行變異，否則不變異。變異操作如下：在1,n范圍內(nèi)隨機(jī)生成一個變異位置P（n為所有個體的數(shù)目），以一定的原則從題庫中選擇一個變異基

11、因，變異基因的選擇原則為：與原基因題型相同的，分?jǐn)?shù)相同，與至少包含原題目一個有效知識點(diǎn)（期望試卷中也有此知識點(diǎn)）。2.4實施流程圖算法實施流程如圖1所示：圖1自動組卷算法實施流程圖2.5實驗結(jié)果系統(tǒng)試題庫中現(xiàn)有單選題、多選題、填空題、判斷題、程序設(shè)計題各200道。群體規(guī)模設(shè)為20，算法執(zhí)行的最大迭代次數(shù)設(shè)為200，試卷難度系數(shù)0.6,適應(yīng)度期望值0.98。試卷總分100，各種題型題數(shù)為：20（單選）,10（多選），10（判斷），15（填空），3（程序設(shè)計題)從表1中的組卷結(jié)果可以看出，在試題庫較大，約束條件較多的情況下，遺傳算法和回溯試探法都有較高的成功率，改進(jìn)遺傳算法的組卷速度明顯快于其它算法。3結(jié)束語本系統(tǒng)利用對遺傳算法研究和改進(jìn)實現(xiàn)了自動組卷。實踐的結(jié)果表明，在滿足約束條件的同時，遺傳算法能較快地組成一份試卷，尤其本文提出的改進(jìn)算法在組卷中應(yīng)用可以有效克服未成熟收斂，提高搜索效率，使種群更快收斂于全局最優(yōu)解。參考文獻(xiàn)：:1陳國良，王煦法遺傳算法及其應(yīng)用M.北京：人民郵電出版社，1996.:2周明，孫樹棟遺傳算法原理及應(yīng)用M.北京：國防工業(yè)出版社，1999.:3王小平，曹立明遺傳算法一一理論、應(yīng)用與軟件實現(xiàn):M.西安：西安交通大