智能优化算法之遗传算法

这篇具有很好参考价值的文章主要介绍了智能优化算法之遗传算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

该算法已被很多篇文章讲解,本文将会去除很多较简单的内容,挑选认为重点核心部分进行讲述,内容中有属于信息的收集整理部分,也有属于自己理解的部分。

1、遗传算法概述

        遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。

2、遗传算法的基本操作

        遗传算法有三个基本操作: 选择( Selection) 、 交叉( Crossover) 和变异( Mutation)
选择。 从当前种群中选出优良的个体, 使它们有机会作为父代种群为下一代种群进行更新迭代。 根据各个个体的适应度值, 按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。 选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。
交叉。 通过交叉操作可以得到新一代个体, 新个体组合了父辈个体的特性。 将群体中的各个个体随机搭配成对, 对每一个个体, 以交叉概率交换它们之间的部分染色体。
变异。 对种群中的每一个个体, 以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。 同生物界中一样,变异发生的概率很低, 变异为新个体的产生提供了机会。

3、遗传算法的基本步骤

        遗传算法的基本步骤包含了编码、解码、初始种群生成、适应度计算、选择、交叉、变异

1)编码: GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,
这些串结构数据的不同组合便构成了不同的点。

        遗传算法的搜索核心是编码方式(遗传算子)的选择,因此对于遗传算法的研究,其中最常见的内容与方向是遗传算子,遗传算子的选择多样性也导致了算法表现的多样性,常见的选择方式如图所示:

智能优化算法之遗传算法

         常见的编码方式有:二进制编码、自然数编码、实数编码和树形编码等,常见的编码有二进制编码与自然数编码,很多实际问题如VRP调度问题更多采用自然数编码。(编码方式不赘述,根据模型需要自行选择即可)

2)初始群体的生成:随机产生N个初始串结构数据, 每个串结构数据称为一个个体, N个
个体构成了一个群体。

3)适应度评估:适应度表明个体或解的优劣性。 不同的问题, 适应性函数的定义不同。

4)选择:选择的目的是为了从当前群体中选出优良的个体。  选择体现了达尔文的适者生存原则。

常见的选择方式有:

        轮盘赌法Roulette-wheel selection:

       轮盘赌选择法是依据个体的适应度值计算每个个体在子代中出现的概率,并按照此概率随机选择个体构成子代种群。轮盘赌选择策略的出发点是适应度值越好的个体被选择的概率越大。

智能优化算法之遗传算法

         为了计算选择概率,需要用到每个个体i的适应度值:

         从给定种群中选出M个个体就等价于旋转M次轮盘,在选择个体前实际上不必对种群中的个体进行排序。

        锦标赛选择(Tournament selection)

        在锦标赛选择中,从种群中随机采样s个个体(注意:采样是有放回的),然后选择最优的个体进入下一代,只有个体的适应度值优于其他s-1个竞争者时才能赢得锦标赛。注意最差的个体永远不会幸存,而最优的个体在其参与的所有锦标赛中都能获胜。

智能优化算法之遗传算法

         可以通过改变锦标赛的大小s来改变,对于较大的s值,弱者被选中的机会较小,常见的有二元锦标赛和三元锦标赛等。与适应度值比例选择相比,锦标赛选择由于缺乏随机噪声,同时锦标赛选择也和遗传算法适应度函数的尺度无关。

        随机遍历选择(Stochastic-universal selection)

        随机遍历选择(SUS)是一种根据给定概率以最小化波动概率的方式选择个体的方法。可以将其认为是一种轮盘赌游戏,在轮盘上有p个等间距的点进行旋转。SUS使用一个随机值在等间隔的空间间隔内选择来选择个体。相比较于适应度比例选择法,该方法中较劣个体也有很好的机会被选择,从而奖励了不公平性。该选择方法是由James Baker提出的,展示了其原理,其中n为要选择的个体数量。随机遍历采样保证了选出的子代,比轮盘赌法更加接近希望得到的结果

智能优化算法之遗传算法

         精英选择(Elite selection)

        精英选择将一小部分最优的候选解原封不动的复制到下一代中,这会对性能产生巨大的影响,因为这保证了GA不会浪费时间重新发现以前拒绝的部分解。通过精英主义被保留下来的个体仍然有资格被选为下一代的父代。精英主义也与记忆有关:记住目前找到的最优解。不过精英主义的问题在于会导致GA收敛到局部最优,所以纯粹的精英主义是一场通向最近局部最优的竞争。

5)交叉:交叉操作是遗传算法中最主要的遗传操作。 通过交叉操作可以得到新一代个体,
新个体组合了其父辈个体的特性。

常见的交叉方式有:

        单点交叉(Single-point crossover)

        单点交叉通过选取两条染色体,在随机选择的位置点上进行分割并交换右侧的部分,从而得到两个不同的子染色体。

智能优化算法之遗传算法

         两点交叉(Two-points crossover)

        两点交叉是指在个体染色体中随机设置了两个交叉点,然后再进行部分基因交换。两点交叉的具体操作过程是:

  1. 在相互配对的两个个体编码串中随机设置两个交叉点;
  2. 交换两个个体在所设定的两个交叉点之间的部分染色体。

智能优化算法之遗传算法

         部分匹配交叉(Partially-matched crossover,PMX)

        部分匹配交叉保证了每个染色体中的基因仅出现一次,通过该交叉策略在一个染色体中不会出现重复的基因,所以PMX经常用于旅行商(TSP)或其他排序问题编码。
        PMX类似于两点交叉,通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体,个别基因会出现重复的情况,为了修复染色体,可以在交叉区域内建立每个染色体的匹配关系,然后在交叉区域外对重复基因应用此匹配关系就可以消除冲突。

Step1:随机选择一对染色体(父代)中几个基因的起止位置(两染色体被选位置相同)。

智能优化算法之遗传算法

Step2:交换这两组基因的位置。

智能优化算法之遗传算法

Step3:做冲突检测,根据交换的两组基因建立一个映射关系,如图所示,以7-5-2这一映射关系为例,可以看到第二步结果中子代1存在两个基因7,这时将其通过映射关系转变为基因2,以此类推至没有冲突为止。最后所有冲突的基因都会经过映射,保证形成的新一对子代基因无冲突。

智能优化算法之遗传算法

最终结果为:

智能优化算法之遗传算法

 还有其他的交叉方法,这里不一一举例说明。

6)变异:变异首先在群体中随机选择一个个体, 对于选中的个体以一定的概率随机地改变
串结构数据中某个串的值。

整体的流程如下:

智能优化算法之遗传算法

4、案例分析

        案例后续讲述

        TSP优化

        遗传算法优化神经网络
 

5、遗传算法特点

相对于传统算法而言,遗传算法有以下突出特点:

优点:

        1). 可适用于灰箱甚至黑箱问题;

        2). 搜索从群体出发,具有潜在的并行性;

        3). 搜索使用评价函数(适应度函数)启发,过程简单;

        4). 收敛性较强。

        5). 具有可扩展性,容易与其他算法(粒子群、模拟退火等)结合

不足:

        1). 算法参数的选择严重影响解的品质,参数的选择大部分是依靠经验;

        2). 遗传算法的本质是随机性搜索,不能保证所得解为全局最优解;

        3).在处理具有多个最优解的多峰问题时容易陷入局部最小值而停止搜索,造成早熟问题,无         法达到全局最优。文章来源地址https://www.toymoban.com/news/detail-487784.html

到了这里,关于智能优化算法之遗传算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (转载)多种群遗传算法的函数优化算法(matlab实现)

            以下内容大部分来源于《MATLAB智能算法30个案例分析》,仅为学习交流所用。         遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的全局优化概率搜索算法。由于优化时不依赖于梯度,具有很强的鲁棒性和全局搜索能力

    2024年02月07日
    浏览(48)
  • matlab simulink 遗传算法优化RBF

    1、内容简介 略 2-可以交流、咨询、答疑 2、内容说明 先用遗传算法优化RBF的权重系数,然后用RBF来做个控制器,查看效果 遗传算法、RBF控制、优化 3、仿真分析 4、参考论文 略  

    2024年02月08日
    浏览(43)
  • 【人工智能】遗传算法

    可以把遗传算法类比成一个游戏,我们需要通过这个游戏来找到最佳的解决方案。 首先,我们需要创建一些角色(也就是种群),每个角色有自己的装备和技能(染色体),但是我们并不知道哪个角色更加强大。 然后,我们让这些角色相互竞争,通过升级、打怪等方式来获

    2024年02月02日
    浏览(44)
  • Matlab | 基于遗传算法的TSP路径优化

    理论基础 问题导入 MATLAB程序实现及结果分析 总结与扩展 TSP (traveling salesman problem,旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还未找到一个多项式时间的有效算法。 TSP问题可描述为: 已知有 n 个城市,各城市

    2024年02月04日
    浏览(44)
  • 基于遗传算法的BP神经网络优化算法(matlab实现)

            BP网络是一类多层的前馈神经网络。它的名字源于在网络训练的过程中,调整网络的权值的算法是误差的反向传播的学习算法,即为BP学习算法。BP算法是Rumelhart等人在1986年提出来的。由于它的结构简单,可调整的参数多,训练算法也多,而且可操作性好,BP神经网

    2024年01月16日
    浏览(54)
  • 【人工智能Ⅰ】实验2:遗传算法

    实验2  遗传算法实验 一、实验目的 熟悉和掌握遗传算法的原理、流程和编码策略,理解求解TSP问题的流程并测试主要参数对结果的影响,掌握遗传算法的基本实现方法。 二、实验原理 旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅

    2024年02月04日
    浏览(45)
  • 基于GA遗传优化的混合发电系统优化配置算法matlab仿真

    目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1遗传算法基本原理 4.2 混合发电系统优化配置问题 4.3 基于GA的优化配置算法 染色体编码 初始种群生成 适应度函数 选择操作 交叉操作 变异操作 5.完整工程文件       基于GA遗传优化的混合发电系统优化配置

    2024年01月25日
    浏览(46)
  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现(数学建模)

    模拟退火算法是一种全局优化算法,解决的问题通常是找到一个最小化(或最大化)某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间,在开始时以一定的温度随机生成初始解,然后一步步降低温度,同时在当前解的周围随机搜索新的解,并根据一定概率接受

    2024年02月02日
    浏览(52)
  • 基于遗传算法的多目标优化进行0-1规划

    第一次写博客不知道从哪里下手, 之所以想开始博客写作一方面是想记录自己写过的代码,另一方面也分享一下自己在编程的时候遇到的问题,也希望可以帮助到各位。 之所以做基于遗传算法的多目标优化进行0-1规划,是因为在做数学建模2021年C题的时候遇到了一个规划题,

    2024年02月07日
    浏览(38)
  • [多目标优化算法]1.NSGA-II——非支配排序遗传算法

    笔者最近在学习有关多目标优化的内容,并对内容进行一些整理。这篇文章算是笔者的一篇个人学习笔记,也希望能对他人提供一定的帮助,若有不足之处,也欢迎指正和建议。 注:本文中所举例子均为最小化问题。            一个多目标优化问题可以用下面的数学形式来

    2023年04月08日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包