遺傳算法入門

1、遺傳算法入門遺傳算法遺傳算法（Genetic Algorithm, GA）是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學(xué)和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應(yīng)性的提高。從某種程度上說遺傳算法是對生物進化過程進行的數(shù)學(xué)方式仿真。這一點體現(xiàn)了自然界中"物競天擇、適者生存"進化過程。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價,把問題的解表示成染色體，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。在算法

2、中也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群染色體，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，也即一個適應(yīng)度函數(shù)中來評價。并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的染色體進行復(fù)制, 淘汰低適應(yīng)度的個體，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代染色體群。對這個新種群進行下一輪進化，至到最適合環(huán)境的值。遺傳算法已用于求解帶有應(yīng)用前景的一些問題，例如遺傳程序設(shè)計、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計算機圖像處理和機器人運動規(guī)劃等。術(shù)語說明由于遺傳算法是由進化論和遺傳學(xué)機理而產(chǎn)生的搜索算法，所以在這個算法中會用到很多生物遺傳學(xué)知識，下面是我們將會用來的一些術(shù)語說

3、明：一、染色體(Chronmosome)染色體又可以叫做基因型個體(individuals),一定數(shù)量的個體組成了群體(population),群體中個體的數(shù)量叫做群體大小。二、基因(Gene)基因是串中的元素，基因用于表示個體的特征。例如有一個串S1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。三、基因地點(Locus)基因地點在算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位?；蛭恢糜纱淖笙蛴矣嬎悖缭诖?S1101 中，0的基因位置是3。四、基因特征值(Gene Feature)在用串表示整數(shù)

4、時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。五、適應(yīng)度(Fitness)各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應(yīng)度函數(shù). 這個函數(shù)是計算個體在群體中被使用的概率。操作算法霍蘭德(Holland)教授最初提出的算法也叫簡單遺傳算法，簡單遺傳算法的遺傳操作主要有三種：選擇(selection)、交叉(crossover)、變異(mutation)這也是遺傳算法中最常用的三種算法：1選擇(selection)選擇

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

6、0.1430.060.0152交叉(Crossover)交叉算子將被選中的兩個個體的基因鏈按一定概率pc進行交叉，從而生成兩個新的個體，交叉位置pc是隨機的。其中Pc是一個系統(tǒng)參數(shù)。根據(jù)問題的不同，交叉又為了單點交叉算子（Single Point Crossover）、雙點交叉算子（Two Point Crossover）、均勻交叉算子 (Uniform Crossover)，在此我們只討論單點交叉的情況。單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，將兩者的部分基因碼值進行交換。假設(shè)如下兩個8位的個體：S1 1000 1111 S2 1110 1100產(chǎn)生一個在1到7之

7、間的隨機數(shù)c，假如現(xiàn)在產(chǎn)生的是2，將S1和S2的低二位交換：S1的高六位與S2的低六位組成數(shù)串10001100，這就是S1和S2 的一個后代P1個體；S2的高六位與S1的低二位組成數(shù)串11101111，這就是S1和S2的一個后代P2個體。其交換過程如下圖所示：Crossover11110000Crossover11110000S11000 1111S21110 1100P11000 1100P21110 11113變異(Mutation)這是在選中的個體中，將新個體的基因鏈的各位按概率pm進行異向轉(zhuǎn)化，最簡單方式是改變串上某個位置數(shù)值。對二進制編碼來說將0與1互換：0變異為1，1變異為0。如下

8、8位二進制編碼：1 1 1 0 1 1 0 0隨機產(chǎn)生一個1至8之間的數(shù)i，假如現(xiàn)在k=6，對從右往左的第6位進行變異操作，將原來的1變?yōu)?，得到如下串：1 1 0 0 1 1 0 0整個交叉變異過程如下圖：圖2. 交叉變異過程  4精英主義 （Elitism）僅僅從產(chǎn)生的子代中選擇基因去構(gòu)造新的種群可能會丟失掉上一代種群中的很多信息。也就是說當(dāng)利用交叉和變異產(chǎn)生新的一代時，我們有很大的可能把在某個中間步驟中得到的最優(yōu)解丟失。在此我們使用精英主義（Elitism）方法，在每一次產(chǎn)生新的一代時，我們首先把當(dāng)前最優(yōu)解原封不動的復(fù)制到新的一代中，其他步驟不變。這樣任何時刻產(chǎn)生的一

9、個最優(yōu)解都可以存活到遺傳算法結(jié)束。上述各種算子的實現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進GA某些性能。比如選擇算法還有分級均衡選擇等等。遺傳算法的所需參數(shù)說簡單點遺傳算法就是遍歷搜索空間或連接池，從中找出最優(yōu)的解。搜索空間中全部都是個體，而群體為搜索空間的一個子集。并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，一般在程序設(shè)計中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大若干個數(shù)量級。大部分遺傳算法的步驟都很類似，常使用如下參數(shù)：Fitness函數(shù)：見上文介紹。Fitnessthreshold（適應(yīng)度閥值）：適合度中的設(shè)定的閥值，當(dāng)最優(yōu)個體的適應(yīng)度達到給

10、定的閥值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時(變化率為零)，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到選擇操作處繼續(xù)循環(huán)執(zhí)行。P：種群的染色體總數(shù)叫種群規(guī)模，它對算法的效率有明顯的影響，其長度等于它包含的個體數(shù)量。太小時難以求出最優(yōu)解，太大則增長收斂時間導(dǎo)致程序運行時間長。對不同的問題可能有各自適合的種群規(guī)模，通常種群規(guī)模為 30 至 160。另一個系統(tǒng)參數(shù)是個體的長度，有定長和變長兩種。它對算法的性能也有影響。由于GA是一個概率過程，所以每次迭代的情況是不一樣的,系統(tǒng)參數(shù)不同，迭代情況也不同。遺傳步驟了解了上面的基本參數(shù)，下

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

12、值最優(yōu)的個體程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進化代數(shù)則停止；種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進時停止。根據(jù)遺傳算法思想可以畫出如右圖所示的簡單遺傳算法框圖：圖3. 簡單遺傳算法框圖 下面?zhèn)未a簡單說明了遺傳算法操作過程：choose an intial populationFor each h in population,compute Fitness(h)While(max Fitness(h) < Fitnessthreshold)do selection do crossoverdo mutation update

13、populationFor each h in population,compute Fitness(h)Return best FitnessRobocode 說明能有效實現(xiàn)遺傳算法的應(yīng)用例子有很多，像西洋雙陸棋、國際名模等等都是遺傳程序設(shè)計學(xué)習(xí)的工具，但是 Robocode 有著其他幾個無可比擬的優(yōu)勢：1. 它是基于面向?qū)ο笳Z言 Java 開發(fā)，而遺傳算法本身的思想也是存在繼承等面向?qū)ο蟾拍睿?. Robocode 是一種基于游戲與編程語言之間的平臺，有一個充滿競技與樂趣的坦克戰(zhàn)斗平臺，你能很快的通過與其他坦克機器比賽而測試自己的遺傳算法；3. Robocode 社群有 4000 個左右各

14、種策略的例子機器人可供你選擇，這些機器人足以讓我們模擬真實的遺傳環(huán)境。而且很多代碼可直接開放源代碼供我們借鑒 ；4. Robocode 是一個開源軟件，你可直接上Robocode控制器上加入自己的遺傳特點，而加快遺傳過程的收斂時間；5. Robocoe 是一個很容易使用的機器人戰(zhàn)斗仿真器，您在此平臺上創(chuàng)建自己的坦克機器人，并與其它開發(fā)者開發(fā)的機器人競技。以得分排名的方式判定優(yōu)勝者。每個 Robocode 參加者都要利用 Java 語言元素創(chuàng)建他或她的機器人，這樣就使從初學(xué)者到高級黑客的廣大開發(fā)者都可以參與這一娛樂活動。如果您對Robocode不是很了解，請參考 developerWorks 網(wǎng)

15、站 Java 技術(shù)專區(qū)文章：“重錘痛擊 Robocode”；在 Robocode 中其實有很多種遺傳算法方法來實現(xiàn)進化機器人，從全世界的 Robocode 流派中也發(fā)展幾種比較成熟的方法，比如預(yù)設(shè)策略遺傳、自開發(fā)解釋語言遺傳、遺傳移動我們就這幾種方法分別加以介紹。由于遺傳算法操作過程都類似，所以前面二部分都是一些方法的介紹和部分例子講解，后面部分會給出使用了遺傳算法的移動機器人人例子。在附錄中，也提供了機器人倉庫中有關(guān)遺傳算法機器人的下載，大家可參考。預(yù)設(shè)策略進化機器人Robocode 坦克機器人所有行為都離不開如移動、射擊、掃描等基本操作。所以在此把這些基本操作所用到的策略分別進化如下編碼：

16、移動策略move-strategy (MS), 子彈能量bullet-power-strategy (BPS), 雷達掃描radar-strategy (RS), 和瞄準(zhǔn)選擇策略target- strategy (TS)。由于Robocode愛好者社群的發(fā)展，每一種基本操作都發(fā)展了很多比較成熟的策略，所有在此我們直接在下面預(yù)先定義的這些策略如下表：MSBPSRSTSrandomdistance-basedalways-turnHeadOnLinearlight-fasttarget-focusLinearcircularPowerful-slowtarget-scope-focusCircul

17、arPerpendicularMedium nearest robotarbitaryhit-rate based Loganti gravity  StatisticStop  AngularBullet avoid  wavewall avoid   track   Oscillators   下面是基本移動策略的說明：· Random：隨機移動主要用來混亂敵人的預(yù)測，其最大的一個缺點是有可能撞擊到其他機器人&#

18、183; Linear：直線移動,機器人做單一的直線行走· circular：圓周移動，這種移動是以某一點為圓心，不停的繞圈· Perpendicular：正對敵人移動，這是很多人采用的一種移動方式，這在敵人右邊， 以隨時調(diào)整與敵人的相對角· Arbitrary：任意移動· AntiGravity：假設(shè)場地有很多力點的反重力移動，本方法是模擬在重力場作用下，物體總是遠離重力勢高的點，滑向重力勢低的點，開始戰(zhàn)場是一個平面然后生成一些勢點重力勢大的勢點的作用就像是一個山(起排斥作用），其衰減系數(shù)與山的坡度對應(yīng)。重力勢小的勢點的作用就像是一個低谷（起吸引作用）

19、，其衰減系數(shù)與谷的坡度對應(yīng)。這樣使本來的平面變得不平了，從來物體沿著最陡的方向向下滑動· Track：跟蹤敵人，敵人移動到哪，機器人也移動到哪，但是總與敵人保持一定最佳躲避子彈距離和角度· Oscillators：重復(fù)做一振蕩移動· Bullet avoid：每當(dāng)雷達覺察到敵人時有所動作。機器人保持與敵人成30度傾向角。自身成 90 度角靜止并逐漸接近目標(biāo)。如果機器人覺察到能量下降介于 0.1 和 3.0 之間（火力范圍），那么機器人就立即切換方向，向左或向右移動。· wall avoid：這是一種使自己的機器人不會被困在角落里或者不會撞墻的移動方式瞄準(zhǔn)

20、策略說明如下：· Headon：正對瞄準(zhǔn)· Linear：直線瞄準(zhǔn)· circular：圓周瞄準(zhǔn)· nearest robot：接近機器人瞄準(zhǔn)· Log：保存每次開火記錄· Statistic：統(tǒng)計學(xué)瞄準(zhǔn)，分析所有打中及未打中的次數(shù)，以其中找出最高打中敵人的概率為準(zhǔn)則· Angular：找到最佳角度瞄準(zhǔn)· Wave：波形瞄準(zhǔn)，子彈以波的方式進行探測Robocode 行為事件坦克的主要都定義在一個主循環(huán)中，我們在程序中定義為上面四個策略定義四種戰(zhàn)略如Move,Radar,Power,Target，當(dāng)某一事件發(fā)生，基于

21、這個事件而定的行為就會觸發(fā)。而每個戰(zhàn)略中都有不同的行為處理方式。這些行為通過遺傳算法觸發(fā)，遺傳算法將調(diào)用這些基本動作并搜索這些策略的最佳組合。基于這些基本動作將有4224 (=4*11*4*3*8)種可能發(fā)生。在Robocode AdvancedRobot 類下有如下的移動函數(shù)：· setAhead和ahead：讓機器人向前移動一定距離.· setBack和back：讓機器人向后移動一定距離· setMaxTurnRate：設(shè)置機器人最大的旋轉(zhuǎn)速度· setMaxVelocity：設(shè)置機器人最大的運動速度· setStop和stop：停止移動或

22、暫停機器人，并記住停止的位置· setResume和resume：重新開始移動停止的機器人· setTurnLeft和turnLeft：向左旋轉(zhuǎn)機器人· setTurnRight和turnRight：向右旋轉(zhuǎn)機器人下面是 doMove 移動方法中使用部分程序代碼：Random：switch(Math.random()*2) case 0： setTurnRight(Math.random()*90);break;case 1： setTurnLeft(Math.random()*90); break; execute();Linear：ahead(200);set

23、Back(200);Circular：setTurnRight(1000);setMaxVelocity(4);ahead(1000);anti gravity： double forceX = 0; double forceY = 0; for (int i=0; i 這里我們用遺傳算法來控制機器人移動位置。這些策略是基于下面幾點：機器人人自己的位置、速度和方位;對手的位置（x,y坐標(biāo)）、速度、方位以及相對角;所有機器人和子彈位置，方位及速度;場地大小等參數(shù)。當(dāng)上面的信息在下一回移動中使用時，出輸出一對坐標(biāo)值，根據(jù)這對坐標(biāo)在Robocode就能得到距離和角度。要想讓移動實現(xiàn)遺傳必須要讓它實現(xiàn)

24、在線學(xué)習(xí)：所以我們的代碼必須做下面幾件事：要有一個函數(shù)收集適應(yīng)度值，在Robocode運行過程中要運用到遺傳操作，遺傳后代要在Robocode運行中產(chǎn)生，而不是事后由手寫入代碼。遺傳操作本例中遺傳算法為實現(xiàn)移動用到兩個類GA和MovePattern。此處的GA比較簡單主要完成數(shù)據(jù)和群體的定義，以及這些定義的讀寫文件操作?；邪ㄈ缦聟?shù)：群體大小、交叉概率、變異概率、精英概率（既告訴從當(dāng)前群體到下一代中有多少移動不需要改變）、方程式中使用的加權(quán)系數(shù)大小，它通過一個主循環(huán)完成MovePattern的封裝。MovePattern類中實現(xiàn)交叉、變異方法等方法，完成移動模式操作。而所有的輸出保存在一個

25、vector函數(shù)當(dāng)中。Vector函數(shù)擁有一對實數(shù)數(shù)組，一個用于計算x坐標(biāo)，另一個用于計算y坐標(biāo)。通過對x,y坐標(biāo)的計算，從而得到距離、角度等值，并產(chǎn)生相就在移動策略。如下，MovePattern包含三個參數(shù)，grad表示vector函數(shù)排列順序，input即表示算法給出的輸入編號，rang是加權(quán)的范圍。public class MovePatteren implements Comparable private int grad, input; private double range; protected double fitness=0; protected double weights

26、X, weightsY; 交叉操作：每一個交叉操作執(zhí)行如下步驟，先在交叉操作中產(chǎn)生一個特征碼。這個特征碼是個0到1之間的變量數(shù)組。有關(guān)交叉的基本原理可參考上面部分。最后通過遍歷vector函數(shù)，把相應(yīng)的加權(quán)值進行交叉操作。protected MovePatteren crossOver(MovePatteren mate, boolean maskx, boolean masky) double wx= new doubleweightsX.length; double wy= new doubleweightsX.length; for(int mask=0; mask <="

27、;" pre="" mask+)="" for(int="" g="0;" g 這里的變異操作比較簡單。把加權(quán)范圍內(nèi)的隨機數(shù)值去代替0到數(shù)組長之間的隨機數(shù)并保存到移動模式中。則完成整個數(shù)組的變異過程：protected void mutate() weightsX(int)(Math.random()*weightsX.length)=Math.random()*range*2-range;weightsY(int)(Math.random()*weightsX.length)=Math.random()

28、*range*2-range;從上面的例子我們知道了遺傳算法的大概實現(xiàn)，但并沒有告訴我們這些組件是如何一起工作的。當(dāng)Robocode開始時，如果文件中沒有數(shù)據(jù)，所以系統(tǒng)會依照輸入的策略隨機生成一個移動模式，如果文件中有數(shù)據(jù)，則加載這些數(shù)據(jù)。每一個移動模式在開始都會給出了一個適應(yīng)度值。當(dāng)所有的移動模式都接收到適應(yīng)度值，并完成各自的編號后，下面的操作將開始執(zhí)行：1. 對所有的移動模式依據(jù)它們的適應(yīng)度值進行分級處理2. 執(zhí)行精英操作3. 執(zhí)行交叉操作4. 應(yīng)用變異操作5. 保存加權(quán)6. 算法重新開始適應(yīng)度值在進行運算過程中由機器人程序不斷調(diào)整，以找到最優(yōu)適應(yīng)度。限于篇副其他的一些策略本文不與詳細(xì)說明，上面所有提到的策略和