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

我要吃章鱼丸子

遗传算法入门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 ) ，也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。

! g7 x3 `, [& g. z: R. k4 _
, C( M8 {7 k0 g* r一.进化论知识

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

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

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

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

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

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

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

+ F# b' ?- x' J% g

　　简单说来就是：繁殖过程，会发生基因交叉( 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 ) ，轮盘赌算法的一个简单的实现如下：

4 W( z3 h8 o$ [: m$ L4 G4 v[url=][/url]
轮盘赌算法/*
* 按设定的概率，随机选中一个个体
. W! i; s$ X' n+ x- C* P表示第i个个体被选中的概率
3 N: n+ H2 _( Z5 Y' L( r*/
2 m2 q! `2 k+ U" [# ?' ]int RWS()
; n4 ]1 x5 S4 Z" L% \) K4 \1 S  ]{
m =0;
; P! Q7 A, T2 c# g$ N: O9 [r =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
. ^# v' q' [. Y4 ?( X{
. r% H+ v9 z. n: e/* 产生的随机数在m~m+P间则认为选中了i
( A. Z' X. z+ i- k& r9 ?, L+ F* 因此i被选中的概率是P
*/
$ u; s7 ^" T! o8 M1 O* \5 mm = m + P;
if(r<=m) return i;
}
}

[url=][/url]
0 @* b7 h# `2 q% }; G
* |3 @, r! K/ I6 a' _1 ?. q

交叉(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背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。

4 H. K' k; c: ^" ~
三.基本遗传算法的伪代码

[url=][/url]
基本遗传算法伪代码/*
8 b8 t/ v! L5 p8 S  E* Pc：交叉发生的概率
! G6 h8 M* g: Y+ d3 y- E9 V* y3 V* Pm：变异发生的概率
* M：种群规模
4 }* i: z4 ?( g9 d$ a) U* G：终止进化的代数
0 m9 n3 I( Y. W/ m, Q  e- @* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop

  H8 V# p0 b6 X# ]& v3 u! t5 t  _% ydo
{
3 B( ~  J' b# b: t$ V3 r　　计算种群Pop中每一个体的适应度F(i)。
- k; ?! a! t* h# B/ v　　初始化空种群newPop
- Y; d9 K- q! L. ?8 N6 M( t9 O- B　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
　　　　if ( random ( 0 , 1 ) < Pm )
; m9 B" g1 Z' q) a: g　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
  x5 q: r, A) g& @　　　　}
( L3 m7 G) M9 @" `9 z6 j& B& _0 L将2个新个体加入种群newPop中
" B  O" w' g9 j) M- m8 H} until ( M个子代被创建 )
用newPop取代Pop
: x! l$ ?0 V2 _}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )

% `) X0 e; R: f! E; m; q
& c. y9 ~! ]5 Z[url=][/url]
/ C% g5 m# F$ t" h4 T6 A  i
1 Z8 ]* ?9 o: ~* ~# x

四.基本遗传算法优化

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

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

+ M; v. g7 j& }0 n: ^

图1. AForge.Genetic的类图

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

9 ^) B2 ?+ K6 {[url=][/url]
13042312
36391315
- z, d* g: v0 f2 j; A41772244
37121399
9 ?, R4 h) {% c% q* d34881535
33261556
9 s3 P# p9 n% S# g7 R! j$ Y* K' u, {0 L32381229
41961004
" ?; G0 T: ^( z) S3 E4312790
4386570
1 V0 {, o# W) d: S7 z( x30071970
' g8 C0 \2 t0 _$ W, S' V25621756
27881491
- n+ G5 Z4 Z7 i& \23811676
2 M  K0 I  k8 {# `. r; b1332695
37151678
39182179
& D* G# p) T9 H# B40612370
- _& w# `* A2 }9 t37802212
36762578
1 N5 P$ C- l9 J40292838
42632931
& d- M4 ^$ \4 k34291908
& O3 W& f  h2 A# b% M- F35072367
33942643
- H1 C& x6 {- T  M; h5 u% H34393201
2 t# y% i6 U3 A) ?2 d29353240
3 B; [, |5 z8 d3 N" {; [3 B! N31403550
  u& Q4 \1 E6 O, _0 N2 d7 a& ~25452357
- |, \: W: O9 E; x2 b27782826
7 t( J9 K9 X; A+ |  y23702975
0 Y2 a0 X% [! n" |[url=][/url]



) |7 l4 p# Q: o. h- k4 R
9 [# `- b6 y4 k- B4 X

操作过程：

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

4 y% w4 \: e6 E5 Z  {[url=][/url]
TSPFitnessFunction类using System;
using AForge.Genetic;
; K% [( N* d; u9 I0 n2 \
namespace GenticTSP
{
///<summary>
& \8 H( H. J- z/// Fitness function for TSP task (Travaling Salasman Problem)
  `0 N2 K4 I  [+ Z5 ?( a8 E' p///</summary>
1 J+ ]* j/ \5 H% i6 }5 S) P8 D5 opublicclass TSPFitnessFunction : IFitnessFunction
* |+ i$ h' j3 C2 Q2 D; H1 @# T{
// map
# i3 y1 \; a, G  aprivateint[,] map =null;
( I4 X" B" C4 u7 f* @8 v9 `/ a
& F, w! T; M# I0 |+ L; i+ j6 a: Z7 f// Constructor
public TSPFitnessFunction(int[,] map)
, O. j9 s+ y8 M- w1 c{
this.map = map;
}

" m( c, f# Y1 R1 K+ @; o0 S! n///<summary>
/// Evaluate chromosome - calculates its fitness value
* ]/ H" X; i6 d+ _7 f# k  \///</summary>
4 x3 \0 v, H" W- _publicdouble Evaluate(IChromosome chromosome)
{
return1/ (PathLength(chromosome) +1);
1 c& g3 `5 Q$ H, y& e# V}
& k0 z) ]6 {% O8 [) S6 V
' ^$ f4 |; ?& Z, l4 x; H" a///<summary>
$ e7 W5 t- g0 _) a2 D) g/// Translate genotype to phenotype
///</summary>
publicobject Translate(IChromosome chromosome)
{
6 z# e( o  I" Greturn chromosome.ToString();
! \! y6 e5 t, G5 ^. a# `}

///<summary>
: Q4 K6 m) E; w/// Calculate path length represented by the specified chromosome
# }3 }3 k5 I0 x6 n4 X7 H///</summary>
' B+ f/ `' l' Cpublicdouble PathLength(IChromosome chromosome)
{
// salesman path
8 }7 S4 O: O) \4 @+ Fushort[] path = ((PermutationChromosome)chromosome).Value;
" Y1 Z' F# }% O+ }. C8 J3 L" s. q
8 ?; Z7 e5 E/ X. p, |. R// check path size
if (path.Length != map.GetLength(0))
( R; o$ z* e$ C! u" e' C5 `; H7 b1 g{
. z( P* v/ N" o6 o) R  ^/ W9 w3 |thrownew ArgumentException("Invalid path specified - not all cities are visited");
}

: t3 q6 k7 o8 p, ?5 X- k, O// path length
- ^% W/ Z8 N& sint prev = path[0];
* p" B5 B7 v  d# F- l$ u- Qint curr = path[path.Length -1];

, T$ K; N8 G' U, E9 i// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
( X% a4 b7 q2 [6 I) d. T! x' _3 ldouble dy = map[curr, 1] - map[prev, 1];
1 I$ ?4 J0 r/ y5 F- Wdouble pathLength = Math.Sqrt(dx * dx + dy * dy);

$ i3 O2 I( G) Q) ~9 o// calculate the path length from the first city to the last
for (int i =1, n = path.Length; i < n; i++)
{
7 ]8 f' N* c" Q" u$ n# V6 Z: Q// get current city
curr = path;
- Y8 q" b0 Q7 y4 D
- x' T' g, p& {5 L6 w# M2 x( _// calculate distance
; v% q  _/ v3 Q$ l4 L( C' M7 sdx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);

3 h" K2 M) r2 G# ?1 g// put current city as previous
prev = curr;
}
# Q# S, |; }# o' _$ X* T" }. u2 w- j" I
( K, b: w/ a3 R9 ~0 ^7 m9 creturn pathLength;
}
2 M7 H3 v, P8 k+ a* s% K}
}
; |# D! a; e9 S/ a4 c8 i
" @8 s9 V- d. v1 ~9 B& i9 b
9 D0 O8 R# u- O2 h" ?[url=][/url]



8 L' J) M0 l) D

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

5 g8 ?, \  m+ V[url=][/url]
GenticTSP类using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

using AForge;
! p* H4 [8 |9 l1 w$ T8 Lusing AForge.Genetic;


namespace GenticTSP
{
class GenticTSP
  U/ n0 p2 l# j: K  _* ~% G{
4 r8 O' h" y3 U4 V) Y
staticvoid Main()
1 H, Q& C" {8 K9 `{
0 ]" c" T" [4 u* r% e* q* f: HStreamReader reader =new StreamReader("Data.txt");

" s% X4 k  v' [' R4 f  E, z8 x4 zint citiesCount =31; //城市数
! @5 b7 m4 j; s. E
int[,] map =newint[citiesCount, 2];
/ N7 g$ R9 C' h' o
. ?7 ]- ?8 S8 B7 H9 X1 E0 @/ h& Rfor (int i =0; i < citiesCount; i++)
) k9 [9 A' y+ D" u6 |{
string value = reader.ReadLine();
string[] temp = value.Split('');
# P/ d$ R3 q) ~+ Z0 f; o+ ^map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
8 l: J$ W% |) q  l}

2 M2 P) g# }5 d1 v  i& M// create fitness function
TSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

4 O) _; T8 H9 \( C9 Z" cint populationSize = 1000; //种群最大规模

2 K2 A$ H* I) G! J& U/*
* 0：EliteSelection算法
* 1：RankSelection算法
3 L8 n1 p' g8 ~9 F( Y* 其他：RouletteWheelSelection 算法
2 ?- d1 z8 H6 v8 `+ ]* */
; b4 m) D' N, V: x7 z/ W6 j" Kint selectionMethod =0;

6 A; I9 v4 x0 v& c* x5 x// create population
- C$ c5 r" f. Y) b. l! I* mPopulation population =new Population(populationSize,
; z0 j% F, W  W; znew PermutationChromosome(citiesCount),
- I) l4 i* K1 e/ f2 w. S8 L6 _fitnessFunction,
! B: N/ w& c. N+ c8 M; Y(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
5 H7 V! O$ @5 o8 o% V) `: [# X(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
(ISelectionMethod)new RouletteWheelSelection()
# q9 ^" b0 T; C$ t* a);
" Y5 v3 K- T7 e. ^
// iterations
8 y) @. W2 w" Y0 g6 H* k1 T$ P& dint iter =1;
int iterations =5000; //迭代最大周期
9 A0 E: B* P& G/ j; i/ K+ [* J7 l
// loop
* p$ i/ G/ B& ?: w2 L2 }) h7 u1 m( [while (iter < iterations)
{
& m! d# {6 Z( @// run one epoch of genetic algorithm
. s+ a/ B2 Q. B5 Ipopulation.RunEpoch();

5 l& h* Q, }3 e5 S# e) _6 d// increase current iteration
iter++;
}

8 s* O8 g( X! O* c% a1 aSystem.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
! @/ C" f* t; R4 d3 [0 J6 SSystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
) J/ c* F6 ~: @7 y! n5 oSystem.Console.Read();

, k; x( T2 e: o  k8 d! |}
: `2 V6 a1 `8 e3 u% D) x/ o$ [}
}

6 D( H' @$ E8 z! Q$ ~5 ^
[url=][/url]

! H* \! n; W1 e! ^6 p+ a& }, s

8 D4 o  o6 K$ Q& x$ x) [2 p2 Z
8 J2 L5 Q9 [1 W/ t  e

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

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

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

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

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

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

5 R( h8 g2 v! |3 q) P( a; J( A


+ ]  l; g  @! r* V8 q