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

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

?

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

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

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

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

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

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

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

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

1）試卷總分約束

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

2）題型分布約束

3）知識(shí)點(diǎn)分?jǐn)?shù)分布約束

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

4）試卷總體難度約束

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

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

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

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

式（8）中，Z表示生成試卷的知識(shí)點(diǎn)覆蓋率，Zp表示期望試卷的知識(shí)點(diǎn)覆蓋率，取絕對(duì)值表示二者之間的偏差.

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

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

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

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

步驟1：生成初始種群

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

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

步驟2：編碼

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

圖1　染色體編碼

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

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

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

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

步驟4：遺傳操作

1）選擇

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

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

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

2）交叉

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

3）變異

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

交叉的具體過程如下：

①選擇種群中的一個(gè)個(gè)體.

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

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

步驟5：終止遺傳算法

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

3實(shí)驗(yàn)及結(jié)果分析

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

題庫中的總知識(shí)點(diǎn)為120個(gè)，編號(hào)從1開始.題庫中的每道試題最少包含1個(gè)知識(shí)點(diǎn)，最多包含4個(gè)知識(shí)點(diǎn).

按照表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時(shí)組卷500次，成功率為100%.運(yùn)行結(jié)果如表3所示.

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

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

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

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

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

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

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

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

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

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

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

4結(jié)論

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

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

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

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

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

［5］朱文堅(jiān)，陳東，劉建素.遺傳算法在多目標(biāo)優(yōu)化設(shè)計(jì)中的應(yīng)用研究［J］.機(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é)研究項(xiàng)目（20101512）

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