二進制編碼遺傳算法在試題組卷中的應用研究

摘要：采用基因段遺傳算法解決多目標試題組卷優化問題是目前比較常用的組卷方法，但其存在適用題庫規模較小，遺傳算子約束條件多，收斂速度慢等缺點。采用多染色體并行遺傳算法解決多目標試題組卷優化問題，就是按照不同的題型劃分為多個染色體種群，然后根據每種題型的目標要求，并行進行遺傳算法操作，將優化結果擬合成最終試卷。這種方法不僅目標控制靈活、方便、收斂速度快、而且適用規模較大的題庫。

關鍵詞：多目標問題；多目標適應度函數；基因段；多染色體

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)35-2253-03

The Multi-chromosomes Parallel Genetic Algorithm

ZHANG Xu-tao1，2，GONG Dun-wei1，ZHANG Yong1

(1.School of Information Electronic Engineering，China University of Mining Technology，Xuzhou 221008，China; 2.Xuzhou Mechanical and Electrical Engineering High Vocational School，Xuzhou 221008，China)

Abstract: The gene segments genetic algorithm adopted as automatic test paper generation system is comparatively common， but it presents that there are some disadvantages in solving the problem about multi-target test paper generation system， such as the less miniature swarms， more limited conditions of the genetic operators andlower constringency velocity. The paper emphasizes particularly on proving that multi-chromosomes parallel genetic algorithm adopted in solving the optimization of multi-targets test paper generation system is provided with more sensitive target control， more convenience， larger swarms and higher velocity than the gene segments genetic algorithm.

Key words: multi-targets problem; multi-targets degree Function;gene segment;multi-chromosomes

遺傳算法（Genetic Algorithm）是一種模擬生物進化全局概率搜索優化的算法，它不僅適用于裝箱等單目標問題的優化，而且在多目標問題優化過程中，也顯示出強大的優越性能。采用遺傳算法對試題組卷優化就是其中的應用范例[1]。隨著計算機技術的廣泛應用，試題組卷優化方法趨向智能化、高效化。試題組卷優化實質上是在試題庫內自動挑選出滿足條件的子集。傳統的組卷方法常采用隨機選取法，即在題庫中隨機搜索滿足約束條件的試題，直到整個試卷各項目標值滿足要求為止。 由于各項目標值之間的關聯關系，這種方法往往需要進行多次回溯，組卷效率不高，成功率較低[2] 。遺傳算法以適應度函數作為搜索信息，使用種群搜索技術，搜索過程既有很大的靈活性，又有隨機性、自適應性和并行性的優點。遺傳算法以其良好的智能搜索技術，得到了廣泛的應用[3]。

采用基因段遺傳算法解決多目標試題組卷優化問題[4]。在實際應用中不僅受到種群規模的限制，還存在收斂速度較慢的缺陷。以基因段作為試卷某種題型的基本單位，給定多目標總體參數，必然要受到不同題型間多目標參數關聯性的影響，將直接加大遺傳算子選取的難度。鑒于此，作者提出一種新的方法來解決試題組卷優化中的多目標問題。首先，在試題組卷過程中，根據不同題型對試題進行分類，將每種試題的全部個體作為一類染色體的種群，通過加權細化各種群多目標參數，確定每類染色體的適用度函數，利用并行程序對多個染色體實施同步遺傳操作，將優化結果擬合成最終試卷。這種方法彌補了采用基因段遺傳算法組卷模式的不足，而且細化組卷要求，突出算法收斂速度快的特點。

1 試題組卷優化問題的描述

一般地，一套試卷由不同題型組成的，按題型劃分若干個類，如下圖1：

圖1試卷的劃分

對于一套試卷，可定義為：

X= X1 ∪ X2∪ … Xi … ∪Xs iN，i [1，s]

其中，Xi代表第i種題型。X表示一套試卷，s為該套試卷題型的總數。對于每種題型中的每道題采用二進制編碼，并按位順序排列，于是構成該題型一個試題分布的組合向量，則

當j=0，說明該道題未被選中，當j=1，說明該道題被選中。mi代表該題型種群的總個數。

試卷中的每道題目具有可能不同的多目標參數，如題分，難度，知識單元分布、估時等目標參數，由此形成目標參數矩陣。對于不同題型的試題而言，所含的目標參數都是一樣的，所以，以一種題型為例，列寫多目標參數矩陣。

如上式所示，組卷中一道試題，具有n項目標參數，考慮第i種題型的多目標矩陣pi，n維向量分別代表題分.1， 難度.2， 知識單元分布.3，教學要求.4，…， 估時.n等目標參數，mi代表該題型種群的總個數。當一種題型編碼組合與相應的目標參數矩陣相乘時，就得到該種題型的多目標適應度函數fi。

Fi=XiT×pi=[fi1 fi2…fin] (1)

其中， fi表示第i種題型一種編碼組合的多目標適應度函數。fi1表示第i種題型編碼組合的第一個目標適應度函數，其余以此類推。

對于由s種題型構成的一套試卷，其多目標適應度函數為：

(2)

根據一套試卷的多目標度函數 的相關約束條件，當采用多目標加權法，就可以確定fi。舉例說明，若s=4，，如果約束條件為f11=f21=f31=f41，則每種題型各占25分。其余情況類似。

2 多染色體并行遺傳算法思想

利用多染色體并行的遺傳算法解決組卷優化的問題，并行的模式應采用任務播種（Task-farming）模式[5]。每種題型中試題的編碼組合可用一個染色體表示，不同題型試題的編碼組合用不同的染色體表示，即構成與題型種類數相一致的初始種群。每個染色體的遺傳操作可以由并行程序中的一子程序進行單獨操作，因此由多種題型構成的試卷可實現多個子程序的同步操作，可得到優化解。并行程序中的主程序負責向各子程序分配題型庫，確立該題型多目標適應度函數。當各子程序利用遺傳算法完成相應的任務后，將各自的優化解送回主程序，擬合成最終的試卷。流程圖如圖2所示。

2.1 適應度函數的確定

當組卷者確定試卷中題型的數目，給定每種題型的多目標度函數值時，根據遺傳操作的實際偏差來定義一種題型在遺傳操作中的適應度函數。

(3)

(3)式中gi·代表組卷者對試卷一種題型設定的多目標期望值，fi·代表實際題型的多目標值。當fi→1時，該題型取得最優解。

采用多染色體并行遺傳算法試題組卷特點是將每種題型中試題的不同組合用一個染色體表示。fi即是該染色體的適應度函數。

3 驗證兩種算法的性能

采用基因段遺傳算法試題組卷是基于不同類型的試題進行基因分段處理的，每種題型的不同組合可用染色體中的部分基因段表示，則一個染色體的適應度函數表達式為：

(4)

公式（4）表示對一個染色體進行適應度評價，當→1，試題組卷取得最優解。

基因段遺傳算法試題組卷實際上是在一個染色體中進行遺傳操作，各基因段間與各基因段內由于復雜的聯系，造成遺傳操作的繁瑣性和低效性。通過兩種遺傳算法定性分析，得出多染色體并行遺傳算法的優越性能。

3.1 時效性比較

采用多染色體并行遺傳算法，在組卷過程中，由于采用并行操作，組卷所需時間為各染色體完成遺傳操作所用時間中的最大值，即T=max[T1，T2…Ts]。在同等條件下，采用基因段遺傳算法，由于染色體含有多個基因段，對應的基因段在遺傳操作中，染色體基因位的長度遠大于前者的長度，加之交叉、變異操作有限定條件，需要一定的延時，因此，染色體完成遺傳操作花費時間要大于前者的時間T。另外，前者算法是將后者基因段轉換成一個染色體進行并行操作，實際上是增加了遺傳操作的處理規模，即增大種群數量，同時也能保證操作用時較短。

3.2 收斂性比較

對于一套試卷，可由不同題型的若干道題目組成，設 ，其中s表示題型的種類，mi表示第i種題型的試題數量，m表示一套試卷的試題總量。對于第i種題型，當采用基因段遺傳算法時，根據染色體的編碼規則，其種群規模X1=2m，對于第i種題型的最優解集mi為m，它的達概率[7]p(mi/X1)m/2m。在同等條件下，當采用多染色體并行的遺傳算法時，根據染色體的編碼規則，其種群規模X1=2mi，對于第i種題型的最優解集mi為m，它的達概率[6] p(mi/X1)m/2mi。顯然，后者的可達性要高于前者，說明后者對最優解的搜索能力強，易于收斂。

3.3 仿真實驗

實驗1 兩種組卷方法在種群規模相同，交叉算子為0.9，變異算子為0.05，進化代數為120的情況下，利用MATLAB軟件仿真，分別得出它們的收斂時間曲線如圖3。

從圖3可知，采用多染色體遺傳算法的收斂時間較短，尤其在種群規模較大的情況下，效果明顯。

實驗2兩種組卷方法在種群規模為1000，進化代數為120的情況下，改變遺傳算子，利用MATLAB軟件仿真，分別得出它們的收斂時間如表1。

不難看出，改變遺傳算子，仍以多染色體收斂用時較短。

實驗3兩種組卷方法在種群規模為1000，交叉算子為0.9，變異算子為0.05，進化代數改變的情況下，利用MATLAB軟件仿真，分別得出它們的收斂時間曲線如下：

從上圖看出，多染色體遺傳算法受進化代數的影響不大，并且比基因段算法用時低。

4結論

綜上所述，多個染色體并行操作的遺傳算法在解決試題組卷優化方面具有以下優點：一、多機并行工作使處理組卷題目的數量大幅增加。二、多染色體的同步操作，增強遺傳操作的有效搜索范圍，收斂速度較快。三、對多目標參數的調整簡單、方便，算法可靠、穩定。

參考文獻：

[1] Hanjun Jin，Xiaorong Wang. Study and Application of Genetic algorithm in Computer Test Construction.IEEE，2005:410-413.

[2] 周紅曉.遺傳算法在試題庫智能組卷中的應用[J].浙江師范大學學報(自然科學版)，2003，26(4):374-378.

[3] Michelle Moore.Teaching students to use genetic algorithms to solve optimization problems，Vol.16.Journal of Computing Sciences in Colleges (2001)19-25.

[4] 王友仁，張砦，施玉霞，等. 題庫系統智能成卷理論和組卷方法研究[J].電子科技大學學報，2006，35(3):363-365.

[5] 陳國良，安虹，陳崚，等.并行算法實踐[M].北京:高等教育出版社，2004.

[6] 鞏敦衛，潘鳳萍.自適應遺傳算法理論及應用[M].徐州:中國礦業大學出版社，2003.