4 遺傳算法應用 

一般來說，用戶在自動組卷時會對試卷的質量提出多方面的要求，如總題量、平均難度、題型比例、章節比例、重點章節比例、知識點的交叉與綜合等，自動組卷就應最大程度的滿足用戶的要求。因此，在組卷之前，我們首先為自動組卷過程建立控制指標相應狀態空間D， 

D=[] 

D的每一行由某一試題的控制指標組成，如題號、題型、章節、難度等，并且這些屬性指標都進行編碼表示成二進制形式，而每一列是題庫中的某一指標的全部取值。在具體出題時，考方可能不會用到所有的指標，所以D包含的個體d_target可以表示為d_request和d_void，d_request表示考方要求的控制指標，d_void表示考方不要求的控制指標。即 

d_target：：=<d_request>：<d_void> 
<d_request>：：={0，1}m 
<d_void>：：={0，1}n 

試題庫[STK]中的每一道試題在建庫時都輸入了相應的屬性指標。試題模型的產生形式是： 

if <data> then 
<model> 
<data>：：={0，1，#}m 

#表示0和1之間的任意一位。 

考試自動出題的遺傳算法如下： 

(1) 根據考方的出題要求，規劃狀態空間庫D中的數據，保留d_request部分，而不要d_void部分，對其剩余部分進行編碼D [1]，D[2]，……D[i]。 

(2) 初始化試題庫[STK]。隨機從題庫中抽出一組試題，并進行編號STK[1],STK[2]……STK[j],確定合適的交換概率Pc和變異概率Pm；并定義其適應值flexibility[k](k=1,2……j) 

flexibility[k]<-0 (k=1,2……j) 

(3) 從試題庫[STK]中取出STK[m](0≤m≤j)與狀態空間庫[D]中的指標D[n] (0≤n≤i)進行匹配。如果STK[m]與D[n]完全匹配，則 

flexibility[k]<-flexibility[k]+1 

如果不匹配，則有 

flexibility[k]<-flexibility[k]+0 

(4) 進行淘汰選擇，保留具有高適應度的試題。即把flexibility[k]為0的STK[m]去掉，這樣就生成了一個新的試題模型STK[h]。 

(5) 重復過程2生成新的試題模型STK[p]。按一定的交換概率Pc從[STK]中隨機選取模型STK[h]和STK[p]，交換彼此位串中對應的值，產生新的試題模型STK[h]、STK[p]，如 

交換前STK[h]=1 1 0 1 0 1 1 

STK[p]=0 0 1 1 1 1 0 

交換前STK[h]=1 1 1 1 0 1 1 

STK[p]=1 1 1 1 1 1 0 

(6) 按一定的變異概率從題庫[STK]中隨機選出一試題模型STK[h]進行基因突變，產生一個新的試題模型。 

(7) 在完成以上選擇、交叉、變異步驟后，產生一個考試試題模型，按照事先確定的誤差精度對其進行收斂性的判別，當其適應度高時，試題組卷成功，轉向步驟8，如果其適應度低，則轉向步驟3繼續執行。 

(8) 輸出相應的考試試題，組卷結束。 

以上用遺傳算法抽題時，交換概率Pc和變異概率Pm的確定很重要。Pc 

太小使選題工作進展緩慢，太大則會破壞適應值高的試題模型。通常規定其為0.4。同樣，Pm太小就不能產生新的試題模型，太大又會產生過多的試題模型。它宜規定為0.1。 

在自動選題時，選題的方式可采用父輩挑選和生存選擇兩種。父輩挑選就是采用不返回隨機抽樣，它使每個題目都有被選中的可能；生存選擇采用允許父輩和子代進行競爭，并讓其中的優良者進入下一輪競爭環境的二分之一擇優選擇。兩種選擇方式共同作用于選題保證了選題的順利完成。在選題的過程中，哪一道題目被選中是一個非均勻隨機事件，其概率依賴于上一次選題的過程。