遗传算法解释及代码完整版

《遗传算法解释及代码完整版》由会员分享，可在线阅读，更多相关《遗传算法解释及代码完整版（15页珍藏版）》请在装配图网上搜索。

1、遗传算法(GA , Genetic Algorithm )，也称进化算法。遗传算法是受达尔 文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介 绍遗传算法前有必要简单的介绍生物进化知识。一进化论知识作为遗传算法生物背景的介绍，下面内容了解即可：种群(Population)：生物的进化以群体的形式进行，这样的一个群体称 为种群。个体：组成种群的单个生物。基因(Gene ): 一个遗传因子。染色体(Chromosome ):包含一组的基因。生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比 较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越 来

2、越少。遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发 生基因变异。简单说来就是：繁殖过程，会发生基因交叉(Crossover )，基因突变(Mutation )，适应度(Fitness )低的个体会被逐步淘汰，而适应度高的个体 会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的， 其中很可能包含史上产生的适应度最高的那个个体。二遗传算法思想借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通 过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解， 增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值 很高的个

3、体。举个例子，使用遗传算法解决“0-1背包问题的思路：0-1背包的解可以编 码为一串0-1字符串(0：不取，1：取)；首先，随机产生M个0-1字符串， 然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些 字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个 近似最优解。编码：需要将问题的解编码成字符串的形式才能使用遗传算法。最简单的一 种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。例如，问 题的解是整数，那么可以将其编码成二进制位数组的形式。将0-1字符串作为 0-1背包

4、问题的解就属于二进制编码。遗传算法有3个最基本的操作：选择，交叉，变异。选择:选择一些染色体来产生下一代。一种常用的选择策略是“比例选择” 也就是个体被选中的概率与其适应度函数值成正比。假设群体的个体总数是M, 那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + + f(Xn)比例选择实现算法就是所谓的轮盘赌算法”(Roulette Wheel Selection ), 轮盘赌算法的一个简单的实现如下：日轮盘赌算法/*按设定的概率，随机选中一个个体* Pi表示第i个个体被选中的概率*/int RWS()m =0;r 二Random(0,l); /r 为 0 至 1

5、的随机数 for (i=1;i=N; i+)/*产生的随机数在mm+Pi间则认为选中了 i *因此i被选中的概率是Pi*/m = m + Pi; if (r=m) return i;希交叉(Crossover)： 2条染色体交换部分基因，来构造下一代的2条新的染色 体。例如：交叉前：OOOOOIOiiiooooooooIIOOOO11100|000001111110|00101交叉后：00000|000001111110|1000011100|011100000000|00101染色体交叉是以一定的概率发生的，这个概率记为Pc。变异(Mutation)：在繁殖过程,新产生的染色体中的基因会以一

6、定的概率出错, 称为变异。变异发生的概率记为Pm。例如：变异前：000001110000000010000变异后：000001110000100010000适应度函数(Fitness Function ):用于评价某个染色体的适应度，用f(x) 表示。有时需要区分染色体的适应度函数与问题的目标函数。例如：0-1背包问 题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并 不一定适合。适应度函数与目标函数是正相关的，可对目标函数作一些变形来得 到适应度函数。三基本遗传算法的伪代码日基本遗传算法伪代码/* Pc：交叉发生的概率* Pm：变异发生的概率* M：种群规模* G：终止进

7、化的代数* Tf：进化产生的任何一个个体的适应度函数超过Tf,则可以终止进化过程 */初始化Pm, Pc, M, G，Tf等参数。随机产生第一代种群Popdo计算种群Pop中每一个体的适应度F(i)。初始化空种群newPopdo根据适应度以比例选择算法从种群Pop中选出2个个体 if ( random ( 0 , 1 ) Pc )对2个个体按交叉概率Pc执行交叉操作if ( random ( 0 , 1 ) Pm )对2个个体按变异概率Pm执行变异操作将2个新个体加入种群newPop中 until ( M个子代被创建)用newPop取代Popuntil (任何染色体得分超过Tf，或繁殖代数超过

8、G )四基本遗传算法优化下面的方法可优化遗传算法的性能。精英主义(Elitist Strategy)选择：是基本遗传算法的一种优化。为了防 止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封 不动的复制到下一代中。插入操作：可在3个基本操作的基础上增加一个插入操作。插入操作将染 色体中的某个随机的片段移位到另一个随机的位置。五.使用AForge.Genetic解决TSP问题AForge.NET是一个C#实现的面向人工智能、计算机视觉等领域的开源架 构。AForge.NET中包含有一个遗传算法的类库。AForge.NET 主页：AForge.NET 代码下载：http:/co

9、de.google.Com/p/aforge/介绍一下AForge的遗传算法用法吧。AForge.Genetic的类结构如下：GEPChromosomoISe lectidnMQtlwdinterfacIFitncssFunctioni nterfac(? IChroDiostsmeGPTre sC hrouiosora图 1. AForge.Genetic 的类图ElitoScRankSelRoulettBinaryChromosomeShortArrayChromosomeSimplcGirite2bfaeeIGPGcnc缺 ExtendsTimeSeriesPredictionFitne

10、ssSy&ibDlicRcffre-ssionFitnessOpt imi zat ionFunc t i on2DOptioiizati on Function IDPe rmu t at i ontJhr omo s.otne下面用AForge.Genetic写个解决TSP问题的最简单实例。测试数据集采用 网上流传的中国31个省会城市的坐标：13042312 36391315 41772244 37121399 34881535 33261556 32381229 41961004 4312790 4386570 30071970 25621756 27881491 23811676 13

11、32695 37151678 39182179 40612370 37802212 36762578 40292838 42632931 34291908 35072367 33942643 34393201 29353240 31403550 25452357 27782826 23702975操作过程:(1) 下载AForge.NET类库，网址： http:/code.google.eom/p/aforge/dow nl oads/list(2) 创建C#空项目GenticTSP。然后在AForge目录下找到AForge.dll 和AForge.Genetic.dll,将其拷贝到TestT

12、SP项目的bin/Debug目录下。再 通过“Add Reference.”各这两个DLL添加到工程。(3) 将31个城市坐标数据保存为bin/Debug/Data.txt。(4) 添加 TSPFitnessFunction.cs，加入如下代码：日 TSPFitnessFunction 类using System;using AForge.Genetic;namespace GenticTSP/summary/ Fitness function for TSP task (TravalingSalasman Problem) /summarypublicclass TSPFitnessFunc

13、tion : IFitnessFunction/ mapprivateint, map =null;/ Construetorpublic TSPF it nessFunc tion(int, map)t his.map = map;/summary/ Evaluate chromosome - calculates its fitness value /summarypublicdouble Evaluate(IChromosome chromosome)return1/ (PathLength(chromosome) +1);/ Translate genotype to phenotyp

14、e /publicobject Translate(IChromosome chromosome)return chromosome.ToS tring(); /summary/ Calculate path length represented by the specified chromosome /summarypublicdouble PathLength(IChromosome chromosome)/ salesman pathushort path = (PermutationChromosome)chromosome).Value;/ check path sizeif (pa

15、 th.Leng th != map.Ge tLeng th(0)thrownew ArgumentException(Invalid path specified - not all cities are visited);/ path lengthint prev = path0;int curr = pat hpa th.Leng th -1;/ calculate distance between the last and the first city double dx = mapcurr, 0 - mapprev, 0;double dy = mapcurr, 1 - mappre

16、v, 1;double pat hLeng th = Mat h.Sqr t(dx * dx + dy * dy);/ calculate the path length from the first city to the lastfor (int i =1, n 二 pat h.Leng th; i n; i+)/ get current citycurr = pathi;/ calculate distancedx = mapcurr, 0 - mapprev, 0;dy = mapcurr, 1 - mapprev, 1;pat hLeng th += Mat h.Sqr t(dx *

17、 dx + dy * dy);/ put current city as previousprev = curr;return pathLength;(5)添加GenticTSP.cs，加入如下代码：日GenticTSP 类using System;using Sys tem.Collec tio ns.Generic;using Sys tem.Linq;using Sys tem.Tex t;using Sys tem.IO;using AForge;using AForge.Genetic;namespace GenticTSPclass GenticTSPstati cvoid Mai

18、n()StreamReader reader =new StreamReader(Data.txt);int citiesCount =31; /城市数int, map =newintcitiesCount, 2;for (int i =0; i citiesCount; i+)st ring value = reader.ReadLine();st ring t emp = value.Spl it();mapi, 0 =int.Parse(temp0); /读取城市坐标mapi, 1二int .Parse( templ);/ create fitness functionTSPFitnes

19、sFunctionfitnessFunction 二new TSPFitnessFunction(map);int populationSize = 1000; /种群最大规模/* 0： EliteSelection 算法* 1： RankSelection 算法* 其他：RouletteWheelSelection 算法* */int selectionMethod =0;/ create populationPopulationpopulation 二new Population(populationSize,new PermutationChromosome(citiesCount),f

20、itnessFunction,(selectionMethod =0) ? (ISelectionMethod)new EliteSelection()(selectionMethod =1) ? (ISelectionMethod)new RankSelection(): (ISelectionMethod)new RouletteWheelSelection();/ iterationsint iter =1;int it era tions =5000; /迭代最大周期/ loopwhile (iter iterations)/ run one epoch of genetic algorithmpopula tio n.RunEpoch();/ increase current iterationiter+;Sys tem.Console.Wri teLine(遍历路径是：0,(PermutationChromosome)population.BestChromosome).ToString();Sys tem.Console.Wri teLine(总路程是：0,fitnessFunction.PathLength(population.BestChromosome);Sys tem.Console.Read();