基于量子遺傳算法的知識分布優化研究

摘要:研究了智能考試系統的知識分布問題，基于量子計算理論，提出采用量子遺傳算法，對知識分布優化策略進行改進，提高了試卷知識分布的覆蓋率和效率。

關鍵詞:量子計算;遺傳算法;智能優化;考試系統

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2009)24-7068-03

Optimal Knowledge Distribution Based on the Quantum Genetic Algorithm

ZHANG Wei， HE Rong

(Yunnan Medical College， Kunming 650051， China)

Abstract: Researched the question about knowledge distribution of intelligent examination system， based on the theory of quantum computing， applied quantum genetic algorithm， to improve the strategy of knowledge distribution optimization for better coverage and efficiency.

Key words: quantum algorithm; genetic algorithm; intelligent optimization; test system

智能組卷是一種新型的計算機考試系統。試卷由撒布在測試區域內的考題按一定出題規則自組織而成， 這些考題具有一定的代表性，能檢測出學生對考察科目知識的學習掌握情況。考試系統中，考題的分布以及組織對于提高系統的測試水平具有重要的意義。傳統的考試系統知識分布有兩種策略，一種是人工規劃(Planning模式)，另一種是大規模的隨機分散(Scattering模式)。前者缺乏靈活性與多樣性，且效率低下，不適宜計算機組卷等大規模考試。而后者若要取得較好的分布，就必須設置遠多于實際需要的考題才能較完整地覆蓋考察科目的測試區域，這與試卷中題目數量的有限性是相互矛盾的，試卷中可能存在考題不合理分布造成的測試陰影和盲區。因此考題的合理分布對智能考試系統的測試效果有重要的作用。盡管針對考試系統國內外進行大量的組卷算法研究，但對于知識點的分布優化問題研究工作還很少，很多研究運用傳統遺傳算法組卷[1]，優化效果不盡理想。針對此問題，本文應用量子遺傳算法優化知識點的分布，克服測試陰影和盲區，使考試系統更大范圍地測試到更有效的學生學習信息。

1 知識覆蓋問題

通過對考試科目的學習，學生學習掌握的知識儲存在頭腦中。由于學生個體之間的學習差異，導致每個學生大腦中儲存和掌握的情況具有不確定性。考試的目的在于，通過試卷測試對學生學習情況做出相對確定的評價。科目知識是相對固定的，我們總是將科目知識當作圖譜，按圖索驥地構造出試卷去測試學生大腦中相關區域中知識的學習掌握情況，即是否掌握，掌握水平如何等。但在目標試卷生成以前，題庫中的考題相對與目標試卷而言表現為存在或不存在兩種可能形態。基于此，本文引入量子態對考題進行描述、編碼和處理。

1.1 試卷分布構成

試卷覆蓋是指由計算機考試系統生成一組考題集合(試卷)對測試區域各個知識點的涵蓋。試卷的目的是系統地測試和評價試卷覆蓋知識區域內學生的學習情況，并對這些數據進行處理，獲得詳盡而準確的信息，傳送到需要這些信息的教師和教學管理部門。

考題是由考點以問題的形式構成的。其中考點與考試科目的相關知識點對應。因此考題的分布是考試系統獲取學生學習信息的關鍵因素之一，其覆蓋范圍以及分布優化也隨之成為研究領域中的重點。

1.2 試卷覆蓋問題

試卷由數量有限的考題組成，每道考題包含若干有針對性的知識點所設置的考點。這些考點形成了考題的測試范圍。如何組織試卷完成對目標區域的檢測，就是考試系統覆蓋性的問題。考題分布優化的任務就是在保持試卷結構完整的前提下，動態調整考題組成，以獲得盡可能大的覆蓋率，也就是使試卷能獲得更廣泛的信息。在保持考點充分覆蓋的前提下，引入以下定義。

假設考察科目所涵蓋的知識范圍用集合S表示，組成每套試卷的考題用集合Q={qi，i=1，2，...，n}表示，每道考題測試的知識范圍為ci，試卷的測試目標知識區域為A，(A?哿S)，則理想的探測效果為。設為試卷有效覆蓋知識區域的度量(考點數)，d2=‖A‖為目標科目知識區域的度量(知識點數)，則稱ρ=d1/d2為試卷覆蓋度。

覆蓋性問題不僅反映了試卷所能測試的范圍，而且通過合理的覆蓋控制還可以使試卷中的考題組合得到優化，提高試卷的命題質量。

1.3 約束條件

我們采用以下公理化方式對知識覆蓋問題進行描述(目標):在考題集合Q={q1，q2，...，qn}中求一個子集T作為試卷，使得滿足以下約束條件。

① 各考題滿足試卷總體約束條件;

② 試卷覆蓋度ρ最大;

③ 考題數目‖T‖為最少。

3 量子遺傳算法的考題分布優化

試卷的考題分布優化是一個多目標優化問題 ，需要在考題數與知識覆蓋率之間達到平衡。即在保持試卷中考題數目與題型符合命題要求的情況下，盡可能增加試卷的知識覆蓋度，使考題獲取最廣泛的測試信息。

3.1 量子遺傳算法

量子遺傳算法是量子計算與遺傳算法相結合的產物。它以量子計算的一些概念和理論為基礎，用量子比特編碼來表示染色體，用量子門作用和量子門更新來完成進化搜索[2]。

我們根據考題在科目知識中的分布和權重(主要是指命題價值)按字典序編號，形成知識地圖的坐標。由于題庫中的考題在目標試卷生成以前具有不確定性，即在目標試卷中既可能存在，也可能不存在。這符合量子力學中的測不準原則。我們對這些編號進行量子編碼，并用量子遺傳算法在命題規則的約束下進行知識分布優化。

3.1.1 量子編碼

1) 量子態引入

我們用Dirac算符|↑>和|→>分別表示考題在目標試卷中表現為存在或不存在的兩種可能形態。若用“1”表示存在，用“0”表示不存在。考題以疊加態的形式存在。即將一個量子比特可能處于|0>和|1>之間的中間態。可表示為:

|Ψ>=α|0>+β|1> (2)

其中α和β分別是|0>和|1>的概率幅，且滿足下列歸一化條件:

|α|2+|β|2=1(3)

式(3)中，|α|2表示量子比特的觀測值在|0>狀態的概率投影，|β|2表示量子比特的觀測值在|1>狀態的概率投影。

定義2.1滿足式(2)和式(3)的一對實數α、β稱為一個量子比特的概率幅，記為[α，β]T。

定義2.2角度ζ(ζ∈[-π/2，π/2])定義為一個量子比特的相位，即ζ=arctan(β/α)。

2) 染色體量子編碼

我們從題型、章節、考題三個方面對試卷的染色體及種群進行量子編碼。

其中，m為染色體的基因個體表示知識分布數量(章節數);k為每個基因的量子比特數表示每道題的屬性數量。n個這樣的個體構成的種群Q(t)={q1t，q2t，...，qnt}表示試卷，其中n為題型數量。

3.1.2 量子旋轉門

量子旋轉門是實現演化操作的執行機構。[3-5]圖1為量子旋轉門示意圖。

其操作規律如下:

θi=k*f(αi，βi) (6)

其中k是一個與算法收斂速度有關的系數，k的取值必須合理選取，如果k的取值過大，算法搜索的網格就很大，容易出現早熟現象，算法易于收斂于局部極值點，反之，如果 k 的取值過小，則搜索速度太慢甚至會處于停滯狀態。因此，本文將k視為一個變量，將k定義為一個與進化代數有關的變量，如，其中t為進化代數，max t是根據待求解的具體問題而設定的一個常數，因此k可以根據進化代數合理地調整網格大小。

函數f(αi，βi)的作用是使算法朝著最優解得方向搜索。本文采用表1的搜索策略。其原理是使當前解逐漸逼近搜索到的最佳解，從而確定量子旋轉門的旋轉方向。其中符號e表示α和β的乘積，即e=α*β，e的正負值代表此量子比特的相位ζ在平面坐標中所處的象限。 如果 e的值為正，則表示ζ處于第一、三象限，否則處于第二或第四象限。

在表1中，α1和β1是搜索到的最佳節的概率幅，α2和β2是當前解的概率幅，當e1，e2同時大于0時，意味著當前解和搜索到的最佳解均處于第一或第三象限。當|ζ1|>|ζ2|時，表明當前解應朝著逆時針方向旋轉，其值為 +1，反之為 -1。同理可推出其他三種情況。

這樣，量子門的更新過程可以描述為qjt+1=G(t)*qjt其中，上標t為進化代數，G(t)為第t代量子門，為第t代某個個體的概率幅，qjt+1為第t+1代相應個體的概率幅。

3.1.3 量子遺傳算法流程(見圖2)

①初始化種群，種群Q={q1，q2，...，qn}，其中qj為種群中的第 j 個個體。 令種群中全部的染色體基因(αi，βi) (i=1，2，...，m)都被初始化為，這意味著一個染色體所表達的是其所有可能狀態的等概率疊加。同時初始化進化代數t=0。

②量子坍塌法測量:對處于疊加態的量子位進行觀測時，疊加態將因此受到干擾，并發生變化，稱為坍塌。擾動使為疊加態坍縮為基本態。確定種群大小n和量子位的數目m，包含n個個體的種群通過量子坍塌，得到P(t)，其中為第t代種群的第j個解(即第j個個體的測量值)，表現形式為長度m為的二進制串，其中每一位為0或1。(量子坍塌即對Q進行測量，測量的步驟是生成一個[0，1] 之間的隨機數，若其大于概率幅的平方，則測量結果值取1，否則取0。

③群體的適應度評價，保存最優解作為下一步演化的目標值。

④算法進入循環。首先判斷是否滿足算法終止條件，如果滿足，則程序運行結束;否則對種群中個體實施一次測量，獲得一組解及其相應的適應度。

⑤根據當前的演化目標，運用量子旋轉門進行調整更新，獲得子代種群。調整過程為根據式(6)計算量子旋轉門的旋轉角，并應用式(5)作用于種群中的所有個體的概率幅，即更新Q。

⑥群體災變:當接連數代的最優個體為局部極值，這時就實行群體災變操作，即對進化過程中的種群施加一個較大擾動，使其脫離局部最優點，開始新的搜索。具體操作為:只保留最優值，重新生成其余個體。

⑦迭代與終止進化代數t'=t+1，算法轉至式(2)繼續執行，直到算法結束。

4 仿真試驗

為了驗證算法的有效性，我們對傳統遺傳算法(CGA)與量子遺傳算法(QGA)所獲得的考題知識覆蓋度進行仿真對比。我們將考題對考查科目所含知識的覆蓋問題簡化為:用12個半徑為200的圓所代表的考題去覆蓋一塊1200×1000的二維平面內用矩形代表的知識區域;種群個體數 P = 45，量子位數目 m = 30，運行 600 代。算法運行結果對照如下。

從圖3所示考題知識分布優化中覆蓋度的變化特性可以看出在不同階段的變化中，量子遺傳算法優化性能高于傳統遺傳算法而且穩定性也更強。

5 結論

在試卷中存在考題不合理分布造成的測試陰影和盲區。通過量子遺傳算法優化考題分布，使其在保證命題要求的情況下，用最少的考題取得最大的覆蓋率，可以有效地消除探測區域內的陰影和盲點。仿真結果也表明，算法能夠較好地完成試卷考題的分布優化，從而有效提高試卷的測試能力，對于實際的試卷命制提供了可靠的解決方案和調整依據。本文提出了創新性的考題分布的優化方法，即確立了試卷的覆蓋模型，并以此為目標函數，運用量子遺傳算法對考題分布進行優化。

參考文獻:

[1] 張維，何蓉. 基于參數估計的遺傳算法組卷研究[J]. 云南民族大學學報，2009，18(3):276-278.

[2] Donald A.Prospective Algorithms for Quantum Evolutionary Computation[C].Proc of the 2nd Quantum Interaction Symposium (QI-2008)， College Publications， UK， 2008.

[3] 黃友銳. 智能優化算法及其應用[M]. 北京:國防工業出版社，2008:38-40.

[4] 唐歡容，蔣浩，鄭金華. 量子多目標進化算法研究[J]. 計算機工程與應用，2007，43(13):48.

[5] Han K H，Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problems[C].Proc of IEEE Conference on Evolutionary Computation.Piscataway:IEEE Press，2000:1354-1360.