最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 遗传算法简介、基本原理及算法实现

    遗传算法算是一个比较复杂的算法,本文主要分为三个部分,第一部分遗传算法的发展、功能、主要思想以及简单的代码命令;第二部分详细介绍遗传算法的机理,第三部分举例并给出一个简单地使用方法。(觉得着急的话可以直接看参考文献对应部分)
    一、什么是遗传算法
    遗传算法的首次提出是在1967年,Holland教授的学生Bagley在其博士论文中提到”GeneticAlgorithm” ,即GA;1975年Holland教授出版了第一本系统叙述其内容的专著,奠定理论基础。今天,遗传算法已经成为十分流行的算法,在组合优化,自动控制,图像处理,机器学习等领域都有很广泛的运用。

    虽然遗传算法存在诸如陷入局部最优解,收敛速度缓慢等问题,人们也进行了很多的修改,但是鉴于遗传算法本身就具有很高的性能,而且各种修正方案都存在一定的复杂性和非普适性,所以经典遗传算法在应用领域还是几乎绝对的主流。

    二、遗传算法的原理

    遗传的算法的背景是达尔文的进化论,没错!算法的求解就是一个不停地繁衍、遗传、淘汰、进化的过程,以求出最适合的根。
    下面这张图能比较简单的表示遗传算法的流程:


    1. 种群初始化:在可行域内随机产生若干个解,称其为初始种群。

    2. 对种群内的每个解进行适应度评估,评价每个个体对环境的适应程度强弱。

    3. 适者生存,不适者淘汰,运用随机数等方式,将不适合的个体淘汰,适合的保留。

    4. 通过交叉互换、变异等方式对中云进行扰动,实质上就是在可行域内进行搜索,搜索出最适合环境的解。

    上述的环境是指目标函数,需要求解最优值的函数,每个个体就是每个可行解,适应度评估就是将可行解带入函数进行计算然后对比其大小,如果可行解代入函数的结果最优,那这个解就是最优解。优胜劣汰是对优秀解的保留,较差解的淘汰,交叉和变异就是对解进行扰动,以进一步提高解的优度。

    三、遗传算法实现

    遗传算法的机理相对复杂,而使用时可能需要编程实现,有没有什么比较方便的现成的工具能够快速使用遗传算法呢?答案!

    没有!

    的反义词!哈哈!

    在Matlab中已经由封装好的工具箱命令,通过调用就能够十分方便的使用遗传算法啦!

    先来说说简单命令:

    函数ga:

    [x, fval,reason]= ga(@fitnessfun, nvars, options)

     

    x是最优解,fval是最优值,@fitnessness是目标函数,nvars是自变量个数,options是其他属性设置。系统默认求最小值,所以在求最大值时应在写函数文档时加负号。

    为了设置options,需要用到下面这个函数:

    options=gaoptimset(‘PropertyName1’, ‘PropertyValue1’, ‘PropertyName2’, ‘PropertyValue2’,‘PropertyName3’, ‘PropertyValue3’, …)

     

    通过这个函数就能够实现对部分遗传算法的参数的设置。

    下面是一些常见的属性、默认属性以及其含义。

    四、遗传算法的详细原理

    1、过程详解

    在这里,用一个比较形象的方式讲解一下遗传算法的寻优机理。

    例如我需要计算(-1,1)内的,函数y=x*x的最小值(基本上知道正确答案了吧= =,最优解为0,最小值也为0)。

    种群初始化运用随机数给出一些初始解,例如0.5, 0.8, -0.2, -0.1。

    将每个可行解带入函数中,发现-0.1得到的结果最小,我们默认其为当前最优解,其他的比较差,而0.8最差,我们选择将它淘汰,重新生成一个新的数,为0.4,为了查看其附近有没有更好的解,我们需要对其进行扰动,在遗传算法中,这种扰动识通过变异、交叉呼唤和自然选择进行的。

    0.5通过变化变为0.1,0.4则变为0.5,-0.2变为0,-0.1变为-0.3,结果发现0的解是最好的。

    经过若干次扰动和测试后,就能够得到最好的解0最好。

    就是这样不停地搜索,4个数,就像是四条鱼随机的在水里游,每经过一个地方就进行测试,以找到最好的食物。这就是遗传算法的过程,通过几个个体的缓慢探索最终找到最优解。

    2、编码

    为了更好的进行后面的扰动,就需要对参数记性特定的编码,在Holland的经典研究中,运用的是二进制,虽然二进制编码具有“汉明悬崖”等的问题,但是二进制凭借其操作简单,计算方便等优势仍处主流。

    设参数的范围是(L,U),k为编码长度,其具体计算公式为:

    c=L+x*δ

    其中,(这个我还是用公式了额)

    编码长度k和所需的精度s有关,通过下列形式求得:

    例如,某个参数的范围是0-10,精度是到整数,则其编码维数为4位。8对应的编码是1000。

    恢复为实际数的公式为:

    其中bi为二进制编码里面的每一位数,例如0101,b1=1, b2=0, b3=1, b4=0。

    当然,目前有诸如格雷编码,实数编码等方式,相比二进制编码更加先进,有兴趣的同学可以上网搜一下~

    作为利用计算机进行计算的算法,要求将迭代初始,迭代过程,迭代终止条件都需要定义清楚,在此介绍迭代初始,在遗传算法中,成为种群初始化。

    在此需要设置一个重要的参数,就是种群规模,在第0章汇总我们看到的种群规模就是4,这个参数的含义就类似一次任务派出搜索员的数量,搜索员数量越多,找的越快,但是需要付出的成本越多,为了平衡两者的关系,一般定为10-100之内,对相对简单的系统,用50以内的种群规模即可。

    种群初始化一般使用直接随机的方法,这样能够快速,简便的生成众多初始可行解。

    3、适应度评估

    无论是在种群初始化化后,还是进行扰动之后,都需要进行适应度评估,适应度的评价标准,就是所求的函数,如果需要函数最大值,则带入求出的值越大,该个体适应度越高,在环境中,就就越不容易被淘汰。在第0章中,-0.1就是适应度比较高的解。

    4、选择交叉变异

    这三个步骤放在一起说,因为是遗传算法的特色过程,类似搜索员在可行域内搜索最优解的过程。

    选择是指根据每个个体的适应度,优胜劣汰,假设淘汰率为0.5,则就讲其中适应度倒数50%的个体直接删除,然后用各种方式来补充,这个是比较机械的方式,方便理解。最常见的选择机制是轮盘赌法,根据适应度将每个个体放在转盘上,是应对越高,占据的面积就越大,然后根据种群规模n,旋转转盘n次,将指针所指的参数加到新种群里面,完成优胜劣汰,毕竟最优秀的个体不见得就能绝对保留,最差的解也不一定就活该淘汰,这是有一定概率出现的。

    在进行选择后,就应该进行繁衍,繁衍是相对的,父母会产生和自己类似但是不见得绝对相同的方式产生后代,变异和交叉互换是会发生的。

    交叉的含义,我直接举例:

    A个体:100100

    B个体:100011

    假设第四位进行互换,就变成了

    A‘个体:100000

    B’个体:100111

    产生新个体,以变异是以一定概率出现的,概率的设定十分有讲究,太高可能会另最优解有变化,丢失最优解,如果太低,则搜索效率很低,故一般设为0.7-0.9。

    变异的含义我同样利用举例来说明:

    A个体:100100

    第四位产生变异。

    A‘个体:100000

    这就是变异,和交叉类似,其概率需要有比较精细的判断,一般设为0.01-0.1。

    5、其他参数

    上面提到了一些比较影响算法性能的参数,除了上面之外,其他的参数也需要谨慎判断。

    计算精度:计算精确度越高,计算所需要的代价会越高,所以需要根据实际需求确定。

    迭代次数:迭代的目的是搜索最优解,一般而言,找到一定精度的最优解,其实就不必再进行迭代了,所以一般会根据函数复杂性设定比较合理的迭代次数。

    综上所述,需要重点分析的参数就是:种群规模,变异概率,交叉概率,计算精度,迭代次数。

    五、遗传算法的实现

    目前实现遗传算法的方式很多,多半是利用编程语言编辑实现,由于编程过程复杂,今天给大家介绍一个已经编好封装的命令,在Matlab中,只需要两句简单的命令就能够利用遗传算法进行计算了相关命令,在前面有所提到,今天我来举几个例子。

    1、命令介绍

    首先我们来复习一下遗传算法(上)里面提到的两句关键命令。

    函数ga:

    x是最优解,fval是最优值,@fitnessness是目标函数,nvars是自变量个数,options是其他属性设置。系统默认求最小值,所以在求最大值时应在写函数文档时加负号。

    为了设置options,需要用到下面这个函数:

    通过这个函数就能够实现对部分遗传算法的参数的设置。

    下面是一些常见的属性、默认属性以及其含义。

    运用上述两个关键命令就能够实现遗传算法的全过程,这是最简单快捷的方法啦!

    下面来举两个例子,一个比较简单,另一个比较难。

    2、简单例子
    首先是简单的例子

    看看它的图像:

    下面来看看代码。首先是函数文件:

    由于ga这个函数是求最小值,所以需要将函数取负号。为了限制范围在-3到3之间,运用这个条件语句进行约束。

    下面是关键的遗传算法代码啦,看!

    参数设定上,我决定直接用默认的,另外为了给大家呈现寻优过程,所以运用了和这个参数@gaplotbestf,来看看寻优过程吧~

    可以发现,结果越来越收敛,最终比较得到比较接近的结果。由于前面去了负,所以这上面的结果也是负,取相反数之后就是答案啦~
    计算结果是:

    结果是,最优解为1.5181,最优值是185.1235。可见结果是比较好的。
    3、困难的例子
    是时候来一个比较难的了!首先来看看函数长什么样:

    哼哼,看公式难,看图更难!

    答案是(0,0),我们接着试试看遗传算法的结果是什么。
    首先是函数文件,这个还是挺难写的:

    真的写了我一年啊orz
    看看主程序:

    为了提高精确度,并且减少后期因为搜索缓慢而导致的偶然停止,我将搜索停止条件设为无穷(就是除非到达1000代,否则搜索会一直进行),进化代数为1000。寻优过程如下:

    可以看到这个寻优过程就比较坎坷= =
    结果是:

    结果还是相对满意的,哈哈~

    4、补充

    当然,在参考文献里面还有直接编出来的代码,另外网络上也有很多写好的程序,有兴趣的可以看看。

    经典遗传算法有其本身的缺点,上面的结果其实可以通过改进变得更加精确。相关方法大家可以看看论文,然后自己编程实现。

    还有一个预防针要打,遗传算法是牛刀,编程代价还是比较高的,对于线性优化等问题,用单纯形法,部分求最值的问题也可以用梯度下降法等解决,遗传算法在解决这种简单的问题,最好还是别放在第一位置,杀鸡焉用牛刀。

    参考文献:卓金武. MATLAB在数学建模中的应用[M]. 北京:北京航空航天大学出版社, 2014. 38-59

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 遗传算法简介、基本原理及算法实现

    发表评论

    • 52会员总数(位)
    • 307资源总数(个)
    • 40本周发布(个)
    • 1 今日发布(个)
    • 329稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情