智能在線考試系統中遺傳算法組卷的設計和實現

吳 英

WU Ying

（上海政法學院，上海 201701）

0 引言

在計算機課程的教學中，把傳統筆試與計算機技術結合到一起的考試方式越來越被師生所接受。智能在線考試系統研究主要是用來實現學生上機考試。軟件系統通過網絡服務器的設置，學生所用的計算機作為客戶端來登錄服務器獲得試題，答題完畢后網上提交試卷，軟件系統對學生的答卷按班級學號等進行分類、整理。然后進行智能化的判卷、給分（對部分題目類型能夠實現）。其中，試題庫系統的開發一直是教學改革中的重要方面，對改進教學方法和提高教學質量以及實現考試的公平性起到了很大的作用。其中全自動成卷模塊是試題庫系統的一個亮點。

1 在線智能考試系統的設計

1.1 系統的組成模塊

學生考試部分：注冊，登錄，驗證信息，試題下載…

系統管理部分：課程管理，試題管理，學生管理，成績管理及查詢，補考管理…

數據庫部分：學生基本信息，學生選課信息，課程信息，教師信息，試卷信息，各題型信息…

1.2 系統各模塊設計

1）用戶登錄和注冊：根據用戶所屬的不同角色顯示不同的操作頁面。如考生登錄時，顯示生成試卷等待頁面；教師登錄時，顯示題庫管理頁面；系統管理員登錄時，顯示系統維護頁面。

2）角色管理：添加角色 修改用戶、刪除用戶、角色權限管理。

3）用戶管理：添加用戶、修改用戶、刪除用戶、分配用戶的角色。

4）題庫管理：（1）試題類別管理，主要實現試題類別的添加、刪除、修改和排序功能；（2）考試試題管理，主要實現試題的添加、刪除、修改和排序功能；（3）試題答案管理，主要實現試題答案的添加、刪除和修改功能。

5）在線答題：（1）動態隨機生成試卷，使用遺傳組卷算法動態地從題庫中取得試卷的題目，每次生成的試卷是不同的；（2）顯示整套試卷。

6）成績管理：……

2 在線智能考試系統的關鍵技術

2.1 ASP .NET技術

ASP .NET是當今最先進的開發平臺，運行在服務器端。它不僅是Active Server Page（ASP）的下一個版本，還提供了一個統一的Web開發模型，其中包括開發人員生成企業級Web應用程序所需的各種服務，利用它可建立功能更加強大的Web應用。作為Microsoft .NET平臺的一部分，ASP .NET提供了劃時代的新程序設計框架，是創建Web應用的首選平臺。ASP .NET開發速度快，并且為開發、部署和運行Web應用提供了最快捷并且可縮放性程度最高的方式。它可選擇任何一種可用的.NET編譯性程序設計語言，不需要重新編譯，極大地簡化了部署的過程，只需要將程序復制到Web服務器即可。此外，它還提供了一些對數據庫訪問的數據控件，比如DataList、Dat—aGrid控件，使得對數據庫操作更加靈活、方便。鑒于ASP .NET的以上優勢和目前遠程考試存在的問題，采用ASP .NET技術結合B/S模式，設計遠程考試系統。

2.2 使用ADO .NET訪問數據庫的方法

系統使用SQL Server 2000作為應用程序的數據庫，考慮實際需要，主要包括七個表，基本結構如下：

1）角色表：角色ID，角色名稱。

2）用戶表：用戶ID，用戶名，密碼，Email，角色ID。

3）考生表：考生ID，用戶，考試時間，成績。

4）問題種類表：問題類型ID，類型名稱，問題順序號。

5）圖片表：圖片ID，圖片標題，圖片存儲地址。

6）問題表：問題表ID，問題標題，問題內容，添加試題的時問，問題類型ID，問題的圖片ID，難度系數，成績。

7）問題答案表：問題ID，答案標題，答案內容，圖片ID，問題ID。

系統采用類DBConnection來封裝訪問數據庫的某些基礎屬性和函數，如數據庫連接字符串、添加數據庫的參數等。

2.3 基于遺傳算法的自動組卷技術

以往智能在線考試系統大多采用隨機選取法和回溯試探法。隨機選取法方法結構簡單，對于單道題的抽取運行速度較快，但是對于整個組卷過程來說組卷成功率低，有時能夠抽取出一組令用戶滿意的試題。只不過由于它隨機選取試題的范圍太大，無法確定目前條件下哪些區域能夠抽取合適的試題，反而可能在那些已經證明是無法抽取合適試題的區域內反復選題，進行大量的無效操作進入死循環，最終導致組卷失敗。即使組卷成功，花費時間也令人難以忍受?；厮菰囂椒ㄊ欠N有條件的深度優先算法，對于狀態類型和出題量都較少的題庫系統而言，組卷成功率較好，但在實際應用時對內存的占用量很大，程序結構相對比較復雜，而且選取試題缺乏隨機性，組卷時間長，對于現今越來越流行的考生網上隨機即時調題的考試過程來說，它已不符合要求。

我們從試題的數量及試題庫結構兩個方面分析，將遺傳算法應用到該系統中，努力實現試卷的生成和考查的知識點盡可能地接近、并由教師控制試卷的難度系數等。遺傳算法是模擬生物界適者生存、自然選擇等生物進化機制發展起來的一種高度并行、隨機和自適應的搜索算法，是解決復雜問題的一個有效途徑。

2.4 遺傳算法的一般結構

在設計遺傳算法時通常按以下步驟進行閉：1）編碼方案：遺傳算法求解問題．一般不是直接在問題的解空間上，而是利用解的某種編碼表示。2）確定適應函數：適應值是對解的質量的一種度量。解的適應值是演化過程中進行選擇的依據。3）選擇策略的確定：優勝劣汰的選擇機制使得適應值好的解有較高的存活概率。4）控制參數的選取：控制參數主要包括種群規模、算法執行的最大代數、執行不同的遺傳操作的概率及一些輔助性的控制參數。5）算子的設計：主要有雜交、變異和再生。6）確定算法的終止準則。

2.5 基于遺傳算法的組卷問題的設計

1）染色體編碼

編碼就是用一種數字排列方案來表示問題的解的方法，利用編碼將問題的解空間映射到GA算法的編碼空間。如何將問題的解轉換為編碼表達的染色體是遺傳算法的關鍵問題，即先要將問題的解空間映射成一組代碼串。編碼方案的選擇依賴于問題的性質，并影響到算法內操作的設計，是影響算法性能的重要因素。常見的編碼方案有二進制編碼、十進制編碼、實數編碼等。采用二進制編碼，用l表示該題被選中，O表示該題未被選中。這種編碼簡單明了，但進行交換等遺傳操作時，各題型的題目數難以精確控制。而且，當題庫中題量很大時，編碼很長。我們采用實數編碼，將一份試卷映射為一個染色體，組成試卷的各個試題映射為基因，基因的值直接用試題的題號表示。這樣染色體的編碼可表示為（G1，G2，G3，…Gn）。其中Gi（i＝l，2，…n，n為試卷的總題目數）為試題編號。比如要組成一份選擇題5道、填空題5道、簡答題2道的一份試卷，則染色體編碼可以是：

編碼時將同一題型的題目放在一起，同時為保證一份試卷中考查點不重復，每條染色體中各基因的考查點編碼必須各不相同。由于不同的題型是從不同的題型表中取出，有可能在同一個基因串中會出現相同的試題編號，它們屬于不同題型，考察的知識點也未必相同。故這種情況很正常的，不影響我們進行組卷。

在實際組卷過程中，假設在試卷中每種題型的數目是固定的，且相同題型的分數和答題時間是相同的。這樣我們將整個編碼串按照題目類型劃分為不同的功能塊，每個功能塊可以認為是獨立的編碼。也就是說每個功能塊對應一種特定的題型。顯然按這種規則產生的群體已經滿足了試卷對題型、分數和答題時間的要求。

2）群體的初始化

根據用戶選定的考試內容及各種題型的題目數，按同一試卷中考查點不重復的原則，從相應題型表中隨機抽取試題。生成初始群體，群體的大小按經驗或實驗給出由于遺傳算法和其它啟發式算法一樣，不對全部解空間進行窮舉搜索。因此初始的候選解群體的選擇會對得到最終解的速度和質量有影響，初始的候選解群體在解空間內分布得越均勻，它們擁有的遺傳基因就越有代表性。

3）適應度函數

在遺傳算法中，以適應度大小來區分群體中個體的優劣。設di（i＝1，2，… ，m，m為試卷的總題目數）表示基因串中所選試題的考查點，用集合表示用戶要求試卷中應包含考查點的集合，生成的試卷滿足用戶關于各考查點要求的程度可以用f1的大小來評價：

可見，f1的取值范圍為：0≤f1≤1，f1的值越小，生成的試卷越接近于用戶關于各考查點的要求。

4）遺傳算子

遺傳算法的交叉概率Pc和變異概率Pm是影響遺傳算法行為和性能的關鍵所在，直接影響算法的收斂性。Pc和Pm越大，算法產生新個體的能力就越強。個體之間的適應度波動比較大，產生新的超平面的能力比較強：Pc和Pm越小，算法使個體趨于收斂的能力越強。個體的平均適應度比較平穩，有可能產生早熟現象。所以我們采用自適應的思想，在算法的運行過程中對Pc和Pm進行調整。讓它們隨著個體適應度值的增加而變小，隨著個體適應度值的減小而增加。由于種群中每一個功能塊對應著一個題型，所以，為了保證每個題型的數目不變，交叉點的選擇不能破壞功能塊的完整性。假設交叉點位于第i個功能塊內，則前i個功能塊不變，從第i+1個功能塊開始逐位交換。（交叉如果在功能塊內也發生的話，可能會出現同一模塊中有重復試題的情況）。普通的變異操作可能會使用戶指定范圍外的題目出現在染色體中，也會使各題型的題目數難以保證，采用有條件的變異算子。即每個個體的每一個基因座上的基因都按設定的變異概率Pm，在一定范圍內（與該基因題型相同且考查點與本個體其他題的考查點不重復）變異。通過變異算子可以達到局部搜索的目的。

5）最優保存策略

進行了選擇、交叉、變異操作后，比較新一代的最好個體與上一代的最好個體的適應度，如下降。則以上一代最好個體替換新一代的最差個體。此策略可以保證迄今為止的最優個體不會被交叉、變異等遺傳運算所破壞。它是遺傳算法收斂性的一個重要保證條件。

3 結束語

我院上機考試系統在實施過程中存在的問題也是顯而易見的。例如：試卷的生成和考查的知識點如何盡可能地接近；交叉概率和變異概率波動度有限，導致某些個體產生早熟現象，未能滿足計劃中的考查點的要求等。如何改變由管理員控制試卷的難度系數，而由系統提高自適應性，最終到達根據學生在考試過程出現的錯誤給予相應的調整是我們需要進一步研究的。

[1]尹紅衛,等.一種改進的遺傳算法及其在組卷系統中的應用[J].現代計算機,2006,05.

[2]陳蕾,等.基于遺傳算法的自動組卷系統的技術實現[J].成都航空職業技術學院學報,2007,03.

[3]張愛文.自適應遺傳算法用于自動組卷中的數學模型設計[J].哈爾濱理工大學學報,2006,05.

[4]白云飛.基于自適應遺傳算法的智能組卷的研究[J].河北工業科技,2006,04.