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

蘇玉慧　龔?fù)?/p>

[摘要]結(jié)合遺傳算法的原理和思想，對考試系統(tǒng)自動組卷的問題進(jìn)行了分析和研究，利用遺傳算法求解試題庫自動組卷問題的方法。討論運用遺傳算法求解在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題，給出了功能塊的概念，并采用了新的編碼方式、交叉算子和變異算子對其進(jìn)行優(yōu)化。

[關(guān)鍵詞]遺傳算法 組卷策略 交叉運算

引言

一個完備的在線考試系統(tǒng)可以使用戶在網(wǎng)上學(xué)習(xí)過后及時檢驗自己的學(xué)習(xí)效果，發(fā)現(xiàn)自己的不足，使得學(xué)習(xí)效率得到很大提高。而在線考試系統(tǒng)的試題庫系統(tǒng)建設(shè)，組卷策略是一個非常重要的環(huán)節(jié)，本文提出一種用改進(jìn)的遺體算法來求解試題組卷問題。

一、傳統(tǒng)遺傳算法的問題求解

遺傳算法的群體搜索策略為多目標(biāo)優(yōu)化提供了非常合適的解決方案。一般來說，多目標(biāo)優(yōu)化問題并不存在一個最優(yōu)解，所有可能的解都稱為非劣解，也稱為Pareto解。傳統(tǒng)優(yōu)化技術(shù)一般每次能得到Pareto解集中的一個，而用遺傳算法來求解，可以得到更多的Pareto解，甚至是整個的解都成為Pareto解。

式中：C為個體的編碼方法； E為個體適應(yīng)度評價函數(shù)；Po為初始群體；M為群體大小；Φ為選擇算子；Г為交叉算子；Ψ為變異算子； T為遺傳運算終止條件。遺傳算法的基本步驟：確定編碼方案、確定適應(yīng)函數(shù)、確定選擇策略、控制參數(shù)的選取、遺傳算子的設(shè)計、算法終止準(zhǔn)則的確定等。用進(jìn)化方法處理多目標(biāo)優(yōu)化問題的關(guān)鍵是進(jìn)化選擇機(jī)制。多目標(biāo)優(yōu)化的遺傳算法與單目標(biāo)優(yōu)化的進(jìn)化算法基本相同，僅在計算適應(yīng)值上有差別。

遺傳算法框架中的參數(shù)往往與待解決的具體問題密切相關(guān)。針對自動組卷問題，我們給出相應(yīng)的算法步驟如下：

步驟1：染色體的編碼

假設(shè)試題庫中有m道題，可用一個m位的二進(jìn)制串來表示，形式為：xl x2 x3…xm其中若xi為1，則表示該題被選中，若xi為0則表示該題未被選中，即

當(dāng)?shù)趇道題被選中

當(dāng)?shù)趇道題未被選中

若一份試卷中有n道試題，則xl x2 x3…xm串中應(yīng)有n個1。

步驟2：初始化群體

通過隨機(jī)的方法生成初始化的串群體。在串群體中，串的長度是相同的，群體的大小根據(jù)需要按經(jīng)驗或?qū)嶒灲o出。

步驟3：計算當(dāng)前種群每個個體的適應(yīng)度值

本問題的適應(yīng)度函數(shù)可定義為

fi表示第i個屬性指標(biāo)與用戶要求的誤差的絕對值。

wi表示第i個指標(biāo)對組卷重要程度的權(quán)值。

f是所有指標(biāo)與用戶要求的誤差絕對值之和。

步驟4：選擇

按照一定的選擇概率對種群進(jìn)行復(fù)制，選擇較好的串生成下一代（個體的適應(yīng)度函數(shù)值越小，該串的性能越好，選擇概率越大），去掉較差的串。

步驟5：交叉

交叉是兩個串按照一定的概率（交叉概率Pc），從某一位開始逐位互換。首先，對每個二進(jìn)制串產(chǎn)生一個在0～1的隨機(jī)數(shù)，若該數(shù)小于Pc，則選擇該串進(jìn)行交叉否則不選擇。隨機(jī)地對被選擇的二進(jìn)制串進(jìn)行配對，并根據(jù)二進(jìn)制串的長度n，隨機(jī)產(chǎn)生交叉位置i，i為[1，n-1]上的一個整數(shù)，然后按下面的方式交叉：

步驟6：變異

變異是二進(jìn)制串的某一位按照一定的概率（突變概率Pm）發(fā)生反轉(zhuǎn)，1變?yōu)?，0變?yōu)?。這里Pm較小，Pm可小于0.001。但在實踐中發(fā)現(xiàn)，在有些遺傳算子中，Pm為0.1時更好。

步驟7：終止

記錄進(jìn)化的代數(shù)，并判斷是否滿足終止條件。若滿足，則輸出結(jié)果，否則轉(zhuǎn)向步驟3繼續(xù)執(zhí)行。終止條件如下：

（a）出現(xiàn)種群滿足f=0；

（b）某個個體適應(yīng)度值達(dá)到指定要求；

（c）達(dá)到指定的進(jìn)化代數(shù)；

（d）當(dāng)前種群中最大適應(yīng)度值與以前各代中最大適應(yīng)度值相差不大，進(jìn)化效果不顯著。

二、改進(jìn)的遺傳算法

（1）編碼的改進(jìn)

根據(jù)標(biāo)準(zhǔn)化試卷中每種題型所占分?jǐn)?shù)和題數(shù)是相同的特地點，給出采用獨立編碼的策略。獨立編碼策略就是將以往的合成編碼分解成多個相對獨立的編碼，在本問題中就是根據(jù)各個題型各自編碼，然后對每一種題型再采用傳統(tǒng)編碼策略進(jìn)行處理，但組與組之間的編碼是獨立的。其中每一組反映一個題型。每一組長度由題庫內(nèi)該題型數(shù)所定。這樣，可以將整個二進(jìn)制串按照題目的類型劃分為不同的功能塊。每個功能塊采用獨立的二進(jìn)制編碼。也就是說，每個功能塊對應(yīng)一種特定的題型，而該功能塊中，“1”代表該題被選中，“0”代表該題未被選中，“1”的數(shù)目即該種題型的試題數(shù)目。顯然，按這種規(guī)則產(chǎn)生的初始種群已滿足試題對題型、分?jǐn)?shù)和答題時間的要求。

因為每一組反映一個題型，每一組長度由題庫內(nèi)該題型數(shù)決定，分別共有k1，k2…kn編碼長度由題庫中所含試題數(shù)決定，n是題型數(shù)。設(shè)試題庫中共有k道試題，編碼形式如下：b1b2…bk，隨機(jī)生成初始化串種群，串長度都是相同的.

且滿足 ，其中，m是試卷所含的題目數(shù)。

其中，ml，m2，…分別為試卷中各個題型所出題目數(shù)。

本問題適應(yīng)度函數(shù)定義為：

其中：wi對應(yīng)為第i組卷因素對組卷重要程度的權(quán)值，ei對應(yīng)為第i組卷因素對組卷目標(biāo)的誤差。

在實際實現(xiàn)時，在資源有限的情況下，必須進(jìn)行“優(yōu)勝劣汰”的選擇，使用的是比例選擇。設(shè)H為任一個染色體，Pt（H）表示t時染色體H出現(xiàn)的概率。在選擇階段，每個染色體根據(jù)它的適應(yīng)值被選擇，因此染色體H在t+1時刻的概率為：

其中 為群體適應(yīng)值，可以看到，染色體H的適應(yīng)值越高，他被選中的概率越大。種群規(guī)模N：N值大進(jìn)化較慢，但易搜索到全局最優(yōu)解，而N值小時進(jìn)化速度快，卻不易搜索到最優(yōu)解，權(quán)衡效率和性能。一般N取值為200左右。

（2）交叉運算的改進(jìn)

由于種群中每一個功能塊對應(yīng)著一個題型，所以，為了保證每個題型的數(shù)目不變，交叉點的選擇不能破壞功能塊的完整性。假設(shè)交叉點位于第i個功能塊內(nèi)，則前i個功能塊保持不變，從第i+1個功能塊開始逐位交換。

（3）變異運算的改進(jìn)

由于在每個功能塊中，“1”的數(shù)目即是該題型試題的數(shù)目，因此在變異過程中應(yīng)保證整個種群所有功能塊中“1”的數(shù)目不變?？蓤?zhí)行如下過程，首先，由變異概率決定某位取反；然后，檢查、修正字符串中“1”的數(shù)目，保證不發(fā)生變化。

（4）用全局最優(yōu)解替換本次迭代的最差解

為保證好的字符串不至于流失，每次遺傳操作前記錄本次迭代的最優(yōu)解，若該解優(yōu)于全局最優(yōu)解則替換全局最優(yōu)解，否則全局最優(yōu)解保持不變。此次遺傳操作后，用全局最優(yōu)解換本代的最差解。遺傳算法組卷的算法描述如下：

主要算法段描述

三、實驗

四、結(jié)束語

對比表3-2、表3-3的實驗結(jié)果可知，在不同種群下，采用功能塊的改進(jìn)的遺傳算法性能優(yōu)于傳統(tǒng)的遺傳算法，而且指標(biāo)有很大的提高，這說明改進(jìn)的遺傳算法降低了問題的求解難度，提高了問題的求解效率。組卷是組成一份誤差在可接受范圍內(nèi)的試卷，并非要求此試卷的整體指標(biāo)一定是全局最優(yōu)，尤其是在改進(jìn)的遺傳算法中，整個試卷的題目類型、題目數(shù)量、題目分?jǐn)?shù)不會產(chǎn)生誤差，而在篇章、難度、區(qū)分度上的一定范圍內(nèi)的誤差是可以接受的。由表3-4可知適當(dāng)?shù)胤糯笳`差可較大幅度縮短求解時間。對比表3-5可知傳統(tǒng)的遺傳算法效率好于普通的隨機(jī)算法，而改進(jìn)的遺傳算法在時間上又優(yōu)于傳統(tǒng)的遺傳算法。

[參考文獻(xiàn)]

[1]曾凌峰.基于遺傳算法的自動組卷策略與實現(xiàn)[J].遼寧科技大學(xué)學(xué)報，2010，（03）.

[2]吳金華，戴淼等.基于遺傳神經(jīng)網(wǎng)絡(luò)的陜西省土地利用結(jié)構(gòu)模型研究[J].安徽農(nóng)業(yè)科學(xué)，2008，（36）.

[3]尹文彬，許騰等.基于遺傳算法的艦艇編隊火力分配問題研究[J].兵工自動化，2010，（05）.

（作者單位：江西財經(jīng)職業(yè)學(xué)院 江西九江）