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

我要吃章鱼丸子

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

6 `& l" I; X' p8 }. W3 h

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

5 T/ f- D0 ^: _9 F
一.进化论知识

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

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

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

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

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

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

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

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

- {7 i# |0 [3 a! C0 ?, g8 s8 x
- l# x, h7 M) |- X1 w二.遗传算法思想

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

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

4 M! K- x9 F6 l

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

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

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

[url=][/url]
轮盘赌算法/*
* 按设定的概率，随机选中一个个体
8 t& Q% G# A/ N9 k* ?& l* P表示第i个个体被选中的概率
4 r! A3 g7 ^( J, p*/
' A3 d! E: Y9 @  oint RWS()
" a" o% F( D) `4 A' r1 h{
m =0;
r =Random(0,1); //r为0至1的随机数
2 y7 a5 o; X9 b' O, K; Ifor(i=1;i<=N; i++)
$ J1 c, E/ H6 s( J{
& L0 j, v3 q8 {5 m' h4 z/* 产生的随机数在m~m+P间则认为选中了i
) R. k0 L0 |8 f8 s* 因此i被选中的概率是P
0 b; \; Z; l. d- G0 ]*/
$ y7 q/ w2 C( k# B" a& \+ [6 @5 A4 _m = m + P;
1 p5 X$ C" ~$ Jif(r<=m) return i;
! ]# |  O: f) e2 N}
}
) E: |3 {, K  C
# P  `2 j5 b. L$ }$ [7 ^. t[url=][/url]
9 v9 E) v! v6 w3 d6 m! \

8 r4 z2 Q1 Y4 s8 D0 [

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

( v& D8 |$ H0 E$ z  B

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

* Y+ u# M. v* E, N8 J; D
三.基本遗传算法的伪代码

1 o8 W$ Y: ~, }! v9 f[url=][/url]
' j/ ~9 o0 n: C, v) X基本遗传算法伪代码/*
% j! o4 e- m6 f* Pc：交叉发生的概率
* Pm：变异发生的概率
8 @8 o+ B, e. }& O# d, y/ r, G* M：种群规模
* G：终止进化的代数
* L' v5 i5 V' ?0 ?4 c: N* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
/ c7 k* [/ w+ |, P' A  [5 Y*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
5 R( N! A) Y$ h% Y5 N* v
/ i  I( Y& v0 T; ?$ s3 V0 g& Hdo
{
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
# m3 t3 N! O, G9 X. t/ Q$ E$ h　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
# l$ L9 ?% q1 v　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
, O# P$ l8 c% v1 }+ w% `　　　　}
6 g: w$ x7 u7 T* p, M  {　　　　if ( random ( 0 , 1 ) < Pm )
- `, u. f/ f. P& h　　　　{
. J- s$ g, D- r* |9 H4 Z　　　　　　对2个个体按变异概率Pm执行变异操作
3 k5 S& y( ]% o9 N: i% C　　　　}
' y" q6 M2 A2 X% W" S" c将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


2 T& u7 E! y, n8 T[url=][/url]

7 w; w+ R$ \9 X- O
5 P2 [: ^+ u- a# A# t
6 {4 x1 t5 G$ l1 ^6 y+ c5 f' g, n# _1 u四.基本遗传算法优化

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

　　精英主义(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的类结构如下：

) w; Z" O7 S' s, Q/ m# M$ e

图1. AForge.Genetic的类图

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

) p* F; d  ?8 Y1 W! d" o; A' r8 z[url=][/url]
( I4 u. J9 Z/ l7 a3 K5 r13042312
( x% ?( u' f- G( Y8 Y8 K$ S36391315
41772244
! U8 W; @& l5 @37121399
34881535
0 N7 o9 G: R2 q" ]2 Q/ j+ ?33261556
( J( B9 B. M% q; G% X2 S% p. P32381229
2 m( S; j5 i$ \5 C' y41961004
4312790
' A9 \% e$ ^; p' w" w: T) \4386570
" Y+ @! C9 M8 b6 S30071970
* {9 v4 j+ t  k  @( H/ e25621756
27881491
23811676
( `9 A; @  f, Q; n1332695
- e, `, n; |) r" x: d37151678
39182179
+ Q8 x3 \7 }( m/ i- Z9 c40612370
37802212
36762578
40292838
42632931
34291908
35072367
33942643
5 @$ [# m0 R3 o) \# m' p% V34393201
) ?" g* J8 d2 S& ^2 O: [/ A29353240
8 u$ z, `/ H: A4 Z  T/ U8 T31403550
. r. i$ E  w& E2 |/ Y25452357
* u; `* W1 s$ ]# X9 Q$ o* C27782826
" `5 m3 S, u8 q$ o6 F23702975
& X: J( p  G: H4 [) Z) ~8 P[url=][/url]
. o* C( y7 k+ Z& n- t' W# G: o
( h: \* a6 M$ {9 q4 |) N& D+ [


# J; G1 |* M/ x, \+ X4 m3 D

操作过程：

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

, Y* l7 _/ R. f4 E; k; c* M[url=][/url]
% O) S' h* r$ \: X5 b* B; G! pTSPFitnessFunction类using System;
using AForge.Genetic;
% Q8 Z1 n9 i# x9 ]
! C3 h$ @" K8 i( b  qnamespace GenticTSP
5 D( m$ ^  ~' O7 b' H{
///<summary>
/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
7 o3 S5 m7 S- f5 Bpublicclass TSPFitnessFunction : IFitnessFunction
3 G. T% j( w  R. S' y0 O4 m  l7 Z{
! X6 H. d2 `/ p' }3 L// map
privateint[,] map =null;
- g, }9 F8 r' g$ r, c
// Constructor
0 W$ [, b4 s! \7 w! c' ~" Ppublic TSPFitnessFunction(int[,] map)
{
this.map = map;
# m# ]8 `8 J7 ?4 V: c}

% `" T' F0 C2 P/ r: j, {- i. y///<summary>
" h3 N7 p% P1 U# e/ k/// Evaluate chromosome - calculates its fitness value
! r: n) Q) i; \8 a# k; g///</summary>
4 g1 J( R1 R" }5 O+ Gpublicdouble Evaluate(IChromosome chromosome)
. ?3 V# d& V' k- A3 Q{
% J- q: f3 {$ o1 Q7 k$ u: ?4 Oreturn1/ (PathLength(chromosome) +1);
}
/ n2 U, p0 b) c1 j3 O1 x* C3 x
///<summary>
/// Translate genotype to phenotype
+ u- H' G5 q' t) c% o& H& L///</summary>
publicobject Translate(IChromosome chromosome)
{
return chromosome.ToString();
! H2 z7 o  S9 b* V, r}

9 f4 a& |; [+ j7 u9 T///<summary>
4 Z0 b8 x& w0 Z. [/// Calculate path length represented by the specified chromosome
; F, T6 F& Y; i6 B: g* S% }9 ?///</summary>
publicdouble PathLength(IChromosome chromosome)
2 H& M. d. @+ K0 U{
4 X: Z0 A0 a' B9 G) ]0 U// salesman path
ushort[] path = ((PermutationChromosome)chromosome).Value;
5 w- n% O% f) x- H3 X
! M- \8 K6 k' T$ A7 w// check path size
if (path.Length != map.GetLength(0))
2 F3 k: \( P! `8 d9 }{
# w* P# T% I' _. ^% |thrownew ArgumentException("Invalid path specified - not all cities are visited");
}
: K5 f) Y! A4 D9 p8 b% h5 s  G% e
// path length
int prev = path[0];
7 E, I' V) j1 n# Q8 F2 B4 U+ @* K# oint curr = path[path.Length -1];
: W; h2 g# i* G; W
// calculate distance between the last and the first city
. Z9 i, M7 n# L7 N7 f( Kdouble dx = map[curr, 0] - map[prev, 0];
& O1 u; i& ^7 I* rdouble dy = map[curr, 1] - map[prev, 1];
( r7 @' ^' @/ K6 V* t: `double pathLength = Math.Sqrt(dx * dx + dy * dy);
  U; x! \& K* u; V0 z
// calculate the path length from the first city to the last
: }$ c- D! i- g+ R$ h8 Jfor (int i =1, n = path.Length; i < n; i++)
0 t/ P* U" x; z" |9 z9 g3 W; ^{
" }: ^" v' \* u4 N1 z8 \, N& G: G// get current city
curr = path;
! Q4 A5 P8 p3 D3 [
// calculate distance
dx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
, [$ s& G3 F* H' o. R; ?) ^pathLength += Math.Sqrt(dx * dx + dy * dy);
2 t8 C, R3 m+ `. N! r/ e" Y& B3 S
/ Y. Q# [8 \0 ^" X' s+ |: g// put current city as previous
prev = curr;
}
# a% j- X9 W8 T6 e) G
" n* I: v& {& g6 x6 F- _, sreturn pathLength;
}
! h& S2 @# O8 ?9 u}
6 ^6 _4 h( T3 g}
% q$ q  C) o$ `! p2 H/ l
' j4 N/ }2 u8 f: \3 q, W3 R+ R& L
+ j' b5 _! l( ~. v; C' X[url=][/url]
$ i; |2 B/ W7 `) ?8 ?7 y# f6 t


. v7 d7 |/ Z, [+ ^8 j7 l. j6 E

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

0 o* j2 D, ?, E6 J7 }( _$ d( n$ g' Z[url=][/url]
GenticTSP类using System;
) n* k, d  J, w& |2 Y+ o- G8 ^1 pusing System.Collections.Generic;
using System.Linq;
using System.Text;
+ Y+ r: Y* ?6 z7 O2 l' Y5 @1 |" W* susing System.IO;

using AForge;
9 A8 D, o; R6 Y, D( M. dusing AForge.Genetic;
; z9 a5 ^! S  K; N4 A) ^

namespace GenticTSP
{
class GenticTSP
; I. {5 z: E" Y$ N8 W3 S8 Z! p{
8 k2 g2 }+ R* G9 o6 w' z, g
; q: t# t% u5 i6 l& Nstaticvoid Main()
: l, v3 i0 U- ^- {# [{
' P) r0 P, T' m, ]2 tStreamReader reader =new StreamReader("Data.txt");
, q' s! f* Z) P' k
% v9 \! s- b" ~1 {6 Rint citiesCount =31; //城市数

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

. {- Q) X' t) R6 cfor (int i =0; i < citiesCount; i++)
{
string value = reader.ReadLine();
4 q! f5 P  b0 R% Mstring[] temp = value.Split('');
3 ?& v  R: E& R, Omap[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
}
+ j; V! }' M  d- t$ ^. @
// create fitness function
& n: L% e4 Z  t& E5 W; o' Q1 f: ATSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);
0 ^! [8 p1 o- d6 w2 S- c$ Q
int populationSize = 1000; //种群最大规模
) ]. C  W+ Q' _* p  e4 P6 }
& j# y+ o, u9 l# H$ h8 B! ?: V4 |/*
* ~: t  m& z7 Z6 m5 m8 i/ {, j* 0：EliteSelection算法
* 1：RankSelection算法
* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;

7 x2 r1 Y1 T6 u$ z1 x1 z! i// create population
+ R( z% k5 W# [# P0 o: XPopulation population =new Population(populationSize,
- I+ ~# P8 Z8 o& mnew PermutationChromosome(citiesCount),
fitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
. M; d9 P2 O9 Y(ISelectionMethod)new RouletteWheelSelection()
);

& e, X6 m3 l" B4 G! p+ B// iterations
7 v* d# J! w) k; D  E( uint iter =1;
. e3 ~+ V! L. p' o$ Vint iterations =5000; //迭代最大周期

// loop
while (iter < iterations)
& o6 J$ r' c& o. u5 w{
// run one epoch of genetic algorithm
population.RunEpoch();
# f1 v$ `' g8 v( Y
! \' U: t1 j6 m' a. A// increase current iteration
iter++;
) S$ t' [, s8 _}

  Q+ h# {" `  q" g$ I# p8 x# \System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
) I/ z5 r! d" [. lSystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();
. O1 I6 D0 L+ S8 i- t) {4 R# s
: n/ @) p) v8 |6 j% y* ?1 g}
7 y, d' m3 F( d9 T6 k! Y7 F}
}
+ V0 ^6 j8 T: R/ x0 y2 G

[url=][/url]
0 [8 Z* W1 M7 n' }+ ^  o0 c



; o4 Y$ B3 S7 t

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

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

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

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

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

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

2 S1 E, V. ~% j9 i* v
3 z) W+ e7 ?: C7 O; X( Z% E