注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

刘邓

每天收获一点点-目标:富足

 
 
 

日志

 
 

算法和数据组织—小试遗传算法  

2012-06-01 17:31:03|  分类: 数据组织和算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

浅析遗传算法

遗传算法是模拟自然进化论适者生存的优化算法,经过多代的繁衍最终获得满足要求的种群或者个体。

遗传算法的几个关键概念:

1.个体与种群 ...这个没神马好解释的,个体又称为染色体,

2.适应度和适应度函数...适应度是度量个体适应生存环境的程度,是遗传算法优化的关键,适应度函数是确定各地适应度的函数模型,以实数来判断个体适应度的大小

3.染色体(个体)与基因

染色体 先编码为2进制的字符串格式 1001

其中每个10就是单个基因,几个10的组合为基因组

遗传算法的三种操作:

选择-复制  交叉 和 变异

1.选择-复制:

对于规模为N的种群S,每个染色体体Xi被选择的概论为PXi),分为N此从S中随机选取N个染色体进行复制产生过渡带Gt1.

Xi被选择的概论公式为:算法和数据组织—小试遗传算法 - 刘邓 - 刘邓
  其中fXi)为Xi的适应度函数值。

2.交叉(杂交)

对于选择出来的种群随机进行杂交,杂交手段由程序员设定如对s1 = 01001011 s2 = 10010101按照后四位进行杂交:

S1 = 01001011  S1' = 01000101

S2 = 10010101 S2'=10010101

则产生了第二个过渡代Gt2 ={S1'S2'}

3.变异

变异也很简单,工具给的的变异率(根据具体情况考虑)

S = 11001101 第三位变异——> 11101101

遗传算法流程图:

算法和数据组织—小试遗传算法 - 刘邓 - 刘邓
 

遗传算法的控制参数:

1.种群的规模及个体数目

2.最大的跌代数

3.交叉率(参加交叉运算的染色体个数栈总体的比率Pc一般为0.40.99

4.变异率(变异位栈全体染色体的基因维数 pm一般为0.00010.1

基本步骤:

1.定义适应度函数fx),确定种群规模N,交叉率Pc,变异率Pm和代数(即遗传的次数)

2.随机产生N个个体S1S2....Sn组成初始种群G = {S1,S2....Sn} 置代数计数器为t = 1

3.计算G中每个个体的适应度fSi

4.检测是否到达指定代数或者是否已经满足了设定的优化条件,如果满足则适应度最大的个体,如果不满足则进入步骤5

5.选择-复制:

计算种群中各个个体的选择概论PSi),然后用模拟轮盘算法的方式由累计概论来产生N个新的个体进行复制操作组成过渡带Gt1.

这里介绍下轮盘算法:

就是生成一个0-1的随机数,然后看其落在哪个个体的区域,显然适应度强的个体被选择的概论更高。累计概论即比如四个个体随机选择四个个体,其分别的选择概论为:0.2,0.1,0.5,0.2

则其对应的累计概论为0.2,0.3,0.8,1.0 也就是说用均等概论的随机数生成器输出0-1的数则其落在每个区域内的概论由累计概论决定,如:随机生成了0.23这个数 因为0.2<0.23<0.3本次选择的是2号个体。

选择复制对应一个表格:

染色体

适应度

选择概论

累计概论

选中次数

S1

XX

0.2

0.2

Y

S2

XXX

0.1

0.30.2+0.1

Z

6.交叉(杂交):

由交叉率Pc确定参与交叉的个体个数N*Pc,然后随机从Gt1中生成C=N*Pm个个体参与杂交,按照特定的杂交操作以后得到的是过渡带Gt2(因为选择的过程中可能出现相同的个体,在杂交前可以加以判断,如果相同则取消)

PS.这里可能涉及总群数量的变化,最简单的遗传算法建立在种群不变的基础上,即由杂交产生的个体取代以前的父本个体,然后和没有被选择的个体组成新的过渡带Gt2.

7.变异:

按照变异率Pm所决定的变异体个数M = N*Pm,然后随机从Gt2中选择M个个体按照设定的变异方式进行变异操作,加入到Gt2中形成新的种群Gt3

8.Gt3当做输入进行步骤4的检测,循环一直到输出期望的结果

9.结束运算。

先写到这吧,后面会用C++写一个用遗传算法求函数局部最优解的小程序。

  评论这张
 
阅读(143)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017