【转】优化算法入门系列文章目录（更新中）

我要吃章鱼丸子

遗传算法入门Posted on 2010-12-23 13:12 苍梧 阅读(103275) 评论(39) 编辑 收藏

2 B/ l3 H# q6 C, J  o

优化算法入门系列文章目录（更新中）：

　　1. 模拟退火算法

　　2. 遗传算法

原文http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

　　遗传算法 ( GA , Genetic Algorithm ) ，也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。

! h; N0 V$ b  G$ [( R# a
一.进化论知识

　　作为遗传算法生物背景的介绍，下面内容了解即可：

　　种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。

　　个体：组成种群的单个生物。

　　基因 ( Gene ) ：一个遗传因子。

　　染色体 ( Chromosome ) ：包含一组的基因。

　　生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。

　　遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。

　　简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变 ( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。

- v" b. T5 k1 n
2 Y9 v; r; ^4 y7 @+ U, s0 \二.遗传算法思想

　　借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

　　举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取） ；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。

　　编码：需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问题的解是整数，那么可以将其编码成二进制位数组的形式。将0-1字符串作为0-1背包问题的解就属于二进制编码。

" S, w2 _+ h0 s' ]7 z( \, s

　　遗传算法有3个最基本的操作：选择，交叉，变异。

　　选择：选择一些染色体来产生下一代。一种常用的选择策略是 “比例选择”，也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M，那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。比例选择实现算法就是所谓的“轮盘赌算法”( Roulette Wheel Selection ) ，轮盘赌算法的一个简单的实现如下：

4 J) H  A7 j4 D& d9 Y. g# q1 B, c$ t[url=][/url]
* H9 j$ ^9 t: d) k$ ^+ m  K$ p轮盘赌算法/*
- m+ q% }: C( ^4 N* 按设定的概率，随机选中一个个体
* P表示第i个个体被选中的概率
  X& w0 D2 m) K3 _' X  T*/
int RWS()
0 g1 R5 }9 Z/ L- H7 T. h{
m =0;
r =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
{
" @4 D! @( v1 v, O" V; c$ R/* 产生的随机数在m~m+P间则认为选中了i
3 ^5 U' U# J% U8 }* 因此i被选中的概率是P
*/
0 x3 D: `7 S0 Tm = m + P;
if(r<=m) return i;
: {% B( E  b# n$ h" L0 d}
}
6 g+ c! v& Q. x; ]
[url=][/url]
4 @, c! Z* ~  Y( ~! i0 _

7 K9 Q8 @: I& _8 @

交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。例如：

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

染色体交叉是以一定的概率发生的，这个概率记为Pc 。

5 R# x, M4 ~- y2 t

变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。变异发生的概率记为Pm 。例如：

变异前：

000001110000000010000

变异后：

000001110000100010000

适应度函数 ( Fitness Function )：用于评价某个染色体的适应度，用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如：0-1背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。

8 ?: \$ `% G& k* i0 q1 p三.基本遗传算法的伪代码
* T  s" {1 J1 n6 k' M; K- ~
: U! Q0 F$ z4 V0 j" o! \[url=][/url]
基本遗传算法伪代码/*
. e0 z4 s$ q2 z) `7 e9 y" Y" U% g* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
- [. U: r, d' ?( _- O4 s
do
" F7 ^7 h" J$ Z$ I( I{
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
& v8 W# t) Q' a' [& |) ?　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
8 ^1 N- D( \+ ^/ \6 W　　　　　　对2个个体按交叉概率Pc执行交叉操作
8 K* ]& Q9 [3 v8 t  w+ T　　　　}
, i% p$ U- m" U# E　　　　if ( random ( 0 , 1 ) < Pm )
　　　　{
& z( }! V+ Z7 [0 ^8 i) R) J$ g　　　　　　对2个个体按变异概率Pm执行变异操作
* z- y( k# D& N  h6 O　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
% y/ L* [4 P1 j0 G用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


[url=][/url]
: W& t& ^' m: b) `& z( }2 f7 g! e: g

2 s, B$ q# k9 ]8 d) q. i2 n
四.基本遗传算法优化

　　下面的方法可优化遗传算法的性能。

　　精英主义(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个省会城市的坐标:

3 e- t9 X% ^  T' N" U! M) l4 C[url=][/url]
13042312
- n9 y% h* [( C3 _36391315
41772244
37121399
) w( f- `1 Q+ g3 M( t/ F5 r34881535
1 b( o% q$ W8 R! y* ?+ }9 K8 R% Y33261556
32381229
41961004
; ~+ I# Q( S" N9 e$ j4312790
8 U3 M# G9 [/ N2 Q7 ?1 B4386570
& N5 S- f& @- N3 T* I4 N2 B- ~30071970
$ C( z; P3 Z9 C25621756
7 d) V! o) g: w  k/ V# Z+ G, {27881491
23811676
1332695
+ [. \0 ^9 \, {/ T$ a* o6 A: z37151678
  c; i- m; y7 H# _39182179
6 {$ D. m+ C4 Y; W40612370
) k$ \' y0 o7 V" K' r- A37802212
36762578
  j: T! V1 U. k+ x40292838
4 A+ z# V8 x' }; M6 p9 f) e42632931
34291908
) x: L' _3 t2 Y9 X; S+ B& Y35072367
7 h+ g: n( m9 `$ M/ k! |# r33942643
34393201
5 {  S0 N8 b2 x5 Q5 d5 P* K: o! k4 J; z# }29353240
31403550
25452357
27782826
23702975
* H$ D. z0 B# z- c[url=][/url]


+ _# }! u1 i& N. b3 C

2 r1 R6 ]* @1 a9 ?/ h1 Y

操作过程：

   (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，加入如下代码：

[url=][/url]
2 `7 H; n1 a$ m0 o9 \TSPFitnessFunction类using System;
using AForge.Genetic;
- m) ~1 J( K9 [$ |: K3 R( Q- h
% E- b) ~! t. O: vnamespace GenticTSP
{
7 ~4 X8 J* [2 ~* p///<summary>
/// Fitness function for TSP task (Travaling Salasman Problem)
! I! V$ g: [$ [7 o///</summary>
publicclass TSPFitnessFunction : IFitnessFunction
0 y4 ~" ?1 i4 ?4 E6 H{
// map
privateint[,] map =null;

; m  Y* |# O3 e) P! Y; {% K. e/ q4 A3 _// Constructor
! P% g6 d" l' Q+ Fpublic TSPFitnessFunction(int[,] map)
{
this.map = map;
3 Q+ X5 Z& j% r$ i) d7 ~( J}

///<summary>
  Y6 V! j  _$ F: ]) I/ t; W( H0 u/// Evaluate chromosome - calculates its fitness value
///</summary>
- ?! w2 K7 G4 Y6 Q3 Upublicdouble Evaluate(IChromosome chromosome)
( P, u; `1 t8 D# n1 c( j& e- e{
9 i2 m2 l$ X# r" Y6 Sreturn1/ (PathLength(chromosome) +1);
}

# Z) s2 i& T; z5 S///<summary>
/// Translate genotype to phenotype
///</summary>
6 p3 f6 @3 E$ d& |+ d+ lpublicobject Translate(IChromosome chromosome)
. x6 }( O8 t# w" [$ t: T/ H{
return chromosome.ToString();
}

- w9 y, T7 K% o( O7 ~///<summary>
/// Calculate path length represented by the specified chromosome
/ e$ d# r. `7 }///</summary>
! v% E& Z* {& `. r2 i1 D% Fpublicdouble PathLength(IChromosome chromosome)
9 i! K& j) p  ?- P" B{
// salesman path
+ W. I: G9 M. a8 ]2 Qushort[] path = ((PermutationChromosome)chromosome).Value;

// check path size
if (path.Length != map.GetLength(0))
7 z0 E3 T. W: |" G5 Y& Q{
thrownew ArgumentException("Invalid path specified - not all cities are visited");
# |) r% T8 i5 h; }}

// 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];
* `/ Y. x5 ?$ e* L8 Idouble dy = map[curr, 1] - map[prev, 1];
$ p6 K  Y7 u) S# D9 n; ndouble pathLength = Math.Sqrt(dx * dx + dy * dy);

6 r3 t8 t( _7 R# N// calculate the path length from the first city to the last
for (int i =1, n = path.Length; i < n; i++)
9 ~/ F1 B3 w" J0 {{
// get current city
curr = path;
1 H5 b6 \7 h$ ^" s! l7 G$ b  F
- C2 J' }& [5 C8 ~' W// calculate distance
( g4 q; j2 l+ g! xdx = map[curr, 0] - map[prev, 0];
; B( X. S9 ]) I9 w1 Cdy = map[curr, 1] - map[prev, 1];
3 g; p. ?  d# y: t6 o: a! FpathLength += Math.Sqrt(dx * dx + dy * dy);
" e* a5 U4 H. v; ?* q
// put current city as previous
1 q  t1 P7 K+ j, v0 M" Nprev = curr;
# K5 O1 W' o" v  \) c+ P6 I}

+ ]- S1 `6 j3 |' {- l; Treturn pathLength;
/ p$ I8 u# I7 ^) s5 B- P2 x( I}
- o* z( b( |% `}
( C/ A3 l: W# v}

0 z$ l5 |6 [+ m3 g1 l( Q/ f
9 I+ Q% w* C8 C. w+ b: G[url=][/url]


# s' j( r4 D+ g& `9 P; N9 ~* R( @

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

[url=][/url]
GenticTSP类using System;
) f' y1 k- X2 e- H& z) musing System.Collections.Generic;
, S% H; ^) F; l* husing System.Linq;
$ a* o& d( Z, H  `, x1 u/ Busing System.Text;
+ [8 ~2 B/ |9 n) r" r( p/ ]( dusing System.IO;

! ~( m* l+ v! w$ |* Musing AForge;
: s' ?8 z0 m7 W5 x, f8 ]* e2 Jusing AForge.Genetic;

0 Z+ `( Y6 c) k0 f
! S2 p2 u: [9 d" xnamespace GenticTSP
( m( [# e1 Z2 n6 N/ |; S{
class GenticTSP
% U' x( c7 z7 T% W* `4 n2 `{
( [/ n4 `2 W/ |9 H, z  x7 A
staticvoid Main()
{
6 ]- g3 k' }4 d  N5 i# ]  |StreamReader reader =new StreamReader("Data.txt");
0 m* T! _& w- c, n2 ]8 C2 p5 E" j  Z
int citiesCount =31; //城市数
& B, y- v+ g3 R) ~% Y" Y* f3 b
int[,] map =newint[citiesCount, 2];

) V( C' U0 X, b( a5 |/ K% q/ ^+ Rfor (int i =0; i < citiesCount; i++)
{
6 z! h/ t2 f8 E/ Q9 }/ I' W# W( `string value = reader.ReadLine();
string[] temp = value.Split('');
! t( s/ B# T2 b, amap[i, 0] =int.Parse(temp[0]); //读取城市坐标
( f9 U8 k# @! [8 U* B- F2 C- g9 Umap[i, 1] =int.Parse(temp[1]);
}
% S5 K4 M6 ]  n7 e) J7 V  Q7 @
9 i" M/ S& @' \// create fitness function
TSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

- C. B/ G" y; Q& n# tint populationSize = 1000; //种群最大规模

: l1 c: Y0 C1 c  F/*
* 0：EliteSelection算法
* 1：RankSelection算法
: e- b  o: [- W/ z7 l* 其他：RouletteWheelSelection 算法
, B. l- U' a0 {3 n- [6 g* */
int selectionMethod =0;

// create population
Population population =new Population(populationSize,
$ G, H" k* j" _5 P( t$ N# unew PermutationChromosome(citiesCount),
fitnessFunction,
5 ?- [) Q7 g! c$ H2 b7 R" r. e(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
2 S' H' l* \7 x8 t! P5 r# z/ t- {(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
  \% F/ B$ C5 g4 q3 A(ISelectionMethod)new RouletteWheelSelection()
);

// iterations
# G# T7 v3 f/ B5 P9 N9 `- qint iter =1;
" w) R9 f; N7 U1 G( B, Mint iterations =5000; //迭代最大周期

& C& ~  T  I- q) `2 u2 J. g// loop
while (iter < iterations)
{
// run one epoch of genetic algorithm
population.RunEpoch();
3 @. P. C9 B  w& i
// increase current iteration
4 {7 A+ l& c# G& qiter++;
}
1 a3 e% I/ l1 h; g
System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
6 @* `, Y( c% G4 tSystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
; W  x: C1 u$ h5 Q3 U# tSystem.Console.Read();

}
}
}

$ [# f( h- B/ V* S! @. N
[url=][/url]



. J( j, c3 Z9 r9 m

网上据称这组TSP数据的最好的结果是 15404 ，上面的程序我刚才试了几次最好一次算出了15402.341，但是最差的时候也跑出了大于16000的结果。

我这还有一个版本，设置种群规模为1000，迭代5000次可以算出15408.508这个结果。源代码在文章最后可以下载。

" J. i# ~: C. P7 ^) w

总结一下使用AForge.Genetic解决问题的一般步骤：

   (1) 定义适应函数类，需要实现IFitnessFunction接口

   (2) 选定种群规模、使用的选择算法、染色体种类等参数，创建种群population

   (3)设定迭代的最大次数，使用RunEpoch开始计算

$ Q, @5 |- r" M- A1 U& W1 j/ M- I' s/ {