三種常用智能組卷算法剖析

摘要：當今社會已經進入了信息化時代，信息傳遞的高速化，信息產業(yè)的多樣化，信息科技的高新化已經成為全球經濟和社會發(fā)展的基本特征。隨著計算機應用的日益普及和深入，傳統(tǒng)的考試方式也面臨著變革，而利用計算機考試系統(tǒng)實現(xiàn)無紙化考試已經成為一種重要的考試方式。基于計算機技術的在線考試系統(tǒng)可以借助于遍布全球的Internet進行，因此考試既可以在本地進行，也可以在異地進行，大大拓展了考試的靈活性。試卷可以根據(jù)題庫中的試題即時自動生成，可避免考試前的壓題；而且可以采用大量標準化試題，在這其中從題庫中的試題即時自動生成試卷是在線考試系統(tǒng)中最關鍵的一個環(huán)節(jié)，是試題庫系統(tǒng)的重要的核心部分，決定到試卷質量的好壞。目前這種智能組卷算法比較常見有隨機組卷算法、回溯組卷算法、遺傳組卷算法，下面逐一剖析這幾種算法的應用。

關鍵詞：智能組卷 隨機組卷算法 回溯組卷算法 遺傳組卷算法

一、 隨機組卷算法

隨機選取法根據(jù)狀態(tài)空間的控制指標，由計算機隨機的抽取一道試題放入試題庫，此過程不斷重復，直到組卷完畢，或已無法從題庫中抽取滿足控制指標的試題為止。該方法結構簡單，對于單道題的抽取運行速度較快，但是對于整個組卷過程來說組卷成功率低，即使組卷成功，花費時間也令人難以忍受。尤其是當題庫中各狀態(tài)類型平均出題量較低時，組卷往往以失敗而告終。

實現(xiàn)隨機組題必須保證所隨機產生的數(shù)據(jù)不能重復。因此，在開發(fā)系統(tǒng)時一般利用SQL語句實現(xiàn)隨機的算法及其產生的優(yōu)化隨機算法。采用SQL語句中NewID（）可以解決好每抽一道題進行一次循環(huán)判斷，而且提高運行中大量的資源空間利用率，運行速度較高，NewID（）語句是使數(shù)據(jù)庫中的數(shù)據(jù)信息隨機排序，然后按一定的題數(shù)，從數(shù)據(jù)庫中讀取試題。

用SQL語句隨機訪問則不需要循環(huán)判斷，它只是在數(shù)據(jù)庫中的表中數(shù)據(jù)隨機重排后讀取，因此速度相對很快。但用SQL語句則不能靈活地對多個表聯(lián)合隨機讀取，而用VC語言則可以實現(xiàn)不同表的數(shù)據(jù)讀取。因此，采取用SQL語句和VC語句混合編程算法則可以大大提高執(zhí)行速度，并滿足靈活性的需要。

二、回溯組卷算法

對于具有完備約束集D的一般問題P及其相應的狀態(tài)空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：

從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結點的所有狀態(tài)結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效率。具體地說，當搜索按深度優(yōu)先策略到達一個滿足D中所有有關約束的狀態(tài)結點時，即“激活”該狀態(tài)結點，以便繼續(xù)往深層搜索；否則跳過對以該狀態(tài)結點為根的子樹的搜索，而一邊逐層地向該狀態(tài)結點的祖先結點回溯，一邊“殺死”其兒子結點已被搜索遍的祖先結點，直到遇到其兒子結點未被搜索遍的祖先結點，即轉向其未被搜索的一個兒子結點繼續(xù)搜索。

在搜索過程中，只要所激活的狀態(tài)結點又滿足終結條件，那么它就是回答結點，應該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜索過為止。

在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。

回溯試探法是將隨機選取法產生的每一狀態(tài)類型記錄下來，當搜索失敗時釋放上次記錄的狀態(tài)類型，然后再依據(jù)一定的規(guī)律（正是這種規(guī)律破壞了選取試題的隨機性）變換一種新的狀態(tài)類型進行試探，通過不斷的回溯試探直到試卷生成完畢或退回出發(fā)點為止，這種有條件的深度優(yōu)先算法，對于狀態(tài)類型和出題量都較少的題庫系統(tǒng)而言，組卷成功率較好，但是在實際應用時發(fā)現(xiàn)這種算法對內存的占用量很大，程序結構相對比較復雜，而且選取試題缺乏隨機性，組卷時間長，后兩點是用戶無法接受的。

三、遺傳組卷算法

遺傳算法是一種并行的、能夠有效優(yōu)化的算法，以Morgan的基因理論及Eldridge 與Gould間斷平衡理論為依據(jù)，同時融合了Mayr的邊緣物種形成理論和Bertalanffv一般系統(tǒng)理論的一些思想，模擬達爾文的自然界遺傳學：繼承（基因遺傳）、進化（基因突變）優(yōu)勝劣汰（優(yōu)的基因大量被遺傳復制，劣的基因較少被遺傳復制）。其實質就是一種把自然界有機體的優(yōu)勝劣汰的自然選擇、適者生存的進化機制與同一群體中個體與個體間的隨機信息交換機制相結合的搜索算法。運用遺傳算法求解問題首先需將所要求解的問題表示成二進制編碼，然后根據(jù)環(huán)境進行基本的操作：selection，crossover，mutation……這樣進行不斷的所謂“生存選擇”，最后收斂到一個最適應環(huán)境條件的個體上，得到問題的最優(yōu)解，其主要步驟如下：

第一步：編碼：GA在進行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結構數(shù)據(jù)，這些串結構數(shù)據(jù)的不同組合便構成了不同的點。

第二步：初始群體的生成：隨機產生N個初始串結構數(shù)據(jù)，每個串結構數(shù)據(jù)稱為一個個體， N個個體構成了一個群體。GA以這N個串結構數(shù)據(jù)作為初始點開始迭代。

第三步：適應性值評估檢測：適應性函數(shù)表明個體或解的優(yōu)劣性。不同的問題，適應性函數(shù)的定義方式也不同。

第四步：選擇：選擇的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進行選擇的原則是適應性強的個體為下一代貢獻一個或多個后代的概率大。選擇實現(xiàn)了達爾文的適者生存原則。

第五步：交換：交換操作是遺傳算法中最主要的遺傳操作。通過交換操作可以得到新一代個體，新個體組合了其父輩個體的特性。交換體現(xiàn)了信息交換的思想。

第六步：變異：變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結構數(shù)據(jù)中某個串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001~0.01之間。變異為新個體的產生提供了機會。

綜上所綜， 隨機組卷算法對于純單道題的抽取運行速度較快，能很好地控制試卷中試題難度的分布情況；回溯算法對于狀態(tài)類型和出題量都較少的題庫系統(tǒng)而言，組卷成功率較好，遺傳組卷算法與前兩種相比，具有良好收斂性、極高魯棒性和廣泛適用性的優(yōu)化方法，一般來說，用戶在自動組卷時會對試卷的質量提出多方面的要求，如總題量、平均難度、題型比例、章節(jié)比例、重點章節(jié)比例、知識點的交叉與綜合等，自動組卷就應最大程度的滿足用戶的要求，適應性更強，效率更高，效果更好。

參考文獻：

[1]王小平，曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002.1.123～140

[2]李律松.Visual C# + SQL Server數(shù)據(jù)庫開發(fā)與實例[M].北京：清華大學出版社，2006.8.1

[3] Ansari N，Hou E.用于最優(yōu)化的計算智能[M].李軍，邊肇 譯.北京：清華大學出版社，1999