twzheng's cppblog

遺傳算法入門

遺傳算法

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

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

遺傳算法已用于求解帶有應(yīng)用前景的一些問題，例如遺傳程序設(shè)計(jì)、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計(jì)算機(jī)圖像處理和機(jī)器人運(yùn)動(dòng)規(guī)劃等。

術(shù)語說明

由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識(shí)，下面是我們將會(huì)用來的一些術(shù)語說明：

一、染色體(Chronmosome)

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

二、基因(Gene)

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

三、基因地點(diǎn)(Locus)

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

四、基因特征值(Gene Feature)

在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。

五、適應(yīng)度(Fitness)

各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù). 這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。

操作算法

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

1．選擇(selection)

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

2．交叉(Crossover)

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

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

S1 1000  1111 S2 1110  1100

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

3．變異(Mutation)

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

如下8位二進(jìn)制編碼：

1 1 1 0 1 1 0 0

隨機(jī)產(chǎn)生一個(gè)1至8之間的數(shù)i，假如現(xiàn)在k=6，對(duì)從右往左的第6位進(jìn)行變異操作，將原來的1變?yōu)?，得到如下串：

1 1 0 0 1 1 0 0

整個(gè)交叉變異過程如下圖：

 

4．精英主義 （Elitism）

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

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

遺傳算法的所需參數(shù)

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

Fitness函數(shù)：見上文介紹。

Fitnessthreshold（適應(yīng)度閥值）：適合度中的設(shè)定的閥值，當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)(變化率為零)，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到選擇操作處繼續(xù)循環(huán)執(zhí)行。

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

pc：在循環(huán)中進(jìn)行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之間的值，Pc太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)。

Pm：變異概率，從個(gè)體群中產(chǎn)生變異的概率，變異概率一般取0.01至0.03之間的值變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。

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

遺傳步驟

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

基本過程為：

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

程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。

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

下面?zhèn)未a簡單說明了遺傳算法操作過程：

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 說明

能有效實(shí)現(xiàn)遺傳算法的應(yīng)用例子有很多，像西洋雙陸棋、國際名模等等都是遺傳程序設(shè)計(jì)學(xué)習(xí)的工具，但是 Robocode 有著其他幾個(gè)無可比擬的優(yōu)勢：

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

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

預(yù)設(shè)策略進(jìn)化機(jī)器人

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

下面是基本移動(dòng)策略的說明：

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

瞄準(zhǔn)策略說明如下：

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

Robocode 行為事件

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

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

下面是 doMove 移動(dòng)方法中使用部分程序代碼：

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   

這里我們用遺傳算法來控制機(jī)器人移動(dòng)位置。這些策略是基于下面幾點(diǎn)：機(jī)器人人自己的位置、速度和方位;對(duì)手的位置（x,y坐標(biāo)）、速度、方位以及相對(duì)角;所有機(jī)器人和子彈位置，方位及速度;場地大小等參數(shù)。

當(dāng)上面的信息在下一回移動(dòng)中使用時(shí)，出輸出一對(duì)坐標(biāo)值，根據(jù)這對(duì)坐標(biāo)在Robocode就能得到距離和角度。要想讓移動(dòng)實(shí)現(xiàn)遺傳必須要讓它實(shí)現(xiàn)在線學(xué)習(xí)：所以我們的代碼必須做下面幾件事：要有一個(gè)函數(shù)收集適應(yīng)度值，在Robocode運(yùn)行過程中要運(yùn)用到遺傳操作，遺傳后代要在Robocode運(yùn)行中產(chǎn)生，而不是事后由手寫入代碼。

遺傳操作

本例中遺傳算法為實(shí)現(xiàn)移動(dòng)用到兩個(gè)類GA和MovePattern。此處的GA比較簡單主要完成數(shù)據(jù)和群體的定義，以及這些定義的讀寫文件操作。基中包括如下參數(shù)：群體大小、交叉概率、變異概率、精英概率（既告訴從當(dāng)前群體到下一代中有多少移動(dòng)不需要改變）、方程式中使用的加權(quán)系數(shù)大小，它通過一個(gè)主循環(huán)完成MovePattern的封裝。MovePattern類中實(shí)現(xiàn)交叉、變異方法等方法，完成移動(dòng)模式操作。而所有的輸出保存在一個(gè)vector函數(shù)當(dāng)中。Vector函數(shù)擁有一對(duì)實(shí)數(shù)數(shù)組，一個(gè)用于計(jì)算x坐標(biāo)，另一個(gè)用于計(jì)算y坐標(biāo)。通過對(duì)x,y坐標(biāo)的計(jì)算，從而得到距離、角度等值，并產(chǎn)生相就在移動(dòng)策略。如下，MovePattern包含三個(gè)參數(shù)，grad表示vector函數(shù)排列順序，input即表示算法給出的輸入編號(hào)，rang是加權(quán)的范圍。

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

交叉操作：每一個(gè)交叉操作執(zhí)行如下步驟，先在交叉操作中產(chǎn)生一個(gè)特征碼。這個(gè)特征碼是個(gè)0到1之間的變量數(shù)組。有關(guān)交叉的基本原理可參考上面部分。最后通過遍歷vector函數(shù)，把相應(yīng)的加權(quán)值進(jìn)行交叉操作。

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  

這里的變異操作比較簡單。把加權(quán)范圍內(nèi)的隨機(jī)數(shù)值去代替0到數(shù)組長之間的隨機(jī)數(shù)并保存到移動(dòng)模式中。則完成整個(gè)數(shù)組的變異過程：

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;
}

從上面的例子我們知道了遺傳算法的大概實(shí)現(xiàn)，但并沒有告訴我們這些組件是如何一起工作的。當(dāng)Robocode開始時(shí)，如果文件中沒有數(shù)據(jù)，所以系統(tǒng)會(huì)依照輸入的策略隨機(jī)生成一個(gè)移動(dòng)模式，如果文件中有數(shù)據(jù)，則加載這些數(shù)據(jù)。每一個(gè)移動(dòng)模式在開始都會(huì)給出了一個(gè)適應(yīng)度值。當(dāng)所有的移動(dòng)模式都接收到適應(yīng)度值，并完成各自的編號(hào)后，下面的操作將開始執(zhí)行：

1. 對(duì)所有的移動(dòng)模式依據(jù)它們的適應(yīng)度值進(jìn)行分級(jí)處理
2. 執(zhí)行精英操作
3. 執(zhí)行交叉操作
4. 應(yīng)用變異操作
5. 保存加權(quán)
6. 算法重新開始

適應(yīng)度值在進(jìn)行運(yùn)算過程中由機(jī)器人程序不斷調(diào)整，以找到最優(yōu)適應(yīng)度。

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

中間解釋程序進(jìn)化機(jī)器人

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

編碼

下表中顯示了TableRex編碼結(jié)構(gòu)，它由一個(gè)行動(dòng)作函數(shù)，二個(gè)輸入和一個(gè)輸出組成。如行6的值 ，這是個(gè)布爾型的表達(dá)式“值 line4 小于 90”，這個(gè)結(jié)果會(huì)在最后一行輸出布爾為1的值。