文章編號 :1671 - 3559(2004) 03 - 0228 - 04收稿日期 :2004 - 03 - 22基金項目 :國家 863 計劃資助項目 (863 - 306 - 01 - 4) ;山東省自然科學(xué)基金資助項目 (者簡介 :楊青 (1972 - ) ,女 ,山東濟南人 ,山東公安專科學(xué)?；A(chǔ)部講師 ,碩士?；谶z傳算法的試題庫自動組卷問題的研究楊 青(山東公安?？茖W(xué)校 基礎(chǔ)部 ,山東 濟南 250014)摘 要 :給出了利用遺傳算法求解試題庫自動組卷問題的新方法 ,討論了運用遺傳算法求解在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題 ,提出了功能塊的概念 ,并采用了新的編碼方式、交叉算子和變異算子。實驗結(jié)果表明 ,改進的遺傳算法相對于其他算法更能有效的解決自動組卷問題 ,具有較好的使用性能和實用性。關(guān)鍵詞 :遺傳算法 ;自動組卷 ;功能塊 ;試題庫中圖分類號 :6 文獻標(biāo)識碼 :由計算機自動從試題庫中選擇試題 ,組成一份符合要求的試卷。它是計算機輔助教學(xué)系統(tǒng) (的重要組成部分。常用的自動組卷方法大致可分為兩類 : (1) 隨機抽取法 1 ,即根據(jù)組卷狀態(tài)空間的控制指標(biāo) ,由計算機隨機抽取一道符合控制指標(biāo)的試題放入組卷題庫 ,此過程不斷重復(fù) ,直到組卷完畢或已無法從題庫中抽取滿足控制指標(biāo)的試題為止。該方法結(jié)構(gòu)簡單 ,具有很大的隨意性和不確定性 ,無法從整體上把握題庫不斷變化的要求 ,不具有智能性。 (2)回溯試探法 ,即將隨機抽取法產(chǎn)生的每一狀態(tài)類型記錄下來 ,當(dāng)搜索失敗時釋放上次記錄的狀態(tài)類型。然后再按照一定的規(guī)律變換一種新的狀態(tài)類型進行試探 ,通過不斷的回溯試探直到試卷生成完畢或退回到出發(fā)點為止 ,文獻 2 就是使用回溯方法實現(xiàn)自動組卷。實踐證明 ,該方法適用于類型和出題量都比較小的題庫系統(tǒng) ,實際應(yīng)用時程序結(jié)構(gòu)相對復(fù)雜 ,而且選取試題隨機性差 ,組卷時間長。對于現(xiàn)在越來越流行的考生隨機即時調(diào)題的考試過程來說 ,它已不符合要求。本文中給出了利用遺傳算法求解自動組卷問題的新思路 ,討論了運用遺傳算法求解在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題 ,提出了功能塊的概念 ,并采用了新的編碼方式、交叉算子和變異算子。最后采用國際上目前評價遺傳算法性能的慣用方法 ,對幾個實例給出了計算機模擬實驗結(jié)果。該結(jié)果表明新算法求解組卷問題具有簡單、通用、收斂速度快、適于并行處理等特點 ,這些都適于試題庫自動組卷問題。1 組卷問題在智能教學(xué)系統(tǒng)中 ,一個非常重要的課題是怎樣在已生成的題庫中自動生成滿足教學(xué)和教師需求的試卷。一套試卷的構(gòu)成需要涉及很多因素 ,在試卷中的每一道試題又包含多個屬性 ,其中與組卷有關(guān)的屬性有如下六項 : (1)題型 ; (2)章節(jié) ; (3) 難度系數(shù) ; (4)區(qū)分度 ; (5)時間 ; (6)分?jǐn)?shù)。組卷中決定一道題 ,就是決定它的上述六個屬性 ,組成一份 n 道題的試卷就是從試題庫中抽取 n 道題 ,組成一個 n 6的矩陣 ,矩陣中的每一列代表一個屬性 ,每一行代表一道題。即S = (1) 題型 :試題的題型。按照現(xiàn)代教育理論對于考試的客觀性的要求 ,試卷應(yīng)包含足夠的客觀性試題 (選擇題、填空題 ) 。而為了考察學(xué)生的思維水平與能力 ,分析運算能力和科學(xué)表達能力 ,試卷又要有一定數(shù)量非客觀性試題?？紤]到上述兩方面的要求 ,試題庫內(nèi)試題應(yīng)包含判斷題、填空題、選擇題、問答題、改錯題、證明題、和計算題 7 種題型 。(2) 章節(jié) :試題內(nèi)容所屬的篇章。為保證試題有第 18 卷第 3 期2004 年 9 月濟南大學(xué)學(xué)報 (自然科學(xué)版 )F J & 18 32004 1995o., 每個章節(jié)都要有相應(yīng)的試題 ,且各章內(nèi)容所占分?jǐn)?shù)應(yīng)與教學(xué)時數(shù)成正比。(3) 難度 :在試卷命題過程中 ,針對不同考試對象、不同階段的考試 ,命題難度也不同。試題難度系數(shù)定義為 d = 1 - (平均分 / 該項滿分 ) 。根據(jù)難度系數(shù)不同 ,將試題分為容易、中等、較難、難四個難度等級 :容易 :0. 05 0. 20中等 :0. 25 0. 40較難 :0. 45 0. 70難 :0. 75 0. 95在組卷中 ,對于各種難度級的試題在試卷中的分布也做出一個參考性規(guī)定 ,即 : (容易 ) : (中等 ) :(較難 + 難 ) 25 :60 :15(4) 區(qū)分度 :試題對考生的水平鑒別和區(qū)分程度的指標(biāo)。為了估計區(qū)分度 ,我們將考生分成高分組和低分組兩個組 ,分別統(tǒng)計高分組和低分組的得分率 ,我們把區(qū)分度定義為 :區(qū)分度 = 高分組的得分率- 低分組的得分率 3 。(5) 分?jǐn)?shù) :每份試卷的分?jǐn)?shù)為 100 分 ,或由用戶指定。(6) 時間 :考試時間為 120 分鐘或由用戶指定 。除了上面六個約束外 ,有時試卷還要滿足教學(xué)要求層次 (掌握、理解、了解 ) 、能力要求 (知識、運用、靈活運用 ) 、試題內(nèi)容的相關(guān)性以及出題頻率等約束。但根據(jù)經(jīng)驗 ,指標(biāo)過多會增加組卷問題的難度并降低其效率。2 傳統(tǒng)遺傳算法的問題求解遺傳算法是基于生物學(xué)進化原理的一種全局搜索算法 ,它模擬了自然界適者生存、優(yōu)勝劣汰這一基本的生物進化過程。遺傳算法的框架是由 4 于 20 世紀(jì) 60 年代提出 ,可描述為 :(1)隨機產(chǎn)生初始種群 ;(2)利用評價函數(shù) (適應(yīng)度函數(shù) ) 對個體計算函數(shù)值 ;(3)按一定的概率對個體進行選擇、交叉、變異等操作產(chǎn)生新種群 ;(4)重復(fù) (2) 、 (3)兩步 ,直到收斂 (找到最佳解或迭代次數(shù)足夠多 ) 。上述框架中的參數(shù)往往與待解決的具體問題密切相關(guān)。針對自動組卷問題 ,我們給出相應(yīng)的算法步驟如下 :步驟 1 :染色體的編碼假設(shè)試題庫中有 m 道題 ,可用一個 m 位的二進制串來表示 ,形式為 : x1 x2 其中若 1 ,則表示該題被選中 ,若 0 則表示該題未被選中 ,即 1 ,當(dāng)?shù)?i 道題被選中 ;0 ,當(dāng)?shù)?i 道題未被選中若一份試卷中有 n 道試題 ,則 x1 x2 中應(yīng)有 n 個 1。步驟 2 :初始化群體通過隨機的方法生成初始化的串群體。在串群體中 ,串的長度是相同的 ,群體的大小根據(jù)需要按經(jīng)驗或?qū)嶒灲o出。步驟 3 :計算當(dāng)前種群每個個體的適應(yīng)度本問題的適應(yīng)度函數(shù)可定義為f = 6i =1f i 表示第 i 個屬性指標(biāo)與用戶要求的誤差的絕對值 , 示第 i 個指標(biāo)對組卷重要程度的權(quán)值 , 驟 4 :選擇按照一定的選擇概率對種群進行復(fù)制 ,選擇較好的串生成下一代 (個體的適應(yīng)度函數(shù)值越小 ,該串的性能越好 ,選擇概率越大 ) ,去掉較差的串。步驟 5 :交叉交叉是兩個串按照一定的概率 (交叉概率 ,從某一位開始逐位互換。首先 ,對每個二進制串產(chǎn)生一個在 0 1 的隨機數(shù) ,若該數(shù)小于 則選擇該串進行交叉 ,否則不選擇。隨機地對被選擇的二進制串進行配對 ,并根據(jù)二進制串的長度 n ,隨機產(chǎn)生交叉位置 i , i 為 1 , n - 1 上的一個整數(shù) ,然后按下面的方式交叉 :交叉前 交叉后a1 a2 1 a1 a2 1 b2 1 b1 b2 1 :變異變異是二進制串的某一位按照一定的概率 (突變概率 發(fā)生反轉(zhuǎn) , 1 變?yōu)?0 , 0 變?yōu)?1。這里 小于 0. 001。但在實踐中發(fā)現(xiàn) ,在有些遺傳算子中 , 0. 1 時更好 5 。步驟 7 :終止記錄進化的代數(shù) ,并判斷是否滿足終止條件。若滿足 ,則輸出結(jié)果 ,否則轉(zhuǎn)向步驟 3 繼續(xù)執(zhí)行 。終止條件如下 :(a)出現(xiàn)種群滿足 f = 0 ;922第 3 期楊青 :基于遺傳算法的試題庫自動組卷問題的研究 1995o., b)某個個體適應(yīng)度值達到指定要求 ;(c)達到指定的進化代數(shù) ;(d)當(dāng)前種群中最大適應(yīng)度值與以前各代中最大適應(yīng)度值相差不大 ,進化效果不顯著。3 改進的遺傳算法在傳統(tǒng)的遺傳算法中 ,初始種群的每個字符串中“ 1”的數(shù)目等于試題的數(shù)目 n ,可進行遺傳操作(交叉、變異 ) 后 ,字符串中“ 1”的數(shù)目可能大于或小于 n ,從而變?yōu)榉欠ń?。此時必須對解進行修正 ,即進行相應(yīng)的運算使字符串中“ 1”的數(shù)目為 n。一般說來 ,這個過程比較復(fù)雜 ,大大增加了運算量。另外 ,對于生成試卷的 6 個屬性指標(biāo) ,我們的要求也不一樣。對于考試分?jǐn)?shù) ,我們希望沒有誤差 ,而對于其他屬性 ,如題型、章節(jié)、難度、區(qū)分度、時間等只要滿足一定的要求就可以了。因此對傳統(tǒng)的遺傳算法做如下改進 :(1) 編碼的改進在實際組卷中 ,假設(shè)在試卷中每種題型的數(shù)目是固定的 ,且相同的題型的分?jǐn)?shù)和答題時間是相同的。這樣 ,可以將整個二進制串按照題目的類型劃分為不同的功能塊。每個功能塊采用獨立的二進制編碼。也就是說 ,每個功能塊對應(yīng)一種特定的題型 ,而該功能塊中 ,“ 1”代表該題被選中 ,“ 0”代表該題未被選中 ,“ 1”的數(shù)目即該種題型的試題數(shù)目。顯然 ,按這種規(guī)則產(chǎn)生的初始種群已經(jīng)滿足了試題對題型、分?jǐn)?shù)和答題時間的要求。(2) 交叉運算的改進由于種群中每一個功能塊對應(yīng)著一個題型 ,所以 ,為了保證每個題型的數(shù)目不變 ,交叉點的選擇不能破壞功能塊的完整性。假設(shè)交叉點位于第 i 個功能塊內(nèi) ,則前 i 個功能塊保持不變 ,從第 i + 1 個功能塊開始逐位交換 。(3) 變異運算的改進由于在每個功能塊中 ,“ 1”的數(shù)目即是該題型試題的數(shù)目 ,因此在變異過程中應(yīng)保證整個種群所有功能塊中“ 1”的數(shù)目不變。可執(zhí)行如下過程 ,首先 ,由變異概率決定某位取反 ;然后 ,檢查、修正字符串中“ 1”的數(shù)目 ,保證不發(fā)生變化。(4) 用全局最優(yōu)解替換本次迭代的最差解為保證好的字符串不至于流失 ,每次遺傳操作前記錄本次迭代的最優(yōu)解 ,若該解優(yōu)于全局最優(yōu)解則替換全局最優(yōu)解 ,否則全局最優(yōu)解保持不變。此次遺傳操作后 ,用全局最優(yōu)解替換本代的最差解。4 實驗411 實驗設(shè)計與實驗數(shù)據(jù)在實驗中將 600 道試題按要求存放于所使用的試題庫中 ,并給出個體評價函數(shù) :f = w1 w2 w3 w4 w5 w6 1 ( i = 1 , 2 , 6) 。 示各試題分?jǐn)?shù)之和與用戶指定的總分之差的絕對值 ; 示各試題估時之和與用戶指定的考試時間之差的絕對值 ; 示各種題型題量與用戶指定的相應(yīng)值的誤差絕對值之和 ; 每一篇章試題分?jǐn)?shù)與用戶指定的相應(yīng)值的誤差絕對值之和 ; 每一難度的試題分?jǐn)?shù)與用戶指定的相應(yīng)值的誤差絕對值之和 ; 每一區(qū)分度試題分?jǐn)?shù)與用戶指定的相應(yīng)值的誤差絕對值之和。以下各表列出一部分實驗結(jié)果。表 1 是運用傳統(tǒng)的遺傳算法在不同種群及不同迭代次數(shù)中得到的最小適應(yīng)度的值 。其中 ,交叉概率 0. 6 ,變異概率 0. 1。表 1 傳統(tǒng)遺傳算法在不同種群及不同迭代次數(shù)中得到的最小適應(yīng)度的值迭代數(shù)目 (代 ) 最小適應(yīng)度的值(種群數(shù)目 = 10) 最小適應(yīng)度的值(種群數(shù)目 = 15) 最小適應(yīng)度的值(種群數(shù)目 = 20)10 109 91 8850 109 88 83100 93 86 74150 86 86 70200 86 83 65250 86 83 65表 2 是運用改進的遺傳算法在不同種群及不同迭代次數(shù)中得到的最小適應(yīng)度的值 。其中 ,交叉概率 0. 8 ,變異概率 0. 005。表 2 改進遺傳算法在不同種群及不同迭代次數(shù)中得到的最小適應(yīng)度的值迭代數(shù)目 (代 ) 最小適應(yīng)度的值(種群數(shù)目 = 10) 最小適應(yīng)度的值(種群數(shù)目 = 15) 最小適應(yīng)度的值(種群數(shù)目 = 20)10 48 34 4450 38 22 30100 24 18 14150 20 14 10200 18 8 10250 16 6 4表 3 是應(yīng)用改進的遺傳算法在不同種群不同終032濟 南 大 學(xué) 學(xué) 報 (自然科學(xué)版 ) 第 18 卷 1995o., 終止條件 1 適應(yīng)度值 f 達到 16 ,終止條件 2適 應(yīng)度值 f 達到 10) 下的運行時間。其中 ,交叉概率 0. 8 ,變異概率 0. 005。表 3 改進遺傳算法在不同種群及不同終止條件中得到的運行時間種群數(shù)目 終止時間 / s(f 10)終止時間 / s( f 16)10 67 2815 21 1220 31 11表 4 是傳統(tǒng)的遺傳算法的求解時間情況 6 。其中 ,交叉概率 0. 6 ,變異概率 0. 05。表 4 傳統(tǒng)的遺傳算法及隨機算法求解組卷問題所用時間實驗次數(shù) 傳統(tǒng)的遺傳算法所用時間/ 4 2542 52 1643 58 301412 實驗分析對比表 1、表 2 的實驗結(jié)果可知 ,在不同種群下 ,采用功能塊的改進的遺傳算法性能優(yōu)于傳統(tǒng)的遺傳算法 ,而且指標(biāo)有很大的提高 ,這說明改進的遺傳算法降低了問題的求解難度 ,提高了問題的求解效率。組卷是組成一份誤差在可接受范圍內(nèi)的試卷 ,并非要求此試卷的整體指標(biāo)一定是全局最優(yōu) ,尤其是在改進的遺傳算法中 ,整個試卷的題目類型、題目數(shù)量、題目分?jǐn)?shù)不會產(chǎn)生誤差 ,而在篇章、難度、區(qū)分度上的一定范圍內(nèi)的誤差是可以接受的。由表 3可知適當(dāng)?shù)胤糯笳`差 ,可較大幅度縮短求解時間。對比表 3、表 4 可知遺傳算法效率好于普通的隨機算法 ,改進的遺傳算法在時間上也優(yōu)于傳統(tǒng)的遺傳算法。5 結(jié)束語組卷問題是一個在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題 ,而它的約束條件難以用數(shù)學(xué)形式描述 ,所以采用