遗传算法解释及代码一看就懂文档格式.docx
《遗传算法解释及代码一看就懂文档格式.docx》由会员分享，可在线阅读，更多相关《遗传算法解释及代码一看就懂文档格式.docx（10页珍藏版）》请在冰点文库上搜索。
这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。
编码：
需要将问题的解编码成字符串的形式才能使用遗传算法。
最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。
例如，问题的解是整数，那么可以将其编码成二进制位数组的形式。
将0-1字符串作为0-1背包问题的解就属于二进制编码。
遗传算法有3个最基本的操作：
选择，交叉，变异。
选择：
选择一些染色体来产生下一代。
一种常用的选择策略是
“比例选择”，也就是个体被选中的概率与其适应度函数值成正比。
假设群体的个体总数是M，那么那么一个体Xi被选中的概率为f（Xi）/（f（X1）+f（X2）+……..+f（Xn））。
比例选择实现算法就是所谓的“轮盘赌算法”（RouletteWheelSelection），轮盘赌算法的一个简单的实现如下：
轮盘赌算法
/*
*按设定的概率，随机选中一个个体
*P[i]表示第i个个体被选中的概率
*/
int
RWS（）
{
m
=0;
r
=Random（0,1）;
//r为0至1的随机数
for（i=1;
i<
=N;
i++）
/*
产生的随机数在m~m+P[i]间则认为选中了i
*因此i被选中的概率是P[i]
=
+
P[i];
if（r<
=m）
return
i;
}
交叉（Crossover）：
2条染色体交换部分基因，来构造下一代的2条新的染色体。
例如：
交叉前：
00000|011100000000|10000
11100|000001111110|00101
交叉后：
00000|000001111110|10000
11100|011100000000|00101
染色体交叉是以一定的概率发生的，这个概率记为Pc。
变异（Mutation）：
在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。
变异发生的概率记为Pm。
变异前：
000001110000000010000
变异后：
000001110000100010000
适应度函数
（FitnessFunction）：
用于评价某个染色体的适应度，用f（x）表示。
有时需要区分染色体的适应度函数与问题的目标函数。
0-1背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。
适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。
三.基本遗传算法的伪代码
基本遗传算法伪代码
*Pc：
交叉发生的概率
*Pm：
变异发生的概率
*M：
种群规模
*G：
终止进化的代数
*Tf：
进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程
初始化Pm，Pc，M，G，Tf等参数。
随机产生第一代种群Pop
do
{
计算种群Pop中每一个体的适应度F（i）。
初始化空种群newPop
do
{
根据适应度以比例选择算法从种群Pop中选出2个个体
if
（random（
0
1
）
<
Pc）
{
对2个个体按交叉概率Pc执行交叉操作
}
Pm）
对2个个体按变异概率Pm执行变异操作
将2个新个体加入种群newPop中
}until（M个子代被创建）
用newPop取代Pop
}until（任何染色体得分超过Tf，或繁殖代数超过G）
四.基本遗传算法优化
下面的方法可优化遗传算法的性能。
精英主义（ElitistStrategy）选择：
是基本遗传算法的一种优化。
为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。
插入操作：
可在3个基本操作的基础上增加一个插入操作。
插入操作将染色体中的某个随机的片段移位到另一个随机的位置。
五.使用AForge.Genetic解决TSP问题
AForge.NET是一个C#实现的面向人工智能、计算机视觉等领域的开源架构。
AForge.NET中包含有一个遗传算法的类库。
AForge.NET主页：
AForge.NET代码下载：
介绍一下AForge的遗传算法用法吧。
AForge.Genetic的类结构如下：
图1.AForge.Genetic的类图
下面用AForge.Genetic写个解决TSP问题的最简单实例。
测试数据集采用网上流传的中国31个省会城市的坐标:
13042312
36391315
41772244
37121399
34881535
33261556
32381229
41961004
4312790
4386570
30071970
25621756
27881491
23811676
1332695
37151678
39182179
40612370
37802212
36762578
40292838
42632931
34291908
35072367
33942643
34393201
29353240
31403550
25452357
27782826
23702975
操作过程：
（1）下载AForge.NET类库，网址：
（2）创建C#空项目GenticTSP。
然后在AForge目录下找到AForge.dll和AForge.Genetic.dll，将其拷贝到TestTSP项目的bin/Debug目录下。
再通过“AddReference...”将这两个DLL添加到工程。
（3）将31个城市坐标数据保存为bin/Debug/Data.txt。
（4）添加TSPFitnessFunction.cs，加入如下代码：
TSPFitnessFunction类
using
System;
AForge.Genetic;
namespace
GenticTSP
///<
summary>
///
FitnessfunctionforTSPtask（TravalingSalasmanProblem）
/summary>
publicclass
TSPFitnessFunction:
IFitnessFunction
//
map
privateint[,]map
=null;
Constructor
public
TSPFitnessFunction（int[,]map）
this.map
map;
Evaluatechromosome-calculatesitsfitnessvalue
publicdouble
Evaluate（IChromosomechromosome）
return1/
（PathLength（chromosome）
+1）;
Translategenotypetophenotype
publicobject
Translate（IChromosomechromosome）
chromosome.ToString（）;
Calculatepathlengthrepresentedbythespecifiedchromosome
PathLength（IChromosomechromosome）
salesmanpath
ushort[]path
（（PermutationChromosome）chromosome）.Value;
checkpathsize
if
（path.Length
!
map.GetLength（0））
thrownew
ArgumentException（"
Invalidpathspecified-notallcitiesarevisited"
）;
pathlength
prev
path[0];
curr
path[path.Length
-1];
calculatedistancebetweenthelastandthefirstcity
double
dx
map[curr,
0]
-
map[prev,
0];
dy
1]
1];
pathLength
Math.Sqrt（dx
*
dy）;
calculatethepathlengthfromthefirstcitytothelast
for
（int
i
=1,n
path.Length;
i
n;
getcurrentcity
path[i];
calculatedistance
+=
putcurrentcityasprevious
curr;
pathLength;
（5）添加GenticTSP.cs，加入如下代码：
GenticTSP类
System.Collections.Generic;
System.Linq;
System.Text;
System.IO;
AForge;
class
staticvoid
Main（）
StreamReaderreader
=new
StreamReader（"
Data.txt"
citiesCount
=31;
//城市数
int[,]map
=newint[citiesCount,
2];
citiesCount;
string
value
reader.ReadLine（）;
string[]temp
value.Split（'
'
map[i,
=int.Parse（temp[0]）;
//读取城市坐标
=int.Parse（temp[1]）;
createfitnessfunction
TSPFitnessFunctionfitnessFunction
TSPFitnessFunction（map）;
populationSize
1000;
//种群最大规模
*0：
EliteSelection算法
*1：
RankSelection算法
*其他：
RouletteWheelSelection算法
selectionMethod
createpopulation
Populationpopulation
Population（populationSize,
new
PermutationChromosome（citiesCount）,
fitnessFunction,
（selectionMethod
==0）
?
（ISelectionMethod）new
EliteSelection（）:
==1）
RankSelection（）:
RouletteWheelSelection（）
iterations
iter
=1;
iterations
=5000;
//迭代最大周期
loop
while
（iter
iterations）
runoneepochofgeneticalgorithm
population.RunEpoch（）;
increasecurrentiteration
iter++;
System.Console.WriteLine（"
遍历路径是：
{0}"
（（PermutationChromosome）population.BestChromosome）.ToString（））;
总路程是：
{0}"
fitnessFunction.PathLength（population.BestChromosome））;
System.Console.Read（）;
升级会员 