Mr,Lon 不知道，還要浪多少年

1  遺傳算法介紹

1.1　遺傳算法概要

    遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它是用來解決多約束條件下的最優問題。

    遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，它決定了個體的形狀的外部表現。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，往往進行簡化，如二進制編碼，初始種群產生之后，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度大小挑選個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼，可以作為問題近似最優解。

    遺傳算法提供了一種求解復雜系統優化問題的通用框架。它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。遺傳算法的主要應用領域有：函數優化、組合優化、生產調度問題、自動控制、機器人自動控制、圖像處理和模式識別、人工生命、遺傳程序設計、機器學習。

1.2　遺傳算法的基本操作

    遺傳算法有三個基本操作：選擇、交叉、變異。這些操作又有不同的方法來實現。

    （1）選擇。選擇是用來確定重組或交叉的個體，以及被選個體將產生多少子個體。首選計算適應度：按比例的適應度計算；基于排序的適應度計算。適應度計算之后是實際的選擇，按照適應度進行父代個體的選擇。可以挑選以下算法：輪盤賭選擇、隨機遍歷抽樣、局部選擇、截斷選擇、錦標賽選擇。

    （2）交叉。基因重組是結合來自父代交配種群中的信息產生新的個體。依據個體編碼表示方法的不同，可以有以下的算法：實值重組；離散重組；中間重組；線性重組；擴展線性重組。二進制交叉、單點交叉、多點交叉、均勻交叉、洗牌交叉、縮小代理交叉。

    （3）變異。交叉之后子代經歷的變異，實際上是子代基因按小概率擾動產生的變化。依據個體編碼表示方法的不同，可以有以下的算法：實值變異、二進制變異。

2  自動組卷的實現

    自動組卷是根據用戶給定的約束條件（總時間、難度系數、考試時間、考試章節、題型比例等），搜索試題庫中與特征參數相匹配的試題，從而抽取最優的試題組合。由此可見，自動組卷問題是一個具有多重約束的組合優化問題。

    傳統的遺傳算法存在搜索后期效率低和易形成末成熟收斂的情況。根據具體情況和需求分析要求，對遺傳算法進了稍微改進，表現為采用實數編碼、分段交叉、有條件生成初始種群。具體解決方案如下。

2.1　染色體編碼及初始群體的設計

    用遺傳算法求解問題， 首先要將問題的解空間映射成一組代碼串，即染色體的編碼問題。在傳統的遺傳算法中采用二進制編碼。用二進制編碼時，題庫里的每一道題都要出現在這個二進制位串中，1表示該題選中，0表示該題未被選中。這樣的二進制位串較長，且在進行交叉和變異遺傳算子操作時，各種題型的題目數量不好控制。采用實數編碼方案，將一份試卷映射為一個染色體，組成該試卷的每道題的題號作為基因，基因的值直接用試題號表示，每種題型的題號放在一起，按題型分段，在隨后的遺傳算子操作時也按段進行，保證了每種題型的題目總數不變。比如，要組一份《C語言程序設計》試卷，其選擇題5道，填空題5道，簡答題3道，則染色體編碼是：

(10、76、23、52、101 | 52、36、67、11、123 | 99、85、45)

選擇題               填空題           簡答題

    試卷初始種群不是采用完全隨機的方法產生，而是根據題型比例、總分、答題時間、知識點不重復、不考章節等要求隨機產生，使得初始種群一開始就滿足了題型、總分、答題時間和知識點等要求。這樣加快遺傳算法的收斂并減少迭代次數，由于不同的題型是從不同的題型表中取出，有可能在同一個基因串中會出現相同的試題編號，因它們屬于不同題型，故這種情況是正常的，不影響組卷。采用分組實數編碼，可以克服以往采用二進制編碼搜索空間過大和編碼長度過長的缺點，同時取消了個體的解碼時間，提高了求解速度。

2.2　適應度函數的設計

    適應度函數是用來評判試卷群體中個體的優劣程度的指標，遺傳算法利用適應度值這一信息來指導搜索方向，而不需要適應度函數連續或可導以及其它輔助信息。因為時間、章節等要求在初始化種群時已經考慮，這里只剩下難度系數要考慮的了。所以適應度函數由試卷難度系數公式轉換而成。試卷難度系數公式：P=∑Di×Si/∑Si；其中i=1，2，....N，N是試卷所含的題目數，Ｄi，Ｓi分別是第i題的難度系數和分數。用戶的期望難度系數EP與試卷難度系數P之差f越小越好，f=|EP-P|， 而適應度函數是值越大越好，因此將目標函數f轉換成適應度函數F=e-0.03f，這種采用加權誤差的適應度函數可以較好地反映求解組卷問題的特征，當試卷個體對各項組卷約束條件的誤差越小時，它的適應度函數值就越大，則表示試卷個體越接近卷目標。

2.3　遺傳算子的設計

    （1）選擇算子。選擇算子的作用在于根據個體的優劣程度決定它在下一代是被淘汰還是被復制。通過選擇，將使適應度高的個體有較大的生存機會。本系統采用輪盤賭方法，它是目前遺傳算法中最常用也是最經典的選擇方法。其具體實現為：規模為M的群體P={a1、a2、… am} ，其被選擇概率為：   （2）交叉算子。由于在編碼時采用的是分段實數編碼，所以在進行交叉時采用分段單點交叉（按題型分段來進行交叉），整個染色體就表現為多點交叉。交叉的實現過程：將群體中的染色體任意進行兩兩配對，對每對染色體產生一個[0， 1 ]的隨機數r，若r≤pc（據經驗，pc值取0.6到0.8），則分段隨機產生一個交叉點，然后分段進行互換以得到下一代。

    交叉后生成的子代有可能因存在重復的題號而非法。出現這種情況要將出現的題號換成該段中沒有出現過的題號，這樣重新得到新子代。

    （3）變異算子。在遺傳算法中，變異概率一般較小。這里不分段進行變異，而是只對某段上的某個基因進行變異。對某個染色體，隨機生成一個[0，1]范圍內的實數r，若r≤pm（據經驗，pm值取0.01到0.02），則對該染色體進行變異，否則不進行變異。變異的操作如下：在[1，n]范圍內隨機生成一個段號f，設該段的段長為L，則在[1，L]范圍內隨機生成一個變異位置P，以一定的原則從題庫中選擇一個變異基因，變異基因的選擇原則為：與原基因題型相同的；滿足答題時間相同；考試章節相同等要求。

2.4　算法的實現偽代碼及實施流程圖

    確定參數：最大代數Max，群體規模N， 交叉概率pc，變異概率pm， 輸入用戶的組卷要求。算法實施流程如圖1所示。

 圖1  算法實施流程圖

2.5　界面設計與實現結果

    系統試題庫是C 語言試題。試題庫中現有單選題、填空題、判斷題、程序設計題、簡答題等。群體規模設為20，算法執行的最大迭代次數設為200， 交叉概率Pc設為0.7，變異概率Pm 設為0.015。

    組卷的具體要求：試卷總分100，用時120min，試卷難度系數0.6，不考章節1.2。組卷結果表明，在進化到120代左右時即可生成一份滿意的試卷且誤差比較小，改進的遺傳算法降低了組卷問題的求解難度，組卷效率高、成功率高；且算法對初值不敏感，具有較好的魯棒性。在初始試卷生成之后，對有必考題要求，可以在試卷生成界面添加必考題。3  結束語

    本文利用遺傳算法研究了實動自動組卷。實踐的結果表明，在滿足約束條件的同時，該方法能較快地組成一份試卷。同時，遺傳算法在其它方面的應用，值得繼續研究、應用。