楊剛（安徽職業(yè)技術(shù)學(xué)院信息工程系，安徽合肥230001）

?

基于遺傳算法的智能組卷研究

楊剛
（安徽職業(yè)技術(shù)學(xué)院信息工程系，安徽合肥230001）

計算機技術(shù)自問世以來，推動并深化了教育教學(xué)改革.在考試環(huán)節(jié)，可以使用計算機輔助測試系統(tǒng)對學(xué)生的學(xué)習(xí)效果進行測試.計算機輔助測試系統(tǒng)的核心功能是根據(jù)約束條件進行組卷.建立了一個改進的組卷數(shù)學(xué)模型，并使用遺傳算法對該模型求解.實驗結(jié)果表明，該方法能夠根據(jù)設(shè)定的約束條件進行組卷，并且有較高的成功率.

遺傳算法；組卷；組卷模型；試卷

在傳統(tǒng)考試中，教師要根據(jù)教學(xué)大綱、考試目的去思考要測驗?zāi)男┲R點、使用哪些題型、有多少主觀題、有多少客觀題，然后組織試題形成試卷，這個過程稱之為組卷.教師每個學(xué)期都要重復(fù)這一過程，浪費了時間.在現(xiàn)代教育領(lǐng)域，可以利用計算機輔助測驗系統(tǒng)代替人工去完成考試過程中的各種繁雜的重復(fù)性工作.計算機輔助測試系統(tǒng)的核心功能是根據(jù)約束條件進行組卷［1］，組卷的本質(zhì)是一個多目標多約束求最優(yōu)解問題.筆者使用遺傳算法進行求解.在編碼時，根據(jù)試卷的特點采用了分段實數(shù)的編碼方案，并且在生成初始種群時，就使種群的個體都滿足強約束條件.在執(zhí)行選擇操作時，融入了精英保留策略，在執(zhí)行交叉操作時，采用了分段單點交叉的方式.最后設(shè)定了遺傳算法的結(jié)束條件，獲得最優(yōu)解或已經(jīng)進化到最大代數(shù).

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

設(shè)定每道試題具有5個屬性，依次是：題號、分值、試題類型、知識點及難度.假設(shè)預(yù)期試卷的總題數(shù)為n，則可以建立一個n*5的矩陣，具體描述如下：

一份試卷需要滿足以下幾個約束條件：

1）試卷總分約束

式（2）中，S表示試卷的總分數(shù)，通常是100分，具體數(shù)值有教師根據(jù)需求設(shè)定.ai2為第i道試題的分值.

2）題型分布約束

3）知識點分數(shù)分布約束

式（4）中，M表示所有試卷中所有試題的知識點并集，N表示試卷期望所包含的知識點的并集，以此求得知識點的覆蓋率.

4）試卷總體難度約束

式（5）中，S為卷總分.

在本文中把生產(chǎn)試卷的總分表示為S，把試卷的難度值表示為D，把試卷的知識點覆蓋率表示為Z，把每種題型的題目數(shù)量表示為T.把用戶的期望值與實際生成試卷的偏差分別分別表示為DS，DD，DZ，DT，他們的計算公式如下：

式（6）中，S表示生成試卷的總分值，Sp表示期望試卷的總分值，取絕對值表示二者之間的偏差.

式（7）中，D表示生成試卷的難度值，Dp表示期望試卷的難度值，取絕對值表示二者之間的偏差.

式（8）中，Z表示生成試卷的知識點覆蓋率，Zp表示期望試卷的知識點覆蓋率，取絕對值表示二者之間的偏差.

式（9）中，Tk表示生成試卷的第k種題型的題目數(shù)量，Tkp表示期望試卷的第k種題型的題目數(shù)量，取絕對值表示二者之間的偏差.

所以組卷的目標函數(shù)f可如下表示：

2遺傳算法在組卷中的應(yīng)用

遺傳算法是一種啟發(fā)式隨機搜索方法，在搜索的過程中，不斷向最優(yōu)解靠近.遺傳算法在執(zhí)行過程中，模仿自然界生物進化過程中選擇和遺傳，是一種多參數(shù)、多群體同時優(yōu)化的方法.使用遺傳算法進行組卷的過程如下.

步驟1：生成初始種群

生成初始種群是遺傳算法的第一步.然后會對初始種群中的個體進行評價，如果初始種群已包含最優(yōu)解，則直接輸出結(jié)果，否則進行選擇、交叉和變異找出最優(yōu)解.

把試卷的約束條件分為強約束和弱約束兩種.強約束包括試卷的總分值，以及各種題型對應(yīng)的題目數(shù)量.初始種群中的每個個體都是隨機產(chǎn)生的，但這種隨機是有限制的，即生成的個體必須滿足試卷總分值和題型分布這2個強約束條件.

步驟2：編碼

應(yīng)用遺傳算法求解問題時，要將問題的解映射成染色體，并采用分段實數(shù)編碼方式.將一份試卷映射為一個染色體，染色體上的每一個基因就是試卷中的一道試題，基因的值直接用試題的題號表示［2］.比如一份試卷型有4個單選題，4個多選題，3個判斷題，2個填空題，2個問答題，它的染色體的編碼如圖1所示.

圖1　染色體編碼

步驟3：選取適應(yīng)度函數(shù)

遺傳算法在對問題求解的過程中，考察個體的唯一指標就是適應(yīng)度值.一般而言，適應(yīng)度值高，則說明個體好，反之說明個體壞，容易被淘汰.所以適應(yīng)度函數(shù)的選取是十分關(guān)鍵的，要能把個體的好壞區(qū)分開來［3］.

在生成初始種群時，種群中的個體已經(jīng)滿足了試卷總分值約束和題型分布約束，因此式（10）中的DS=0，DT=0，故組卷的目標函數(shù)轉(zhuǎn)變?yōu)?/p>

通常適應(yīng)度函數(shù)就是目標函數(shù).由公式（11）可知，當f的值趨近于0時，生成的試卷越符合約束條件.但函數(shù)取最小值不方便執(zhí)行后續(xù)的選擇操作，因此對其做如下變換得到適應(yīng)度函數(shù)：

步驟4：遺傳操作

1）選擇

采用輪盤賭作為選擇算子，但輪盤賭容易發(fā)生優(yōu)良個體丟失的情況.因此，在執(zhí)行選擇的過程中加入了精英保留策略，該策略能夠?qū)⒏复羞m應(yīng)度值最高的個體保留下來.具體的實現(xiàn)步驟是：

①在進化的過程中，對每一進化后產(chǎn)生的子代種群，計算其每個個體的適應(yīng)度值，并找出最大值.

②將子代種群中的最優(yōu)個體與父代種群中的最優(yōu)個體相比，如果父代種群的最優(yōu)個體的適應(yīng)度值大，則隨機從子代種群中選擇一個個體，淘汰該個體后，把父代種群中的最優(yōu)個體加入種群中；如果子代種群的最大適應(yīng)度值比較大，則不改變子代種群，繼續(xù)進行求解.

2）交叉

設(shè)定的編碼方案是分段實數(shù)編碼，每種題型即一段，為保證交叉操作不影響題型的分布，設(shè)定交叉在段內(nèi)進行，且同一段內(nèi)只交叉一個基因，整個染色體就表現(xiàn)為多點交叉［4］.

3）變異

在交叉操作后，對種群中的個體進行評價，如果沒有找到最優(yōu)解，則執(zhí)行變異操作.把變異算子也改進為在段內(nèi)進行，且為單點變異.并且在變異操作中加入以下幾個約束條件：不能選擇重復(fù)的試題，新的試題的分值要與原來相同，新的試題的所包含知識點是與原有知識點，或是原有知識點的子集［5］.

交叉的具體過程如下：

①選擇種群中的一個個體.

②在個體中各題型對應(yīng)的段內(nèi)隨機尋找一個基因.

③從題庫中抽取一個對應(yīng)的試題，改變第二步基因位上的值.

步驟5：終止遺傳算法

遺傳算法的運算過程是一種迭代，如果使用不當，會陷入無線循環(huán)中.設(shè)置最大進化代數(shù)為500，當進化到500代時，如果仍然沒有找到最優(yōu)解，算法將停止運算.

3實驗及結(jié)果分析

在操作系統(tǒng)Microsoft Windows XP，CPU Intel Core i3 2.4 GHz，2 G內(nèi)存，C#4.0環(huán)境下，編程實現(xiàn)了遺傳算法.為了驗證算法的可行性和有效性，使用題庫《電工電子》進行組卷實驗.該題庫包含單選題、多選題、判斷題、填空題及簡答題5種題型，每種題型單題的分值分別為1，2，1，1-4和3-10.該題庫的題型數(shù)量級難度分布特征如表1所示.

題庫中的總知識點為120個，編號從1開始.題庫中的每道試題最少包含1個知識點，最多包含4個知識點.

按照表2設(shè)置試卷的約束條件.設(shè)置初始種群數(shù)量為20，選擇次數(shù)為10次，最大迭代次數(shù)為500.設(shè)定適應(yīng)度期望值為0.95，0.96，0.97，0.98，0.99，各組卷500次.

表1　題庫《電工電子》的特征

表2　《電工電子》試卷組卷要求

適應(yīng)度為0.95時組卷500次，成功率為100%.運行結(jié)果如表3所示.

表3　《電工電子》適應(yīng)度為0.95組卷結(jié)果

適應(yīng)度為0.96時組卷500次，成功率為100%.運行結(jié)果如表4所示.

適應(yīng)度為0.97時組卷500次，成功率為100%.運行結(jié)果如表5所示.

表4　《電工電子》適應(yīng)度為0.96組卷結(jié)果

表5　《電工電子》適應(yīng)度為0.97組卷結(jié)果

適應(yīng)度為0.98時組卷500次，成功率為97.4%.運行結(jié)果如表6所示.

適應(yīng)度為0.99時組卷500次，成功率為93.5%.運行結(jié)果如表7所示.

表6　《電工電子》適應(yīng)度為0.98組卷結(jié)果

表7　《電工電子》適應(yīng)度為0.99組卷結(jié)果

適應(yīng)度值從0.95至0.99，所需的平均進化代數(shù)如表8所示.

表8　《電工電子》適應(yīng)度值與平均進化代數(shù)

4結(jié)論

根據(jù)適應(yīng)度函數(shù)，當適應(yīng)度的值越接近1.0，表明生成的試卷越符合預(yù)期要求.本文的實驗結(jié)果顯示，當適應(yīng)度期望值在0.98以下時，組卷的成功率為100%.當適應(yīng)度期望值為0.98和0.99時，組卷的成功率在92%以上.已達到預(yù)期的要求.

［1］黃光揚，龍文祥.教育測量與評價［M］.上海：華東師范大學(xué)出版社，2002

［2］張晉，李冬黎，李平.遺傳算法編碼機制的比較研究［J］.中國礦業(yè)大學(xué)學(xué)報，2002，（6）：45-48.

［3］李延梅.一種改進的遺傳算法及應(yīng)用［D］.廣州：華南理工大學(xué)，2012.

［4］賀榮，陳爽.在線組卷策略的研究與設(shè)計［J］.計算機工程與設(shè)計，2011，（6）：2183-2186.

［5］朱文堅，陳東，劉建素.遺傳算法在多目標優(yōu)化設(shè)計中的應(yīng)用研究［J］.機械工程師，2001，（12）：35-37.

（責(zé)任編輯李健飛）

A Research on Intelligent Test Paper Com poser Based on Genetic Algorithm

YANG Gang
（Department of Information Engineering，Anhui Vocational College Technology，Hefei，Anhui 230011，China）

Since computer technology came into being，it has promoted the deepening of educational reform.In the test session，the computer-aided test system is used for testing students'learning effect.This system includes multiple functional modules with its core function of composing test paper based on constraints.In this paper，an imp roved test paper mathematical model is established and genetic algorithm is used to solve the model.The experiment results show that the method can be used to compose test papers based on the fixed constraints，possessing a higher success rate.

genetic algorithm；test paper composer；test paper composer model；test paper

TP39

A

1673-1972（2016）03-0042-05

2016-04-16

2010年安徽省高等教育質(zhì)量工程教學(xué)研究項目（20101512）

楊剛（1982-），男，安徽五河人，講師，主要從事算法分析與設(shè)計、軟件工程研究.