遺傳算法在通用考試系統自動組卷中的研究與應用

摘要： 本文根據教師教學效果及考生考試所存在的問題，闡述了利用計算機組卷實現考試規范化、科學化的必要性。通過分析有關組卷策略，選擇模擬退火遺傳算法解決自動組卷中組合優化問題。通過對組卷過程及各種影響它的重要因子的分析，確定其數學模型，并根據遺傳算法的思想，對數據進行預處理以及選擇染色體編碼方案，經過適應度評價、選擇算子、交叉算子、變異算子以及迭代終止條件，最后將其應用于實踐。實驗結果表明，本文采取的數學模型是適合用戶的需求的。本文對自動組卷系統進行了設計，其研究結果具有一定的參考價值。

關鍵詞：遺傳算法 模擬退火算法 模型 自動組卷

引言

隨著計算機技術和人工智能的發展，計算機技術已進入現代教育領域并形成一門新興的邊緣科學。利用計算機建立試題庫，實現計算機自動選題、組卷，是實現考試規范化科學化的重要措施，更是實現考教分離的一個重要手段。如何從試題庫中快速地、能滿足用戶各項要求地抽出試題組成一份試卷就是組卷需要解決的問題。本文在對組卷系統進行研究的同時，結合遺傳算法理論，利用我院的《編程語言基礎》課程，探討一種合適的算法解決考試系統中的自動組卷的問題。

一、遺傳、模擬退火算法概述

模擬退火遺傳算法是將遺傳算法與模擬退火算法相結合而構成的一種優化方法。遺傳算法的局部搜索能力很差，但把握搜索過程總體的能力較強；而模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優解，但模擬退火算法對整個搜索空間的狀況了解不多，不便于使搜索過程進入最有希望的搜索區域，從而使得模擬退火算法的運算效率不高。但如果將遺傳算法與模擬退火算法相結合，互相取長補短，則有可能開發出性能優良的新的全局搜索算法，這就是遺傳模擬退火算法的基本思想。

與基本遺傳算法的總體運行過程類似，遺傳模擬退火算法也是從一組隨機產生的初始解（初始群體）開始全局最優解的搜索過程，它先通過選擇、交叉、變異等遺傳操作來產生一組新的個體，然后獨立地對產生的各個個體進行模擬退火過程，以其結果作為下一代群體中的個體。這個運行過程反復迭代地進行，直到滿足某個中止條件為止。

傳統遺傳算法存在提前收斂的缺陷，而模擬退火算法由于采用概率接受目標函數值變好的試探點，因此這種搜索策略有利于避免搜索過程因陷于局部最優解而無法自拔的弊端。將這兩個方法結合起來形成遺傳模擬退火算法可以更好地解決組卷的優化工作。

二、自動組卷系統設計

自動組卷系統［１，２］實質上也是一個信息處理系統。本課題要設計一個自動組卷系統，該系統能夠從題庫中選擇合適的試題組成滿足考試要求和用戶要求的考試試卷系統。教師通過該系統，先在系統中設置試卷的各種約束條件及要求，系統自動地從試題庫中快速地組出針對不同測評目的的試卷，以滿足各類考試及測評要求。自動組卷系統要有一個開放式的數據庫，可以讓教師將自己收集到的試題經審查后錄入到試題庫中，使得題庫不斷地豐富，組出來的試卷分布更合理。

根據需求分析的結果，本系統主要由5個模塊組成：系統管理模塊、試卷管理模塊、試題管理模塊、系統維護以及幫助等。系統層次結構如圖1所示。

三、實驗結果及分析

為驗證該模擬退火遺傳算法的可行性與有效性，以《編程語言基礎》課程為例，在試驗中題庫共有1000道題，填空、選擇、寫程序執行結果、完成程序、編程5種題型，8個知識點。設置試卷中各題型所占的分值比例為2∶3∶2∶1∶2，題目數量的比例為20∶15∶4∶5∶2，8個知識點所占的比例為10∶20∶10∶20∶10∶10∶10∶10，難∶較難∶中∶較易∶易為5∶15∶50∶20∶10。整卷的難度系數為0.6。

經過測試，將得到的試卷用于學生測試，測試的試卷分析表如表1所示。由此可見，這個結果是符合要求的。

由于該算法在當前的智能教學系統的理論研究與實際應用具有重要意義，本課題的研究是十分必要的，它也為構建一個完善的ICAI系統打下了很好的基礎。

參考文獻：

［1］程艷.計算機自適應考試的理論模型研究.計算機與現代化，2006，133(9)：24-27.

［2］畢忠勤，陳光喜，徐安農.計算機自適應測試系統的算法.桂林電子工業學院學報，2004，24(6)：50-53.

［3］王遠志，孫立鐫.基于遺傳模擬退火算法約束求解算法.2005，10(2)：26-30.

［4］Li Shouzhi，Li Minyuan，Pan，Yongxiang.Genetic Annealing Algorithm and Its Convergence Analysis.CONTROL THEORY AND APPLICATIONS，2001，19(3)：376-380.