分享好友 行情首页 行情分类 切换频道
遗传算法精讲
2024-12-24 05:31  浏览:72

    智能优化算法又称现代启发式算法,是一种具有全局优化性能、通用性强且适合于并行处理的算法。

这种算法一般具有严密的理论依据,而不是单纯凭借专家经验,理论上可以在一定的时间内找到最优解或近似最优解。 

常用的智能优化算法有

    遗传算法 、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

    (本经典算法研究系列,日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。

1、遗传算法概述

      在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。 

    基本遗传算法(Simple Genetic Algorithms,GA)又称简单遗传算法或标准遗传算法,是由Goldberg总结出的一种最基本的遗传算法,其遗传进化操作过程简单,容易理解,是其它一些遗传算法的雏形和基础。

 

2、基本遗传算法的组成

(1)编码(产生初始种群

(2)适应度函数

(3)遗传算子(选择、交叉、变异

(4)运行参数

 

接下来,咱们分门别类,分别阐述着基本遗传算法的五个组成部分

1、编码

遗传算法(GA)通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。

正如研究生物遗传是从染色体着手,而染色体则是由基因排成的串。

基本遗传算法(SGA)使用二进制串进行编码。 

 

初始种群:基本遗传算法(SGA)采用随机方法生成若干个个体的集合,该集合称为初始种群。

初始种群中个体的数量称为种群规模。

 

2、适应度函数 

遗传算法对一个个体(解)的好坏用适应度函数值来评价,适应度函数值越大,解的质量越好。

适应度函数是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准

它的设计应结合求解问题本身的要求而定。 

 

3.1、选择算子

遗传算法使用选择运算对个体进行优胜劣汰操作。

适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。

选择操作的任务就是从父代群体中选取一些个体,遗传到下一代群体。

 

基本遗传算法(SGA)中选择算子采用轮盘赌选择方法。

 

Ok,下面就来看下这个轮盘赌的例子,这个例子通俗易懂,对理解选择算子帮助很大。

轮盘赌选择方法
轮盘赌选择又称比例选择算子,其基本思想是
各个个体被选中的概率与其适应度函数值大小成正比。

设群体大小为N,个体xi 的适应度为 f(xi),则个体xi的选择概率为

 

 

轮盘赌选择法可用如下过程模拟来实现
(1)在[0, 1]内产生一个均匀分布的随机数r。
(2)若r≤q1,则染色体x1被选中。
(3)若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。 
其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为

 

积累概率实例: 

 

轮盘赌选择方法的实现步骤:
(1)计算群体中所有个体的适应度值
(2)计算每个个体的选择概率
(3)计算积累概率
(4)采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配
来确定各个个体是否遗传到下一代群体中。

例如,有染色体
s1= 13 (01101)
s2= 24 (11000) 
s3= 8   (01000)
s4= 19 (10011)

假定适应度为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

染色体的选择概率为

 

染色体的累计概率为

 

 

根据上面的式子,可得到

 

 

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

 

   r1 = 0.450126,    r2 = 0.110347 

   r3 = 0.572496,    r4 = 0.98503 

 

 

 

3.2、交叉算子

交叉运算,是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因
从而形成两个新的个体。

交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用
是产生新个体的主要方法。
基本遗传算法(SGA)中交叉算子采用单点交叉算子。

单点交叉运算

3.3、变异算子 

变异运算,是指改变个体编码串中的某些基因值,从而形成新的个体。
变异运算是产生新个体的辅助方法,决定遗传算法的局部搜索能力,保持种群多样性。

交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。
基本遗传算法(SGA)中变异算子采用基本位变异算子。

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0
则将其变为1;反之,若原有基因值为1,则将其变为0 。

基本位变异算子的执行过程

4、运行参数

(1)M  :种群规模 
(2)T  : 遗传运算的终止进化代数 
(3)Pc  :交叉概率 
(4)Pm :变异概率

 

三、浅出遗传算法

遗传算法的本质

遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传
到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式突变。
通过这些遗传操作,模式逐步向较好的方向进化,最终得到问题的最优解。

遗传算法的主要有以下八方面的应用
(1)组合优化      (2)函数优化 (3)自动控制      (4)生产调度 
(5)图像处理      (6)机器学习 (7)人工生命      (8)数据挖掘

 

四、遗传算法的应用

遗传算法的应用举例、透析本质(这个例子简明、但很重要

已知x为整数,利用遗传算法求解区间[0, 31]上的二次函数y=x2的最大值。

 

[分析]

原问题可转化为在区间[0, 31]中搜索能使 y 取最大值的点 a 的问题。
个体[0, 31] 中的任意点x
适应度:函数值f(x)=x2 
解空间:区间[0, 31

这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。

[]

(1) 设定种群规模,编码染色体,产生初始种群。
将种群规模设定为4;用5位二进制数编码染色体;取下列个体组成初始种群S1

s1= 13 (01101),  s2= 24 (11000)
s3= 8 (01000),    s4= 19 (10011) 

(2) 定义适应度函数, 取适应度函数
f (x)=x^2

(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,
直到适应度最高的个体,即31(11111)出现为止。

首先计算种群S1中各个体
s1= 13(01101),    s2= 24(11000)
s3= 8(01000),      s4= 19(10011)
的适应度f (si), 容易求得
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

再计算种群S1中各个体的选择概率

由此可求得
P(s1) = P(13) = 0.14
P(s2) = P(24) = 0.49
P(s3) = P(8) = 0.06
P(s4) = P(19) = 0.31

再计算种群S1中各个体的积累概率

 

 

选择-复制 

设从区间[0, 1]中产生4个随机数如下:
r1 = 0.450126,     r2 = 0.110347 
r3 = 0.572496,     r4 = 0.98503

 

于是,经复制得群体
s1’ =11000(24),  s2’ =01101(13) 
s3’ =11000(24(24被选中俩次),  s4’ =10011(19

 

 

 

交叉

设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。
设s1’与s2’配对,s3’与s4’配对。
s1’ =11000(24),  s2’ =01101(13
s3’ =11000(24),  s4’ =10011(19
分别交换后两位基因,得新染色体
s1’’=11001(25),  s2’’=01100(12
s3’’=11011(27),  s4’’=10000(16

 

变异  

设变异率pm=0.001。
这样,群体S1中共有
5×4×0.001=0.02
位基因可以变异。
0.02位显然不足1位,所以本轮遗传操作不做变异。

于是,得到第二代种群S2
s1=11001(25),   s2=01100(12
s3=11011(27),   s4=10000(16

第二代种群S2中各染色体的情况

 

假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中,则得到群体
 s1’=11001(25),  s2’= 01100(12
 s3’=11011(27),  s4’= 10000(16

做交叉运算,让s1’与s2’,s3’与s4’ 分别交换后三位基因,得 
  s1’’=11100(28),    s2’’ = 01001(9
  s3’’ =11000(24),   s4’’ = 10011(19

这一轮仍然不会发生变异。
于是,得第三代种群S3
 s1=11100(28),  s2=01001(9
 s3=11000(24),  s4=10011(19

第三代种群S3中各染色体的情况

设这一轮的选择-复制结果为

s1’=11100(28),   s2’=11100(28

s3’=11000(24),   s4’=10011(19

 

做交叉运算,让s1’与s4’,s2’与s3’ 分别交换后两位基因,得

  s1’’=11111(31),  s2’’=11100(28

  s3’’=11000(24),  s4’’=10000(16

 

这一轮仍然不会发生变异。

 

 

于是,得第四代种群S4 

s1=11111(31)(出现最优解),  s2=11100(28

s3=11000(24),  s4=10000(16

 

显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。

 

于是,遗传操作终止,将染色体(11111)作为最终结果输出。

然后,将染色体“11111”解码为表现型,即得所求的最优解:31。

将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。 

 

所以,综合以上各代群的情况,如下

ok,完。
文章有误之处,一经发现,立马修正。同时,也望各位不吝指正。
-------------------------------------------

  1. 遗传算法入门-博客园-苍梧 
    本文主要参考,推荐!感谢作者~

  2. 经典算法研究系列:七、深入浅出遗传算法
    July大神写的,通俗易懂,推荐

  3. HELLO,遗传算法
    博主语言轻松,用python描述了遗传算法求解一个函数最大值的例子。

  4. 遗传算法理论基础与简单应用实例
    博主总结整理的内容,挺不错的,文中的链接有实例应用。

  5. 遗传算法入门到掌握(一) CSDN-GA代码下载
    袋鼠跳的例子来描述了GA算法,帮助理解GA。

  6. 非常好的理解遗传算法的例子
    求下述二元函数的最大值的例子

  7. 遗传算法学习心得

引用地址:https://blog.csdn.net/v_JULY_v/article/details/6132775

 

    以上就是本篇文章【遗传算法精讲】的全部内容了,欢迎阅览 ! 文章地址:http://w.yusign.com/quote/3846.html 
     行业      资讯      企业新闻      行情      企业黄页      同类资讯      网站地图      返回首页 述古往 http://w.yusign.com/mobile/ , 查看更多   
最新新闻
相册管家 2.7.9手机相册「相册管家 2.7.9」
360加固ACCESS_COARSE_LOCATION通过WiFi或移动基站的方式获取用户错略的经纬度信息,定位精度大概误差在30~1500米ACCESS_FINE_LO
苹果12价格深度解析,市场定位、影响因素与未来趋势展望苹果12手机价格「苹果12价格深度解析,市场定位、影响因素与未来趋势展望」
摘要:苹果12的价格分析涉及市场定位、影响因素和未来趋势预测。苹果12在市场上定位中高端,价格受供应链、竞争态势、技术投入和
旧手机值多少钱,如何“以旧换新”换购新款 iPhone?手机以旧换新「旧手机值多少钱,如何“以旧换新”换购新款 iPhone?」
近日,苹果在其官方微信中分享了新的“以旧换新”方案,其好处在于,能够更轻松地入手最新款的 iPhone,操作简单、安心,不用担
此千元机“难能不可贵” 荣耀8X、8X MAX手机体验评测荣耀8x手机尺寸「此千元机“难能不可贵” 荣耀8X、8X MAX手机体验评测」
此前,荣耀推出的X系列第一款全面屏手机——荣耀畅玩7X,无论是配置上还是在价格上都得到了许多消费者的青睐,并且在某电商平台上获
金溪农商银行举行预备党员转正、入党宣誓仪式
周骏强 严若兰 为进一步践行省联社党建领行战略,进一步做好党员发展工作,增强党组织的凝聚力、战斗力和影响力,近日,金溪农商
红米的8A手机红米手机怎么样「红米的8A手机」
外观手感:这款手机是入门机,在质感方面自然没有办法和旗舰相比。边框和后盖是一体塑料,但是并没有特别明显的廉价感,握持手感
饥荒秘籍代码大全 手机版秘籍饥荒手机版「饥荒秘籍代码大全 手机版秘籍」
饥荒数据库为您提供饥荒物品代码、物品属性介绍、物品的合成和获取方法,快来一起了解下吧!点击查看>:饥荒数据库 今天小编跟大
玩手机上瘾 | “低头族”头晕或因耳朵出问题低头玩手机「玩手机上瘾 | “低头族”头晕或因耳朵出问题」
引言Introduction_能引起头晕的疾病有上百种,如贫血、心脏病、颈椎病、脑动脉硬化、耳石症等,但患者往往不知道该挂哪个科室的
盘点2023年度最佳手游模拟器,性能与兼容性全面评测手机游戏模拟器「盘点2023年度最佳手游模拟器,性能与兼容性全面评测」
1、蓝叠模拟器:作为市场上最受欢迎的Android模拟器之一,蓝叠模拟器以其流畅的运行能力和出色的图形性能而闻名,它能够轻松应对
作品 | 青春映绿茵,足球跃海浪——青岛青春足球场
△ 图1 西瞰碧海△ 图2 东望崂山‘’PART.1。概况青岛青春足球场是山东省首座大型专业足球场,选址于青岛市城阳区,总用地面积16
本企业新闻
推荐企业新闻
发表评论
0评