数学建模社区-数学中国

标题: 【转】优化算法入门系列文章目录（更新中） [打印本页]

---

作者: 我要吃章鱼丸子    时间: 2016-4-8 14:13
标题: 【转】优化算法入门系列文章目录（更新中）
遗传算法入门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 ) ，也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。

# @8 g2 d3 S0 \4 A$ N: D
一.进化论知识

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

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

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

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

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

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

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

7 x+ F& \3 c' O1 }% `6 d* m3 [1 D4 w

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

二.遗传算法思想

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

! H9 Y+ k' K8 v* U

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

$ P8 }; J/ {& a0 \5 e[url=][/url]
* h+ C8 o: H. a4 ]轮盘赌算法/*
. N) u" A/ ?- K0 X7 W' o* 按设定的概率，随机选中一个个体
! N' ]2 R+ B! N5 `* P表示第i个个体被选中的概率
*/
int RWS()
{
m =0;
r =Random(0,1); //r为0至1的随机数
% h3 k  y8 k# G' Q1 b4 A( Ifor(i=1;i<=N; i++)
3 n+ Z: p+ ]% ]& j: r{
/* 产生的随机数在m~m+P间则认为选中了i
* 因此i被选中的概率是P
# y$ p5 l2 s. u6 t9 s$ V*/
m = m + P;
2 ^6 f: L. h! E! gif(r<=m) return i;
}
}

[url=][/url]
. Y6 i: u6 b4 w
  A6 }3 T! I# [1 p1 F- ?0 ?
; e: ~- K9 U; Y5 n

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

" C/ P$ U9 t% K4 J* B7 Q
8 A/ C9 k$ V6 P' `- a. _& A三.基本遗传算法的伪代码

[url=][/url]
$ U: O" u! e- F- P" x. Y; G基本遗传算法伪代码/*
* Pc：交叉发生的概率
* Pm：变异发生的概率
  p! A# H3 n1 N8 @" O  k* M：种群规模
* G：终止进化的代数
* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
# u# J0 g+ _5 @' W8 ]*/
初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
6 ^, c* R' V5 _( s
6 t7 i9 S. W7 \$ ?8 {do
{
　　计算种群Pop中每一个体的适应度F(i)。
5 [8 f8 s3 n+ _4 e8 Y, `" s　　初始化空种群newPop
9 A+ E% C$ H( m4 q# C7 P　　do
　　{
( R! Z2 X  D) @9 @　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
9 _, a5 c+ T. l+ h; w　　　　if ( random ( 0 , 1 ) < Pc )
　　　　{
2 ~0 g2 W0 I8 Z/ x0 K" L　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
( P5 p  U7 M9 `4 \　　　　if ( random ( 0 , 1 ) < Pm )
) p4 o. m& O* ~) @* E0 p% w1 L　　　　{
0 X4 P$ N: q! H# L　　　　　　对2个个体按变异概率Pm执行变异操作
3 S! p6 M2 r0 a8 [! v9 A, i　　　　}
将2个新个体加入种群newPop中
4 A6 }7 ^! t+ N, i0 h; r} until ( M个子代被创建 )
) }0 v# q4 J% t% \* z用newPop取代Pop
}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )
; d/ `. R% \" G: @

) T! S0 I4 `. C  z$ K[url=][/url]



0 Y5 j4 ~; k( \9 ~! _' B. Q四.基本遗传算法优化

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

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

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

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

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

0 F, f- `$ I" S% Z/ |* L

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

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

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

图1. AForge.Genetic的类图

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

4 h4 }  J4 @  b+ i[url=][/url]
1 s4 x8 ^; P. u3 r) R- I13042312
/ J* x% [. K# x36391315
) \6 Z' W( D, b41772244
' ^4 v' }8 {+ J# c8 S+ j6 ~37121399
7 _7 Y3 m6 `( y8 \! Q8 h34881535
( o6 l/ c- B: W, C33261556
1 B: Y. b* t) i+ J, A! v3 e/ N32381229
* t- _' g* l- Q: i41961004
4312790
9 x1 {% ]0 n/ ~1 E4386570
( b, y5 `7 C; D" P: W30071970
8 v: B: H+ Z+ a# r4 M25621756
  w- E* J% i: v9 F- w) q27881491
23811676
1332695
37151678
7 U/ I6 w6 M# Y- V6 y6 r39182179
! ]& \5 A5 Y% V40612370
: A( f2 h  v5 h& S8 z* l; b% N37802212
36762578
40292838
42632931
' Z* d; J4 ]. T0 u8 }7 L34291908
35072367
33942643
$ D9 n9 k. Z: i$ g34393201
& H: d1 Z1 d% E. K5 R% ^29353240
31403550
) O, T  E+ r4 B* l( h% P5 x25452357
27782826
23702975
[url=][/url]
/ K9 K: O5 P. H& G0 ~2 l8 V
, c6 @, u# i* ^- ~& N! Q9 S8 w

' S# c2 F; _: h) u& R: t5 E- m2 |0 k
% q3 F$ m) l$ @) t" Y, Q

操作过程：

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

. w8 I! T# f1 X. k6 L[url=][/url]
TSPFitnessFunction类using System;
9 v9 ^. X  Z, t$ Eusing AForge.Genetic;
0 X! y" }7 Z, v
. @8 f5 J9 M( ?7 a9 M. l$ Lnamespace GenticTSP
{
///<summary>
/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
publicclass TSPFitnessFunction : IFitnessFunction
4 I$ J% k) T# Z; W% h{
% z8 l6 ]+ V3 Z2 ~  {// map
privateint[,] map =null;
4 C  ?) _+ d* v3 j4 k+ g% |
. D, i4 ?" i$ R6 f7 }; ]$ V+ z// Constructor
) E. i. g- }1 c  s8 \$ x; K7 }public TSPFitnessFunction(int[,] map)
{
this.map = map;
9 R$ N( u1 s  M+ `+ B* ]}
; ^- D. j7 C( f! j, w0 o) y
7 U6 n' L$ ~$ M& y* e///<summary>
, @; C5 z5 Y9 {2 i5 t) t2 c/// Evaluate chromosome - calculates its fitness value
///</summary>
6 ]" A0 ^% }3 S1 q# Fpublicdouble Evaluate(IChromosome chromosome)
+ O7 }. N, a; X8 X& p+ D; \* h' c{
return1/ (PathLength(chromosome) +1);
0 w) O2 r9 e; c  B" N  T. Y) a}

3 i( Z" J: p3 e( w. W5 _///<summary>
# r" f) e) s! z. A/// Translate genotype to phenotype
///</summary>
) B5 K% }, W) a, g: j( e/ u9 jpublicobject Translate(IChromosome chromosome)
{
return chromosome.ToString();
8 K+ Z+ j" Z$ ~* |# N}

) N+ l" c& j+ T" V/ j5 n- s///<summary>
; O- o  @( v1 ?5 `/// Calculate path length represented by the specified chromosome
///</summary>
' k  A' I# x: Vpublicdouble PathLength(IChromosome chromosome)
{
6 u7 \8 X/ t8 x// salesman path
9 y7 s# V3 C& Q% H7 V) d7 sushort[] path = ((PermutationChromosome)chromosome).Value;
1 y9 u: d2 s: p1 P  Q: }5 `
- S" n; ~: x+ x% O6 |8 _// check path size
if (path.Length != map.GetLength(0))
9 A: O+ Y3 P8 ^5 `9 \{
. l4 r6 Q4 [% y! `- Zthrownew ArgumentException("Invalid path specified - not all cities are visited");
$ T% T& ?. U' e" @4 d5 A2 d5 n}

// path length
int prev = path[0];
int curr = path[path.Length -1];
2 w0 Z5 d9 }! m' I4 }' i4 Y
// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
double dy = map[curr, 1] - map[prev, 1];
6 \# V8 ^1 R, M, U0 q  o; fdouble pathLength = Math.Sqrt(dx * dx + dy * dy);
' a& O9 A" B: W/ p7 w! D6 ~8 U6 T! Y
3 U: i5 J/ n2 A- ~& c// calculate the path length from the first city to the last
* q! D$ ^; @0 L& Gfor (int i =1, n = path.Length; i < n; i++)
( B' [6 @! l, |{
// get current city
curr = path;
* b1 O+ z6 h! K
// calculate distance
6 B- J$ R4 [9 Pdx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
pathLength += Math.Sqrt(dx * dx + dy * dy);
4 W1 i! [5 s. P! D* z  ]) U
// put current city as previous
prev = curr;
}

; ?" y9 ?! r! treturn pathLength;
}
}
- _  [  f: ~: t; |}

9 k* U) q8 L$ d3 P
[url=][/url]


8 ]+ k" ?3 b% ], ]

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

[url=][/url]
3 ^7 {' l, h8 fGenticTSP类using System;
using System.Collections.Generic;
using System.Linq;
. e6 ~' W2 h: y  ]& U+ ]using System.Text;
using System.IO;

using AForge;
using AForge.Genetic;
8 G2 ^  E$ j- `: m1 ^3 n: n
, g7 i4 W! ?! A# E2 _
/ D  M' r& R4 O7 `4 I4 B& onamespace GenticTSP
* x$ X3 {3 y* P- \6 V{
: J1 ?' Q$ ~. X) {class GenticTSP
{
1 o: i+ i7 F5 l% \' H' N" o3 h
1 b7 V" ?' M( o3 O7 bstaticvoid Main()
% c. |9 n& Z2 d" l8 e( X7 _  n{
# A- V% l; I3 KStreamReader reader =new StreamReader("Data.txt");

' s  G0 t1 `7 ~; p* Bint citiesCount =31; //城市数
; _' s  [: [$ I  c
int[,] map =newint[citiesCount, 2];
! x0 t! }: d% Y; j  L
8 [7 I. ?/ _4 F7 Sfor (int i =0; i < citiesCount; i++)
. C- W% m, D4 z% u& {" W/ k{
- e6 t1 [1 k7 |" zstring value = reader.ReadLine();
; P; F0 J; z: S' m  T) S7 J. D3 ]string[] temp = value.Split('');
% r% |8 s9 G' j1 N0 wmap[i, 0] =int.Parse(temp[0]); //读取城市坐标
2 l+ _2 [8 U4 O/ Z7 o8 @map[i, 1] =int.Parse(temp[1]);
: P* |- X% |* U- O( s3 ]0 v& c}

/ r8 r+ G8 a$ M; B) G6 ]// create fitness function
% n. G8 H# z( K) bTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

/ I0 {% Y' b3 A. j8 g) j. gint populationSize = 1000; //种群最大规模
, b/ r" J+ d2 m2 D; q6 X1 |; x& Y# O
/*
7 Q) f9 H: R6 F" l* 0：EliteSelection算法
* 1：RankSelection算法
0 |5 Q0 e4 B+ z" N( o1 q# v7 T( o9 q% [* 其他：RouletteWheelSelection 算法
* */
int selectionMethod =0;
) \# F( N( Z( x* u8 v: z/ Y
// create population
Population population =new Population(populationSize,
new PermutationChromosome(citiesCount),
fitnessFunction,
(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
(ISelectionMethod)new RouletteWheelSelection()
);
, u/ x$ ]6 e1 l, O' E7 K4 |
/ \: y( @- ]% u// iterations
( G! J1 U4 i1 y9 g* ?# uint iter =1;
int iterations =5000; //迭代最大周期

8 e0 q5 }3 z" @) v; t// loop
while (iter < iterations)
* l% e6 P+ t4 h! X% m  v4 J6 M{
8 f0 P/ b% }9 L9 N2 H( k// run one epoch of genetic algorithm
! }4 j) q. d2 x! H& v5 y# Gpopulation.RunEpoch();
/ V7 l9 D. ]- [, }# e# f& [4 ~5 |
// increase current iteration
9 V; M( _0 {: @$ H/ Z4 a1 y( biter++;
}

6 }# N, e  p2 l+ D+ ?. z6 e! s( RSystem.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
System.Console.Read();

}
9 Y8 \; O: h- x8 o# |- n0 W/ b( `}
}


[url=][/url]
. l) S+ W: _- F, W) c- k8 k* d

' O3 ?6 ^( y4 `' s$ r% L+ `
: i) e$ I8 ?* W1 n+ T
% f/ F; ]9 l$ A  k- d$ w

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

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

. f! K$ O; K! ]

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

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

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

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

" J0 i2 u: {/ x7 D4 k/ b. I0 B


; V' O- }8 w5 Y6 }: N/ y5 Z

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5