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

我要吃章鱼丸子

遗传算法入门Posted on 2010-12-23 13:12 苍梧 阅读(103275) 评论(39) 编辑 收藏
2 a# V4 ]2 k9 D% i2 E
5 a1 \! j' _6 H7 h

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

0 [# \- ~! ^7 q( D) V
一.进化论知识

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

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

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

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

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

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

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

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

3 V6 m% o+ |$ R* N3 x
4 j, m+ W4 ^% _! F/ t/ z二.遗传算法思想

　　借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化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个最基本的操作：选择，交叉，变异。

1 t3 z! r7 ?3 A# F5 s* ?+ U

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

5 ~( Q: I1 X+ `3 s( P  ~5 q  x[url=][/url]
轮盘赌算法/*
# V8 B  }( i$ L& b* 按设定的概率，随机选中一个个体
; G0 ]  x4 O- z4 R' d* P表示第i个个体被选中的概率
  L, ^- ^9 f% i5 t8 J5 f# Y*/
int RWS()
{
' b. U9 P. Z  F( O; Jm =0;
4 |9 c  [# {. L3 Cr =Random(0,1); //r为0至1的随机数
! |2 `6 t8 e$ g& R7 {1 Efor(i=1;i<=N; i++)
{
/* 产生的随机数在m~m+P间则认为选中了i
* 因此i被选中的概率是P
*/
m = m + P;
if(r<=m) return i;
}
}
5 X1 G4 i8 f' a4 @+ D( v1 p
[url=][/url]

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

( M( @2 N0 H  c7 }" f

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

三.基本遗传算法的伪代码
% z& n7 N# }$ ~/ R, s
[url=][/url]
基本遗传算法伪代码/*
* Pc：交叉发生的概率
" T6 g% t2 ~9 q8 N/ O# N* Pm：变异发生的概率
* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
% y" o9 d0 S4 j  o7 W. L  i*/
; G' z" ]$ T( e' k初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
5 ~6 T8 n  p! G0 w- `2 f: C/ q6 s5 A
do
5 Z+ w% Y# _  t0 f{
# P7 T9 G; t' z　　计算种群Pop中每一个体的适应度F(i)。
　　初始化空种群newPop
　　do
1 N9 Q7 g) @/ [, K, Y! V9 h, e　　{
  G0 V' ^$ p! V7 C: M9 x; d. u7 Z　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
, h  ^9 |9 E' E　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
& t' Z" s2 S8 u; G# r　　　　　　对2个个体按交叉概率Pc执行交叉操作
7 N7 I( h8 c0 ~% g0 H2 c6 i& ]　　　　}
$ k4 |" ^" d, @8 L　　　　if ( random ( 0 , 1 ) < Pm )
　　　　{
& \8 z: h( B8 {' c1 ^7 x( i) H　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


[url=][/url]

2 Z: R& f3 L) t" M) l
; ^5 s" w/ C  f$ F$ a% U. f, u) p
, F+ H3 J8 ^: p: Z9 T( d$ S四.基本遗传算法优化

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

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

$ P9 Z( t+ u0 j

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

图1. AForge.Genetic的类图

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

[url=][/url]
13042312
36391315
41772244
4 k1 @8 G$ B' }" [: L7 c37121399
4 |" x% i6 a) v+ h# q34881535
33261556
32381229
9 c+ S4 W1 g. d  x) M9 o41961004
4312790
4386570
30071970
25621756
27881491
23811676
1332695
9 ~" |# j5 |: Y  w9 r7 V- v$ y- O37151678
% W/ F' [- g# C# e! R: m  d; [' H39182179
0 W) Z% S3 A6 T: s, a40612370
$ o5 M& F  K' n/ v. L  i  G, W37802212
36762578
40292838
4 s6 x. r. k4 y42632931
" X, Z; p% j1 g# ^34291908
35072367
  G7 d, }: i& M7 \" I9 T33942643
; ^1 u8 l) @' C8 ^  d  s2 G; ^7 J34393201
29353240
! e% l! d. v- `6 H( o8 B/ F31403550
25452357
27782826
23702975
0 q0 G! u- a, d2 o( Y2 Z[url=][/url]

) f$ P0 V) y. C  s; s- I


/ y/ u2 ~/ 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;
* d! F' E8 Y  k& v/ Wusing AForge.Genetic;

namespace GenticTSP
0 f. Y% V/ R2 x) E3 l& R/ n6 Y{
$ b8 n! ~2 P* N6 c+ U; ]8 x///<summary>
. W! |4 W0 E; O/ H/ J9 x) G' i* [+ s/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
& c# k! A0 U1 I* Apublicclass TSPFitnessFunction : IFitnessFunction
5 _; ~( [! a" V) w( u6 E$ Y5 k6 ^" p{
- s& r7 {5 {; L- t- P// map
$ ]1 L6 t1 W2 Q5 X( T$ }privateint[,] map =null;

// Constructor
public TSPFitnessFunction(int[,] map)
{
this.map = map;
}
; ]) P' L8 q/ }! }4 i: t1 z
' r' j8 \& |) K7 }///<summary>
/// Evaluate chromosome - calculates its fitness value
///</summary>
* p2 o. n7 \6 P' }6 Q2 E- y6 {publicdouble Evaluate(IChromosome chromosome)
( Q- O' [. D5 |+ @% v! p6 K{
return1/ (PathLength(chromosome) +1);
9 P' k4 L. M8 l8 }) J8 @0 M4 w}
3 ^2 n+ Z- `- L
! a- w8 [7 W' ?& P9 M7 _///<summary>
3 a. O% b$ e8 }0 }: s/// Translate genotype to phenotype
+ {1 f2 |; i2 P7 _- i0 o- j( g$ Y( ]///</summary>
( \; V- s, H2 y# @" epublicobject Translate(IChromosome chromosome)
{
return chromosome.ToString();
8 b. u/ r8 g; e. U7 o7 d}
- n) u4 F& f0 `+ ]. I5 o
: e4 V4 P7 @0 Z* w2 g///<summary>
% W& j9 l  e% n% ~* e  o: s/ ^/// Calculate path length represented by the specified chromosome
///</summary>
publicdouble PathLength(IChromosome chromosome)
7 _% H! o2 @- v. M2 v{
// salesman path
( Y/ u0 v  c5 [ushort[] path = ((PermutationChromosome)chromosome).Value;
7 R* J  q$ L5 d9 y3 L3 e
. r! y. @. o0 H. ^: D+ H// check path size
1 q' q9 q$ i: Z1 {5 eif (path.Length != map.GetLength(0))
0 t  F5 C" w3 x7 x1 N9 F# L6 G8 X{
- ?8 G4 @; I# O) s0 Jthrownew ArgumentException("Invalid path specified - not all cities are visited");
0 R1 e! Y1 C1 V  g' ]}

// path length
$ z/ j# i6 t: C! t1 `0 u( g! `int prev = path[0];
int curr = path[path.Length -1];
0 D: Q/ _; k; A: [) L% J  i
- J( {5 T/ x/ o4 T7 C// calculate distance between the last and the first city
  N7 t6 e2 ^  e* ?, [- Y! Zdouble dx = map[curr, 0] - map[prev, 0];
: _, y* X( F+ Sdouble dy = map[curr, 1] - map[prev, 1];
double pathLength = Math.Sqrt(dx * dx + dy * dy);
; A- Y8 I( g5 N
- ?+ p8 X7 U+ ?* S// calculate the path length from the first city to the last
2 D. h. V! ], i7 Ofor (int i =1, n = path.Length; i < n; i++)
. \# @7 i& w" @{
4 X1 S) Q# P" q; b, u# S5 r1 z// get current city
. a' K; n9 ], ^& e9 Q% Ccurr = path;

2 n$ O% @/ j! H0 T4 x9 D// calculate distance
dx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
& Y7 B% T* w6 J9 \0 k: bpathLength += Math.Sqrt(dx * dx + dy * dy);

7 c" H, q5 ?* `3 w8 c" s2 \// put current city as previous
prev = curr;
}
0 Q1 d; q7 g0 k
return pathLength;
1 ]$ U# W2 [3 y3 l$ B' o; N}
5 ~6 k! j1 g9 n2 @- ^}
6 ]3 o2 I$ B  x  m+ v5 V}
5 n+ G" j$ H$ N
% h/ W9 k* N' H
[url=][/url]
$ N8 P" m( B( |. M6 O/ c$ z


7 o7 a3 b% R0 M8 q* O7 J$ ~" c; Q; N

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

[url=][/url]
0 w! o  |4 t( T0 y6 ?" a5 H; }& CGenticTSP类using System;
" I- _% {4 O' s$ c" Busing System.Collections.Generic;
using System.Linq;
using System.Text;
' {% Z1 C, w- y* dusing System.IO;

using AForge;
using AForge.Genetic;
8 l9 N3 ^3 h% W6 d. ?

$ Z' A  {4 t& f4 s% dnamespace GenticTSP
& n" x5 J; s1 C1 `! [{
class GenticTSP
{
7 {" R8 b+ n  B2 a6 e
staticvoid Main()
{
StreamReader reader =new StreamReader("Data.txt");
6 t' G# M8 D, d2 o) r
int citiesCount =31; //城市数
3 V4 ^1 K1 g( W" [6 m9 B
int[,] map =newint[citiesCount, 2];

for (int i =0; i < citiesCount; i++)
{
string value = reader.ReadLine();
' B* z5 v" @$ j6 f0 [* u8 R7 qstring[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
$ z- Z5 ~: ^/ F% [3 v2 {" q% M( B}
, @2 `) X7 }$ O# h  b6 s- W8 ?. f3 q
5 \$ U4 P: C9 z& g% E2 \3 x8 ~// create fitness function
! l6 Z$ c; Y* Z4 H1 @8 k' }; nTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);
" R; ~2 B, {; [) T+ L! n
int populationSize = 1000; //种群最大规模

/*
/ X8 S: T+ M! V$ R& R* 0：EliteSelection算法
( g& _- i7 i) A# i, b' @' }" i* 1：RankSelection算法
8 J/ j& p3 I! d3 i  C* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;
2 X8 m3 }1 f* m# l0 M$ T! v
  J! n/ u7 V# G2 M// create population
# \$ x/ U5 b+ c# q) @- }0 Q2 ?6 P# m9 {Population population =new Population(populationSize,
new PermutationChromosome(citiesCount),
( t/ O' S: \3 Z6 sfitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
1 A- ~8 M0 w0 k0 w5 y1 Y/ e- }(ISelectionMethod)new RouletteWheelSelection()
3 P4 x! l  h9 ^% Q/ R. d& Y& C);
2 o4 _: y- r8 j/ C
// iterations
int iter =1;
0 h1 T7 a. m0 Wint iterations =5000; //迭代最大周期
  d. G- W2 ^  o2 N6 n6 y/ u
// loop
# h* ~; V# r1 F  U$ iwhile (iter < iterations)
# c* \7 Y2 a' B1 `{
- S% m/ K* m* V5 |7 L2 F1 c5 I// run one epoch of genetic algorithm
' J+ K) H, @$ a! Cpopulation.RunEpoch();
, v7 P: S. ?- g. K6 t6 V: o
6 z6 {8 o2 ~! z3 K; A6 t// increase current iteration
, H6 a2 W4 V9 n" w* hiter++;
$ R( d6 `9 n1 x7 u}

System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
. F* @( G$ x  Q3 I3 @' ~( i/ _System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();

}
}
/ M3 P5 X1 O: ^. ?+ |# b}


2 K! R" N9 c, [: U[url=][/url]

/ `0 _/ a+ e+ w# u3 V; m* j

9 J- V' @' r# E6 h0 a$ ^, ?- Z; S& t
. m) i1 ^# p+ J0 p, G$ ~( T) v

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

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

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

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

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

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

/ s$ o. b4 F! E/ U, N$ j
% Q+ ^! T, J/ f4 y9 @  c0 q