倪雪飛 孫吉花

【摘要】在線考試系統(tǒng)中的自動(dòng)組卷技術(shù)是系統(tǒng)的核心，是近年來的一門綜合新興學(xué)科，它是根據(jù)每次的考試要求通過系統(tǒng)來實(shí)現(xiàn)自動(dòng)生成考試試卷，從而克服傳統(tǒng)的一些弊端。本系統(tǒng)考試的要求包括：考試人員類被，考試方向，考試試題類別，試題數(shù)量，試卷分值，試題分值，考試時(shí)間等參數(shù)。通過考試了解當(dāng)前階段的任務(wù)完成情況和存在的不足。自動(dòng)組卷能夠避免考試中因?yàn)槿藶橹饔^因素造成的影響，自動(dòng)組卷技術(shù)已經(jīng)被越來越多的在線考試系統(tǒng)采用。

【關(guān)鍵詞】自動(dòng)組卷 ?遺傳算法 ?在線考試

當(dāng)今社會(huì)工作節(jié)奏的加快，為了能夠增強(qiáng)自己在社會(huì)中的競(jìng)爭(zhēng)力，學(xué)習(xí)充電是必須的，但是繁瑣的異地資格考試很是浪費(fèi)時(shí)間和精力，在線考試系統(tǒng)就應(yīng)運(yùn)而生，在線考試系統(tǒng)需要做到能夠真實(shí)有效的考察一個(gè)人的知識(shí)掌握情況，這就需要在組卷上算法上做到盡量智能化。特別是要避免人工組卷帶來的不安全性和不客觀性，所以在線考試系統(tǒng)采用的組卷技術(shù)一般都是自動(dòng)組卷。其中常見的組卷技術(shù)有隨機(jī)組卷、回溯組卷和遺傳算法組卷等，下面我們?cè)敿?xì)講解遺傳算法組卷。

遺傳算法

遺傳算法概述

遺傳算法[1]（Genetic？Algorithm，簡(jiǎn)稱GA）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法，由美國的J.Holland教授1975年首先提出。遺傳算法是一種模擬達(dá)爾文的生物進(jìn)化理論物競(jìng)天擇的計(jì)算模型，通過對(duì)自然界生物進(jìn)化的模擬來解決多約束條件下的最優(yōu)解。算法實(shí)施流程圖如圖1所示

遺傳算法是對(duì)種群中的個(gè)體進(jìn)行操作，問題空間的參數(shù)通過基因鏈的形式表示出來，編碼的好壞對(duì)算法解決問題的能力有直接影響。目前，存在的編碼方式包括二進(jìn)制編碼、動(dòng)態(tài)編碼、格雷碼編碼[2]、十進(jìn)制編碼和實(shí)數(shù)編碼等多種方式。在本系統(tǒng)的組卷應(yīng)用中，在組卷過程中對(duì)數(shù)據(jù)庫的存取訪問速度受到試題數(shù)據(jù)結(jié)構(gòu)的影響較大，為了能夠在組卷過程中減少數(shù)據(jù)訪問的時(shí)間開銷，直接以題號(hào)作為基因的值，每種題型的題號(hào)放在一起，這樣就能快速的獲得指定類型的試題。因此，本系統(tǒng)采用分段的實(shí)數(shù)編碼方案，比如要組一份“后勤理論”的試卷6道單選，5道多選，3道判斷，2道論述，其染色體的編碼為：

（10，12，3，5，9，40） ?（25，32，21，6） ?（16，51，11） ?（7，26）

單選題 ? ? ? 多選題 ? ? 判斷題 ? ?論述題

在遺傳算法的開始，一般采取的是隨機(jī)生成初代種群，以達(dá)到遍歷所有狀態(tài)的目的。但是這樣會(huì)一定程度上延長進(jìn)化的時(shí)間，本文針對(duì)系統(tǒng)的使用對(duì)象和問題的實(shí)際情況，采用不完全的隨機(jī)初始化種群的方法，初始化種群的時(shí)候就設(shè)定試卷的考試方向、各個(gè)題型的數(shù)量、分?jǐn)?shù)以及考試時(shí)間，這樣生成的種群就已經(jīng)滿足了試卷的一大部分要求，加快了算法的收斂和減少了迭代次數(shù)，同時(shí)取消了個(gè)體解碼時(shí)間，提高了求解速度。

適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是遺傳算法尋求最優(yōu)解的依據(jù)，一般來說是由目標(biāo)函數(shù)直接轉(zhuǎn)化而來，通過它來對(duì)群體中的個(gè)體的優(yōu)劣程度進(jìn)行評(píng)估，指導(dǎo)算法的搜索方向，因此適應(yīng)度函數(shù)的好還是至關(guān)重要的，因此，一份試卷的適應(yīng)度[3]越高，那么它就越接近算法的最優(yōu)解，本文在初始化種群中就已經(jīng)約束了試題方向、分?jǐn)?shù)、考試時(shí)間等輔助信息，只需要考慮試卷的難度系數(shù)就行了，所以本文中所用的適應(yīng)度函數(shù)是由試卷的難度系數(shù)公示轉(zhuǎn)換而成的。試卷的難度系數(shù)為公式1：

（1）

其中Di 為第i道題的難度系數(shù)，Si為第i道題的分?jǐn)?shù) ，n為試卷中試題的總數(shù)目。用戶的期望難度EP與試卷的難度P之間的差越小越好。如果一份試卷中期望含有N個(gè)知識(shí)點(diǎn)，而一個(gè)個(gè)體試卷中含有M個(gè)知識(shí)點(diǎn)，那么該份試卷中知識(shí)點(diǎn)覆蓋率為 ，上面說到EP和P之間的差值越小越好，知識(shí)點(diǎn)覆蓋率則越大越好，本文中遺傳算法的適應(yīng)度函數(shù)為公式2：

（2）

公式2中f1為知識(shí)點(diǎn)分布權(quán)重，f2為難度系數(shù)所占權(quán)重，其中f1為零時(shí)，那么只考慮難度系數(shù);f2為零時(shí)，只考慮知識(shí)點(diǎn)覆蓋率，由于本系統(tǒng)使用對(duì)象的特點(diǎn)，只考慮難度系數(shù)。

遺傳算子

1.選擇算子

選擇算子[4]的主要作用是根據(jù)個(gè)體的適應(yīng)度大小決定個(gè)體是被選中還是淘汰，這樣適應(yīng)度高的個(gè)體生存機(jī)會(huì)就要高一些，為了讓遺傳算法在組卷中發(fā)揮更好，本文采用的是輪盤賭方法，根據(jù)個(gè)體的適應(yīng)度的不同，個(gè)體被選中的概率為公式5-1所示，通過公式可以看出，個(gè)體的適應(yīng)度越高，被選中的概率就越大，這樣優(yōu)秀的個(gè)體就能夠得到保留。

2.交叉算子

本文在對(duì)個(gè)體進(jìn)行染色題編碼的時(shí)候采用的是分段實(shí)數(shù)編

碼，所以交叉就采用了分段單點(diǎn)交叉策略，具體實(shí)現(xiàn)過程為：隨機(jī)選擇個(gè)體使其兩個(gè)為一組，通過交叉概率Pc和適當(dāng)?shù)臈l件進(jìn)行交換，產(chǎn)生兩個(gè)新的個(gè)體，其中Pc的選擇會(huì)影響到算法的收斂性，如果Pc過大，產(chǎn)生新個(gè)體的速度就越快，但是容易使得優(yōu)秀個(gè)體遭到破壞，而Pc過小，則會(huì)使的搜索過程緩慢。

3.變異算子

在對(duì)個(gè)體進(jìn)行交叉后，對(duì)個(gè)體的基因進(jìn)行基于概率Pm進(jìn)行基因變異，這個(gè)概率一般較小，對(duì)Pm的設(shè)置不能過小，如果過小不易產(chǎn)生新個(gè)體，如果過大就變成了純粹的隨機(jī)搜索。本文在交叉的時(shí)候采用了分段單點(diǎn)交叉，這里就不進(jìn)行分段變異了，而是對(duì)整個(gè)基因的某段上的某個(gè)基因進(jìn)行變異。通過隨機(jī)生成一個(gè)[1，n]的隨機(jī)數(shù)r，r作為一個(gè)變異位置，然后從題庫中選取一個(gè)變異基因，在選取的時(shí)候要保證新選擇的基因要與原基因具有相同的題型，相同的分?jǐn)?shù)，相同的考試方向。

遺傳算法控制參數(shù)設(shè)置[5]

遺傳算法的多個(gè)參數(shù)中交叉概率Pc和變異概率Pm對(duì)算法的影響較大，其中Pc的選擇會(huì)影響到算法的收斂性，如果Pc過大，產(chǎn)生新個(gè)體的速度就越快，但是容易使得優(yōu)秀個(gè)體遭到破壞，而Pc過小，則會(huì)使的搜索過程緩慢。而Pm的取值的大小同樣影響算法的性能，在保持群體保持多樣性的前提下Pm不能設(shè)置過大，如果Pm取值過大，會(huì)使算法變?yōu)殡S機(jī)搜索，Pm取值過小，個(gè)體的多樣性就無法得到滿足，從而使得算法陷入局部最優(yōu)的狀態(tài)，而過早收斂。為了避免因?yàn)榻徊娓怕屎妥儺惛怕嗜≈翟斐伤惴ㄐ阅苁艿接绊?，加快遺傳算法收斂和有效的避免其陷入局部最優(yōu)狀態(tài)，同時(shí)保持較為優(yōu)良的試卷個(gè)體，本文采取交叉概率 Pc 和變異概率 Pm 的自適應(yīng)策略，即使得交叉概率 Pc 和變異概率 Pm能夠隨適應(yīng)度自動(dòng)改變，當(dāng)種群的個(gè)體趨于一致或者陷于局部最優(yōu)時(shí)，交叉概率Pc和變異概率 Pm就增加，當(dāng)群體適應(yīng)度比較分撒時(shí)，交叉概率 Pc 和變異概率 Pm就減小。

可以通過實(shí)驗(yàn)對(duì)Pc和Pm的值進(jìn)行設(shè)定從而取最佳值，通過實(shí)驗(yàn)可以Pc取值范圍在0.2～1.0之間時(shí)，組卷的成功次數(shù)多，而迭代次數(shù)少，在組卷方面呈現(xiàn)先增后減，在迭代次數(shù)上呈現(xiàn)先減后增。Pm取值過大時(shí)，組卷的成功率較低，迭代次數(shù)增加，這是由于變異造成的群體中優(yōu)良的個(gè)體遭到了破壞，但是取值過小產(chǎn)生新個(gè)體的速率就會(huì)降低，導(dǎo)致種群不能實(shí)現(xiàn)多樣性。當(dāng)種群規(guī)模較小時(shí)，組卷成功率很低，因?yàn)榉N群的規(guī)模本身就小，這樣就不具備多樣性的特點(diǎn)，使得算法的搜索空間局限性很強(qiáng)，出現(xiàn)了未成熟收斂的情況。隨著種群規(guī)模的提高，算法的搜索空間加大，這樣組卷的成功率也提高，但是平均迭代次數(shù)也會(huì)隨著種群的提高而提高，這樣也會(huì)影響算法的效率。

【參考文獻(xiàn)】

[1]陳國良、王熙發(fā)等，遺傳算法及其應(yīng)用，北京：人民郵電出版社，2001，1～400

[2]李華山;格雷碼的代數(shù)結(jié)構(gòu)和分形生成的遞歸算法[J];北方工業(yè)大學(xué)學(xué)報(bào);1996年01期

[3]Holland J. Adaptation in Natural and Artifical Systems[M].AnnArbor：The University of Michigan Press，1975，1～50

[4]王小平，曹立明.遺傳算法一理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002

[5]劉學(xué)增，周敏. 改進(jìn)的自適應(yīng)遺傳算法及其工程應(yīng)用[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版）. 2009（03）