进化计算简介和遗传算法的实现–AForge.NET框架的使用(六)

29 2月

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2012/02/29/aforge_6/

开学了,各种忙起来了。

上一篇介绍了AForge.NET在人工神经网络上的一点点使用,但是老觉不过瘾。matlab用着实在不习惯,就又琢磨了一下进化计算。

进化计算简介

进化计算算不上新的方法了,已经有大量研究人员作出了努力,这导致了大量的进化计算算法出现。他们不仅研究算法本身,还致力于扩大算法的应用范围。

众所周知,现实世界存在大量复杂问题,它们中一部分无法用常规方法在合理的时间内获得精确解,而另一部分甚至没有行之有效的解决方案。

最著名的例子就是TSP问题,该问题意在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。

而进化计算可以应用于这些问题,因为大多数情况下这类问题允许我们在合理时间内给出较优解。

进化计算并不能保证找到特定问题的最佳解决方案,但是可以找到一个很好的解决办法,该方案可能是非常接近的最佳解决方案。

进化算法的分支和运用

进化计算是一些算法的统称,主要包括Genetic Algorithms (GA遗传算法), Genetic Programming (GP遗传规划) 和 Gene Expression Programming (GEP基因表达式编程)。

进化算法主要可以解决以下类别问题:

1.函数优化

2.符号回归

3.时间序列预测

4.旅行商问题

遗传算法简介

Genetic Algorithms(遗传算法)最早由John Holland基于进化观点在1960提出。从那时起相关研究不断进行。

大部分研究成果运用到很多领域,并取得了很好的效果。虽然遗传算法的历史悠久,但是目前还是不断有新的方法被提出,扩宽了运用领域。

 

遗传算法基于达尔文的“适者生存”理论和遗传学机理的生物进化过程。算法作用于每一代的基因,而每个基因都是问题的可能解。

一般遗传算法的运用有以下4个步骤:

1.随机选择个体,并进行交叉

2.变异

3.计算适应度

4.选择下一个世代的个体

算法的停止条件一般是指定的迭代数目完成或者得到一个可靠解。

交叉算法中最简单的单点交叉,即随机选择两个基因的一个点,交换两个基因的一部分。

基因1:0 0 0 1 1 0 1
基因2:1 0 0 1 0 0 0
结果  :0 0 0 1 0 0 0

还有一种不错的方式是两点交叉,随机选择两个基因的两个点,交换两个点之间的部分。

变异一般用单点变异

基因1:0 1 0 0 1 0 1
结果  :0 1 0 0 0 0 1

用Aforge.Net实现遗传算法

我觉得Aforge.Net的优越就在于不是提供特定的实现,而是重在提供一个可以扩展的框架,方便学习和研究。

s3

我以函数最优化为例。函数我选用:x^0.5+sin(x/23)*30 范围从0到100

s3

先用matlab估计一下最优值

output

建立适应度评价函数;

publicclass MyOwnFunction : OptimizationFunction1D {publicMyOwnFunction() :base(new AForge.Range(0, 100)) { }publicoverridedoubleOptimizationFunction(double x) {return Math.Sqrt(x)+ Math.Sin(x/23)*30; } }

遗传算法主要的类是Population类。它容纳了所有的染色体,提供了适应度评价方法、编码方式和选择方式。

MyOwnFunction f =new MyOwnFunction(); Population population =new Population(40,new BinaryChromosome(32),f,new EliteSelection());

这段代码的意思是适应度函数使用自定义的MyOwnFunction,编码使用二进制编码,长度为32,每个世代个体数目为40,选择方式为“精英取舍”。

这个名字很霸气,其实就是排个序,然后把不好的移除而已,代码如下;

public classEliteSelection:ISelectionMethod {/// <summary> ///Initializes a new instance of the <see cref="EliteSelection"> class. /// </see></summary> publicEliteSelection( ) { } /// <summary>/// Apply selection to the specified population. /// </summary> /// /// <param name="chromosomes">Population, which should be filtered. /// <param name="size">The amount of chromosomes to keep. /// /// <remarks>Filters specified population keeping only specified amount of best /// chromosomes.</remarks> /// public voidApplySelection(List<ichromosome> chromosomes, int size ) {// sort chromosomes chromosomes.Sort( );// remove bad chromosomes chromosomes.RemoveRange( size, chromosomes.Count - size ); } }

一般情况可以使用赌轮盘的方式进行下一个世代的选择。完整代码:

Console.WriteLine("Start!"); MyOwnFunction f =new MyOwnFunction(); Population population =new Population(40,new BinaryChromosome(32),f,new EliteSelection()); population.RunEpoch();double goodX=f.Translate(population.BestChromosome); Console.WriteLine("Best Chromosome === >{0}", goodX); Console.WriteLine("Best Result === >{0}", f.OptimizationFunction(goodX)); Console.WriteLine("Over!"); Console.ReadLine();

效果:

data

基本符合,和matlab估算的值差了0.0002左右。

如果要输出最后世代的所有结果,可以使用

for (int i =0; i < population.Size; i++) { Console.WriteLine("chromosome{0} == >{1}", i, f.Evaluate(population[i])); }

结果如下图:
data2

写在最后:

1.个人觉得AForge.NET用着比matlab方便,因为它的整体架构比较统一,而不像matlab是由工具箱提供的,使用风格迥异。

2.AForge.Net的进化计算这块远远比神经网络部分完整,基本不需要自己实现什么。

3.AForge.Fuzzy中的隶属度函数的表示实现不够丰富,只实现了中间型的两种,我扩写了其他种类的,等整理好了就发出来。

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2012/02/29/aforge_6/

发表评论

您的电子邮箱地址不会被公开。