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

我要吃章鱼丸子

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

5 _: `3 a: w8 d9 Q+ `1 `0 J一.进化论知识

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

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

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

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

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

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

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

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

( U3 f% s& g& B0 T9 M7 |$ p二.遗传算法思想

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

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

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

! L$ R% |0 D- W& t' y+ R

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

6 T% e$ L7 _! u- d, h+ O* g/ b. X

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

2 {+ ^" y3 H5 M7 E& Z# E[url=][/url]
轮盘赌算法/*
  r$ n! `- m. y+ z2 I+ ]# ~, f* 按设定的概率，随机选中一个个体
4 D: c! f/ B# D6 ^+ S+ h# Q  C* P表示第i个个体被选中的概率
*/
int RWS()
3 T3 x/ [# |/ C  @  d{
m =0;
r =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
{
. B9 ?+ T9 ]# U8 q. ^, c/* 产生的随机数在m~m+P间则认为选中了i
* S4 L5 o, {& m. S9 m* 因此i被选中的概率是P
$ i* \! L- o! d/ j' \*/
# _5 M% L1 l2 U' j6 ]m = m + P;
if(r<=m) return i;
0 [6 [5 d' b- h6 v}
5 @5 l( U% Q) G/ {5 |$ d7 {9 |}

+ I# r  e' j# d. U& ~5 w2 R[url=][/url]
% W6 Y# H2 o: e7 z& O& p% n

  G6 n" b  i7 b% C% h9 s! K% `7 K1 W

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

8 W! Z7 F3 n) v3 I* K' [) O2 D1 N

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

0 t1 K% [+ ?* N- r, E( L5 _三.基本遗传算法的伪代码
0 w  w& x; R. ^3 c+ f+ i3 a2 E+ ~  D
[url=][/url]
基本遗传算法伪代码/*
* Pc：交叉发生的概率
* j" M7 D1 I2 \# @6 u+ Z! g$ D* Pm：变异发生的概率
$ B$ o3 h" _3 O" `; U* M：种群规模
& W" h. s* m5 m6 _/ k3 k# @( q( M* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
7 M4 g9 K9 ~4 q" a9 m; q7 ?初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop

6 {( b, d: {5 U. N7 L5 G. P5 A/ odo
* P7 c0 Y; Q2 D9 y{
　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
7 A* q1 w+ \) ?　　do
　　{
0 ]3 N' a3 h* w* f% a/ u　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
+ j5 p% S1 \) n" c* @& Y+ T1 K% k　　　　{
( R' D3 k7 |2 m  G　　　　　　对2个个体按交叉概率Pc执行交叉操作
, @- L1 ?+ o( t; |9 W- f* X! f. w1 f　　　　}
& a9 p# R& ?) e4 n9 V　　　　if ( random ( 0 , 1 ) < Pm )
　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
/ C1 H5 i( w, f  M8 E# w　　　　}
+ |1 Q+ O/ x+ o, W0 L/ @' i将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
& Z( K+ z7 @! O& [}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )
8 F4 {# X1 a7 l
& j7 r, {* o# G- z7 Q; N; F, N. |7 {
0 k5 c! ]1 [" P6 ^5 x. f4 c[url=][/url]
- O" \, r/ u3 `$ g1 Z* w+ t7 p


( U# {2 s8 c) _2 W6 L; A! x! M四.基本遗传算法优化

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

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

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

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

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

+ L/ [) i1 N7 I/ I, Y3 @

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

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

  {! ^1 l' S' N( l- g: V3 ^

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

图1. AForge.Genetic的类图

/ a3 y" L- j5 c8 U

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

: T1 b; E( `+ e) m1 f[url=][/url]
13042312
; v! [" _$ D& R) }: l/ O( `; p9 K36391315
1 Z8 j4 R5 c1 t: p# o5 ?6 g$ V& m41772244
! F! G& n' R' \7 W- o37121399
34881535
& O# @+ K' m) N33261556
4 i/ m6 b! h( o' K; p# a32381229
41961004
4312790
) X8 j, B$ g+ Q/ y! ^* A: J4386570
9 u* `% _7 b1 S1 Q/ }30071970
3 |* m3 F- e; G# S! V. V25621756
27881491
23811676
1332695
37151678
7 b( g8 n9 c  v39182179
40612370
% m2 U, U( E7 _% a" |37802212
2 r# n1 h& e- h0 M$ _+ W  q$ M36762578
40292838
42632931
34291908
35072367
33942643
8 A; A! C' P5 h) ?0 l; |1 m4 h34393201
' T* J# ^1 [# }  m& j7 t29353240
31403550
25452357
27782826
23702975
$ E* y7 i, T( Z- @7 H; f2 n" R[url=][/url]

# a. x" i0 I8 n3 ~: Y' D4 K% _! U
' l# c1 t4 J* H* q: C+ G+ t3 t! Q7 M

操作过程：

   (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;
" N8 m. q3 T+ Busing AForge.Genetic;

& k( A- E4 T- S! S7 m2 dnamespace GenticTSP
{
///<summary>
/// Fitness function for TSP task (Travaling Salasman Problem)
  M. N/ _# i& r///</summary>
* T; v6 S- I$ W) a2 q! Z; jpublicclass TSPFitnessFunction : IFitnessFunction
- H1 y" L  p% S5 `{
7 P% {1 w; d) U// map
privateint[,] map =null;
  I( M* E7 E4 E
$ @' ~# y" f7 C8 V! k2 j0 }// Constructor
public TSPFitnessFunction(int[,] map)
2 F! D! R  Q% m  L' b{
this.map = map;
}

///<summary>
/ {' ?/ }: Y7 i+ N" }1 p+ B3 W/// Evaluate chromosome - calculates its fitness value
  ^! I2 a7 g" n3 h+ l- N  L///</summary>
! [0 x  r5 h# m* Apublicdouble Evaluate(IChromosome chromosome)
{
+ z( L1 v% j5 c) A2 N' j7 ~; X- `return1/ (PathLength(chromosome) +1);
! W/ X8 O9 |* t5 \/ C# M}
/ |4 B( `! c% |$ ]6 G0 ^* T
///<summary>
0 n3 Z  J. g5 m1 v! H" k, [/// Translate genotype to phenotype
4 ?9 N/ S* w5 ^: d///</summary>
( E5 j1 e! n3 Dpublicobject Translate(IChromosome chromosome)
" p% K3 z( j, ~0 I# h' r0 p( N{
return chromosome.ToString();
, e$ \+ B) ^% i/ B% V, I8 Y* ?}

///<summary>
/// Calculate path length represented by the specified chromosome
///</summary>
publicdouble PathLength(IChromosome chromosome)
{
' ^) o! O1 g3 ~% `& g+ m// salesman path
ushort[] path = ((PermutationChromosome)chromosome).Value;

3 ~2 I8 O1 L. A% O// check path size
; H1 @) }6 U0 X" @. |: Eif (path.Length != map.GetLength(0))
3 e9 f1 a+ t; P( l{
1 \% n3 M- y+ W1 c% V$ z9 z7 Y6 H9 qthrownew ArgumentException("Invalid path specified - not all cities are visited");
}
1 R" D( o. T8 D8 ~
2 {* ?. j) S+ y, [* X// path length
3 q% o$ o. W, u% Lint prev = path[0];
int curr = path[path.Length -1];

+ q, r, e3 x- \// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
* r0 m8 G! n$ _. p' Y6 |# Kdouble dy = map[curr, 1] - map[prev, 1];
double pathLength = Math.Sqrt(dx * dx + dy * dy);
& F- Z0 I9 v6 I. g5 R* |( d
// calculate the path length from the first city to the last
2 {' r1 y7 l' z% rfor (int i =1, n = path.Length; i < n; i++)
{
& [2 Y7 m, n* Q5 h0 `/ Z2 `3 x// get current city
, d8 P' \- h# x3 @& Lcurr = path;
1 K- f. ]9 f. n2 j9 P+ _
// calculate distance
dx = map[curr, 0] - map[prev, 0];
: I& J! l& @* y2 L9 ^; Tdy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);
, ~% [9 b1 F9 U6 U4 f  Z
// put current city as previous
prev = curr;
% n" Z# X- }* e}
( H$ f1 x' P! V, S6 e
return pathLength;
}
0 g" h3 k8 F! o  f2 W- Z) M9 O  A+ J}
}
# ?( |4 M; M4 }5 K) t. h- ~$ `

[url=][/url]
. |! i/ T, ^+ {

7 s; t- l4 R: U

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

[url=][/url]
GenticTSP类using System;
. g2 P! Q( R2 a1 E2 Ousing System.Collections.Generic;
- k0 L! ~* a( e* Q! D4 Rusing System.Linq;
* D: `7 b  I! ausing System.Text;
using System.IO;

using AForge;
using AForge.Genetic;


8 K$ {! k" N, _) [* A3 g" U4 bnamespace GenticTSP
/ h5 z1 s& [4 A" S/ v{
class GenticTSP
{
% H' @7 ?- S6 T* g& {
staticvoid Main()
{
! }  {: D9 }. M7 PStreamReader reader =new StreamReader("Data.txt");
9 |$ ?4 g  ^5 Z7 N$ f
int citiesCount =31; //城市数
3 S  k) J% G& F+ N" k' S
int[,] map =newint[citiesCount, 2];

for (int i =0; i < citiesCount; i++)
7 ]2 H) v" ?4 ~. O6 |{
3 R4 F  y7 g$ L: z7 @$ P6 o$ P5 Qstring value = reader.ReadLine();
string[] temp = value.Split('');
+ R4 Z3 M% l) @+ s! D( F& Pmap[i, 0] =int.Parse(temp[0]); //读取城市坐标
8 l; L& E1 Q! y' |4 u' pmap[i, 1] =int.Parse(temp[1]);
}

. k# T9 I$ h* J1 ^5 r// create fitness function
TSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);
2 a2 O9 G+ U6 m8 D$ O: v
int populationSize = 1000; //种群最大规模
7 E, Q: O) u6 i" N, i5 f1 i& F
+ |2 W0 ^# e* O$ l' D1 T8 i' j/*
* 0：EliteSelection算法
. q* i( S) R0 H6 m# N0 P* 1：RankSelection算法
* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;

; Y' M  O6 N" M9 m0 p$ p) ^/ {# t// create population
Population population =new Population(populationSize,
/ ]4 w1 _' j9 S% y" F! S9 Cnew PermutationChromosome(citiesCount),
fitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
(ISelectionMethod)new RouletteWheelSelection()
);
2 g5 j5 {2 ]0 T( b, T; }5 M+ x: ^* N
// iterations
int iter =1;
int iterations =5000; //迭代最大周期

// loop
* j$ P/ H% G7 n* Rwhile (iter < iterations)
{
// run one epoch of genetic algorithm
. i% r/ v- M5 Z& X- w! V% s0 [) ~# Hpopulation.RunEpoch();
+ B& g6 y% F- E
, w0 f9 w9 f6 y5 ], D5 t% H// increase current iteration
2 `; I" v" m2 Citer++;
8 w$ K1 f9 n9 I7 B4 h6 S& w}
/ U% h# l) z! j8 d+ V& C
System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();
* y4 }  V/ f- D+ {
8 D7 p. A" S; j7 J# [) t}
1 U; _5 k' ~! _; Y. a" x}
}
* E2 w+ t6 ?* ?3 C+ ?. C

[url=][/url]
# N1 ?' R" Z$ D; H8 x

% }% w$ I: }" Q7 U. U' J0 t
/ [" r3 _3 s& y: r! ]+ Q* N5 I

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

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

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

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

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

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

) K. p- g( O& V. e$ G, j