形成性測評系統自動組卷策略實現

李守宏

（遼寧廣播電視大學圖書館，沈陽 110034）

形成性測評系統自動組卷策略實現

李守宏

（遼寧廣播電視大學圖書館，沈陽 110034）

形成性測評是指對學習者學習過程的全面測評，對學習者課程學習成果的階段性考核。在線考試是遠程教育形成性測評中最基本、最常用的方式之一，編制高質量的試卷可以有效地檢驗學生對知識的掌握水平及教師的教學效果。遺傳算法是建立在自然選擇和群體遺傳學基礎上的一種計算優化方法，適合于并行處理，具有應用范圍廣、收斂速度快等顯著特點。而形成性測評中自動組卷策略是需要教師根據不同教學階段、不同教學任務、不同學生學習狀況進行多方面的組卷要求的過程，這是一個多目標優化求解問題的過程。采用遺傳算法進行自動組卷設計，從參數編碼、適應函數的設計、遺傳操作的設計、控制參數的設計等幾個方面進行設計和改進，系統可自動生成多份按策略規劃的試卷，保證了試卷的準確率和科學性。

形成性測評；自動組卷；遺傳算法

0 引 言

形成性測評是指對學習者學習過程的全面測評，是對學習者課程學習成果的階段性考核［1－3］。在線考試是Internet的一個重要應用［4］，是遠程教育形成性測評中最基本、最常用的方式之一，編制高質量的試卷可以有效地檢驗學生對知識的掌握水平及教師的教學效果，而試卷質量又依賴于組卷策略的科學性。因此，研究組卷算法策略，提高試題的科學性，對形成性測評系統有著極為重要的作用。

遺傳算法是建立在自然選擇和群體遺傳學基礎上的一種計算優化方法［5－7］，是模擬生物在自然環境中的遺傳選擇和自然淘汰的生物進化過程而形成的一種自適應全局優化概率搜索算法模型［8］。它具有隱并行性和全局搜索等顯著特性，同時，遺傳算法具有應用范圍廣、收斂速度快、思想簡單、易于實現、應用效果明顯等優點［9］。而形成性測評中自動組卷策略是需要教師根據不同教學階段、不同教學任務、不同學生學習狀況進行多方面的組卷要求的過程，這是一個多目標優化求解問題的過程，采用遺傳算法作為形成性測評系統中自動組卷策略，能很好的滿足自動組卷的需要［10－11］。

1 組卷策略試題屬性指標設計

形成性測評系統中試題都是由教師錄入并存放在試題庫中，試題本身含有固定的屬性，試題各項屬性指標的設計直接影響到形成性測評系統組卷的準確性和效率性。在本文提到的形成性測評系統中，試題屬性指標主要有題號、題型、課程、難度和分數5項［12－13］。

2 自動組卷的算法設計

本系統采用遺傳算法作為形成性測評系統中自動組卷策略，算法主要從參數編碼、設計適應函數、設計遺傳操作、設計控制參數4個方面進行設計和改進。

2.1 確定編碼方案及初始種群的生成

確定編碼方案的第一步是解決染色體編碼問題，即采用何種方法將問題的解空間映射成一組代碼，常用的編碼方法有二進制編碼方法、動態編碼、實數編碼方法等［14］，而選擇何種編碼方案依賴于問題的性質。在形成性測評系統中，為了避免隨著題庫中題量的不斷增多，染色體的長度不斷增加，使計算的復雜度增加，組卷時間增長，同時考慮到實際組卷時每種題型的題數和分數相互獨立，而且統一題型內部各題的分數都是相同的特征，因此本系統采用按照題型進行分段實數編碼方法［15］。分段實數編碼方法是將一份試卷映射為一個染色體（個體），組成該試卷的每道試題的題號作為基因，基因的值直接用試題號表示，即每一段基因都由試題的實際題號組成（不能出現相同題號），再將多個題型編碼段串聯在一起，組成一個染色體，此染色體即是一份試卷，試卷中的每一個題目在題庫中的編號就是染色體中的一個基因。每段代碼的長度由該題型的試題數決定，各題型的代碼段相互獨立。

圖1 染色體代碼片段

總的來說染色體的編碼可以表示為：（M1，M2，M3，…，Mn），其中Mi為試題題號。遺傳算法在進行遺傳操作前，需要產生一個由若干初始解組成的初始種群。初始化種群是指隨機產生N個初始串結構數據，每個串結構數據稱為一個個體，N個個體構成了一個群體。在形成性測評系統中，種群是根據不同題型及題量的要求，從初始化后滿足條件的試題中隨機生成。這樣設計的初始種群可有效縮短染色體的編碼長度，提高算法的收斂速度，同時滿足了不同課程、題型和題量等方面的要求［16］。初始化種群算法如下：

2.2 設計適應函數

遺傳算法中，適應度函數是評價試卷種群中個體的優劣程度的指標，直接影響到自動組卷算法性能的好壞。本系統的適應度函數反映了染色體對應的各個試題屬性與用戶的成卷要求之間的差別，其偏差值用來構造目標函數F，偏差值越小時，適應度就越大，越符合組卷要求。通常意義上是適應值越大的個體越好，適應值越小的個體越差。綜上所述，自動組卷的目標函數就是取各項組卷指標偏差之和的最小值，即在形成性測評系統中組卷問題的目標函數為：minf（x）。

2.3 遺傳算子設計

2.3.1 選擇算子

選擇算子的作用有2點：一是能夠在一定程度上保持原來的種群中的優良個體的特性；二是使得算法能夠搜索新的基因空間，從而使新種群中的個體具有多樣性。本系統采用選擇算子適應度比例法，即后代遺傳的可能性是根據個體的不同適應值的概率決定的［17］。

2.3.2 交叉算子

在遺傳算法中，交叉算子可以使原來的種群中的優良個體的特性能夠在一定程度上保持，同時也能使算法搜索新的基因空間，從而在種群中產生多樣性個體。具體過程如下：隨機從群體中選取2個個體進行交叉運算，通過在群體中隨機挑選2個染色體，并按照設定的交叉概率PC對每對染色體上的基因進行交換產生新個體，完成交叉的工作。在遺傳算法的組卷過程中，組卷最終必須滿足題型題量的要求，每種題型對應染色體中的一個獨立分段。因此，在進行交叉運算時可采用分段單點交叉，按題型分段來進行交叉，整個染色體就表現為多點交叉。交叉后生成的新個體的新段有可能存在重復的題號或章節編號，則應該重新選擇交叉點，并重新交叉以得到新的子代。具體算法如下：

2.3.3 變異算子

在遺傳算法中，大部分的搜索功能由選擇和交叉完成，而變異只是增加找到最優解的能力，同時保持群體多樣性并防止出現早熟現象。變異是以很小的概率隨機的改變種群某個個體某個位置的基因，即把父個體編碼串中某個基因位上的值按某種方式進行改變，產生子個體。變異與選擇算子結合保證了遺傳算法的有效性，使遺傳算法的隨機搜索能力有所提高。具體算法如下：

2.4 設定控制參數

在遺傳算法中，4個運行參數需要提前設定：

1）種群大小。遺傳算法的算法的速度與種群的大小有關，如果種群規模較小，則可提高組卷的收斂速度，但多樣性會隨之降低，不易找到最優解。相反，如果種群規模較大，則組卷的收斂速度降低，計算的復雜度會增加，但容易得到最優解。

2）交叉率和變異概率。交叉率和變異概率直接影響著問題優化的收斂速度和最終解的質量，因此，交叉率和變異概率選取對遺傳算法的影響非常大。一般交叉率Pc取值較大，變異概率Pm取值較小。

3）終止進化代數。遺傳算法要考慮的一個問題是迭代終止條件的設定。最常用的終止方法是規定遺傳迭代的次數，達到此最大迭代次數即終止；第二種終止方法是基于群體中收斂的程度，即已生成的所有個體的平均適應度與最好個體的平均適應度的比大于等于0.995，則算法終止；第三種終止方法是算法在連續多少代后適應值沒有改進時，或適應值比期望適應度值大時則停止迭代，算法終止。

3 自動組卷策略實現

教師在編輯自動組卷策略之前，必須完成題庫的建立，建立題庫時，需要為試題標注相應屬性。當題庫建立完成后，教師可通過策略管理界面編輯自動組卷策略，如圖2所示。

圖2 自動組卷策略界面

按圖2中所示選擇不同的題型、難易程度、各種題型數量、試題分數、課程、策略名稱等，系統會根據所選策略自動進行策略校驗，如圖3所示，校驗有效后，便可根據相應策略自動進行組卷［12－13］。

圖3 組卷策略校驗

4 結 語

本文提出了利用遺傳算法在形成性測評系統中實現自動組卷策略，并在參數編碼、適應函數的設計、遺傳操作的設計、控制參數的設計等幾個方面進行設計和改進，系統可實現在1分半左右時間內自動生成50份不同試題及題序的試卷，并可對創建的試卷進行修改、預覽等操作，在很大程度上提高形成性測評系統組卷工作效率，保證了試卷的科學性與準確性。

［1］陳海建.電大系統中對形成性考核管理的研究［J］.上海科學教育，2008（11）：17.

［2］梅曉妍，王民權.高等職業教育形成性考核的探索與實踐［J］.職業教育研究，2007（1）：148-149.

［3］魏霞，王勝.網絡學習評價現狀分析及對策［J］.中國醫學教育技術，2007（4）：159-162.

［4］劉陽，曹寶香，馬艷.基于Web考試系統的研究與實現［J］.沈陽師范大學學報：自然科學版，2006，24（4）：208-211.

［5］HOLLAND J H.Adaptation in nature and artificial systems［M］.Michigan：The University of Michigan Press，1975：45-50.

［6］PONES J C，GIDDENS T，SURYA B Y.The development and evaluation of an improved genetic algorithm based on migration and artificial selection［J］.IEEE Transactions on Systems，Man and Cybernetics，1994，24（1）：30-33.

［7］JOHN J G.Optimization of control parameters of GA［J］.IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）：1-20.

［8］周明，孫樹棟.遺傳算法原理及應用［M］.北京：國防工業出版社，1999：8-15.

［9］董聰.廣義遺傳算法［J］.大自然探索，1998，16（1）：17-30.

［10］毛秉毅.基于遺傳算法的智能組卷系統數據庫結構的研究［J］.計算機工程與應用，2003，39（6）：230-232.

［11］孫勇，柏云.基于遺傳算法的試題組卷策略［J］.淄博學院學報，2002，4（3）：27-28.

［12］中央廣播電視大學財經部.西方經濟學形成性考核冊［M］.北京：中央廣播電視大學出版社，2011：1-5.

［13］中央廣播電視大學理工部.計算機應用基礎形成性考核冊［M］.北京：中央廣播電視大學出版社，2011：1-6.

［14］魏平，于海光，熊偉清.基于進化穩定策略的單親遺傳算法求解組卷問題［J］.微電子學與計算機，2005（1）：105-109.

［15］萬文軍，彭輝云.一種改進實數編碼遺傳算法及其應用［J］.江西電力職業技術學院學報，2007（2）：71-73.

［16］趙亮，馮博琴.組卷要求的可滿足性檢查［J］.計算機工程與應用，2004，40（27）：222-224.

［17］潘正君，康立山，陳毓屏.演化計算［M］.北京：清華大學出版社，桂林：廣西科技出版社，1998：9-13，16-35.

Realization of automatic test paper strategy in formative evaluation system

LI Shouhong
（Library，Liaoning Radio ＆TV University，Shenyang 110034，China）

Formative evaluation refers to a comprehensive evaluation of learners learning process；it is the periodic assessment of learners'curriculum learning outcomes.The online exam is one of the most basic，most common ways in formative evaluation of distance education，and the composition of high-quality examination papers can effectively test the effect of the students'mastery level of knowledge and teachers'teaching effectiveness.The genetic algorithm is an optimum calculating method on the base of natural selection and population genetics，is suitable for parallel processing with a wide range of applications，high convergence speed and other notable features.While the automatic test paper strategy in formative evaluation is a process that needs teachers meeting various requirements of generating test paper according to the different stages of teaching，different teaching tasks and different students'learning situations，consequently，this is a process of solving multi-objective optimization problems.Using genetic algorithms for automatic generating test paper design，it designs and makes improvement from the aspects of encoding parameter，adapting to the design of the function，the genetic manipulation，the control of parameter etc.，and the system can automatically generate multiple copies of papers that based on the strategic planning，so as to ensure the papers'accuracy and scientific.

Formative evaluation；Automatic test paper；Genetic Algorithms

TP311.52

A

10.3969／j.issn.1673-5862.2013.02.033

1673-5862（2013）02-0277-05

2013-03-15。

遼寧省教育廳2012年科學研究一般性項目（L2012495）。

李守宏（1962-），男，遼寧沈陽人，遼寧廣播電視大學高級工程師。