必威体育Betway必威体育官网
当前位置:首页 > IT技术

【遗传算法】遗传算法入门示例

时间:2019-06-03 13:41:03来源:IT技术作者:seo实验室小编阅读:58次「手机版」
 

遗传算法实例

问题:求二元函数的最大值

f(x)=x^2,x\in[0,31]

遗传算法实现步骤:

1.编码

编码方法包括:二进制编码法、浮点编码法、符号编码法

这里使用二进制编码。由于变量的最大值31,固采用5个位即可表达全部的值

x=6   00110

2.产生初始群体

01101     11000    01000  10011

3.评价个体的适应度--适应度函数

这里采用与适应度成正比的概率作为适应度

p=fi/\sum fi

4.选择运算

第0代
序号 群体 适应值 选择概率 期望次数

选中次数 

选择结果
1 01101 169 0.1444 0.58 1 01101
2 11000 576 0.4923 1.97 2 11000
3 01000 64 0.0547 0.22 0 11000
4 10011 361 0.3085 1.23 1 10011

适应值 为 f(群体反编码值)    如f(13)=169

选择概率:p=fi/\sum fi       如p=169/(169+576+64+361)=0.1444

期望次数:采用确定性算法,对于规模为N的群体,一个选择概率为p的染色体被选择的期望次数e。公式:e=p*N,取\left \lfloor e \right \rfloor

选择结果:

常用的选择算子:

  1. 轮盘赌选择(Roulette Wheel Selection):是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

  2. 随机竞争选择(Stochastic Tournament):每次按轮盘赌选择一对个体,然后让这两个个体进行竞争,适应度高的被选中,如此反复,直到选满为止。

  3. 最佳保留选择:首先按轮盘赌选择方法执行遗传算法的选择操作,然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。

  4. 无回放随机选择(也叫期望值选择Excepted Value Selection):根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下:

    (1) 计算群体中每个个体在下一代群体中的生存期望数目N。

    (2) 若某一个体被选中参与交叉运算,则它在下一代中的生存期望数目减去0.5,若某一个体未 被选中参与交叉运算,则它在下一代中的生存期望数目减去1.0。

    (3) 随着选择过程的进行,若某一个体的生存期望数目小于0时,则该个体就不再有机会被选中。

  5. 确定式选择:按照一种确定的方式来进行选择操作。具体操作过程如下:

    (1) 计算群体中各个个体在下一代群体中的期望生存数目N。

    (2) 用N的整数部分确定各个对应个体在下一代群体中的生存数目。

    (3) 用N的小数部分对个体进行降序排列,顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。

  6. 无回放余数随机选择:可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中,因而选择误差比较小。

  7. 均匀排序:对群体中的所有个体按期适应度大小进行排序,基于这个排序来分配各个个体被选中的概率。

  8. 最佳保存策略:当前群体中适应度最高的个体不参与交叉运算和变异运算,而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。

  9. 随机联赛选择:每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。

  10. 排挤选择:新生成的子代将代替或排挤相似的旧父代个体,提高群体的多样性。

转载来自:作者:短短的路走走停停被抢注啦

            链接:https://www.jianshu.com/p/ae5157c26af9

5.配对进行交配,其中交配位是随机选择的rand(5):位的话是从左边往右边数。

交配规则:

编号 群体 交配对象 交配位 第1代 适应值
1 01101 2 4 01100 144
2 11000 1 4 11001 625
3 11000 4 2 11011 729
4 10011 3 2 10000 256

6.得到第一代

第1代
序号 群体 适应值 选择概率 期望次数

选中次数 

选择结果
1 01100 144 0.0821 0.3284 0 11001
2 11001 625 0.3563 1.4252 1 11011
3 11011 729 0.4156 1.6624 2 11011
4 10000 256 0.1460 0.5840 1 10000

不停地选择、配对(交叉)、变异。

变异:

异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变,它也是产生新个体的一种操作方法。本例中,我们采用基本位变异的方法来进行变异运算,其具体操作过程是:

• 首先确定出各个个体的基因变异位置;

• 然后依照某一概率将变异点的原有基因值取反。

相关阅读

遗传算法(GA)

遗传算法(Genetic Algorithm) 一个讲得很清楚的博客:非常好理解的遗传算法的例子 简单理解: 用计算机模拟人类进化,适应环境(符合条

遗传算法(GA)的新手入门必备,python3案例

遗传算法简介 遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模

遗传算法入门

原文地址为:遗传算法入门优化算法入门系列文章目录(更新中):1. 模拟退火算法2. 遗传算法遗传算法 ( GA , Genetic Algorithm ) ,也称进

简单遗传算法MATLAB实现

原文地址为:简单遗传算法MATLAB实现遗传算法的概念最早是由Bagley J.D 于1967年提出的。后来Michigan大学的J.H.Holland教授于1975

遗传算法原理及算法实例

遗传算法原理解析 遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和

分享到:

栏目导航

推荐阅读

热门阅读