文档章节

遗传算法

c
 ctsm
发布于 2014/01/13 01:10
字数 2088
阅读 4.1W
收藏 26

一、遗传算法的应用

函数优化(遗传算法的经典应用领域);
组合优化(实践证明,遗传算法对于组合优化中的NP完全问题,如0-1背包问题,TSP等,非常有效);
自动控制;

机器人智能控制;

组合图像处理和模式识别;

人工生命;

遗传程序设计;



二、遗传学基本概念与术语

基因型(genotype):性状染色体的内部表现;

表现型(phenotype):染色体决定性状的外部表现,或者说,根据基因型形成的个体;

进化(evolution):逐渐适应生存环境,品质不断得到改良。生物的进化是以种群的形式进行的。

适应度(fitness):度量某个物种对于生存环境的适应程度。

选择(selection):以一定的概率从种群中选择若干个个体。一般,选择过程是一种基于适应度的优胜劣汰的过程。

复制(reproduction):细胞分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新细胞就继承了旧细胞的基因。

交叉(crossover):两个染色体的某一相同位置处DNA被切断,前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交;

变异(mutation):复制时可能(很小的概率)产生某些复制差错,变异产生新的染色体,表现出新的性状。

编码(coding):DNA中遗传信息在一个长链上按一定的模式排列。

          遗传编码可看作从表现型到基因型的映射。

解码(decoding):基因型到表现型的映射。

个体(individual):指染色体带有特征的实体;
种群(population):个体的集合,该集合内个体数称为种群的大小;



三、遗传算法的基本思路


在开始介绍一个实例之前,有必要了解一下轮盘赌选择法,因为基本遗传算法就是用的这个选择策略。

轮盘赌选择
又称比例选择方法.其基本思想是:各个个体被选中的概率与其适应度大小成正比.

具体操作如下:
(1)计算出群体中每个个体的适应度f(i=1,2,…,M),M为群体大小;
(2)计算出每个个体被遗传到下一代群体中的概率;

       

(3)计算出每个个体的累积概率;

       (q[i]称为染色体x[i] (i=1, 2, …, n)的积累概率)

     

(4)在[0,1]区间内产生一个均匀分布的伪随机数r;
(5)若r<q[1],则选择个体1,否则,选择个体k,使得:q[k-1]<r≤q[k] 成立;
(6)重复(4)、(5)共M次



四、一个简单的实例

1. 产生初始种群

s1= 13 (01101)

s2= 24 (11000) 

s3= 8   (01000)

s4= 19 (10011)


2. 计算适应度

假定适应度为f(s)=s^2 ,则

f (s1) = f(13) = 13^2 = 169

f (s2) = f(24) = 24^2 = 576

f (s3) = f(8) = 8^2 = 64

f (s4) = f(19) = 19^2 = 361

3. 选择

染色体的选择概率为:

染色体的累计概率为:

根据上面的式子,可得到:

例如设从区间[0, 1]中产生4个随机数: 

   r1 = 0.450126,    r2 = 0.110347 

   r3 = 0.572496,    r4 = 0.98503 

4. 交叉

基本遗传算法(SGA)中交叉算子采用单点交叉算子。

单点交叉运算

5. 变异

6. 至下一代,适应度计算→选择→交叉→变异,直至满足终止条件


五、遗传算法应用

这里使用具体的应用例子:函数优化

  • 问题的提出

     一元函数求最大值:

用微分法求取f(x)的最大值:

可求得最大值点:f(1.85)=3.85

0. 编码

     表现型:x
     基因型:二进制编码(串长取决于求解精度)
     串长与精度之间的关系:
     若要求求解精度到6位小数,区间长度为2-(-1)=3,即需将区间分为3/0.000001=3&times;106等份。
          所以编码的二进制串长应为22位。

1. 产生初始种群

     产生的方式:随机
     产生的结果:长度为22的二进制串
     产生的数量:种群的大小(规模),如30,50,…
          1111010011100001011000
          1100110011101010101110
          1010100011110010000100
          1011110010011100111001  
          0001100101001100000011    
          0000011010010000000000

2. 计算适应度

     不同的问题有不同的适应度计算方法
     本例:直接用目标函数作为适应度函数
     ①将某个体转化为[-1,2]区间的实数:
        s=<1000101110110101000111> → x=0.637197
     ②计算x的函数值(适应度):
        f(x)=xsin(10πx)+2.0=2.586345

     (0000000000000000000000)→-1
     (1111111111111111111111)→2

     上面的①其实就是二进制与十进制之间的转换:
     第一步,将一个二进制串(b21b20…b0)转化为10进制数:
        

      第二步,x’对应的区间[-1,2]内的实数:

     

3. 遗传操作

    选择:轮盘赌选择法;
    交叉:单点交叉;
    变异:小概率变异

  • 模拟结果

     设置的参数:
     种群大小50;交叉概率0.75;变异概率0.05;最大代数200。
     得到的最佳个体:
     smax=<1111001100111011111100>;
     xmax=1.8506;
     f(xmax)=3.8503;

  • 运行结果



六、总结

编码原则
完备性(completeness):问题空间的所有解都能表示为所设计的基因型;
健全性(soundness):任何一个基因型都对应于一个可能解;
非冗余性(non-redundancy):问题空间和表达空间一一对应。

适应度函数的重要性
     适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。
     一般而言,适应度函数是由目标函数变换而成的,对目标函数值域的某种映射变换称为适应度的尺度变换(fitness scaling)。

适应度函数设计不当有可能出现欺骗问题:
(1)进化初期,个别超常个体控制选择过程;
(2)进化末期,个体差异太小导致陷入局部极值。

欺骗问题举例:

可以想象一下,假设地球像类似灾难电影《后天》一样,出现有毒的雾霾,喜马拉雅山脉下有100只猴子(种群大小),只有爬上珠穆朗玛峰顶端的猴子才能生存下来,

因为喜马拉雅山脉有很多山峰,我们以高度作为适应度,case(1):如果不在珠峰的猴子若比在珠峰半山腰的猴子要高,因为种群大小不变,在珠峰的猴子可能就会被淘汰;

case(2):100只猴子都不在珠峰;

1. 选择的作用:优胜劣汰,适者生存;

2. 交叉的作用:保证种群的稳定性,朝着最优解的方向进化;

3. 变异的作用:保证种群的多样性,避免交叉可能产生的局部收敛;

下图很好地表现了遗传算法的精髓。

遗传算法的特点

  • 自组织、自适应和自学习性
    在编码方案、适应度函数及遗传算子确定后,算法将利用进化过程中获得的信息自行组织搜索。

  • 本质并行性
    内在并行性与内含并行性

  • 不需求导
    只需目标函数和适应度函数

  • 概率转换规则
    强调概率转换规则,而不是确定的转换规则


七、补充

因为遗传算法的每个操作对不同的应用选择的策略各有优劣,所以具体情况,具体分析,在此附上:

1. 选择

适应度计算:
按比例的适应度函数(proportional fitness assignment)
基于排序的适应度计算(Rank-based fitness assignment)

选择算法:
轮盘赌选择(roulette wheel selection)

随机遍历抽样(stochastic universal selection)
局部选择(local selection)
截断选择(truncation selection)
锦标赛选择(tournament selection)

2. 交叉

因为编码分二进制和浮点数编码,所以交叉和变异都有两类;

实值重组(real valued recombination):

离散重组(discrete recombination)

中间重组(intermediate recombination)

线性重组(linear recombination)

扩展线性重组(extended linear recombination)

二进制交叉(binary valued crossover):

单点交叉(single-point crossover)

多点交叉(multiple-point crossover)

均匀交叉(uniform crossover)

洗牌交叉(shuffle crossover)

缩小代理交叉(crossover with reduced surrogate)

3. 变异

实值变异
二进制变异

另外,遗传算法背后的理论支撑——模式定理,可以在对遗传算法有深入研究和优化的时候再详看。

© 著作权归作者所有

上一篇: KNN的一些总结
下一篇: K-means算法
c
粉丝 10
博文 6
码字总数 12826
作品 0
广州
私信 提问
加载中

评论(0)

【优化算法系列】关于遗传算法,你需要知道的事

如何使用遗传算法 遗传算法的运行过程 完整的遗传算法运算流程 遗传算法的基本操作 基本遗传算法 基本遗传算法的数学模型 基本遗传算法的步骤 遗传算法的具体例证 改进遗传算法 改进的遗传算...

AllenMoore
2018/02/02
84
0
【工具使用系列】关于 MATLAB 遗传算法与直接搜索工具箱,你需要知道的事

如何使用遗传算法与直接搜索工具箱 初步使用遗传算法工具 使用遗传算法工具GUI 从命令行使用遗传算法 遗传算法应用实施 遗传算法举例 初步使用直接搜索工具 浏览模式搜索工具 从命令行运行模...

AllenMoore
2018/02/02
234
0
优化算法之遗传算法

前几天,在听了学长关于遗传优化算法应用在考虑TMD作用的地震分析之后,感觉到优化算法一系列的优化算法的强大之处。回来也趁热打铁查了一下资料,大致理解一下遗传算法的机理。下面就记录分...

sinat_38321889
2018/01/08
0
0
遗传算法初接触

遗传算法(Genetic Algorithm, GA)是模拟达尔文的遗传选择和自然淘汰的生物进化工程的计算模型,它由美国Michigan大学J.Holland教授于1975年首先提出。 GA是全局寻优的优化算法,简单通用,...

文艺小青年
2017/06/30
0
0
人工智能--遗传算法(旅行商问题)

人工智能是研究使计算机来模拟人的某些思维过程和智能行为(如学习、推理、思考、规划等)的学科,主要包括计算机实现智能的原理、制造类似于人脑智能的计算机,使计算机能实现更高层次的应用...

空城机
2019/01/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 提前接受社会的毒打教育

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @爱吃蛋挞的kk:分享Buddy Guy的单曲《I Need You Tonight》 《I Need You Tonight》- Buddy Guy 手机党少年们想听歌,请使劲儿戳(这里) 凌...

小小编辑
17分钟前
23
0
成都哪里可以开租赁费发票-成都新闻网

成都哪里可以开租赁费发票【1.3.2 - 2.9.3.0 - 0.5.6.8.】李生,adb的全称为Android Debug Bridge,是Android手机通用的一个USB端口。百度CarLife的部分车机采用了...

提供格
20分钟前
21
0
成都哪里可以开钢材发票-成都新闻网

成都哪里可以开钢材发票【1.3.2 - 2.9.3.0 - 0.5.6.8.】李生,adb的全称为Android Debug Bridge,是Android手机通用的一个USB端口。百度CarLife的部分车机采用了该...

多徐重
22分钟前
17
0
成都哪里可以开医疗器械发票-成都新闻网

成都哪里可以开医疗器械发票【1.3.2 - 2.9.3.0 - 0.5.6.8.】李生,adb的全称为Android Debug Bridge,是Android手机通用的一个USB端口。百度CarLife的部分车机采用...

识过人石
23分钟前
43
0
函数

if ( ) {return 10;}else {return 20;}//“单一出口”理念,虽然上面这么写可以,但是最好只有一个return//把需要返回的值赋值给一个变量,最后统一返回,这样将来修改方便 void ...

heronos
34分钟前
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部