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

我要吃章鱼丸子

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

$ S; \- ^3 f1 H% I
; c8 M1 ]" ]/ j1 d$ `. o* K一.进化论知识

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

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

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

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

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

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

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

( C5 ~" j% P% ^. E1 T$ z3 C

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

2 f6 o8 F$ Z/ v+ G" |
- H) Y/ R) ]1 b& J- T$ D0 ]- ]二.遗传算法思想

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

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

/ {8 N* d% a$ U

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

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

0 q, R8 A% p5 N7 l

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

[url=][/url]
; m  k) k0 a$ C轮盘赌算法/*
* 按设定的概率，随机选中一个个体
4 @% C" N# |/ a* P表示第i个个体被选中的概率
*/
9 H* V( ^) D5 ~* bint RWS()
{
m =0;
+ `, z! q0 I8 Z8 er =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
9 o. G4 |# D9 j5 q4 R# N+ l  O( r/ O{
/* 产生的随机数在m~m+P间则认为选中了i
; E" E- X- J, `: l* 因此i被选中的概率是P
8 \- U1 q; x% Y5 C0 _5 k*/
m = m + P;
% z: E1 s7 f  j7 M2 z5 Z  W6 p8 xif(r<=m) return i;
5 r# |9 F4 o2 b8 z% T}
# X+ e0 p4 v. T" b0 S2 H. @( `# p}
% q9 k+ f; q& p  X* U1 b# y* i  T
& p% F( ~( r; E& L+ E3 [[url=][/url]


! h' `0 Z5 j8 {+ ^

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

三.基本遗传算法的伪代码
3 \) E- Z+ w+ Y+ M( \& |" c) _
[url=][/url]
& A3 I( B& F8 U* }; ]3 i; B基本遗传算法伪代码/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
. |- V# K' f8 R9 w" C* M：种群规模
  m/ X" a+ V9 I! S* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
: ]' U& B' P7 I0 q2 b$ r*/
# T# O. a2 [6 t7 \. ^初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
* ?# O6 b$ F$ o0 }9 t
do
{
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
　　{
: C4 M4 i" M$ E+ c! K  ~4 W8 u- ?　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
5 o0 ]& [! O; ?8 s- G% W/ J　　　　{
　　　　　　对2个个体按交叉概率Pc执行交叉操作
+ g# ~# n" J- J9 X9 f/ V" \　　　　}
, c$ s4 a# l0 m  N7 z& k5 Q　　　　if ( random ( 0 , 1 ) < Pm )
0 |& Q, [( p; x* T1 ~, I　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
0 a, o) P* c6 i5 @4 \$ [" z( O/ O9 o　　　　}
' G2 ~) X! v) ~( y1 j0 X将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


$ D& e: ]0 J- B[url=][/url]
+ E# S- P1 ]6 [


6 a- A# O2 B5 s9 ]8 ?2 s( w四.基本遗传算法优化

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

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

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

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

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

/ P3 u6 Y  s" y

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

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

0 O7 {5 x) X0 M+ ~" `

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

图1. AForge.Genetic的类图

; u8 `: u. I- i- r" ~4 Q
8 y* t! }6 r; p2 ^

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

[url=][/url]
13042312
# B% P7 [( Z1 }, n2 K36391315
" U  j% r8 N' i/ g+ o4 V+ R41772244
37121399
. Q$ f$ V6 h0 `1 J& t0 V0 q34881535
33261556
32381229
7 j8 C5 t! a& e  x41961004
4312790
; m0 X/ _2 l; X5 R2 s3 U1 d4386570
30071970
& i2 {2 K5 E. M( y1 b6 O8 l" E9 l25621756
. U* B1 b. G% u6 M1 u; u27881491
( A# x0 d- B& q* l' I" s8 G23811676
1332695
- Y8 U1 E0 {2 D37151678
; [- C/ N: W& I39182179
; y7 X1 N. O( T7 g' V40612370
37802212
36762578
40292838
42632931
7 \6 N4 h  N. ?+ o2 j8 f0 u34291908
35072367
33942643
+ b" q7 |: Q/ L; j1 {. @2 a34393201
9 O+ y) |, g7 e& S29353240
# K4 Q6 t0 G# n$ E) ?" ?$ ]) `- u7 P! E31403550
25452357
: ]3 M, }7 ]/ L0 V+ P27782826
23702975
- G1 X% X! t5 H4 R8 q[url=][/url]

/ x$ P. J8 |/ U
' j6 x  E- x2 _! G5 U" P

- {$ h& p! d1 B

操作过程：

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

# N# z" V# i- Z5 C2 q[url=][/url]
1 B7 i; \, P8 J: ^* E( W8 R, eTSPFitnessFunction类using System;
using AForge.Genetic;
2 ~% q0 c0 z- j  l
& F2 j) ^, N2 h2 L3 S* Onamespace GenticTSP
{
///<summary>
, M2 \# g* M% r3 \8 w, d& u3 G( ~/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
; m: v% V& E7 `7 Y6 N, H0 B! Upublicclass TSPFitnessFunction : IFitnessFunction
{
// map
privateint[,] map =null;

// Constructor
public TSPFitnessFunction(int[,] map)
, }. O2 O0 q( A; S: W0 n{
this.map = map;
}

///<summary>
$ p5 B- }# ]4 d) Y) ]5 \0 `/// Evaluate chromosome - calculates its fitness value
9 g. [) P' A' Q$ z" d- q///</summary>
publicdouble Evaluate(IChromosome chromosome)
5 |' ]' b. C2 Q$ N; x{
$ L& ]: _6 ^2 m; n+ A* H$ Oreturn1/ (PathLength(chromosome) +1);
}
3 a8 j8 u$ @/ V' Y+ X
///<summary>
% Y6 L1 `' T0 `3 b/// Translate genotype to phenotype
# o7 r, W* M" ^///</summary>
publicobject Translate(IChromosome chromosome)
9 m& |/ w4 ^# |2 @{
return chromosome.ToString();
}
. |) _; S. u6 B
///<summary>
/// Calculate path length represented by the specified chromosome
7 b( g, R, Q$ N$ g' [4 b4 f& _///</summary>
7 \1 v8 T" q# F1 s: e( cpublicdouble PathLength(IChromosome chromosome)
/ r" v+ }; R" n6 ]; {3 ]{
// salesman path
3 I) e3 i( T, H  O( p; T/ e& vushort[] path = ((PermutationChromosome)chromosome).Value;

5 t; ^  X% r. I" h) A) h# V8 L4 b// check path size
if (path.Length != map.GetLength(0))
( @6 r' j8 |0 B- l1 z{
thrownew ArgumentException("Invalid path specified - not all cities are visited");
}
$ s+ P, k7 e# I9 Y
0 M6 `! _, \0 M3 u// path length
int prev = path[0];
int curr = path[path.Length -1];

// calculate distance between the last and the first city
9 \' E2 w+ `7 U6 J# Vdouble dx = map[curr, 0] - map[prev, 0];
# o* a: m( v$ \8 Y0 |- q4 ^double dy = map[curr, 1] - map[prev, 1];
" I, J- ~1 H, Jdouble pathLength = Math.Sqrt(dx * dx + dy * dy);

// calculate the path length from the first city to the last
# D  Y+ P/ M0 y- a& p8 y8 }for (int i =1, n = path.Length; i < n; i++)
{
+ R/ a& ?* E3 B1 O+ Q7 q) p' X// get current city
6 J  F+ B' ~3 _! J& Vcurr = path;
8 Z( ^0 [- O6 J3 I- o
// calculate distance
dx = map[curr, 0] - map[prev, 0];
. A& s0 _+ @/ Q: j3 Hdy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);
4 f& G' H/ O; G# L% b4 R+ w
8 u' d: a+ V/ M) K8 g! V// put current city as previous
prev = curr;
8 F* \9 R/ M/ W" l  ]0 ?3 ]}

1 B8 E5 `1 |3 m" k! s" }2 Nreturn pathLength;
3 X3 r/ H6 C1 T}
}
}
& N% B( |3 y3 T

1 a. l+ ?" C2 R3 s5 t[url=][/url]
+ Q) v& l0 w3 ~, u0 T
- C8 ^# l  L& H9 c* `% C% U9 z* z7 r

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

[url=][/url]
- u% P) z% J0 r- n6 X. q( E/ aGenticTSP类using System;
7 E* u- g& T( d) U' G( w5 W3 P6 gusing System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

using AForge;
! s$ N4 d3 t" v2 |8 M& ?$ Qusing AForge.Genetic;


; V/ U) r1 v8 K* ~# g; ~" hnamespace GenticTSP
7 Z0 V; _( _! z  T. G{
class GenticTSP
6 t- d% `1 c  W5 b{
/ K+ B) D6 L% d9 o- t
- e7 H# q0 W9 f* |$ U( Q" O; |% |staticvoid Main()
# Z/ q7 i$ @1 h9 F7 [6 t: Q{
StreamReader reader =new StreamReader("Data.txt");
2 Q$ J* ~* c' H" V* n, H/ `
7 g  p& e+ c. D9 }, |+ Dint citiesCount =31; //城市数

3 l4 U* A# ~. X- e1 Sint[,] map =newint[citiesCount, 2];
+ L4 O) l3 f! y9 |; w! S
1 ]& \' {, S1 c3 U0 }6 b! g/ Bfor (int i =0; i < citiesCount; i++)
1 |; p3 `& q6 F! F$ x( L{
9 c5 |; K  y, J; A5 T7 n, wstring value = reader.ReadLine();
% g& u4 r7 p% ?% jstring[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
- h+ U. Y, ?% i+ Cmap[i, 1] =int.Parse(temp[1]);
9 g+ S2 I7 \- B  o}
0 ?& h. w+ Y, ^5 L5 [+ N. L
9 T/ `  }1 B2 W4 b// create fitness function
3 f% Q1 u; w+ `* b5 C& S, d+ U; JTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);
( b/ H4 @1 a* R6 U6 z  n! h2 e! ^
int populationSize = 1000; //种群最大规模
+ a3 \& }$ M/ u6 e. Z% g& r# a& R  r2 ~
" O- {0 y% ^! a1 y+ d+ @7 B) K$ y: D# C3 `/*
/ ]0 B7 Z6 |/ x0 ~* 0：EliteSelection算法
* 1：RankSelection算法
8 q- ?2 O7 R, |% |# [& R4 D+ O' q* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;
& F( p! y. F; E! d  r$ h0 T
/ S/ K* h$ s0 N1 C( O) Y8 Q. C// create population
Population population =new Population(populationSize,
+ R; e  x& ?, N/ U1 inew PermutationChromosome(citiesCount),
5 O$ l. x6 |( I# T/ RfitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
- g6 J7 \$ @$ C5 k) Y(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
" J9 j2 x3 `* e; M(ISelectionMethod)new RouletteWheelSelection()
; q: q7 K# o& m2 x9 K/ E# s5 y);

// iterations
int iter =1;
int iterations =5000; //迭代最大周期

// loop
* T+ S1 c' ?/ D' K# |; u3 o  \. K  l& l2 @while (iter < iterations)
{
// run one epoch of genetic algorithm
population.RunEpoch();

# ]% _, g/ V+ |+ Y- s+ v7 J0 g// increase current iteration
iter++;
}
* G/ z6 |" d$ S8 c4 ?, _
1 ?! E2 F- H) @9 g& |$ L  ^System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
' E( t" X6 t+ W5 nSystem.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();

: E/ l/ i* G2 ~( N" Q}
) `6 V2 \" M( i: }8 S  F& H}
8 Z  g! }: `( ~# Q}


[url=][/url]


% D# t! N$ h8 d" C8 x( r- w

6 L1 \! Y/ }4 @- {0 q

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

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

4 ]0 U/ b: G6 B% F5 k8 m

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

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

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

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

/ k( \% X6 c3 j0 p8 @6 y- v


7 ]! c: Q/ U3 w9 n