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

我要吃章鱼丸子

遗传算法入门Posted on 2010-12-23 13:12 苍梧 阅读(103275) 评论(39) 编辑 收藏
5 u$ C1 w& u) m/ G5 r2 p. o# X

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

6 J' T1 k, V: F  m2 c( u* Q1 K
一.进化论知识

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

　　种群(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背包问题的一个“近似最优解”。

  `! p- M) {: t) J9 L

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

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

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

8 b4 i( Z5 K- U; T0 w2 O[url=][/url]
3 S6 R7 R) _) X- y( G" |- r, d轮盘赌算法/*
: U) o1 C! c, u5 c5 g& e* 按设定的概率，随机选中一个个体
$ H/ w+ @& i0 H  D8 m; i0 `/ i" G* P表示第i个个体被选中的概率
- _! J3 C8 ]+ o( `*/
8 S6 q0 b% {4 ^% R$ A" rint RWS()
{
8 i  z. F  s* J/ E0 Fm =0;
r =Random(0,1); //r为0至1的随机数
3 O' g" W! V" W# Z* R% |3 v+ |( d4 dfor(i=1;i<=N; i++)
& b$ \4 b3 z- X( U+ p{
/* 产生的随机数在m~m+P间则认为选中了i
% O% N5 W+ u+ X- C, t* 因此i被选中的概率是P
*/
m = m + P;
4 ^: N( d, P5 S1 Qif(r<=m) return i;
7 m! z) @) a2 Q" Q}
& ^; l0 W0 d* M5 X2 g% P}

[url=][/url]
% q! f8 W, [7 X5 Q6 S0 Z0 n

6 D- N& c( \; n, r

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

# L0 K1 u. i. k5 b7 K, L9 A

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

) U* t, a4 R% @; ^  I2 r
9 X. |/ O. ~- R三.基本遗传算法的伪代码
8 Q0 C4 K: w" V8 P4 g- B& Q; k+ ]
[url=][/url]
基本遗传算法伪代码/*
% f: s9 K& F+ \. g. ]5 m( I* Pc：交叉发生的概率
3 K8 [+ F, A  {# c/ C. W* D$ c* Pm：变异发生的概率
+ ^- D6 v; }! L+ ]* M：种群规模
* G：终止进化的代数
* L. H# J0 v3 D% G/ P5 P4 z* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop

do
{
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
0 k) Q8 M  I) S1 Y3 \% W+ |　　do
+ `4 p! y' n* }6 l& w+ s- X　　{
* b$ t) l! a8 F　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
/ z  Z2 T& `+ D3 l7 {. W. m3 _　　　　if ( random ( 0 , 1 ) < Pc )
- G; X- Z% }: C) g5 }) N5 D! G　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
" P4 ]( n  r3 f2 p# K! Y1 o　　　　if ( random ( 0 , 1 ) < Pm )
0 B4 F4 G2 w; V, C9 ?- S: g　　　　{
5 ^  I; M  b6 P0 W' R　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
将2个新个体加入种群newPop中
  D' l) G2 W* P} until ( M个子代被创建 )
用newPop取代Pop
  k4 `/ f: B2 U6 S$ J0 e}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )

1 }$ o4 Y* Q# P( [
[url=][/url]
1 X  }3 S; M9 r$ L" i, A6 r/ y! X
. g/ F5 S5 o7 ]$ K: _
! p# m8 x1 J/ Z
四.基本遗传算法优化

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

　　精英主义(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/

: v9 J3 q( Q8 c, \' X

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

0 ~1 O( m. F( p) h5 h+ B

图1. AForge.Genetic的类图

# P& a- b6 d! T2 }

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

7 U/ D5 l) k4 t/ U! C2 ~2 W[url=][/url]
13042312
36391315
( U! Y. E9 e0 _/ C' |* `' P6 l: P0 E41772244
7 O# e( `/ j8 W37121399
34881535
* n/ ~8 z" C6 v0 y- A33261556
* Y+ p& O( F+ Y1 c0 Y& p4 v32381229
41961004
  m; w- g1 w& Z! [4312790
4386570
) }% ~* g9 Q; n30071970
% u$ J5 Q/ k/ I. |25621756
+ R# R  `1 Y9 i' M27881491
" N2 g8 {9 w; o( `4 A' Y23811676
1332695
$ v9 t2 u. C# m+ g0 L37151678
39182179
3 l" ~  b  C- S6 b5 `5 x7 c( ]40612370
5 Q+ R1 t2 e; B. t8 r+ ^2 |37802212
! T" C' |# [- V: W) h* N& \6 \36762578
7 K* ^  x4 j. U: c! w# C# [; z40292838
42632931
& _9 ?& J3 E" {9 _6 }' o1 S34291908
9 n, R0 z. W. j8 P" A# t6 b: Y35072367
. O0 _! e. Q! S9 N* S33942643
34393201
29353240
; E/ \! |  d: w31403550
% p- N5 C+ q: W9 [0 u& d25452357
! t" M8 U! V$ ~& u) y. X0 t! |27782826
23702975
$ f1 c, I! G3 p[url=][/url]
4 Z( @# V( x4 }+ F$ ]

4 o0 F, `* q5 C# v) _, w. \6 X
- Z" U5 L! g7 X6 ?" z4 d2 ?1 m
& B  Q' {0 O$ E

操作过程：

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

7 f+ h' u0 d0 Z6 m" ]( V[url=][/url]
TSPFitnessFunction类using System;
* v5 c6 g: E" j, W5 dusing AForge.Genetic;

# `5 F  y7 t7 N' X) ?namespace GenticTSP
2 d$ [( m- i# T& k& L- b6 T+ T{
. S0 Z( Y8 v9 S: g6 c6 {: v, R///<summary>
7 X5 _5 [) F0 L/ K/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
% k8 {& B6 ^4 c& {! C5 ^; jpublicclass TSPFitnessFunction : IFitnessFunction
{
// map
privateint[,] map =null;
# I' f+ i% d' t1 A4 s
// Constructor
# x% c1 B2 R9 P0 K6 k0 u. Ppublic TSPFitnessFunction(int[,] map)
2 k: d, a0 a/ E{
- O. U; |$ H& j& o9 B) j4 U9 Q0 Wthis.map = map;
' P3 C* ^& `: M( u: s6 ^- U}

///<summary>
5 ?# O$ Z( @3 c. o2 B/// Evaluate chromosome - calculates its fitness value
  v, l$ t& w$ U0 \: _///</summary>
publicdouble Evaluate(IChromosome chromosome)
  Q' [4 @) p! u2 f; Y) p{
5 Z# |/ ?1 Z5 Y# \/ Xreturn1/ (PathLength(chromosome) +1);
1 ^- h4 U: d  y8 {9 s5 e0 ?  n}

3 |; a. l5 \6 N7 N+ P' F( J; w///<summary>
2 Y* s0 B% y) J8 P8 b) }/// Translate genotype to phenotype
///</summary>
publicobject Translate(IChromosome chromosome)
{
2 c/ z1 J8 x& ~/ M  {5 @* ereturn chromosome.ToString();
1 l3 U/ Z% L# _! ?1 o}
' V# w# ]8 S  D6 _' D' M
///<summary>
; }  e3 d: F; I9 E  }/// Calculate path length represented by the specified chromosome
///</summary>
  D' O. Q) R- Rpublicdouble PathLength(IChromosome chromosome)
{
4 v8 F, s/ ?1 R7 ~& r, }# F// salesman path
ushort[] path = ((PermutationChromosome)chromosome).Value;

// check path size
if (path.Length != map.GetLength(0))
0 Q7 z0 m+ @/ F7 k8 l% A, o, x{
thrownew ArgumentException("Invalid path specified - not all cities are visited");
}

// path length
$ V/ C6 [; j6 P* \# u9 {# E$ vint prev = path[0];
# u- X* `. l! P* h( ?int curr = path[path.Length -1];

: x' Q1 b2 [9 G, Y. P9 {// calculate distance between the last and the first city
1 O' p, N, ^0 }  s: S. p: Qdouble dx = map[curr, 0] - map[prev, 0];
" R4 {0 g$ F& @1 C! R! U8 Mdouble 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
- _, [/ _& @5 Q" J5 C, Icurr = path;

// calculate distance
dx = map[curr, 0] - map[prev, 0];
3 j5 b  M  H5 T2 Q3 ddy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);

// put current city as previous
: N3 C% z3 r& T0 C7 L0 Vprev = curr;
6 o: J5 s, L5 J8 c}
& h% A% |1 X% n: ~* e
$ J3 q; E# G( R, S! Oreturn pathLength;
}
9 c" N6 T, S; k( |- r- I}
; q+ b8 U  I0 e! T& c) W' L# H3 I}
6 R+ a8 q- T. ]6 M+ C* |. G
7 i7 N% f2 ?& `3 X' |4 A3 F0 b
[url=][/url]

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

  K) v: S8 R* `% v8 _$ Y[url=][/url]
GenticTSP类using System;
using System.Collections.Generic;
- f- w: [+ J* P& susing System.Linq;
using System.Text;
using System.IO;

% a% L. ^* U; g7 Jusing AForge;
using AForge.Genetic;


7 h4 O3 Z5 q& k4 h' knamespace GenticTSP
4 A, V/ _9 ?; m* C/ P1 q3 T{
class GenticTSP
{

staticvoid Main()
{
5 m& C6 B: ?. T: I, a# rStreamReader reader =new StreamReader("Data.txt");

int citiesCount =31; //城市数
; }( y7 |! k# u* o
) P) X% Z; w, |* Dint[,] map =newint[citiesCount, 2];

" w6 V3 v- Z1 [% n6 l! ?% j. Ifor (int i =0; i < citiesCount; i++)
: |& P  m9 ^+ l1 P* {9 N; ?{
$ r3 X, l$ {' ]! f5 R- C. i4 v# tstring value = reader.ReadLine();
string[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
8 T- t4 P6 t- S& c" }1 o5 v}
$ e1 x3 Y* x& q/ ~- I% `
// create fitness function
- [8 O$ n* {  w0 n/ xTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

. U$ w" n7 o  M, w; N) nint populationSize = 1000; //种群最大规模
1 _: j1 \$ ?' a( J% h
/*
3 m: v9 Z0 W% N+ g( L+ n* 0：EliteSelection算法
* 1：RankSelection算法
* 其他：RouletteWheelSelection 算法
6 G( f  [0 z) [* R5 u* */
' q4 V! ~, l  {% f& ]int selectionMethod =0;

// create population
Population population =new Population(populationSize,
$ V: l: i3 _. U: q4 }4 i/ Anew PermutationChromosome(citiesCount),
) q4 I  g' N1 o; Z8 t1 j& SfitnessFunction,
& \) s: R4 E" n(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
(ISelectionMethod)new RouletteWheelSelection()
);
- F0 Q& \; Z8 l& _
& |1 v: r  |6 y  p( _" N0 M2 Y// iterations
+ a5 t3 N. D* |3 H- V! j3 aint iter =1;
int iterations =5000; //迭代最大周期
! b, l" Q, }1 Q# u. U, _
// loop
while (iter < iterations)
$ w9 p' e( U7 g) I' I$ ^{
% k1 W& t2 X! d0 y. y- I6 z// run one epoch of genetic algorithm
population.RunEpoch();

// increase current iteration
5 Z/ J1 L" e+ K$ o0 ]  oiter++;
% Z  ]' i9 a* r# i+ @}
5 @* Y/ }* b( Q" t# n
: \: C% s: ?# v( oSystem.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
" H8 E; E# P3 C) ]3 n% eSystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();

}
}
8 ^6 ^( k8 K2 t9 j5 ]$ G}
! y, L2 S: g) q9 j4 }* D/ G
! W3 q& Z3 W0 \* r' N* h" V9 e
[url=][/url]
) s+ A) H5 M! Y) R% s' g; M

& Y( C! I8 A" i3 g

- w& r# v' q7 s2 g# l8 b

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

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

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

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

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

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