遺傳算法入門

原文位址為： 遺傳算法入門

優化算法入門系列文章目錄（更新中）：

　　1. 模拟退火算法

　　2. 遺傳算法

　　遺傳算法 ( GA , Genetic Algorithm ) ，也稱進化算法 。 遺傳算法是受達爾文的進化論的啟發，借鑒生物進化過程而提出的一種啟發式搜尋算法。是以在介紹遺傳算法前有必要簡單的介紹生物進化知識。

一.進化論知識 

　　作為遺傳算法生物背景的介紹，下面内容了解即可：

　　種群(Population)：生物的進化以群體的形式進行，這樣的一個群體稱為種群。

　　個體：組成種群的單個生物。

　　基因 ( Gene ) ：一個遺傳因子。 

　　染色體 ( Chromosome ) ：包含一組的基因。

　　生存競争，适者生存：對環境适應度高的、牛B的個體參與繁殖的機會比較多，後代就會越來越多。适應度低的個體參與繁殖的機會比較少，後代就會越來越少。

　　遺傳與變異：新個體會遺傳父母雙方各一部分的基因，同時有一定的機率發生基因變異。

　　簡單說來就是：繁殖過程，會發生基因交叉( Crossover ) ，基因突變 ( Mutation ) ，适應度( Fitness )低的個體會被逐漸淘汰，而适應度高的個體會越來越多。那麼經過N代的自然選擇後，儲存下來的個體都是适應度很高的，其中很可能包含史上産生的适應度最高的那個個體。

二.遺傳算法思想 

　　借鑒生物進化論，遺傳算法将要解決的問題模拟成一個生物進化的過程，通過複制、交叉、突變等操作産生下一代的解，并逐漸淘汰掉适應度函數值低的解，增加适應度函數值高的解。這樣進化N代後就很有可能會進化出适應度函數值很高的個體。

　　舉個例子，使用遺傳算法解決“0-1背包問題”的思路：0-1背包的解可以編碼為一串0-1字元串（0：不取，1：取） ；首先，随機産生M個0-1字元串，然後評價這些0-1字元串作為0-1背包問題的解的優劣；然後，随機選擇一些字元串通過交叉、突變等操作産生下一代的M個字元串，而且較優的解被選中的機率要比較高。這樣經過G代的進化後就可能會産生出0-1背包問題的一個“近似最優解”。

　　編碼：需要将問題的解編碼成字元串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進制編碼，即将問題的解編碼成二進制位數組的形式。例如，問題的解是整數，那麼可以将其編碼成二進制位數組的形式。将0-1字元串作為0-1背包問題的解就屬于二進制編碼。

　　遺傳算法有3個最基本的操作：選擇，交叉，變異。

　　選擇：選擇一些染色體來産生下一代。一種常用的選擇政策是 “比例選擇”，也就是個體被選中的機率與其适應度函數值成正比。假設群體的個體總數是M，那麼那麼一個體Xi被選中的機率為f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。比例選擇實作算法就是所謂的“輪盤賭算法”( Roulette Wheel Selection ) ，輪盤賭算法的一個簡單的實作如下：

輪盤賭算法

int RWS()

{

m =0;

r =Random(0,1); //r為0至1的随機數

for(i=1;i<=N; i++)

{

m = m + P[i];

if(r<=m) return i;

}

}

交叉(Crossover)：2條染色體交換部分基因，來構造下一代的2條新的染色體。例如：

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉後：

00000|000001111110|10000

11100|011100000000|00101

染色體交叉是以一定的機率發生的，這個機率記為Pc 。

變異(Mutation)：在繁殖過程，新産生的染色體中的基因會以一定的機率出錯，稱為變異。變異發生的機率記為Pm 。例如：

變異前：

000001110000000010000

變異後：

000001110000100010000

适應度函數 ( Fitness Function )：用于評價某個染色體的适應度，用f(x)表示。有時需要區分染色體的适應度函數與問題的目标函數。例如：0-1背包問題的目标函數是所取得物品價值，但将物品價值作為染色體的适應度函數可能并不一定适合。适應度函數與目标函數是正相關的，可對目标函數作一些變形來得到适應度函數。

三.基本遺傳算法的僞代碼 

基本遺傳算法僞代碼

初始化Pm，Pc，M，G，Tf等參數。随機産生第一代種群Pop

do

{

　　計算種群Pop中每一個體的适應度F(i)。

　　初始化空種群newPop

　　do

　　{

　　　　根據适應度以比例選擇算法從種群Pop中選出2個個體

　　　　if ( random ( 0 , 1 ) < Pc )

　　　　{

　　　　　　對2個個體按交叉機率Pc執行交叉操作

　　　　}

　　　　if ( random ( 0 , 1 ) < Pm )

　　　　{

　　　　　　對2個個體按變異機率Pm執行變異操作

　　　　}

将2個新個體加入種群newPop中

} until ( M個子代被建立 )

用newPop取代Pop

}until ( 任何染色體得分超過Tf， 或繁殖代數超過G )  

四.基本遺傳算法優化 

 　　下面的方法可優化遺傳算法的性能。

 　　精英主義(Elitist Strategy)選擇：是基本遺傳算法的一種優化。為了防止進化過程中産生的最優解被交叉和變異所破壞，可以将每一代中的最優解原封不動的複制到下一代中。

 　　插入操作：可在3個基本操作的基礎上增加一個插入操作。插入操作将染色體中的某個随機的片段移位到另一個随機的位置。

五. 使用AForge.Genetic解決TSP問題

　　AForge.NET是一個C#實作的面向人工智能、計算機視覺等領域的開源架構。AForge.NET中包含有一個遺傳算法的類庫。

　　AForge.NET首頁：http://www.aforgenet.com/

　　AForge.NET代碼下載下傳：http://code.google.com/p/aforge/

　　介紹一下AForge的遺傳算法用法吧。AForge.Genetic的類結構如下：

圖1. AForge.Genetic的類圖

   下面用AForge.Genetic寫個解決TSP問題的最簡單執行個體。測試資料集采用網上流傳的中國31個省會城市的坐标:

13042312

36391315

41772244

37121399

34881535

33261556

32381229

41961004

4312790

4386570

30071970

25621756

27881491

23811676

1332695

37151678

39182179

40612370

37802212

36762578

40292838

42632931

34291908

35072367

33942643

34393201

29353240

31403550

25452357

27782826

23702975

操作過程：

   (1) 下載下傳AForge.NET類庫，網址：http://code.google.com/p/aforge/downloads/list

   (2) 建立C#空項目GenticTSP。然後在AForge目錄下找到AForge.dll和AForge.Genetic.dll，将其拷貝到TestTSP項目的bin/Debug目錄下。再通過“Add Reference...”将這兩個DLL添加到工程。

   (3) 将31個城市坐标資料儲存為bin/Debug/Data.txt 。

   (4) 添加TSPFitnessFunction.cs，加入如下代碼：

TSPFitnessFunction類 using System;

using AForge.Genetic;

namespace GenticTSP

{

///<summary>

/// Fitness function for TSP task (Travaling Salasman Problem)

///</summary>

publicclass TSPFitnessFunction : IFitnessFunction

{

// map

privateint[,] map =null;

// Constructor

public TSPFitnessFunction(int[,] map)

{

this.map = map;

}

///<summary>

/// Evaluate chromosome - calculates its fitness value

///</summary>

publicdouble Evaluate(IChromosome chromosome)

{

return1/ (PathLength(chromosome) +1);

}

///<summary>

/// Translate genotype to phenotype

///</summary>

publicobject Translate(IChromosome chromosome)

{

return chromosome.ToString();

}

///<summary>

/// Calculate path length represented by the specified chromosome

///</summary>

publicdouble PathLength(IChromosome chromosome)

{

// salesman path

ushort[] path = ((PermutationChromosome)chromosome).Value;

// check path size

if (path.Length != map.GetLength(0))

{

thrownew ArgumentException("Invalid path specified - not all cities are visited");

}

// path length

int prev = path[0];

int curr = path[path.Length -1];

// calculate distance between the last and the first city

double dx = map[curr, 0] - map[prev, 0];

double dy = map[curr, 1] - map[prev, 1];

double pathLength = Math.Sqrt(dx * dx + dy * dy);

// calculate the path length from the first city to the last

for (int i =1, n = path.Length; i < n; i++)

{

// get current city

curr = path[i];

// calculate distance

dx = map[curr, 0] - map[prev, 0];

dy = map[curr, 1] - map[prev, 1];

pathLength += Math.Sqrt(dx * dx + dy * dy);

// put current city as previous

prev = curr;

}

return pathLength;

}

}

}

   (5) 添加GenticTSP.cs，加入如下代碼：

GenticTSP類 using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.IO;

using AForge;

using AForge.Genetic;

namespace GenticTSP

{

class GenticTSP

{

staticvoid Main()

{

StreamReader reader =new StreamReader("Data.txt");

int citiesCount =31; //城市數

int[,] map =newint[citiesCount, 2];

for (int i =0; i < citiesCount; i++)

{

string value = reader.ReadLine();

string[] temp = value.Split('');

map[i, 0] =int.Parse(temp[0]); //讀取城市坐标

map[i, 1] =int.Parse(temp[1]);

}

// create fitness function

TSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

int populationSize = 1000; //種群最大規模

int selectionMethod =0;

// create population

Population population =new Population(populationSize,

new PermutationChromosome(citiesCount),

fitnessFunction,

(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :

(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :

(ISelectionMethod)new RouletteWheelSelection()

);

// iterations

int iter =1;

int iterations =5000; //疊代最大周期

// loop

while (iter < iterations)

{

// run one epoch of genetic algorithm

population.RunEpoch();

// increase current iteration

iter++;

}

System.Console.WriteLine("周遊路徑是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());

System.Console.WriteLine("總路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));

System.Console.Read();

}

}

}

網上據稱這組TSP資料的最好的結果是 15404 ，上面的程式我剛才試了幾次最好一次算出了15402.341，但是最差的時候也跑出了大于16000的結果。

我這還有一個版本，設定種群規模為1000，疊代5000次可以算出15408.508這個結果。源代碼在文章最後可以下載下傳。

總結一下使用AForge.Genetic解決問題的一般步驟：

   (1) 定義适應函數類，需要實作IFitnessFunction接口

   (2) 標明種群規模、使用的選擇算法、染色體種類等參數，建立種群population

   (3)設定疊代的最大次數，使用RunEpoch開始計算

本文源代碼下載下傳

轉載請注明本文位址： 遺傳算法入門