系統組卷算法的研究

摘要:針對當前計算機網絡考試系統的相關技術展開研究。主要對系統組卷算法進行了重點分析和研究，從如何選取遺傳算法出發，選擇基于遺傳算法的組卷算法進行設計使其更適用于計算機網絡考試系統。

關鍵詞:網絡考試系統;遺傳算法

中圖法分類號:TP312 文獻標識碼:A 文章編號:1009-3044(2010)02-327-02

System Test Paper Algorithm

YI Gang， QIU Li

(JiangXi Ahead Software Vocational College， Nanchang 330041， China)

Abstract: In view of the current examination system， computer network-related technology research. Algorithm of the system mainly focused analysis and research， from how to select the genetic algorithm， the selection based on genetic algorithms Algorithm design to make it more applicable to the examination system of computer networks.

Key words: network test system; genetic algorithm

1 試題的選取

網上考試系統的一個重要環節，就是隨機組成試卷。因此，在建立該系統前，必須對試題、試卷、考試等的相關理論基礎做必要的分析，并在此基礎上抽象出試題庫建設框架理論，從而進行進一步的開發與研究。

2 遺傳算法

組卷算法是網上考試系統設計的一個重要組成部分，直接影響考生的成績和考試的可信度。計算機組卷實際上是一個多目標優化的問題，也就是讓一份試卷的各個參數都盡量接近用戶的期望值。

2.1 傳統的組卷算法

隨機抽題法是最常用的組卷算法，它根據狀態空間的控制指標，由計算機隨機地抽選一道試題加入試卷中，此過程不斷重復，直到組卷完畢或己無法從試題庫中抽選滿足指標的試題為止。

另外一種是將專家系統引入試題組卷中而形成的基于專家系統的組卷算法，專家系統是一種能夠依靠大量專門知識解決特定領域中復雜問題的計算機智能軟件系統。

2.2 遺傳算法

遺傳算法(Genetic Algorithm，簡稱GA)產生于20世紀60年代末，是由美國Michigan大學的Holland教授提出來的。它是一種迭代式搜索算法，根據一定的標準在迭代過程中在保持種群穩定的基礎上，激勵好的結構，淘汰劣質結構。遺傳算法是從進化論和遺傳學機理而產生的直接搜索優化方法;在這個算法中使用了串、群體、基因等各種進化和遺傳學的概念。遺傳算法是進化算法中產生最早，影響最大，應用廣泛的一個領域，

2.2.1 遺傳算法的步驟

1) 選擇適當的編碼方式，把參數集合X和域轉換成位串結構空間S;

2) 定義適應值函授f(x) ;

3) 確定遺傳策略，選擇恰當的群體大小，選擇、交叉和變異的方法，以及其它的遺傳參數;

4) 在一定編碼方案下，隨機產生一個初始種群;

5) 用相應的解碼方法，將編碼后的個體轉換成問題空間的決策變量，并計算群體中個體位串解碼后的適應值f(x) ;

6) 按照遺傳策略，運用選擇、交叉和變異算子作用于群體，并形成新一代的種群。

7) 反復執行步驟5-6，直至滿足收斂判據為止。

3 基于遺傳算法的組卷算法的設計

遺傳算法是從進化論和遺傳學機理而產生的直接搜索優化方法，是目前功能最強大，應用最廣泛的一種多目標優化算法，遺傳算法的群體搜索策略為多目標優化提供了優秀的解決方案，是目前組卷算法的最優選擇算法。因此，本系統采用遺傳算法做為考試系統的組卷算法并對該組卷算法進行詳細的設計。

3.1 遺傳編碼的方法

按照遺傳算法的工作流程，用遺傳算法求解問題時，必須在目標問題實際表示與遺傳算法的染色體位串結構之間建立聯系，這就是確定遺傳編碼和解碼運算。編碼的策略和方法對遺傳算子，特別是對交叉和變異算子的功能和設計有著很大的影響。交叉是遺傳算法生成新群體，帶動群體進化的主要方法，是遺傳算法的核心;變異是維持群體多樣性，突破局部極值的重要手段。這兩個遺傳算子的操作方式影響了整個遺傳算法的性能。

針對傳統的二進制編碼方式的不足，本文使用了分段整數編碼的策略。將整個個體編碼分解成多個相對獨立的整數編碼。在分段整數編碼中，每段的長度(即染色體的長度)由該題型題數決定，題型相同的試題放在一起，每一種題型作為一段來進行編碼。編碼長度由組卷要求的試題總數決定。分段整數編碼采用自適應的變異率和變異量，它克服了傳統的二進制分段編碼計算量大、權的表示精度受限等缺點，取消了編碼和解碼的過程，縮短了求解時間，在進化時表現出良好的搜索性能。

為了加快遺傳算法的收斂并減少迭代次數，試卷的初始種群PO不再完全隨機產生，而是根據教師輸入的題型數量、總分的要求隨機產生，這樣產生的初始種群在一開始就己經滿足了題型和總分的要求，再加上采用分段整數編碼方式，克服了以往傳統的二進制編碼方式搜索空間過大和編碼過長的缺點，提高了組卷的求解速度。

3.2 遺傳算子的設計

遺傳算法的操作算子一般包括選擇、交叉、變異三種基本形式。算子的設計是遺傳策略主要組成部分。

1) 選擇算子:目前，選擇方法主要有適應值比例選擇、Boltzmann選擇、聯賽選擇、排序選擇、De Jong的精英選擇(elitist selection)，以及Holland的穩態選擇 (steady-state selection)等。考慮到各種選擇算子的選擇誤差及組卷算法的效率，本文采用適應值比例方法選擇算子。在適應值比例選擇中，每個個體被選擇的期望數量與其適應值和群體平均適應值的比例有關，采用輪盤賭的方式來實現。適應值比例選擇方式首先計算每個個體的適應值，然后計算出此適應值在群體適應值總和中所占的比例。

設群體的規模為N，個體的適應值為Fi，則其選擇概率Pi為:

經過選擇操作以后，各個體期望被選中的次數Ni為:

然后將Ni的小數部分作為概率進行貝努利試驗，若試驗成功，則該個體被選擇，如此反復，直到選滿為止。

2) 交叉算子:通常的交叉方式有一點交叉、兩點交叉、多點交叉以及一致交叉等形式。交叉操作的步驟如下:

① 隨機選出要交配的一對個體;

② 根據位串長度L，對要交配的一對個體隨機選取一個或幾個交叉位置;

③ 根據交叉概率pc (0

最基本的交叉方式是一點交叉，對于隨機選出的兩個串，隨機選擇一個交叉位，對這兩個位串中該位置右側部分的染色體進行交換，產生兩個新的子位串，如A1，A2一點交叉后形成B1，B2:

A1=a11a12…a1l1|a1l1…a1L

A2=a21a22…a1l1|a2l2 …a2L

一點交叉，虛線為交叉位:

B1= a11a12…a1l1|a2l2 …a2L

B2= a21a22…a1l1|a1l1…a1L

一點交叉操作的信息量比較小，交叉位的選擇可能帶來較大的誤差，為了增加交叉的信息量，我們采用多點交叉的方式。也就是在單點交叉的基礎上，對于選定的兩個個體位串，隨機選擇多個交叉點:

設染色體位串長度為L，隨機選擇的兩個父串為:

A1=a11a12…a1l1 A2=a21 a22…a1l1

隨機選擇N個交叉點為:x1，x2，x3，…xn∈{1，2，3， …，L-1}，

其中xm

實數編碼的算術交叉過程中，當產生不合法的解如，交叉后試題的編號不在試題庫中該題型的范圍時，則可以重新進行交叉運算或者在通過匹配交換的原則進行替換。

3) 變異算子:遺傳算法中的變異運算是將個體染色體編碼串中的某些基因位上的基因值用該基因位的其他等位基因來替換，從而形成一個新的個體。交叉運算從全局的角度出發探測一些較好的個體編碼結構，有助于種群接近問題的最優解，它決定了遺傳算法的全局搜索能力;而變異算子從局部的角度出發調整編碼串中的部分基因值，使種群中個體更加逼近最優解，改善了遺傳算法的局部搜索能力，并且可以維持種群的多樣性，防止早熟現象的產生。交叉算子與變異算子相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使得遺傳算法能夠以良好的搜索性能完成最優化問題的尋優過程。

變異本身是一種局部隨機搜索，與選擇/交叉算子結合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力;同時使得遺傳算法保持種群的多樣性，以防止出現非成熟收斂。在變異操作中，變異率不能太大，如果變異率大于0. 5，遺傳算法就退化為隨機搜索，那么遺傳算法的一些重要的數學特性和搜索能力也不復存在了。 由于普通的變異操作可能會使用戶指定范圍外的題目出現在染色體中，也會使各題型的題目數難以保證，針對分段實數編碼策略的特點，我們采用段內基本位變異操作，即各題型在各自編碼段內進行變異，具體的變異操作是:

計算個體發生變異的概率

對種群中的每一個個體，以原始的變異概率Pm為基礎，計算個體發生變異的概率:

pm(aj)=1-(1-pm)L j=1，2，…n L為群體的大小

給定均勻的隨機變量:r∈[0，1]，將每個個體發生變異的概率與r比較，如果r≤pm(aj)，則對該個體進行變異，否則不發生變異。如果發生變異，為了保證題型和知識點的一致性，我們按照以下方式操作:

① 判斷發生變異的個體所在的段及該段對應的題型;

② 從該題型中，優先選擇與原基因知識點相同的試題發生變異;其次選擇與原基因知識點不相同但題型相同的試題發生變異，得到新的個體。

4 結束語

本文通過對試卷選取的相關標準以及對傳統組卷算法的分析，提出了使用遺傳算法來作為本系統的組卷算法。簡單的介紹了遺傳算法，設計了本組卷算法的遺傳算子以及算法的終止條件，給出了基于遺傳算法的組卷算法流程圖。

參考文獻:

[1] 王玲，王明俊.“通用試題庫計算機管理系統”的開發與研究[J].信息與控制，2001(7).

[2] 張文修，梁怡.遺傳算法的數學基礎[M].西安:西安交通大學出版社，2000.

[3] 蔡自興，徐光枯.人工智能及其應用[M].北京:清華大學出版社，1996.

[4] Russel，Norvig.Artificial Intelligence a Modern Approach[M].北京:機械工業出版社，2000.

[5] 李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京:科學出版社，2002.

[6] 譚新良.基于整數編碼和自適應遺傳算法的智能組卷算法[J].電腦與信息技術，2007，15(4).