實例講解遺傳算法——基于遺傳算法的自動組卷系統【理論篇】

一、遺傳算法介紹

1.1 遺傳算法概要

遺傳算法（Genetic Algorithm，簡稱GA）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法，由美國的J.Holland教授1975年首先提出。遺傳算法是一種模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，通過模擬自然進化過程搜索最優解，它常用來解決多約束條件下的最優問題。

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

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

1.2 遺傳算法的基本操作及步驟

（1）初始化。設置進化代數計數器，設置最大進化代數，隨機生成N個個體作為初始種群。

（2）計算機適應度。計算初始種群中每個體的適應度。

（3）選擇。選擇是用來確定重組或交叉的個體，以及被選個體將產生多少子個體。按照上面得出的適應度進行父代個體的選擇?？梢蕴暨x以下算法：輪盤賭選擇、隨機遍歷抽樣、局部選擇、截斷選擇、錦標賽選擇。

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

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

1.3 遺傳算法特點

(1)遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優。　　

(2)許多傳統搜索算法都是單點搜索算法，容易陷入局部的最優解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優解的風險，同時算法本身易于實現并行化。　　

(3)遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數值來評估個體，在此基礎上進行遺傳操作。適應度函數不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用范圍大大擴展。　　

(4)遺傳算法不是采用確定性規則，而是采用概率的變遷規則來指導他的搜索方向。　　(5)具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，并獲得更適應環境的基因結構。

1.4 關于遺傳算法的幾點補充（初學者可能會有的疑問）

1、在選擇的過程中，選擇多少次，會不會造成種群的減少，選到重復的怎么辦？

答：選擇次數沒有限制，即然是選擇肯定就會有沒選上的，因此會造成種群數量減少，選到重復的個體舍棄重新選擇。建議選擇的次數少于種群數量，因為不重復，因此當次數為種群數量時即全部選擇了，這樣就失去了選擇的意義。舍棄重復的是因為重復的個體對種群的差異化沒有幫忙（試想極端情況下全是重復個體，那么交叉后全是一樣的，沒有意義）。

2、即然計算出了種群中每個個體的適應度，為什么不直接選擇適應度高的，舍棄適應度低的，而要用其他算法來選擇？

答：適應度低的個體也可能存在優質基因?，F實生活中的例子：一對傻子生了個聰明兒子。

3、交叉的過程是隨機交叉還是兩兩交叉，交叉多少次合適？

答：隨機或兩兩交叉都可以，交叉次數大于或等于初始種群中個體數量/2。因為交叉一次產生兩個新個體，而第3步的變異不產生新個體，因此為保證種群中個體的數量不致于越來越少（人口負增長），交叉次數大于或等于初始種群中個體數量/2。

二、遺傳算法在自動組卷中的應用

自動組卷是根據出卷者給定的約束條件（目前考慮試題總數量、總分、知識點分布、難度系數、題型比例等因素），搜索試題庫中與特征參數相匹配的試題，從而抽取最優的試題組合。由此可見，自動組卷問題是一個具有多重約束的組合優化問題。

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

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

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

(1、6、13、12、10、4 | 18、22、25、28 | 52、36、67、11、123 | 31、35、32、47、44 | 99、85、45)

單選題多選題判斷題填空題問答題

試卷初始種群不是采用完全隨機的方法產生，而是根據總題數、題型比例、總分等要求隨機產生，使得初始種群一開始就滿足了題數、總分等要求。這樣加快遺傳算法的收斂并減少迭代次數。采用分組實數編碼，可以克服以往采用二進制編碼搜索空間過大和編碼長度過長的缺點，同時取消了個體的解碼時間，提高了求解速度。

2.2　適應度函數的設計

適應度函數是用來評判試卷群體中個體的優劣程度的指標，遺傳算法利用適應度值這一信息來指導搜索方向，而不需要適應度函數連續或可導以及其它輔助信息。因為題數，總分等要求在初始化種群時已經考慮，這里只剩下知識點分布跟難度系數要考慮的了。所以適應度函數跟試卷難度系數和知識點分布有關。試卷難度系數公式：P=∑Di×Si/∑Si；其中i=1，2，....N，N是試卷所含的題目數，Ｄi，Ｓi分別是第i題的難度系數和分數。知識點分布用一個個體知識點的覆蓋率來衡量，例如期望本試卷包含N個知識點，而一個個體中所有題目知識點的并集中包含M個（M<=N），則知識點的覆蓋率為M/N。用戶的期望難度系數EP與試卷難度系數P之差越小越好，知識點覆蓋率越大越好，因此適應度函數如下：

f=1-(1-M/N)*f1-|EP-P|*f2

其中f1為知識點分布的權重，f2為難度系數所占權重。當f1=0時退化為只限制試題難度系數，當f2=0時退化為只限制知識點分布。

2.3　遺傳算子的設計

（1）選擇算子。選擇算子的作用在于根據個體的優劣程度決定它在下一代是被淘汰還是被復制。通過選擇，將使適應度高的個體有較大的生存機會。本系統采用輪盤賭方法，它是目前遺傳算法中最常用也是最經典的選擇方法。其具體實現為：規模為M的群體P中各個個體的適應度為P={A1、A2、… Am} ，其被選擇概率為： Ai/∑Ai(i從0到m)。

（2）交叉算子。由于在編碼時采用的是分段實數編碼，所以在進行交叉時采用分段單點交叉（按題型分段來進行交叉），整個染色體就表現為多點交叉。交叉的實現過程：將群體中的染色體任意進行兩兩配對，對每對染色體產生一個[0， N-2 ]的隨機數r，r即為分段點，將r后的兩道題目互換（保證分值相加一樣）得到下一代。交叉后生成的子代有可能因存在重復的題號而非法。出現這種情況要將出現的題號換成該段中沒有出現過的題號，這樣重新得到新子代。

（3）變異算子。在遺傳算法中，變異概率一般較小。這里不分段進行變異，而是只對某段上的某個基因進行變異。變異的操作如下：在[1，n]范圍內隨機生成一個變異位置P，以一定的原則從題庫中選擇一個變異基因，變異基因的選擇原則為：與原基因題型相同的，分數相同，與至少包含原題目一個有效知識點（期望試卷中也有此知識點）。

2.4　實施流程圖

算法實施流程如圖所示：

圖1 算法實施流程圖

2.5　程序設計

程序設計請看下篇：實例講解遺傳算法——基于遺傳算法的自動組卷系統【實踐篇】

參考文章

浪了N年：基于遺傳算法自動組卷的實現

百度百科：遺傳算法

posted @ 2011-05-19 23:35 artwl 閱讀(20107) 評論(17) 收藏舉報

刷新頁面返回頂部

個人簡介

var ME = {
	"name": "土豆/Artwl",
	"job": "coding",
	"languages": [
		"JS", "HTML",
                "CSS", "jQuery"
		"MVC",".NET",
		"設計模式"
	],
	"hobby": [
		"閱讀", "旅游",
		"音樂", "電影"
	]
}

TOP

實例講解遺傳算法——基于遺傳算法的自動組卷系統【理論篇】

一、遺傳算法介紹

1.1 遺傳算法概要

1.2 遺傳算法的基本操作及步驟

1.3 遺傳算法特點

1.4 關于遺傳算法的幾點補充（初學者可能會有的疑問）

二、遺傳算法在自動組卷中的應用

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

2.2 適應度函數的設計

2.3 遺傳算子的設計

2.4 實施流程圖

2.5 程序設計