没有合适的资源?快使用搜索试试~ 我知道了~
遗传算法与优化问答(重要有代码).pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 42 浏览量
2022-05-22
23:45:21
上传
评论
收藏 1.39MB PDF 举报
温馨提示
试读
26页
。。。
资源推荐
资源详情
资源评论
.
实验十 遗传算法与优化问题
一、问题背景与实验目的
遗传算法(Genetic Algorithm—GA),是模拟达尔文的遗传选择和自然淘
汰的生物进化过程的计算模型,它是由美国 Michigan 大学的 J.Holland 教授于
1975 年首先提出的.遗传算法作为一种新的全局优化搜索算法,以其简单通用、
鲁棒性强、适于并行处理及应用范围广等显著特点,奠定了它作为 21 世纪关键
智能计算之一的地位.
本实验将首先介绍一下遗传算法的基本理论,然后用其解决几个简单的函数
最值问题,使读者能够学会利用遗传算法进行初步的优化计算.
1.遗传算法的基本原理
遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参
数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而
得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生
存竞争,适者有最好的机会生存和产生后代.后代随机化地继承了父代的最好特
征,并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环
境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解.值
得注意的一点是,现在的遗传算法是受生物进化论学说的启发提出的,这种学说
对我们用计算机解决复杂问题很有用,而它本身是否完全正确并不重要(目前生
物界对此学说尚有争议).
(1)遗传算法中的生物遗传学概念
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法;故而在
这个算法中要用到各种进化和遗传学的概念.
.
首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关
系.这些概念如下:
序号
1
2
3
4
5
6
7
8
9
10
11
12
13
遗传学概念
个体
群体
染色体
基因
基因位
适应值
种群
选择
交叉
交叉概率
变异
变异概率
进化、
适者生存
遗传算法概念
要处理的基本对象、结构
个体的集合
个体的表现形式
染色体中的元素
数学概念
也就是可行解
被选定的一组可行解
可行解的编码
编码中的元素
某一基因在染色体中的位置 元素在编码中的位置
个体对于环境的适应程度, 可行解所对应的适应函数
或在环境压力下的生存能力 值
被选定的一组染色体或个体 根据入选概率定出的一组
可行解
从群体中选择优胜的个体, 保留或复制适应值大的可
淘汰劣质个体的操作
交换
率(可能性大小)
染色体水平上基因变化
(可能性大小)
一代又一代地优化
行解,去掉小的可行解
新解
一般为 0.65~0.90
编码的某些元素被改变
一般为 0.001~0.01
优的可行解
一组染色体上对应基因段的 根据交叉原则产生的一组
染色体对应基因段交换的概 闭区间[0,1]上的一个值,
染色体上基 因变化的 概率 开区间 (0,1)内的一个 值,
个体进行优胜劣汰的进化, 目标函数取到最大值,最
(2)遗传算法的步骤
遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程,主要有
三个基本操作(或称为算子):选择( Selection)、交叉( Crossover)、变异
(Mutation).
遗传算法基本步骤主要是:先把问题的解表示成“染色体”,在算法中也就
是以二进制编码的串,在执行遗传算法之前,给出一群“染色体”,也就是假设
.
的可行解.然后,把这些假设的可行解置于问题的“环境”中,并按适者生存的
原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉、变异过程产
生更适应环境的新一代“染色体”群.经过这样的一代一代地进化,最后就会收
敛到最适应环境的一个“染色体”上,它就是问题的最优解.
下面给出遗传算法的具体步骤,流程图参见图 1:
第一步:选择编码策略,把参数集合(可行解集合)转换染色体结构空间;
第二步:定义适应函数,便于计算适应值;
第三步:确定遗传策略,包括选择群体大小,选择、交叉、变异方法以及确
定交叉概率、变异概率等遗传参数;
第四步:随机产生初始化群体;
第五步:计算群体中的个体或染色体解码后的适应值;
第六步:按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一
代群体;
第七步:判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数,
不满足则返回第五步、或者修改遗传策略再返回第六步.
得到结果
是
产生初始群体
是否满足终止条件
否
结束程序
计算每个个体的适应值
以概率选择遗传算子
选择一个个体
复制到新群体
选择两个个体进行
交叉插入到新群体
选择一个个体进行
变异插入到新群体
得到新群体
.
图 1 一个遗传算法的具体步骤
遗传算法有很多种具体的不同实现过程,以上介绍的是标准遗传算法的主要
步骤,此算法会一直运行直到找到满足条件的最优解为止.
2.遗传算法的实际应用
例 1:设
f (x) x
2
2x 0.5
,求
max f (x), x [1,2]
.
注:这是一个非常简单的二次函数求极值的问题,相信大家都会做.在此我
们要研究的不是问题本身,而是借此来说明如何通过遗传算法分析和解决问题.
在此将细化地给出遗传算法的整个过程.
(1)编码和产生初始群体
首先第一步要确定编码的策略,也就是说如何把
1
到 2 这个区间内的数用计
算机语言表示出来.
编码就是表现型到基因型的映射,编码时要注意以下三个原则:
完备性:问题空间中所有点(潜在解)都能成为 GA 编码空间中的点(染色
体位串)的表现型;
健全性:GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解;
非冗余性:染色体和潜在解必须一一对应.
这里我们通过采用二进制的形式来解决编码问题,将某个变量值代表的个体
表示为一个{0,1}二进制串.当然,串长取决于求解的精度.如果要设定求解精
度到六位小数,由于区间长度为
2 (1) 3
,则必须将闭区间
[1,2]
分为
310
6
等分.因为
2097152 2
21
310
6
2
22
4194304
所以编码的二进制串至少需要
22 位.
将一个二进制串(b
21
b
20
b
19
… b
1
b
0
)转化为区间
[1,2]
内对应的实数值很简
单,只需采取以下两步(Matlab 程序参见附录 4):
1)将一个二进制串(b
21
b
20
b
19
… b
1
b
0
)代表的二进制数化为 10 进制数:
(b
21
b
20
b
19
b
1
b
0
)
2
(
b
i
2
i
)
10
x '
i0
21
2)
x '
对应的区间
[1,2]
内的实数:
.
x 1 x'
2 (1)
2
22
1
例 如 , 一 个 二 进 制 串 a=<1000101110110101000111> 表 示 实 数
0.637197.
x '
=(1000101110110101000111)
2
=2288967
x 1 2288967
3
0.637197
22
2 1
二 进 制 串 <0000000000000000000000> ,
<1111111111111111111111>,则分别表示区间的两个端点值-1 和 2.
利用这种方法我们就完成了遗传算法的第一步——编码,这种二进制编码的
方法完全符合上述的编码的三个原则.
首先我们来随机的产生一个个体数为 4 个的初始群体如下:
pop(1)={
<1101011101001100011110>, %% a1
<1000011001010001000010>, %% a2
<0001100111010110000000>, %% a3
<0110101001101110010101>} %% a4(Matlab 程序参见附录 2)
化成十进制的数分别为:
pop(1)={ 1.523032,0.574022 ,-0.697235 ,0.247238 }
接下来我们就要解决每个染色体个体的适应值问题了.
(2)定义适应函数和适应值
由于给定的目标函数
f (x) x
2
2x 0.5
在
[1,2]
内的值有正有负,所以必
须通过建立适应函数与目标函数的映射关系,保证映射后的适应值非负,而且目
标函数的优化方向应对应于适应值增大的方向,也为以后计算各个体的入选概率
剩余25页未读,继续阅读
资源评论
苦茶子12138
- 粉丝: 1w+
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功