基于改進遺傳算法的智能組卷系統設計?

高凌潔

（寶雞職業技術學院 寶雞 721013）

基于改進遺傳算法的智能組卷系統設計?

高凌潔

（寶雞職業技術學院 寶雞 721013）

針對傳統隨機組卷模型在組卷速度和組卷質量方面存在的問題，對傳統遺傳算法進行改進，提出一種基于改進遺傳算法的智能組卷系統。基于試題組卷約束，構建試題組卷數學模型，并通過遺傳編碼方法對試卷個體屬性值進行保存，從而提高運算速率；針對組卷過程中知識點容易沖突問題，利用分段多點的變異策略和雜交策略進行優化；同時針對種群多樣性問題，提出一種大比率雜交和變異策略，從而提高組卷速度。最后借助C#語言+Mysql數據庫分別進行編程和試題庫構建，通過仿真驗證改進算法在收斂性和質量方面的優勢。

遺傳算法；智能組卷；遺傳編碼；適應度函數；組卷質量

1 引言

在智能組卷系統中，如何保障生成的試卷能最大限度地滿足教學的需求，并提高試卷組卷的質量、難度、出題時間等問題，是當前的一個難點，也是一個重點。但是，傳統的隨機組卷算法帶有很大的隨機性，同時知識點、試題難度等也不能把握，大大減少了試卷的質量，不能發揮考試測驗的效果。如當試題庫規模和試卷指標設置越多的情況下，隨機組卷算法在計算速度、組卷質量方面都很難達到滿意效果。而遺傳算法是一種模仿自然界生物在自然環境下的遺傳和進化過程而形成的一種自適應全局優化搜索算法，具有全局優化強、操作簡單的特點。遺傳算法的原理是通過在代與代之間維持由潛在解構成的種群來實現全局搜索和多樣性，從而為多目標的優化提供了更好的解決方法。而近年來，遺傳算法也被廣泛的應用在智能組卷問題求解中，并取得豐碩成果。但后期收斂速度慢、多個約束條件下出現沖突等問題仍然不能得到有效滿足。對此，文章給出一種改進遺傳算法的組卷系統，并通過設計開發，得到滿意效果。

2 組卷數學模型構建

假設試題庫中的每道題可通過n項不同的指標來決定其是否可以被組卷，從而構成了一個n維度的向量（an1題型，an2分數，an3難度，an4章節，……），其中，ani表示第i道試題存在的全部指標。而在試題庫之中包含p道試題，由此構成了一個m*n的矩陣。

在上述的目標矩陣X則為需要求解的目標矩陣，每一列之中表示了每一道題所包含的一個屬性，而每一行則代表一道題的左右的屬性值，apn表示第 p道題的第n個屬性。從而得到試題構成的染色體模型：

對試題指標選擇設置相應的約束條件。所謂的約束條件，通常被認為是能夠提高組卷質量的方法。試卷指標很多，主要包括各題型包含的題數、試題分值、預計答題時間、每章節出題數量、每章節出題分值、試卷難易分布、試卷總題型數量及總分、試卷區分度、知識點覆蓋、試卷認知程度。其中知識點覆蓋的約束條件為

其中，y(j，i)=1表示第i題的第 j個知識點，否則為0，k則表示輸入的知識點覆蓋數。

試卷難易分布指標約束條件為

其中，b(j)表示第 j類試題難度的總分數；y(j，i)=1表示第i道題屬第 j難度，否則值為0。

3 傳統基于遺傳算法的組卷

傳統遺傳算法被廣泛用在試卷生成之中，其具體的思路為：對試題進行自然數編碼，然后抽取出設定數量的初始試卷，從而作為遺傳算法的交配池。利用遺傳算法設計適應度函數，從而對每一道試題的適應度值進行計算，同時按照預先設置的交叉、變異操作進行運算，衡量適應度值是否滿足要求。如果通過計算出來的適應度值滿足，那么解碼生成相應的試卷，如果不滿足，那么繼續進行交叉、變異運算，直到適應度值滿足設定要求，即停止迭代。具體如圖1所示。

圖1 遺傳算法

遺傳算法的特點在于適合全局搜索，而不適合局部搜索。因此，在早期搜索中，這種算法在試卷生成占極大優勢，但容易陷入“早熟”問題，從而得不到試卷組合最優解，達不到提高試卷質量的目的。同時其變異、交叉、選擇等操作屬于獨立的，不能確保試卷中的實體知識點不重復問題。

4 基于改進遺傳算法的試卷組卷

4.1 適應度函數設計

而入門的小學生和初中低年級學生，處境就比較尷尬。從國外引進的童書繪本中，以外研出版社引進的偏文字英語故事書為主，對英語入門級學生而言難度偏高；其他出版社，更多為直接出中文譯作。而承載著認知啟蒙、培養語言興趣使命的入門級英語原版繪本，市面上實在是少之又少（漆秋香，2015），視聽資源更是缺乏。偶爾出現，價格還偏高。正版資源少，盜版也是無源之水。

為有效地設計試卷組卷的適應度函數，本文則提出一種基于線性關系的適應度函數，具體思路為通過對不同目標屬性 fi賦予不同的權值，從而得到組合的目標函數 f，最終計算目標函數的適應度。

其中，∑wp=1。

4.2 初始種群改進

為提高組卷收斂速度，改變傳統的隨機搜索方法，在對初始種群進行篩選過程中引入知識點分布、題型約束等參數。具體算法設計如圖2所示。

圖2 初始種群改進流程

4.3 遺傳算子改進

4.3.1 選擇操作改進

對選擇算子來講，物競天擇、適者生存是其構建的基本思路。而根據這樣的選擇方式，最后可能會因為種群數量不多，形成過早收斂的問題。對此，在遺傳算法改進中，引入輪盤賭方式，從而增加適應度值小的個體概率，增加種群數量。具體思路為：

對于給定的種群 XP，其中的某個個體apn適應度值可以用 fi表示，由此先計算出種群所有個體的適應度總和SUM，然后計算出每個個體的選擇概率XPi=fi/SUM ，找出其中的最大概率max，按照隨機原則產生一個0～max的隨機數a，如果a＜XPi那么這個個體被選中，如果a＞XPi，則淘汰。由此，對于一些適應度較小的試題，也有可能被選中。然后，利用精英選擇思想，通過適應度函數計算出其中是適應度最大和最小的個體，保留適應度較大，淘汰適應度較小的試題。

4.3.2 雜交操作改進

雜交是一種重要的工具，可獲得更加優秀的個體。為避免選題知識點的沖突，提出一種改進的分段多點雜交方法，具體策略如圖3所示。

圖3 雜交操作改進

在圖3的雜交操作中，雜交知識點相同的試題，從而得到新的后代，對新產生的后代進行適應度計算，適應度較低的直接淘汰，保留適應度較高的后代。

4.3.3 變異操作改進

為進一步防止在試卷組卷過程中陷入局部最優的問題，對傳統的變異操作進行改進，提出一種分段多點變異策略，即在保證題型和知識點不變的前提下，從試題庫中抽取新的具有相同難度、知識點的題型來替代舊的題型，從而保持試題的實時性更新。具體操作如圖4所示。

圖4 變異操作策略

4.4 改進遺傳算法

根據上述的改進，可以將傳統的圖1用于試卷組卷的遺傳算法改進為如圖5所示。

圖5 基于改進遺傳算法的組卷策略

5 算法驗證

5.1 仿真部署及工具

為驗證算法的正確性和效率，采用C#進行編程開發，采用Mysql對試題庫進行構建。試題庫數量總共為10萬條，題型總共分為5種：選擇、填空、判斷、計算、簡答，編碼01～05；難度設計為較易、易、中、難、較難，分別編號為01～05；區分度編碼設計為9種，分別從01～09；知識點總共為100個，編碼設計為00～99；答題時間設計為1-30個單位，1個單位30s。

5.2 仿真編程

以改進變異策略的編程為例，其具體實現代碼為：

//從數據庫中選擇相同知識點和同類型與同分數的試題題號

var other DΒ=from a in problem List

where a.Points.Intersect(problem.Points).Count()＞0

select a;

List＜Problem＞small DΒ =other DΒ.Where(p=＞Is Contain

(paper， p)).Where(o=＞ o.Score==temp.Score o.Type==temp

.Type o.ID!=temp.ID).To List();

//從符合要求的試題中隨機選一題替換

if(small DΒ.Count＞0)

{

int change Index=rand.Next(0，small DΒ.Count);

u.Problem List[index]=small DΒ[change Index];

}

5.3 仿真結果

設置最大迭代數為1000，迭代初始種群規模10、20、50、100、150。根據編程仿真，可以得到在不同初始種群規模下的迭代時間。具體見圖6所示。

圖6 不同種群規模下的迭代時間統計

同時以100次試驗為例，分別對改進遺傳算法、遺傳算法和傳統隨機抽取算法進行比較，可以得到表1的結果。

表1 不同組卷算法比較

由此可以看出，隨著規模的擴大，其迭代時間越來越長，并呈現出線性的變變化關系，從而說明該算法性能好、收斂速度快的優勢。

6 結語

本文通過對遺傳算法中的選擇操作、交叉算子、變異算子進行改進，對基于實數編碼的智能組卷矩陣模型進行求解，從而得到不同指標參數下的試題組卷最優求解，從而大大提高了組卷質量，并克服了傳統組卷時間較長的問題，大大提高組卷效率。

［1］周顯春，劉東山.無紙化考試智能生成試卷技術的綜述［J］.電腦知識與技術，2011，36：9501-9502，9508.ZHOU Xianchun，LIU Dongshan.An overview of the intelligent generation of test paper in the paperless examination［J］.Computer Knowledge and Technology，2011，36：9501-9502，9508.

［2］宮磊，趙方.基于改進自適應遺傳算法的智能組卷算法［J］.計算機與現代化，2012（5）：152-156.GONG Lei，ZHAO Fang.Intelligent generating test paper algorithm based on improved adaptive genetic algorithm［J］.computer and modernization，2012（5）：152-156.

［3］李欣然，靳雁霞.一種求解組卷問題的量子粒子群算法［J］.計算機系統應用，2012（7）：244-248.LI Xinran，JIN Yanxia.A quantum behaved particle swarm optimization algorithm for solving the problem of generating test paper［J］.Computer System Application，2012（7）：244-248.

［4］李書全，孫雪，孫德輝，等.遺傳算法中的交叉算子的述評［J］.計算機工程與應用，2012（1）：36-39.LI Shuquan，SUN Xue，SUN Dehui，et al.Review of crossover operator in genetic algorithm［J］.Computer Engineering and Application，2012（1）：36-39.

［5］馬永杰，云文霞.遺傳算法研究進展［J］.計算機應用研究，2012（4）：1201-1206，1210.MA Yongjie，WEN Xia.Study on cloud genetic algorithm in［J］.Application Research of computers，2012（4）：1201-1206，1210.

［6］張超群，鄭建國，錢潔.遺傳算法編碼方案比較［J］.計算機應用研究，2011（3）：819-822.ZHANG Chaoqun，ZHENG Jianguo，QIAN Jie.Comparison of genetic algorithm coding scheme［J］.Computer Application Research，2011（3）：819-822.

［7］金弟，劉杰，楊博，等.局部搜索與遺傳算法結合的大規模復雜網絡社區探測［J］.自動化學報，2011（7）：873-882.JIN Di，LIU Jie，YANG Bo，et al.The large-scale complex network community detection［J］.automation of combining local search and genetic algorithm，2011（7）：873-882.

［8］曹道友，程家興.基于改進的選擇算子和交叉算子的遺傳算法［J］.計算機技術與發展，2010（2）：44-47，51.CAO Daoyou，CHENG Jiaxing.Genetic algorithm［J］.computer technology and development to improve the selection operator and crossover operator based on 2010（2）：44-47，51.

［9］趙鑫寧，喻歆，吳錫.一種基于混合概率選擇算子的改進遺傳算法［J］.成都信息工程大學學報，2016（3）：247-254.ZHAO Xinning，YU Xin，WU Tin.A hybrid genetic algorithm［J］.Journal of probability selection operator based on Chengdu Information Engineering University，2016（3）：247-254.

［10］董妍汝.基于選擇算子的遺傳算法改進［J］.辦公自動化，2015（16）：59-61，42.DONG Yanru.Genetic algorithm based on selection operator to improve［J］.Office Automation，2015（16）：59-61，42.

Design of Intelligent Test Paper System Based on Improved Genetic Algorithm

GAO Lingjie
（Baoji Vocational Technology College，Baoji 721013）

Aiming at the problems existing in the test paper speed and quality of the traditional random test paper model，this paper improves the traditional genetic algorithm，and proposes a new intelligent test paper system based on improved genetic algorithm.Based on the constraint of the test paper，test paper build mathematical model，and to test individual attribute values are preserved by genetic encoding method，so as to improve the operation rate，for the test process of knowledge points to the conflict，the variation strategy and cross sectional multi point strategy for optimization，at the same time to solve the problem of population diversity，a large the ratio of crossover and mutation strategy，so as to improve the test speed.Finally with the C#language and Mysql database to achieve the test paper system，greatly improve the quality and speed of the test paper.

genetic algorithm，intelligent generating test paper，genetic coding，fitness function，test paper quality

TP391

10.3969/j.issn.1672-9722.2017.10.005

Class Number TP391

2017年4月10日，

2017年5月13日

高凌潔，女，講師，碩士，研究方向：計算機技術。