数学建模社区-数学中国

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

---

作者: 我要吃章鱼丸子    时间: 2016-4-8 14:13
标题: 【转】优化算法入门系列文章目录（更新中）
遗传算法入门Posted on 2010-12-23 13:12 苍梧 阅读(103275) 评论(39) 编辑 收藏
& K# D# V2 P5 ~) k

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

　　1. 模拟退火算法

　　2. 遗传算法

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

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

; S0 G3 u4 ~, t1 Y: C一.进化论知识

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

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

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

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

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

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

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

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

4 x& d7 Y% d% H* ~6 B7 L, p% |
* x* G- y7 i* w3 t! I$ n' V3 ~二.遗传算法思想

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

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

- [" O; k; H: h" |6 T/ e

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

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

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

[url=][/url]
轮盘赌算法/*
/ o! P. L$ F) h( X! ~* 按设定的概率，随机选中一个个体
* c0 H& f1 n- M7 Y) D' D* P表示第i个个体被选中的概率
*/
int RWS()
{
m =0;
1 x/ w: l/ k9 hr =Random(0,1); //r为0至1的随机数
for(i=1;i<=N; i++)
  u" d6 O6 Z7 d; h  l4 ]+ z/ M{
/* 产生的随机数在m~m+P间则认为选中了i
* 因此i被选中的概率是P
*/
m = m + P;
, Q- W2 ?0 V' Aif(r<=m) return i;
9 ]% P' R2 ~" c; \}
}
$ J8 t- J) \5 }9 V9 Z
6 R- \- @8 {0 Q8 x. @$ i[url=][/url]

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

交叉前：

00000|011100000000|10000

11100|000001111110|00101

交叉后：

00000|000001111110|10000

11100|011100000000|00101

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

% z! N; o$ t# Q

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

变异前：

000001110000000010000

变异后：

000001110000100010000

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

$ H5 G! l3 m/ X2 B" N  e三.基本遗传算法的伪代码

[url=][/url]
0 k& X0 p' q+ Q" q+ Q基本遗传算法伪代码/*
: D9 I1 b( z5 C* Pc：交叉发生的概率
3 I& f  r- v9 B* Pm：变异发生的概率
4 y* ~" \2 a4 c# ?" `. n* M：种群规模
* G：终止进化的代数
8 Z! X0 h' O8 k" t* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
: a+ X& A+ }! f/ N4 `; L- d*/
& c, D4 p; ?( |) Z% a% _7 ?/ f初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop
6 z$ t$ Q5 f" G' \3 }. e
9 A1 Y& t6 `" ^7 W  |do
" e& L% H" E) P9 A3 J7 M{
　　计算种群Pop中每一个体的适应度F(i)。
; z+ M: ?0 g# y% Z　　初始化空种群newPop
" b* [( T  S' V　　do
　　{
　　　　根据适应度以比例选择算法从种群Pop中选出2个个体
　　　　if ( random ( 0 , 1 ) < Pc )
; q$ G( a# }3 Y0 `: [　　　　{
: C1 c9 I2 ~& R" ]# c7 L　　　　　　对2个个体按交叉概率Pc执行交叉操作
　　　　}
6 j% R( v- R8 _* v+ C8 b　　　　if ( random ( 0 , 1 ) < Pm )
0 e3 ]% `1 K  Z9 W! P  n4 ^　　　　{
& o, Q+ f4 _+ x- D+ h1 V　　　　　　对2个个体按变异概率Pm执行变异操作
　　　　}
将2个新个体加入种群newPop中
} until ( M个子代被创建 )
用newPop取代Pop
) o+ E) o) s# a- ^}until ( 任何染色体得分超过Tf， 或繁殖代数超过G )


+ r- d/ h3 `! ][url=][/url]
! x) X1 W9 U; W7 L' T

( b* u9 e* A& E; E4 z  r7 @4 Z  X0 M1 |. [
4 }2 N+ j7 m3 A  K3 A四.基本遗传算法优化

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

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

& _! G2 r# v4 d

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

. W) N6 {& T# ]" i

图1. AForge.Genetic的类图

. L1 u) f) o% s' D

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

[url=][/url]
; D( A# Z9 q' ?* ?& p3 b/ n+ r13042312
( T; n# a9 O4 ]; _7 S% I, d* f36391315
41772244
37121399
- U) n7 l+ _  b- Q% ^34881535
33261556
1 b$ Y5 g, l2 e+ H7 S8 d32381229
41961004
4312790
6 l! }: ?: F2 g% ?, B$ d4386570
# Y3 ]. U! Y; u. s1 K) F& Y30071970
' s/ f& S" d7 V8 y7 J% x7 Z25621756
& i. F" _3 e5 ^27881491
. C- v( ^: Z  R( r9 ~7 p23811676
1332695
37151678
4 r: _. V4 h% l) ^6 |: _& }39182179
40612370
37802212
36762578
40292838
42632931
$ n: ~( o2 L5 S$ n34291908
35072367
# z4 M+ D/ ]& u33942643
9 d  L  Z& w% q+ ?. Q34393201
29353240
31403550
: Q6 `, b' A: m  o% d25452357
2 _4 G: v# S! q3 Y27782826
23702975
[url=][/url]
, C8 }2 t% D' i! H/ b9 \" j/ I- |


# U1 _1 D! k5 ?* K4 _2 S

操作过程：

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

2 I5 B& B- h/ `[url=][/url]
3 ?2 c1 m3 }" ~* A2 MTSPFitnessFunction类using System;
3 `/ I  A  C* m1 b! vusing AForge.Genetic;
) w  J  X1 ~) y
namespace GenticTSP
{
///<summary>
/// Fitness function for TSP task (Travaling Salasman Problem)
///</summary>
3 c! a0 t9 R; h# {, }0 n& [5 gpublicclass TSPFitnessFunction : IFitnessFunction
# d1 e! N, p& e% W3 s  Q{
5 l( E& X' O: o) K. e& J" g// map
) A2 B9 x0 ?4 ]6 W' {$ Fprivateint[,] map =null;
4 y4 c( ~9 K2 }& n
// Constructor
4 d1 y, ]) X3 e2 X; q+ ?. K- Epublic TSPFitnessFunction(int[,] map)
6 I, y) _6 V; p3 M% b: J7 c{
$ a% k( x5 |: v& a' Jthis.map = map;
}
( z0 f" w0 A! F8 ]
! c& C2 `+ r# N///<summary>
/// Evaluate chromosome - calculates its fitness value
///</summary>
7 t" {, J6 S) d3 e8 O3 V" bpublicdouble Evaluate(IChromosome chromosome)
{
8 {# m8 M6 `* ]  k" h2 I9 kreturn1/ (PathLength(chromosome) +1);
1 V* x/ |* W* l$ u- h% z1 |* ^}
( X8 j5 m& [7 b) G7 @+ l' h
///<summary>
+ m- N5 x& \1 k2 ^/// Translate genotype to phenotype
///</summary>
publicobject Translate(IChromosome chromosome)
% y( N, ~% `9 A% H{
return chromosome.ToString();
}
* L$ ?) G3 k# R! i
& e' b# l% w; d+ I5 B4 y; n5 ~3 X///<summary>
/// Calculate path length represented by the specified chromosome
///</summary>
8 B1 Z* G* {3 t& a3 Jpublicdouble PathLength(IChromosome chromosome)
{
" d$ B: ~8 M' n5 y  W- i1 N// salesman path
ushort[] path = ((PermutationChromosome)chromosome).Value;

// check path size
if (path.Length != map.GetLength(0))
{
' S3 z3 A' o0 i7 }thrownew ArgumentException("Invalid path specified - not all cities are visited");
}
: \1 N. p+ g# G) q0 C3 u
9 a  a4 }1 A( V- @) O0 A& ~// path length
3 S3 t; H. j$ n4 y7 qint prev = path[0];
int curr = path[path.Length -1];
$ X8 |) h5 h7 R; P8 h3 T
! e+ D* n3 k: L# z& e4 h+ l& [// calculate distance between the last and the first city
double dx = map[curr, 0] - map[prev, 0];
% w) Z: A2 }+ j: I- bdouble dy = map[curr, 1] - map[prev, 1];
double pathLength = Math.Sqrt(dx * dx + dy * dy);

- o2 t. C/ ?. Q/ H" P// calculate the path length from the first city to the last
/ B( o% Q" ]4 [  D8 \for (int i =1, n = path.Length; i < n; i++)
{
// get current city
8 X- a, P" T* s8 `( m# Icurr = path;
7 v* ?/ Z- R) j: o6 \3 u' c9 B# g
* l4 c6 d4 N4 c" ^// calculate distance
+ b: a: b% P" N* Pdx = map[curr, 0] - map[prev, 0];
dy = map[curr, 1] - map[prev, 1];
6 z) X* d& G* F8 e! z, R$ g8 x- ZpathLength += Math.Sqrt(dx * dx + dy * dy);

0 y1 @1 g2 k) a) d( }7 _. f// put current city as previous
prev = curr;
  t) E5 t* t' ~4 H}

' Y3 T! |7 [7 f1 `8 [5 R# o. p. nreturn pathLength;
}
}
}
' w( R  b" f7 e
" `  Y" t/ ]  t4 y7 X9 V
[url=][/url]

1 l4 \5 j1 ~; e" F9 o
/ R, S- f. y6 U6 E2 V+ w

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

[url=][/url]
+ D6 k8 M) I: f* bGenticTSP类using System;
* h. N. E# F( m8 K+ M5 l% gusing System.Collections.Generic;
* g8 m! J9 e, l/ M, d: W5 ~3 ousing System.Linq;
using System.Text;
; S+ L) [7 S+ N, ^using System.IO;
3 y# e( l- N$ m7 u
using AForge;
using AForge.Genetic;

3 r# n2 l0 H) @, W
6 |: {( r: u% Unamespace GenticTSP
{
class GenticTSP
- U4 p' ~  S8 E; {, V: l1 N{
9 `/ m2 S5 J: V/ X
5 g: o! {2 R' o$ Ustaticvoid Main()
# {# V; G! g1 l: B{
StreamReader reader =new StreamReader("Data.txt");

* A. a# q$ U* tint citiesCount =31; //城市数

, G. ~# C- z1 [int[,] map =newint[citiesCount, 2];
0 }: Z7 J. B, |6 r3 F$ y: X
for (int i =0; i < citiesCount; i++)
  l* ]' ?3 g: ~8 Y7 J1 E{
string value = reader.ReadLine();
string[] temp = value.Split('');
map[i, 0] =int.Parse(temp[0]); //读取城市坐标
map[i, 1] =int.Parse(temp[1]);
/ P; c. D# I( }( I7 n; l# G}
4 `: H: J2 [* A- n8 C
, k: {, l" v* |$ e* y! M// create fitness function
- J/ C5 k( [3 JTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map);

: l. Z6 b, s8 X, A* h+ Qint populationSize = 1000; //种群最大规模

9 u# a/ j7 u( B2 M$ F$ D- n/*
3 W; I9 A3 N8 b* 0：EliteSelection算法
! a& k5 B) Q6 z6 W* 1：RankSelection算法
) h& L/ Q! ~0 u; I4 Y( @$ b* 其他：RouletteWheelSelection 算法
* */
9 O# O1 R5 |: f7 h8 N( aint selectionMethod =0;

// create population
Population population =new Population(populationSize,
5 R- I- z, ~0 w" j# pnew PermutationChromosome(citiesCount),
! N6 M, N6 ]! |fitnessFunction,
0 n2 c' ?3 ]9 P5 V6 @. R  r(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() :
7 P% G% M5 U2 P4 V4 ~8 D(selectionMethod ==1) ? (ISelectionMethod)new RankSelection() :
(ISelectionMethod)new RouletteWheelSelection()
);
% O2 \7 g1 z$ H/ D
" k+ i' ~+ i' O. N3 \) F2 m. V// iterations
int iter =1;
, i5 K+ F+ J7 Q8 `" b) Hint iterations =5000; //迭代最大周期

& _1 H  e1 V, I) T2 B// loop
while (iter < iterations)
{
// run one epoch of genetic algorithm
population.RunEpoch();

+ Y3 ~8 `. [0 e" n! c* [// increase current iteration
/ Y: b7 O1 t7 e1 A$ l. ~, \iter++;
}
' w8 _+ \4 m9 X1 F6 s6 p3 b; D
System.Console.WriteLine("遍历路径是： {0}", ((PermutationChromosome)population.BestChromosome).ToString());
System.Console.WriteLine("总路程是：{0}", fitnessFunction.PathLength(population.BestChromosome));
( T; r  X7 U; u4 C2 ^' rSystem.Console.Read();
  `% f- F+ ?/ f+ o
4 Q7 T$ `; ~( m3 j( B, c8 V: `}
}
; n0 j; |4 t3 n6 ]- \}
' v4 J& y- l& h

[url=][/url]
. B% L! k( f0 b- G0 G9 D

, x, U. E6 d7 [7 u, n
# _5 l5 T0 O0 \5 J1 M2 j

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

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

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

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

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

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

! x: i' ^- R+ }  [- o' T
4 F- i( {( F! k, K  Q* Q

---

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

Powered by Discuz! X2.5