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

我要吃章鱼丸子

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

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

一.进化论知识

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

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

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

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

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

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

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

' ?% F  n2 o! G7 Y2 k4 |+ W$ n

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

5 y+ R4 {: R4 s$ j  X5 l* |* \: I二.遗传算法思想

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

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

0 A. E$ W! `; P2 j

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

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

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

[url=][/url]
  s& U' M. D4 E) b/ S轮盘赌算法/*
* 按设定的概率，随机选中一个个体
  ?9 K% A$ [- u1 q% g3 d* P表示第i个个体被选中的概率
4 A4 g5 @- W6 b2 J( G0 b*/
int RWS()
{
1 U3 e# b# ]- s5 Q' `" \m =0;
, q# m+ b- m7 C  z  r, Kr =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
{
4 e3 x* [2 ^; ?/* 产生的随机数在m~m+P间则认为选中了i
* 因此i被选中的概率是P
3 F; w8 c4 r9 I& i. R% F3 X*/
) \* b& ^5 U. @: Fm = m + P;
' J( l- o2 F* B5 ]0 w6 [3 oif(r<=m) return i;
}
}
4 L) n3 z3 |1 U$ S# ]
[url=][/url]


, V% ^0 ?/ R  f

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

9 B8 \& R4 @' X

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

# B/ l: }2 u; x# r$ N) t" ?# K$ f1 W
三.基本遗传算法的伪代码
3 Z8 r( i) r  k  P
1 @3 j" p: t! f+ J: U[url=][/url]
2 x- w6 ^  J- N. u5 p( i基本遗传算法伪代码/*
" t. g- G2 ?  w2 ~& X$ F3 u% o* Z* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
& R' b$ H! z9 L9 i$ K3 ]$ S* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop

do
{
3 d! F% G+ N$ E5 }0 V' z/ M　　计算种群Pop中每一个体的适应度F(i)。
+ f8 [. U' J) c, {' I9 V' _　　初始化空种群newPop
　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
" y% j8 R( a0 e, ^! N. \4 ?, I( W　　　　if ( random ( 0 , 1 ) < Pc )
3 `# I7 ]0 k6 P) r' [8 n7 S3 ^% g　　　　{
7 l4 {/ {# ?' _" \4 J+ O　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
　　　　if ( random ( 0 , 1 ) < Pm )
$ ]3 o& }1 k2 P# F　　　　{
' j; J1 H' R9 t, u) H　　　　　　对2个个体按变异概率Pm执行变异操作
! V8 p  T1 `2 f, x/ z8 O( x) i* n　　　　}
将2个新个体加入种群newPop中
  }* A8 C: i& I0 L1 ]} until ( M个子代被创建 )
- l/ m3 ]+ ]  ^5 j用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )
/ q" P/ h6 ~4 l8 T
) B1 B. z; Q$ O4 i
[url=][/url]



1 M5 m5 I& G* P' J; j- A# n' f. c  c四.基本遗传算法优化

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

　　精英主义(Elitist Strategy)选择：是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。

　　插入操作：可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。

五. 使用AForge.Genetic解决TSP问题

　　AForge.NET是一个C#实现的面向人工智能、计算机视觉等领域的开源架构。AForge.NET中包含有一个遗传算法的类库。

: Y* V, e- J1 R6 f3 Y

　　AForge.NET主页：http://www.aforgenet.com/

　　AForge.NET代码下载：http://code.google.com/p/aforge/

　　介绍一下AForge的遗传算法用法吧。AForge.Genetic的类结构如下：

: ?: [0 |4 ~! N. m+ ]

图1. AForge.Genetic的类图

- s' q5 K$ r2 d& i; L: O
0 p( V" r, K5 I3 o

   下面用AForge.Genetic写个解决TSP问题的最简单实例。测试数据集采用网上流传的中国31个省会城市的坐标:

  \+ b1 d; l, p) r& ^[url=][/url]
2 T  j% @" c- ~. t& y# D13042312
36391315
. b7 g3 @2 D# q* X& U! o" f41772244
37121399
- T! K$ A5 e! j* c) P6 S34881535
& e, _) Y8 Q' o6 g8 f33261556
32381229
41961004
$ d- y: G, }" n) ~! T4312790
4386570
- S1 R! x/ B: X0 |- `3 h! E30071970
25621756
27881491
  f$ s9 o& s# {9 H8 t- s" p23811676
1332695
37151678
; N$ |: L" P1 }$ u! n) h7 C# d39182179
$ R3 {6 X1 G- `  S+ O40612370
37802212
) Z: ?; x0 L6 n7 ?8 d" w36762578
40292838
42632931
8 r4 H% N7 S  F. L% d0 {- }34291908
" g0 @7 S; e" ?/ W$ D. n35072367
33942643
34393201
9 d$ E! O: }6 S29353240
31403550
25452357
27782826
0 m" \6 ?0 h5 z4 ]7 t( S5 T23702975
[url=][/url]



! X) |6 E( O8 ^' I- ^' P

操作过程：

   (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]
TSPFitnessFunction类using System;
. Z9 w9 v' f; Wusing AForge.Genetic;

) h& e9 Z, [. }+ S3 M/ Inamespace GenticTSP
! d5 G! G3 c* T{
9 z5 \; P( \7 D! U# d! o///<summary>
/ o: b6 b7 j& Y. r; t6 G5 k1 b/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
" x3 X' \, ?, ^' j2 Ppublicclass TSPFitnessFunction : IFitnessFunction
{
' J& s! ?9 j. n// map
% S  B  G3 G" z% ~9 ?2 f$ Kprivateint[,] map =null;
9 x" x; v( K/ z' P* o
// Constructor
public TSPFitnessFunction(int[,] map)
{
4 E; n+ e5 E  X0 n, x9 Xthis.map = map;
}
: F& [8 H% m8 M1 p
///<summary>
4 l3 L8 C; d/ d" p. M/// Evaluate chromosome - calculates its fitness value
; Q! B4 E0 o8 \///</summary>
$ l) T$ r) D' _; B/ v! q5 ?publicdouble Evaluate(IChromosome chromosome)
{
# h+ H3 p" L/ f# }; B7 }4 x9 G; }return1/ (PathLength(chromosome) +1);
}

///<summary>
% L# a6 f3 a. Y/ I/// Translate genotype to phenotype
///</summary>
publicobject Translate(IChromosome chromosome)
{
return chromosome.ToString();
0 C4 U% G9 l6 v) Q. Z6 m4 D. k}
; a; o" R, Q! J0 U6 x
5 F2 Q: F$ T# F  \3 n1 N) o& R, @///<summary>
/// Calculate path length represented by the specified chromosome
7 J) L. `- P! T3 z2 W7 }///</summary>
publicdouble PathLength(IChromosome chromosome)
{
; J3 `- W# I" a, A7 R) j. Z// salesman path
" H! ~: P. R, Xushort[] path = ((PermutationChromosome)chromosome).Value;

: n4 x5 p4 H0 T4 ~% `2 J8 N// check path size
! X4 Q5 q% Z$ @4 H, b4 `if (path.Length != map.GetLength(0))
{
0 V4 S4 d4 G1 A1 [thrownew ArgumentException("Invalid path specified - not all cities are visited");
8 ^- x1 e5 u  s}

# o, L: {4 F$ D5 |6 G' ~! u' B// path length
- o! G+ `- z1 \9 Y+ V0 s* c4 H" pint prev = path[0];
int curr = path[path.Length -1];
4 B! p& M4 k  I" V' z; q
// calculate distance between the last and the first city
' _; a7 L& H3 I+ d, s$ {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++)
4 ?  }( v) v1 o* ^( k$ V6 v. i{
// get current city
* ]7 g# w: s- J$ `" }0 \/ j+ a- Bcurr = path;

1 Q6 C% m! P' ]// calculate distance
; L) d  G' d8 Ydx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
+ {/ J, |2 X" G  D! zpathLength += Math.Sqrt(dx * dx + dy * dy);

// put current city as previous
2 n- a2 b1 _# P- {/ R- ~& Bprev = curr;
) S% y) `% B. q5 ?}

6 a8 l& p+ B0 ]8 G/ A, F5 N! wreturn pathLength;
/ T0 w0 V8 A5 A4 j% F' T0 o. {}
$ X+ G, M+ l, s  I, h% T, r" K}
& R1 K  f6 }3 ^}
6 ?" E! r, c& X5 O" f& c% n, s
1 ~7 [" h0 ]( Z( r8 O9 y
4 b# T# i( U: H4 F/ V7 h[url=][/url]
: A- r' `( {  b$ [2 r% W5 ~( @
! w3 w+ I- W& s. O8 ~
$ A  w6 ~" a5 L9 i. k- Z; \

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

" U  m$ c2 g1 O/ s* {9 r[url=][/url]
GenticTSP类using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
' X+ y7 ^! W/ D+ n$ Q! l% v
" L6 g, b# {) `8 `' c2 N$ G5 B' jusing AForge;
using AForge.Genetic;
  m* ]* T6 ?6 ^) g5 W

; a! B$ S  @3 y! [namespace GenticTSP
" z. O9 ~. J2 ]# p) y. y{
class GenticTSP
{
# H2 ]6 j9 X0 ~/ k" e2 A
staticvoid Main()
3 O# a3 j! P' c/ y! ^# ^8 v! ~{
+ M8 c  f8 C1 u: Z9 gStreamReader reader =new StreamReader("Data.txt");
) j9 J- F1 I! c2 W) S
- `- {* m0 F3 y2 O) ]! B, r3 c) |& {int citiesCount =31; //城市数

8 F6 Z, T! h) \9 r0 |int[,] map =newint[citiesCount, 2];

5 |) r! C/ a5 O% }1 N' ?for (int i =0; i < citiesCount; i++)
" Y: {4 P/ h% u& r8 \: \{
string value = reader.ReadLine();
5 F" k; V0 {' ]/ d% `string[] temp = value.Split('');
: b2 n$ P( k3 a! e( L) omap[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
}
0 I2 U5 w; Y6 @$ P
; M( s2 a% r8 R# j0 d; s+ ?5 J3 F4 ?// create fitness function
" T) `! E; f* d+ OTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

, N/ Z5 M* \4 L8 {* _8 Z6 e* S8 eint populationSize = 1000; //种群最大规模

/*
* 0：EliteSelection算法
* 1：RankSelection算法
* 其他：RouletteWheelSelection 算法
+ G" f! }. H2 U$ }. V* */
int selectionMethod =0;

// create population
Population population =new Population(populationSize,
  h% C# c/ t5 z' a% B9 Enew PermutationChromosome(citiesCount),
; h: E2 n( {- y. Y- X1 KfitnessFunction,
% ], S' g9 x% F, R% h; D(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
& {+ h- {6 z: {5 t( ~(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
- c  j* z# Q$ T% |: M* M(ISelectionMethod)new RouletteWheelSelection()
. o0 e& D1 Y* j7 T! I);
6 z8 ?' f' i. ~' K4 r
// iterations
int iter =1;
int iterations =5000; //迭代最大周期

. @  Q. n. {* a$ A2 }// loop
while (iter < iterations)
; N$ j/ z/ N$ O- P, `{
// run one epoch of genetic algorithm
  p/ q5 V$ m' p9 z1 f/ V" w* Mpopulation.RunEpoch();

& P, ^1 O1 @0 [3 |7 @$ W$ _0 Q// increase current iteration
! d- w; }; I* E  k# Xiter++;
}

# y6 L4 s. c+ R; ZSystem.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
. b! T3 K- W& USystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();
* u5 ^# X( w6 f
}
7 h9 X& m) p: }}
}
4 ]5 X! G; T% b! k/ G2 Z1 K/ F0 I
9 r4 t0 B/ r& B# }
[url=][/url]
/ c  Z  O% W7 v


* A7 ~4 z( m2 ~
8 F1 ~3 U5 [/ c: V1 O9 C+ d2 m$ i* L

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

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

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

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

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

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

& U3 X, A. ?* S* u8 y; `