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

我要吃章鱼丸子

遗传算法入门Posted on 2010-12-23 13:12 苍梧 阅读(103275) 评论(39) 编辑 收藏
8 c+ P5 A" z( H1 T/ U

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

一.进化论知识

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

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

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

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

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

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

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

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

* ~% t$ R9 o* R+ w二.遗传算法思想

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

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

2 h0 M! B5 m; ]# k

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

* d4 ~' k; S- N1 W8 v. Z

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

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

$ v7 G6 P4 @! W) N& [[url=][/url]
轮盘赌算法/*
* 按设定的概率，随机选中一个个体
* P表示第i个个体被选中的概率
- {/ b9 p# R9 E5 `0 F+ Y. m7 g) c*/
int RWS()
{
m =0;
7 W6 M0 X, d0 H; n" O) Zr =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
9 H9 e! w. x; p1 c$ D" G1 @2 ]7 r" q{
/* 产生的随机数在m~m+P间则认为选中了i
* 因此i被选中的概率是P
*/
m = m + P;
( [# S" A! W" v; v5 ~, Gif(r<=m) return i;
: I. X7 ^$ o0 o, [( |: V}
8 X$ i$ e3 _: }; t8 F# l& v}
+ Y2 f( g- {& e/ i
8 [# J- Q: r' l1 v- x7 |6 ][url=][/url]
; e, Q4 L' _+ K: h( ~
& ~1 B: H  b& Z* B; {, P( [7 v

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

) l' S- ^- }2 C8 X$ B
7 _; m) L8 M  V( e# x  \3 m三.基本遗传算法的伪代码
7 ]* q, j* ^1 j% L. J0 {
* y1 U) o) ]2 ~9 s' Z3 }! Y5 X[url=][/url]
基本遗传算法伪代码/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
* M：种群规模
  ^) S6 T( c! p5 `* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
4 u* Q" z3 {& H( a" ?6 ^
do
{
, {2 k1 G+ U5 n& u: y6 x; S& N　　计算种群Pop中每一个体的适应度F(i)。
9 M# O2 S  v: N　　初始化空种群newPop
* I8 O4 W: o* c' t- r　　do
　　{
9 i8 f( x7 h0 \* V+ D+ E　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
+ F, r) I  p, ^9 K　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
3 Q" X: F9 i6 p* M# {4 M　　　　if ( random ( 0 , 1 ) < Pm )
6 b* m4 x% ^0 n: ]　　　　{
　　　　　　对2个个体按变异概率Pm执行变异操作
7 }5 g/ }+ B( S+ s　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


[url=][/url]
8 b  n  B8 e$ D5 H3 ~; G& c

$ ^1 D3 ^/ r; C
四.基本遗传算法优化

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

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

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

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

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

0 [; P5 i% E) l" p- N- q7 P

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

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

0 c1 Q+ S3 h% d& T  @

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

2 ~; U5 G+ C4 ]& t

图1. AForge.Genetic的类图

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

; L8 ^( i+ Z! R3 Q, G0 {2 M[url=][/url]
: U+ {6 |0 R6 V13042312
36391315
; C+ L1 G8 @9 k) x! v3 c4 ]41772244
37121399
34881535
# Z# i, H4 o( @- \; q& R% u7 d33261556
* @, K/ E/ Q) `) H32381229
41961004
4312790
; D4 t4 V/ N- T9 t4386570
30071970
25621756
, D$ N' ], @5 p) p! r$ h8 B27881491
9 w$ L0 P1 Y) Q" ?) }" \( q3 Q23811676
1332695
) v& k1 I! H( o% }; N37151678
39182179
40612370
+ H. @5 J! u0 ]; }% a; U$ P4 v37802212
* L- E& ^5 J$ K& Y2 n# x/ y6 J36762578
+ a: W$ Q. N8 n40292838
42632931
& c/ y3 f& C/ d1 j& o, _4 u34291908
& Y- @: h8 r: f& y35072367
33942643
* ?% z) p% E" y5 w# ~% @34393201
29353240
+ w; T  |$ o. Q; d! M& g3 _: M31403550
25452357
6 A% `; |; s5 P8 |" o27782826
23702975
[url=][/url]
5 O* o& R: H, ?9 d
# i" B9 `, d* J  V0 I9 T, _: Q0 C  p
6 O( {1 C, q" ]: |" U
/ F' b8 `" s* h, C  H# ?- l) p4 H5 n0 i
  v( g1 ^- C/ h  t, E1 A3 G) ~3 k6 r

操作过程：

   (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]
7 c' G2 H; }1 C, f9 i+ g1 G. z, ZTSPFitnessFunction类using System;
using AForge.Genetic;

namespace GenticTSP
{
///<summary>
- v/ t4 V! u2 f7 m9 Y/// Fitness function for TSP task (Travaling Salasman Problem)
+ Y. f) Y/ x. b///</summary>
publicclass TSPFitnessFunction : IFitnessFunction
{
: \6 B& q* A9 e/ s4 K// map
privateint[,] map =null;
+ N- ^1 B' ~. _: z5 _+ ^
# s' r# ?, i2 G// Constructor
public TSPFitnessFunction(int[,] map)
0 X3 e: p! C3 Z! I# F0 U, B, t4 ]: z{
this.map = map;
! ~" s& ^+ v; r5 ~! |}

///<summary>
/// Evaluate chromosome - calculates its fitness value
///</summary>
8 N; C" z9 q8 apublicdouble Evaluate(IChromosome chromosome)
& X2 K: c$ h9 \% |" l# \: T1 s{
return1/ (PathLength(chromosome) +1);
0 T* Z4 @- Q% T  w6 n6 ~, U4 d# \}

///<summary>
8 n! |0 G4 u. P8 R; \, B. L/// Translate genotype to phenotype
  v4 h' g7 O9 t9 p% J///</summary>
" i1 u, l8 P3 ?3 }6 dpublicobject Translate(IChromosome chromosome)
3 }$ K, m# B1 ?: S6 x{
0 N2 ^+ l0 C; d: n: }return chromosome.ToString();
}

4 w8 h( [0 j# S! ~" d3 m* q///<summary>
0 c! M( ?3 f- `4 F/// Calculate path length represented by the specified chromosome
+ Y+ b' W' V) f6 `4 O///</summary>
5 \: h3 p3 O5 c' }1 p# l6 N3 rpublicdouble PathLength(IChromosome chromosome)
* m6 W# U3 S  F# P1 r{
// salesman path
3 j1 B6 D: t1 X& cushort[] path = ((PermutationChromosome)chromosome).Value;
1 U# W! I( |: w* |* B/ L
// check path size
if (path.Length != map.GetLength(0))
{
thrownew ArgumentException("Invalid path specified - not all cities are visited");
}
# [# V+ {, {2 z0 Z8 f
3 r) B+ F  J& r5 v// path length
int prev = path[0];
int curr = path[path.Length -1];
5 x1 g7 L$ G% E+ ^
// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
/ G- r( |2 E- P: G% _' gdouble dy = map[curr, 1] - map[prev, 1];
% B. G3 |3 H8 Q+ ^double pathLength = Math.Sqrt(dx * dx + dy * dy);
$ F' j5 G2 Q6 |+ P) @2 @$ T
// calculate the path length from the first city to the last
for (int i =1, n = path.Length; i < n; i++)
{
// get current city
* _" O$ _0 k1 @curr = path;
( q/ d* D9 b6 F! D7 N! a% ^0 k/ O( {
// calculate distance
! J$ i+ V5 m$ g- C! _dx = map[curr, 0] - map[prev, 0];
' N1 R# |) O( bdy = map[curr, 1] - map[prev, 1];
, N6 B) \1 k, t8 g" ZpathLength += Math.Sqrt(dx * dx + dy * dy);

// put current city as previous
/ Z& t6 \- c- Q$ c+ g* k# H" ~prev = curr;
}
2 w3 M9 k/ m/ C# [# T: u
7 ~; f- a7 P  x9 H2 Areturn pathLength;
% X( C, m/ p) y& M$ G6 j+ w}
}
/ R/ A* Y; D4 |& j6 M: D& t. r}
& @3 _# n, w+ o2 j8 R: @
' {4 N1 `) O4 e5 L4 L/ z! G2 W5 ~
[url=][/url]

( n' Y$ _7 F9 ^: W

, [8 s; C: y0 M$ o/ f1 s* n

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

7 Y9 k+ u# R* y+ D# h* G[url=][/url]
GenticTSP类using System;
3 `7 \% J* m0 ~" q! Jusing System.Collections.Generic;
using System.Linq;
using System.Text;
8 G+ r) }  Q1 H# E9 `) W$ ?  \using System.IO;

5 V6 R5 E$ A" \" _* lusing AForge;
( R# i  y& }, h3 w1 Husing AForge.Genetic;

" @% s. G+ \& j- B0 J8 m
% P& p: u) S) E# i8 }- l6 S, [namespace GenticTSP
. s) p9 C2 y8 Y{
class GenticTSP
{

staticvoid Main()
& q4 y1 N: f8 {7 [4 C% l{
' k' a, n6 e( q) X4 a; eStreamReader reader =new StreamReader("Data.txt");
0 E+ p5 d# {) X7 t, L
int citiesCount =31; //城市数
+ [" V  g  y, i( X% u: y- w+ e
int[,] map =newint[citiesCount, 2];

for (int i =0; i < citiesCount; i++)
$ U( o1 r, Y) `+ d{
string value = reader.ReadLine();
string[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
% X% S& D0 l- U7 n5 Z}

// create fitness function
TSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

) Z2 ~0 H' K& D) F7 ?2 T) yint populationSize = 1000; //种群最大规模

- d) Q2 S- J* R1 Y) j, N( r# ?$ |/*
* 0：EliteSelection算法
* 1：RankSelection算法
; A! @2 u0 Z! r, @* 其他：RouletteWheelSelection 算法
. ^4 P5 f: r1 z0 J/ l" O' ]: b* */
# D2 c' M3 I8 g4 p4 n, v8 I  Lint selectionMethod =0;
2 {6 i& L6 X; o/ I. I/ f6 [- q1 B
// create population
: w" X+ L+ |" ^0 q* ~2 ^( APopulation population =new Population(populationSize,
3 a* q+ @3 m* Z6 r7 n; Unew PermutationChromosome(citiesCount),
fitnessFunction,
, F9 `  |  K8 D1 T( k/ A% R(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
+ Q$ V: q9 U1 T(ISelectionMethod)new RouletteWheelSelection()
( k6 T1 g% n' P; V);
) }+ ~% v6 S6 R% r
' B( ~! y- R( ^% y// iterations
int iter =1;
int iterations =5000; //迭代最大周期
9 x& o- L" U3 n$ h- }# I
// loop
8 u! }3 c7 ]6 u, M+ [while (iter < iterations)
2 Q) D, `. ?0 m9 `' ^$ f{
! o7 Q, O1 M8 n- J2 c// run one epoch of genetic algorithm
population.RunEpoch();
: t7 H- a, D5 X# b! T
$ d! f' t* f$ ~5 n; A4 p// increase current iteration
iter++;
}
% o2 ?2 S1 w  x* K3 T& U) k
/ s) A7 n2 \9 T9 M& {+ K) [  USystem.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
* X9 l, c) O: F# h3 _System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();
! F8 G$ x4 ~: g( W9 o. n
) A1 i) L$ z% ~8 p1 e}
}
}

- a! Q  N% S2 D) x
[url=][/url]



" Z1 K) I9 j( @
' j" W2 G9 y! y1 `# |

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

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

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

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

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

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

4 q$ F$ M, K1 `* x- u$ e
# ?2 e! k1 b' P3 S( S: J* J/ r

" G2 n$ G" E; B- s/ g$ d7 \