twzheng's cppblog

遺傳算法入門

遺傳算法

遺傳算法（Genetic Algorithm, GA）是近幾年發展起來的一種嶄新的全局優化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現各個個體的適應性的提高。從某種程度上說遺傳算法是對生物進化過程進行的數學方式仿真。

這一點體現了自然界中"物競天擇、適者生存"進化過程。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價,把問題的解表示成染色體，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在算法中也即是以二進制編碼的串。并且，在執行遺傳算法之前，給出一群染色體，也即是假設解。然后，把這些假設解置于問題的“環境”中，也即一個適應度函數中來評價。并按適者生存的原則，從中選擇出較適應環境的染色體進行復制, 淘汰低適應度的個體，再通過交叉，變異過程產生更適應環境的新一代染色體群。對這個新種群進行下一輪進化，至到最適合環境的值。

遺傳算法已用于求解帶有應用前景的一些問題，例如遺傳程序設計、函數優化、排序問題、人工神經網絡、分類系統、計算機圖像處理和機器人運動規劃等。

術語說明

由于遺傳算法是由進化論和遺傳學機理而產生的搜索算法，所以在這個算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明：

一、染色體(Chronmosome)

染色體又可以叫做基因型個體(individuals),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。

二、基因(Gene)

基因是串中的元素，基因用于表示個體的特征。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。

三、基因地點(Locus)

基因地點在算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位。基因位置由串的左向右計算，例如在串 S＝1101 中，0的基因位置是3。

四、基因特征值(Gene Feature)

在用串表示整數時，基因的特征值與二進制數的權一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。

五、適應度(Fitness)

各個個體對環境的適應程度叫做適應度(fitness)。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數. 這個函數是計算個體在群體中被使用的概率。

操作算法

霍蘭德(Holland)教授最初提出的算法也叫簡單遺傳算法，簡單遺傳算法的遺傳操作主要有三種：選擇(selection)、交叉(crossover)、變異(mutation)這也是遺傳算法中最常用的三種算法：

1．選擇(selection)

選擇操作也叫復制操作，從群體中按個體的適應度函數值選擇出較適應環境的個體。一般地說，選擇將使適應度高的個體繁殖下一代的數目較多，而適應度較小的個體，繁殖下一代的數目較少,甚至被淘汰。最通常的實現方法是輪盤賭(roulette wheel)模型。令Σfi表示群體的適應度值之總和，fi表示種群中第i個染色體的適應度值，它被選擇的概率正好為其適應度值所占份額fi／Σfi。如下圖表中的數據適應值總和Σfi=6650,適應度為2200變選擇的可能為fi／Σfi=2200/6650=0.394.

2．交叉(Crossover)

交叉算子將被選中的兩個個體的基因鏈按一定概率pc進行交叉，從而生成兩個新的個體，交叉位置pc是隨機的。其中Pc是一個系統參數。根據問題的不同，交叉又為了單點交叉算子（Single Point Crossover）、雙點交叉算子（Two Point Crossover）、均勻交叉算子 (Uniform Crossover)，在此我們只討論單點交叉的情況。

單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，將兩者的部分基因碼值進行交換。假設如下兩個8位的個體：

S1 1000  1111 S2 1110  1100

產生一個在1到7之間的隨機數c，假如現在產生的是2，將S1和S2的低二位交換：S1的高六位與S2的低六位組成數串10001100，這就是S1和S2 的一個后代P1個體；S2的高六位與S1的低二位組成數串11101111，這就是S1和S2的一個后代P2個體。其交換過程如下圖所示：

3．變異(Mutation)

這是在選中的個體中，將新個體的基因鏈的各位按概率pm進行異向轉化，最簡單方式是改變串上某個位置數值。對二進制編碼來說將0與1互換：0變異為1，1變異為0。

如下8位二進制編碼：

1 1 1 0 1 1 0 0

隨機產生一個1至8之間的數i，假如現在k=6，對從右往左的第6位進行變異操作，將原來的1變為0，得到如下串：

1 1 0 0 1 1 0 0

整個交叉變異過程如下圖：

 

4．精英主義 （Elitism）

僅僅從產生的子代中選擇基因去構造新的種群可能會丟失掉上一代種群中的很多信息。也就是說當利用交叉和變異產生新的一代時，我們有很大的可能把在某個中間步驟中得到的最優解丟失。在此我們使用精英主義（Elitism）方法，在每一次產生新的一代時，我們首先把當前最優解原封不動的復制到新的一代中，其他步驟不變。這樣任何時刻產生的一個最優解都可以存活到遺傳算法結束。

上述各種算子的實現是多種多樣的，而且許多新的算子正在不斷地提出，以改進GA某些性能。比如選擇算法還有分級均衡選擇等等。

遺傳算法的所需參數

說簡單點遺傳算法就是遍歷搜索空間或連接池，從中找出最優的解。搜索空間中全部都是個體，而群體為搜索空間的一個子集。并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，一般在程序設計中交叉發生的概率要比變異發生的概率選取得大若干個數量級。大部分遺傳算法的步驟都很類似，常使用如下參數：

Fitness函數：見上文介紹。

Fitnessthreshold（適應度閥值）：適合度中的設定的閥值，當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時(變化率為零)，則算法的迭代過程收斂、算法結束。否則，用經過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到選擇操作處繼續循環執行。

P：種群的染色體總數叫種群規模，它對算法的效率有明顯的影響，其長度等于它包含的個體數量。太小時難以求出最優解，太大則增長收斂時間導致程序運行時間長。對不同的問題可能有各自適合的種群規模，通常種群規模為 30 至 160。

pc：在循環中進行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之間的值，Pc太小時難以向前搜索，太大則容易破壞高適應值的結構。

Pm：變異概率，從個體群中產生變異的概率，變異概率一般取0.01至0.03之間的值變異概率Pm太小時難以產生新的基因結構，太大使遺傳算法成了單純的隨機搜索。

另一個系統參數是個體的長度，有定長和變長兩種。它對算法的性能也有影響。由于GA是一個概率過程，所以每次迭代的情況是不一樣的,系統參數不同，迭代情況也不同。

遺傳步驟

了解了上面的基本參數，下面我們來看看遺傳算法的基本步驟。

基本過程為：

1. 對待解決問題進行編碼,我們將問題結構變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結構的過程叫譯碼。
2. 隨機初始化群體P(0)：=(p1, p2, … pn)；
3. 計算群體上每個個體的適應度值(Fitness)
4. 評估適應度,對當前群體P(t)中每個個體Pi計算其適應度F(Pi)，適應度表示了該個體的性能好壞
5. 按由個體適應度值所決定的某個規則應用選擇算子產生中間代Pr(t)
6. 依照Pc選擇個體進行交叉操作
7. 仿照Pm對繁殖個體進行變異操作
8. 沒有滿足某種停止條件，則轉第3步，否則進入9
9. 輸出種群中適應度值最優的個體

程序的停止條件最簡單的有如下二種：完成了預先給定的進化代數則停止；種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進時停止。

根據遺傳算法思想可以畫出如右圖所示的簡單遺傳算法框圖：

下面偽代碼簡單說明了遺傳算法操作過程：

choose an intial population
For each h in population,compute Fitness(h)
While(max Fitness(h) < Fitnessthreshold)
do selection
    do crossover
do mutation  
 update population
For each h in population,compute Fitness(h)
Return best Fitness

Robocode 說明

能有效實現遺傳算法的應用例子有很多，像西洋雙陸棋、國際名模等等都是遺傳程序設計學習的工具，但是 Robocode 有著其他幾個無可比擬的優勢：

1. 它是基于面向對象語言 Java 開發，而遺傳算法本身的思想也是存在繼承等面向對象概念；
2. Robocode 是一種基于游戲與編程語言之間的平臺，有一個充滿競技與樂趣的坦克戰斗平臺，你能很快的通過與其他坦克機器比賽而測試自己的遺傳算法；
3. Robocode 社群有 4000 個左右各種策略的例子機器人可供你選擇，這些機器人足以讓我們模擬真實的遺傳環境。而且很多代碼可直接開放源代碼供我們借鑒 ；
4. Robocode 是一個開源軟件，你可直接上Robocode控制器上加入自己的遺傳特點，而加快遺傳過程的收斂時間；
5. Robocoe 是一個很容易使用的機器人戰斗仿真器，您在此平臺上創建自己的坦克機器人，并與其它開發者開發的機器人競技。以得分排名的方式判定優勝者。每個 Robocode 參加者都要利用 Java 語言元素創建他或她的機器人，這樣就使從初學者到高級黑客的廣大開發者都可以參與這一娛樂活動。如果您對Robocode不是很了解，請參考 developerWorks 網站 Java 技術專區文章：“重錘痛擊 Robocode”；

在 Robocode 中其實有很多種遺傳算法方法來實現進化機器人，從全世界的 Robocode 流派中也發展幾種比較成熟的方法，比如預設策略遺傳、自開發解釋語言遺傳、遺傳移動我們就這幾種方法分別加以介紹。由于遺傳算法操作過程都類似，所以前面二部分都是一些方法的介紹和部分例子講解，后面部分會給出使用了遺傳算法的移動機器人人例子。在附錄中，也提供了機器人倉庫中有關遺傳算法機器人的下載，大家可參考。

預設策略進化機器人

Robocode 坦克機器人所有行為都離不開如移動、射擊、掃描等基本操作。所以在此把這些基本操作所用到的策略分別進化如下編碼：移動策略move-strategy (MS), 子彈能量bullet-power-strategy (BPS), 雷達掃描radar-strategy (RS), 和瞄準選擇策略target- strategy (TS)。由于Robocode愛好者社群的發展，每一種基本操作都發展了很多比較成熟的策略，所有在此我們直接在下面預先定義的這些策略如下表：

下面是基本移動策略的說明：

• Random：隨機移動主要用來混亂敵人的預測，其最大的一個缺點是有可能撞擊到其他機器人
• Linear：直線移動,機器人做單一的直線行走
• circular：圓周移動，這種移動是以某一點為圓心，不停的繞圈
• Perpendicular：正對敵人移動，這是很多人采用的一種移動方式，這在敵人右邊， 以隨時調整與敵人的相對角
• Arbitrary：任意移動
• AntiGravity：假設場地有很多力點的反重力移動，本方法是模擬在重力場作用下，物體總是遠離重力勢高的點，滑向重力勢低的點，開始戰場是一個平面然后生成一些勢點重力勢大的勢點的作用就像是一個山(起排斥作用），其衰減系數與山的坡度對應。重力勢小的勢點的作用就像是一個低谷（起吸引作用），其衰減系數與谷的坡度對應。這樣使本來的平面變得不平了，從來物體沿著最陡的方向向下滑動
• Track：跟蹤敵人，敵人移動到哪，機器人也移動到哪，但是總與敵人保持一定最佳躲避子彈距離和角度
• Oscillators：重復做一振蕩移動
• Bullet avoid：每當雷達覺察到敵人時有所動作。機器人保持與敵人成30度傾向角。自身成 90 度角靜止并逐漸接近目標。如果機器人覺察到能量下降介于 0.1 和 3.0 之間（火力范圍），那么機器人就立即切換方向，向左或向右移動。
• wall avoid：這是一種使自己的機器人不會被困在角落里或者不會撞墻的移動方式

瞄準策略說明如下：

• Headon：正對瞄準
• Linear：直線瞄準
• circular：圓周瞄準
• nearest robot：接近機器人瞄準
• Log：保存每次開火記錄
• Statistic：統計學瞄準，分析所有打中及未打中的次數，以其中找出最高打中敵人的概率為準則
• Angular：找到最佳角度瞄準
• Wave：波形瞄準，子彈以波的方式進行探測

Robocode 行為事件

坦克的主要都定義在一個主循環中，我們在程序中定義為上面四個策略定義四種戰略如Move,Radar,Power,Target，當某一事件發生，基于這個事件而定的行為就會觸發。而每個戰略中都有不同的行為處理方式。這些行為通過遺傳算法觸發，遺傳算法將調用這些基本動作并搜索這些策略的最佳組合?；谶@些基本動作將有4224 (=4*11*4*3*8)種可能發生。在Robocode AdvancedRobot 類下有如下的移動函數：

• setAhead和ahead：讓機器人向前移動一定距離.
• setBack和back：讓機器人向后移動一定距離
• setMaxTurnRate：設置機器人最大的旋轉速度
• setMaxVelocity：設置機器人最大的運動速度
• setStop和stop：停止移動或暫停機器人，并記住停止的位置
• setResume和resume：重新開始移動停止的機器人
• setTurnLeft和turnLeft：向左旋轉機器人
• setTurnRight和turnRight：向右旋轉機器人

下面是 doMove 移動方法中使用部分程序代碼：

Random：

switch(Math.random()*2) {
 case 0： setTurnRight(Math.random()*90);
break;
case 1： setTurnLeft(Math.random()*90);
 break; }
 execute();

Linear：

ahead(200);
setBack(200);

Circular：

setTurnRight(1000);
setMaxVelocity(4);
ahead(1000);

anti gravity：

 double forceX = 0;
  double forceY = 0;
  for (int i=0; i   

這里我們用遺傳算法來控制機器人移動位置。這些策略是基于下面幾點：機器人人自己的位置、速度和方位;對手的位置（x,y坐標）、速度、方位以及相對角;所有機器人和子彈位置，方位及速度;場地大小等參數。

當上面的信息在下一回移動中使用時，出輸出一對坐標值，根據這對坐標在Robocode就能得到距離和角度。要想讓移動實現遺傳必須要讓它實現在線學習：所以我們的代碼必須做下面幾件事：要有一個函數收集適應度值，在Robocode運行過程中要運用到遺傳操作，遺傳后代要在Robocode運行中產生，而不是事后由手寫入代碼。

遺傳操作

本例中遺傳算法為實現移動用到兩個類GA和MovePattern。此處的GA比較簡單主要完成數據和群體的定義，以及這些定義的讀寫文件操作?；邪ㄈ缦聟担喝后w大小、交叉概率、變異概率、精英概率（既告訴從當前群體到下一代中有多少移動不需要改變）、方程式中使用的加權系數大小，它通過一個主循環完成MovePattern的封裝。MovePattern類中實現交叉、變異方法等方法，完成移動模式操作。而所有的輸出保存在一個vector函數當中。Vector函數擁有一對實數數組，一個用于計算x坐標，另一個用于計算y坐標。通過對x,y坐標的計算，從而得到距離、角度等值，并產生相就在移動策略。如下，MovePattern包含三個參數，grad表示vector函數排列順序，input即表示算法給出的輸入編號，rang是加權的范圍。

public class MovePatteren implements Comparable {
 private int grad, input;
 private double range;
 protected double fitness=0;
 protected double[] weightsX, weightsY;    
… }

交叉操作：每一個交叉操作執行如下步驟，先在交叉操作中產生一個特征碼。這個特征碼是個0到1之間的變量數組。有關交叉的基本原理可參考上面部分。最后通過遍歷vector函數，把相應的加權值進行交叉操作。

protected MovePatteren crossOver(MovePatteren mate, boolean[] maskx, boolean[] masky) {
  double[] wx= new double[weightsX.length];
  double[] wy= new double[weightsX.length];
  for(int mask=0; mask <="" pre="" mask++)="" for(int="" g="0;" g  

這里的變異操作比較簡單。把加權范圍內的隨機數值去代替0到數組長之間的隨機數并保存到移動模式中。則完成整個數組的變異過程：

protected void mutate() {
weightsX[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
weightsY[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
}

從上面的例子我們知道了遺傳算法的大概實現，但并沒有告訴我們這些組件是如何一起工作的。當Robocode開始時，如果文件中沒有數據，所以系統會依照輸入的策略隨機生成一個移動模式，如果文件中有數據，則加載這些數據。每一個移動模式在開始都會給出了一個適應度值。當所有的移動模式都接收到適應度值，并完成各自的編號后，下面的操作將開始執行：

1. 對所有的移動模式依據它們的適應度值進行分級處理
2. 執行精英操作
3. 執行交叉操作
4. 應用變異操作
5. 保存加權
6. 算法重新開始

適應度值在進行運算過程中由機器人程序不斷調整，以找到最優適應度。

限于篇副其他的一些策略本文不與詳細說明，上面所有提到的策略和行為程序都可在網上或IBM的開發雜志上找到成熟的講解和例子機器人。有興趣的朋友可以把這些策略都加入到自己的遺傳算法中來。我們取群體大小為50，選擇概率為0.7，交叉概率為0.6，變異概率為0.3，與Robocode部分例子機器人測試，經過150代后你會發現系統產生了很多有趣的策略。比如撞擊策略，這些策略都不在我們定義的策略之中。

中間解釋程序進化機器人

遺傳算法可被看做任意基因組字符串。但是你必須決定這些字符所代表的意義，也就是說如何解釋每一個基因組。最簡單的方法是把每一個基因組視為java代碼，編譯并運行它們。但是這些程序編譯都很困難，所以也就有可能不能工作。Jacob Eisenstein設計了一種機器翻譯語言TableRex來解決這個問題。在java中，TableRex被用于進化和解釋動行時的Robocode 機器人。通過測試，只要我把TableRex解釋程序作為文件放入Robocode控制器目錄中，這些控制器就會讀取文件并開始戰斗。TableRex是一些最適合遺傳算法的二進制編程。只要符合TableRex程序文法，每個程序都能被解釋。

編碼

下表中顯示了TableRex編碼結構，它由一個行動作函數，二個輸入和一個輸出組成。如行6的值 ，這是個布爾型的表達式“值 line4 小于 90”，這個結果會在最后一行輸出布爾為1的值。