遺傳算法在計算機考試系統中的應用研究

摘 要：現如今，計算機考試系統已經取代了傳統的紙質試卷方式，大幅度減少了監考教師的工作量。應當注意到遺傳算法在其中也起到了非常重要的作用。文章簡單描述了什么是遺傳算法，然后結合實例詳細闡述了遺傳算法在計算機考試系統的應用方法。

關鍵詞：遺傳算法；計算機；考試系統

遺傳算法的整體搜索策略、優化搜索方法在計算時可以不借助梯度信息以及其他輔助知識，只需要借助可影響搜索方向的目標函數、適應度函數。也就是說遺傳算法提供了一種實用、高效地復雜系統問題解決框架。也正因為如此，遺傳算法的應用領域非常廣泛。其中計算機考試系統便是其中之一。近年來，隨著IT行業的發展，基于遺傳算法的計算機考試系統研究也越來越成熟[1]。

1 遺傳算法概述

遺傳算法是模擬達爾文生物進化論中的自然選擇、生物進化過程的一種過程搜索最優解方法。這種算法是1975年美國Holland教授提出的。具有可以直接操作結構對象、無連續求導限制、全局尋最優解、內在隱并行性的特點。在實際應用中，遺傳算法可采用概率化方法，自動化獲取、搜獲、調整得到最優解。正是因為這些特點，遺傳算法被廣泛應用在信號處理、機器學習等方面。尤其是在計算機考試系統設計方面，遺傳算法作為其中關鍵技術之一，起到了非常重要的作用[2]。

2 基于遺傳算法的計算機考試系統設計

2.1系統框架

計算機考試系統主要包括3個部分：（l）服務器端。服務器端又可分為3個模塊，即教師信息管理模塊，在這個模塊中可以進行教師信息的增、刪、改、查；考試成績回收模塊。其主要功能就是從學生客戶端回收評分成績；數學備份模塊，主要是對系統中的數據庫數據進行備份，一旦發生意外情況，可自動恢復。（2）教師客戶端。其中包括考試信息管理模塊、學生信息管理模塊、試題維護模塊、考試狀態管理模塊4個部分。其中考試信息管理模塊主要提供設置考試班級、日期、市場以及試卷組建、分配功能；學生信息管理模塊主要就是對學生信息進行增、改、刪、查；試題維護模塊主要是指對試題的增、刪、改、查；考試狀態管理是指實現對學生參加考試、正在考試、未參加考試3種狀態的管理，這一模塊能有效幫助教師實現對學生的實時監控。（3）學生客戶端。該部分包括試題下載、自動評分兩個模塊。在試題下載模塊中，學生完成登錄后，就可通過該模塊將試題下載到本地。當學生完成答卷之后，單擊“交卷”，系統就會對學生試卷自動閱卷，評分并將其最終結果傳送到服務器端。另外，如果考試時間為零，系統也會進行自動閱卷、評分，并發送到服務器[3]。

2.2遺傳算法應用原理

在計算機考試系統中包含多套考試題，在考試過程中系統可依照成套標準靈活選擇試題。但以往的組卷方法靈活度不足，無法有效控制試題選取。因而，為了進一步提高試題的靈活性，實現重新組卷，可采用遺傳算法。這樣便能模擬自然遺傳規律，搜索最優解。其主要應用步驟包括：應用遺傳算法理論進行組卷問題分析；先定義染色體，實現試題編碼；而后初始化種群，并對種群進行遺傳算法操作；經過選擇、交叉、變異，搜索到最優解后算法停止。其中交叉操作是指對于不同的染色體利用某種方式使其部分基因交換，這樣就可以形成一個新的染色體。常見的交叉方法包括單點交叉、多點交叉、均勻交叉。選擇操作是指在完成某個染色體個體的適應度函數值計算后，采用輪盤賭選擇機制進行選擇；變異操作是指用其他字符代替某個染色體編碼串的部分基因，對于計算機算法來說，其變異方式包括二進制編碼染色體變異、浮點編碼染色體變異。可以說遺傳算法應用組卷，既能保證高效的組卷速度，也能保證試卷質量。但需要注意的是傳統的遺傳算法容易出現過早收斂的問題。隨后，隨著遺傳算法研究的深入，多種能夠彌補過早收斂問題的遺傳算法走進了人們的視野。如單親遺傳算法、基于概率和自適應遺傳算法、采用功能結構改進遺傳算法等。

2.3遺傳算法應用實踐分析

本文主要針對一種改進的遺傳算法進行了分析。其主要應用步驟如下[4-5]。

2.3.1編碼

以往傳統的遺傳算法編碼算法主要是應用二進制編碼方式。這種編碼方式能科學地、迅速地表達出多變量優化問題。但二進制編碼的編碼長度較長、搜索空間較大，其搜索效率較低。本文提出了一種基于實數矩陣的編碼方式，既能有效減少個體編碼時間，也能提高求解速度，從而盡可能快地完成最優試卷的求解。其基本思想是：先將試題庫中的每個試題作為分析對象，而后對其進行獨立的實數編碼。如果試題具有Ⅳ_個屬性值，那么其特征向量則應為N+l維，維與組卷參數一一對應。比如難度、題型等。其中的主要映射方式是：試卷與矩陣染色體對應，試題與矩陣向量對應，試題屬性就是染色體基因位。

2.3.2適應度設計

適應度在遺傳算法中起到了非常重要的作用。通過適應度參數能夠定量地分析種群個體在遺傳計算中能夠達到的最優解。這樣就能夠進行多種遺傳算法操作，并且還能夠有效控制算法終止條件。也就是說適應度對遺傳算法的收斂有著非常大的影響。在設計適應度函數時，由于其函數定義域無條件限制，因而采用將定義域限制為不同的集合。在選擇使用度函數時，應保證函數的區別性，從而保證即便是輸入不同，在計算后也能夠保證輸出的可區分，最終提高搜索效率。

針對組卷問題，在設計適應度函數時可應用一種基于線性尺度變換的適應度函數。其主要操作方法是目標屬性賦權值、組合目標函數、計算整體適應值。為了保證種群的多樣性，可以將指數比例變換方法應用到適應度設計中，如采用F=exp （-af），作為目標函數。

2.3.3種群初始化

種群初始化的關鍵在于起點選擇。以往的遺傳算法采用的隨機方式進行種群初始化。雖然這樣能提高種群的多樣性，但是若將其應用在組卷中，則達不到良好的組卷效果。為此，在種群初始化時應加以改進、優化。如可以采用這樣一種種群初始化方法：依據知識點、題型對試卷的約束，綜合分析系統參數，最終得到最優試卷種群。

2.3.4改進遺傳算子

之所以進行遺傳算子改進是為了保證算法更加科學，滿足組卷要求。結合傳統的基礎選擇、變異、雜交算子，對傳統選擇算子可以采用基于適應值排序的選擇方法，以降低比例變換參數對算子的影響；對傳統雜交算子，可采用分段多點雜交方法，避免雜交子代的沖突；對傳統變異算子，可采用分段多點變異方法，以保證在題型、知識點的情況下，進行新舊試卷更換。

2.3.5算法實現

首先，在算法過程中。試題數據庫選擇SQL Server2000，同時采用MATLAB2010進行算法編碼。其試題的基本參數主要包括題型、難度、曝光度、區分度、知識點。其中題型包括選擇、填空、判斷、計算、簡單共5個。難度包括較難、難、中、易、較易5個。曝光度分為9種。區分度也分為9種。知識點共100個。在應用遺傳算法時，對于參數設置可將其進化代數設置為1 000，種群規模分為10，20，50 3種。其算法流程主要包括：開始、染色體編碼、種群初始化生產、依據適應度排序。而后如果滿足停止條件，則進行試卷編排、輸出，最終結束。如果不滿足停止條件，則要進行遺傳選擇操作，雜交操作，變異操作，并返回到適應度排序操作，繼續循環下去，直至滿足停止條件，進行試卷編排、輸出后，結束算法。通過應用結果能夠看出采用這種算法能夠有效提高種群群體平均適應值的收斂速度，且能夠保證基本上都可以達到最優值。最重要的是能保證指標誤差小于1%。如果種群規模不同，其遺傳進化速度也會有所不同。也就是如果迭代代數增加，則種群規模變大，進化速率提升。 總的來說，應用上述算法具有3個方面的優勢：（l）能夠降低算法過程沖突。比如在種群初始化階段，可根據實際需求靈活設置；其基因變異、染色體雜交算子基本是同題型、通知識點變異，在變異操作時能避免數據庫沖突。（2）試題編碼方式有助于系統試題屬性擴展。（3）分段雜交算子能保證系統數據知識點的穩定，減少題庫中存在試題編號的問題。

3 計算考試系統設計

3.1需求分析

首先，在用戶需求方面，結合實際分析能夠發現基于遺傳算法的計算機考試系統應滿足一下幾個要求：操作靈活、安全穩定、高效。其次，在功能需求方面，其計算機考試系統應包括題庫管理、組卷、統計分析、教師和學生管理[6]。

3.2系統結構

之前已經提到了系統的三大客戶端及其每個客戶端下屬的功能模塊。為此，在系統結構設計中應保證每個功能模塊都能夠實現。該系統結構主要是采用B/S結構模式，對用戶操作界面、系統功能實現、題庫數據存儲等部分進行層次處理，從而保證邏輯結構的清晰、完整，避免出現功能耦合現象，最終提高系統的編碼效率和可擴展性。

3.3數據庫設計

數據庫設計主要包括概念結構設計、邏輯結構設計、系統功能模塊設計、主功能模塊設計、成績模塊設計。其中概念結構設計包括數據實體、數據屬性、數據關系3方面內容。該系統的主要數據實體包括教師、學生、試題、試卷、試題；而數據屬性是指數據實體與關系的基本特征；數據關系是指數據與實體的一對一、一對多、多對一關系。邏輯結構設計是指各數據表之間的邏輯關系表示。系統功能模塊設計是指對每個功能模塊進行細化、設計[7]。如上文中提到的教師模塊內容、功能。主功能模塊設計亦是如此。之所以將成績模塊單獨列出，主要是因為該模塊對題庫的各項指標有較大的影響，并且其實用功能也非常強。

4結語

綜上所述，結合實際需求，對遺傳算法進行改進，能有效提高計算機考試系統的實用性。但也應當認識到隨著計算機技術的發展，遺傳算法的應用會更加成熟、廣泛。

[參考文獻]

[1]溫靜，郝大治，張曉峰.基于遺傳算法的智能組卷考試系統研究[J].科技傳播，2017 （22）：134，179

[2]蘭青青.基于遺傳算法的智能組卷考試系統設計[J].信息系統工程，2017 （5）：174.

[3]卞勇.基于遺傳算法在線考試系統題庫的設計與實現[J].寧波職業技術學院學報，2016 （6）：87-89

[4]馮秀梅.基于遺傳算法的智能組卷考試系統研究與實現[D].濟南：山東師范大學，2016

[5]馬玲.基于遺傳算法的在線考試系統開發研究[J].信息化建設，2016 （5）：43.

[6]魏冬梅.基于遺傳算法的自動組卷系統的設計及實現[D].石家莊：河北科技大學，2015.

[7]劉召華.基于遺傳算法的考試系統設計與實現[D]楊凌：西北農林科技大學，2015