遗传算法学习心得体会1.docx
- 文档编号:9492109
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:14
- 大小:21.77KB
遗传算法学习心得体会1.docx
《遗传算法学习心得体会1.docx》由会员分享,可在线阅读,更多相关《遗传算法学习心得体会1.docx(14页珍藏版)》请在冰点文库上搜索。
遗传算法学习心得体会1
遗传算法学习心得体会
篇一:
遗传算法总结
遗传算法总结
遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局自适应概率搜索算法。
一、遗传算法流程图
图1遗传算法流程图
二、遗传算法的原理和方法
1)染色体编码
把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。
deJong曾提出了两条操作性较强的实用编码原则:
编码原则一:
应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案;编码原则二:
应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。
编码方法主要有以下几种:
二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法、参数级联编码方法、多参数交叉编码方法。
2)适应值计算
由解空间中某一点的目标函数值f(x)到搜索空间中对应个体的适应度函数值
Fit(f(x))的转换方法基本上有一下三种:
a.直接以待解的目标函数值f(x)转化为适应度函数值Fit(f(x))(:
遗传算法学习心得体会),令
?
f(x)目标函数为最大化函数
Fit(fx())=?
?
?
f(x)目标函数为最小化函数
?
cmax?
f(x)f(x)?
cmax
b.对于最小值的问题,做下列转化Fit(f(x))?
?
,其中cmax是
0其他?
f(x)的最大输入值。
c.若目标函数为最小值问题,Fit(f(x))?
1
c?
0,c?
f(x)?
0
1?
c?
f(x)
1
c?
0,c?
f(x)?
0
1?
c?
f(x)
若目标函数为最大值问题,Fit(f(x))?
3)选择、交叉、变异
遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作:
根据每个个体的适应度值大小选择。
适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体的被遗传到下一代群体中的概率较小。
其中选择的方法有:
轮盘赌选择、随机竞争选择、最佳保留选择、无回放随机选择、确定式选择等。
遗传算法中的所谓交叉运算,是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体。
交叉操作主要有单点交叉、两点交叉与多点交叉、均匀交叉和算数交叉四种。
遗传算法中的变异运算,是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他基因来替换,从而形成一个新的个体。
主要有基本位变异、均匀变异、边界变异等几种变异操作方法。
4)控制参数选择
交叉概率pcpm
三、算例
minf(x1,x2)?
(x1?
3)2?
(x2?
2)2
2
?
g1(x1,x2)?
x12?
x2?
5?
s.t.?
h1(x1,x2)?
x1?
2x2?
4?
0?
x,x?
10,x?
n
121?
(1)
1)三种不同的遗传方法
方法一:
原模型中x1、x2均为决策变量,操作如下。
a.采用混合整数编码,对x1进行十进制编码,x2进行二进制编码;b.适应度函数值采用Fit(f(x1,x2))?
1
计算,其中
c?
f(x1,x2)
c?
?
?
max{0,g1(x1,x2)?
5}?
?
?
max{0,|h1(x1,x2)?
4|},?
=?
=10000;
c.采用赌轮盘选择、单点交叉和基本位变异;
d.pc=0.8,pm=0.1,遗传代数为200,种群中个体数100;e.终止条件为连续十次最优个体保持不变或遗传代数到达200。
方法二:
已知等式约束h1(x1,x2),可得x2?
(4?
x1)/2,则原问题可化为
minf(x1)?
(x1?
3)2?
((
4?
x1
)?
2)22
(2)
4?
x12?
2
g(x)?
x?
()?
5111?
2?
s..t?
0?
x1?
10,x1?
n?
4?
x1?
0?
?
10
2?
x
minf(x1)?
(x1?
3)2?
(1)2
2
即等式约束简化后的模型为4?
x12?
2
g(x)?
x?
()?
5?
1
s..t?
112?
?
0?
x1?
4,x1?
n
其中a~b的操作如下,而c~e的操作同方法一。
a.对x1进行十进制编码;
b.适应度函数值采用Fit(f(x1,x2))?
(3)
1
计算,其中
c?
f(x1,x2)
c?
?
?
max{0,g1(x1,x2)?
5},?
=10000
方法三:
在方法二的基础上,改变x1的编码方法,对x1进行二进制编码。
由于0?
x1?
4,且为自然数,则二进制编码至少为3位,但3位的二进制可以表示0~7的整数,所以存在冗余编码。
则通过惩罚来排除冗余编码,即适应度函数值采用
Fit(f(x1,x2))?
1
计算。
c?
f(x1,x2)
其中c?
?
?
max{0,g1(x1,x2)?
5}?
?
?
max{0,x1(i)?
4},?
=10000。
x1(i)表示个体解码后的x1。
2)三种方法的计算结果
方法一可得到三个不同的解:
解1:
x1?
2,x2?
1,Fit(f(x1,x2))?
0.4646,f(x)?
2.0000,适应度趋势图如下:
图2方法一解1的适应度趋势图
解2:
x1?
0,x2?
2,Fit(f(x1,x2))?
0.1075,f(x)?
9.0000,适应度趋势图如下:
篇二:
遗传算法学习心得
基本概念
遗传算法(Geneticalgorithms,Ga)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。
Ga的组成:
(1)编码(产生初始种群)
(2)适应度函数
(3)遗传算子(选择、交叉、变异)
(4)运行参数
编码
基因在一定能够意义上包含了它所代表的问题的解。
基因的编码方式有很多,这也取决于要解决的问题本身。
常见的编码方式有:
(1)二进制编码,基因用0或1表示(常用于解决01背包问题)如:
基因a:
00100011010(代表一个个体的染色体)
(2)互换编码(用于解决排序问题,如旅行商问题和调度问题)
如旅行商问题中,一串基因编码用来表示遍历的城市顺序,如:
234517986,表示九个城市中,先经过城市2,再经过城市3,依此类推。
(3)树形编码(用于遗传规划中的演化编程或者表示)
如,问题:
给定了很多组输入和输出。
请你为这些输入输出选择一个函数,使得这个函数把每个输入尽可能近地映射为输出。
编码方法:
基因就是树形结构中的一些函数。
(4)值编码(二进制编码不好用时,解决复杂的数值问题)
在值编码中,每个基因就是一串取值。
这些取值可以是与问题有关任何值:
整数,实数,字符或者其他一些更复杂的东西。
适应度函数
遗传算法对一个个体(解)的好坏用适应度函数值来评价,适应度函数值越大,解的质量越好。
适应度函数是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。
如TSP问题,遍历各城市路径之和越小越好,这样可以用可能的最大路径长度减去实际经过的路径长度,作为该问题的适应度函数。
遗传算子——选择
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作:
适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。
选择操作的任务就是按某种方法从父代群体中选取一些个体,遗传到下一代群体。
SGa(基本遗传算法)中采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子,基本思想:
各个个体被选中的概率与其适应度函数值大小成正比。
设群体大小为n,个体i的适应度为Fi,则个体i被选中遗传到下一代群体的概率为:
遗传算子——交叉
所谓交叉运算,是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因,从而形成两个新的个体。
交叉运算在Ga中起关键作用,是产生新个体的主要方法。
1.单交叉点法(用于二进制编码)
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如:
交叉前:
00000|01110000000010000
11100|00000111111000101
交叉后:
00000|00000111111000101
11100|01110000000010000
2.双交叉点法(用于二进制编码)
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.
如:
交叉前:
01|0010|11
11|0111|01
交叉后:
11|0010|01
01|0111|11
3.基于“与/或”交叉法(用于二进制编码)
对父代按位”与”逻辑运算产生一子代a;按位”或”逻辑运算产生另一子代B。
该交叉策略在解背包问题中效果较好.
如:
交叉前:
01001011
11011101
交叉后:
01001001
11011111
4.单交叉点法(用于互换编码)
选择一个交叉点,子代的从初始位置出发的部分从一个基因复制,然后在另一个基因中扫描,如果某个位点在子代中没有,就把它添加进去。
如:
交叉前:
87213|09546
98356|71420
交叉后:
87213|95640
98356|72104
5.部分匹配交叉(PmX)法(用于互换编码)
先随机产生两个交叉点,定义这两点间的区域为匹配区域,并用交换两个父代的匹配区域。
父代a:
872|130|9546
父代B:
983|567|1420变为:
TEmPa:
872|567|9546
TEmPB:
983|130|1420
对于TEmPa、TEmPB中匹配区域以外出现的数码重复,要依据匹配区域内的位置逐一进行替换。
匹配关系:
153670子代A:
802|567|9143
子代B:
986|130|5427
6.顺序交叉法(oX)(用于互换编码)
从父代A随机选一个编码子串,放到子代A的对应位置;子代A空余的位置从父代B中按B的顺序选取(与己有编码不重复)。
同理可得子代B。
父代a:
872|139|0546
父代B:
983|567|1420
交叉后:
子代a:
856|139|7420
子代B:
821|567|3904
7.循环交叉(cX)法(用于互换编码)
cX同oX交叉都是从一个亲代中取一些城市,而其它城市来自另外一个亲代,但是二者不同之处在于:
oX中来自第一个亲代的编码子串是随机产生的,而cX却不是,它是根据两个双亲相应位置的编码而确定的。
父代A:
123456789
|||||
父代A:
546923781
可得循环基因:
1->5->2->4->9->1
用循环的基因构成子代A,顺序与父代A一样
12459
用父代B剩余的基因填满子代A:
126453789
子代B的编码同理。
(循环基因5->1->9->4->2->5)
遗传算子——变异
变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换,从而形成一个新的个体。
Ga中的变异运算是产生新个体的辅助方法,它决定了Ga的局部搜索能力,同时保持种群的多样性。
交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。
注:
变异概率Pm不能太小,这样降低全局搜索能力;也不能太大,Pm>0.5,这时Ga退化为随机搜索。
篇三:
遗传算法总结
遗传算法
概念
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,它借鉴了达尔文的进化论和孟德尔的遗传学说。
其本质是一种高效、并行、全局搜索的方法,它既能在搜索中自动获取和积累有关空间知识,并自适应地控制搜索过程以求得最优解遗传算法操作使用适者生存的原则,在潜在的解决方案种群中逐次产生一个近视最优方案。
在遗传算法的每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近视解。
这个过程导致种群中个体的进化,得到的新个体比原个体更适应环境,就像自然界中的改造一样。
应用
遗传算法在人工智能的众多领域具有广泛应用。
例如,机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化(如TSP、背包问题)、函数的最大值以及图像处理和信号处理等等。
遗传算法多用应与复杂函数的优化问题中。
原理
遗传算法模拟了自然选择和遗传中发生的复制、交叉、和变异等现象,从任一初始种群出发,通过随机选择、交叉、变异操作,产生一群更适合环境的个体,使群体进行到搜索空间中越来越好的区域,这样一代一代地不断繁衍进化,最后收敛到一群最适合环境的个体求得问题的最优解。
算法流程1.编码:
解空间中的解数据x,作为作为遗传算法的表现型形式。
从表现
型到基本型的映射称为编码。
遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基本型串结构数据,这些串结构数据的不同的组合就构成了不同的点。
2.初始种群的形成:
随机产生n个初始串数据,每个串数据称为一个个体,
n个串数据构成了一个群体。
遗传算法以这n个串结构作为初始点开始迭代。
设置进化代数计数器t0;设置最大进行代数T;随机生成m个个体作为初始群体P(0)。
3.适应度检测:
适应度就是借鉴生物个体对环境的适应程度,适应度函数
就是对问题中的个体对象所设计的表征其优劣的一种测度。
根据具体问题计算P(t)的适应度。
4.选择:
将选择算子作用于群体。
选择的目的是把优化的个体直接遗传到
下一代或通过配对交叉产生新的个体再遗传到下一代。
选择操作是建立在群体中个体的适应度评估基础上的。
5.交叉:
将交叉算子作用于群体。
所谓交叉是指把两个父代个体的部分结
构加以替换重组而生成新个体的操作。
遗传算法中起核心作用的就是交叉算子。
6.变异:
将变异算子作用于群体。
即是对群体中的个体串的某些基因座上
的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
7.终止条件判断:
若t到的具有最大适应度个体作为最优解输出,终止计算。
遗传算法流程图如下图所示:
遗传算法
下几种:
适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法是最简单也是最常用的选择方法。
在该方法中,各个个体的选择概率和其适应度值成比例。
设群体大小为n,其中个体i的适应度为,则i被选择的概率,为遗传算法
2、交叉:
在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。
同样,遗传算法中起核心作用的是遗传操作的交叉算子。
所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。
通过交叉,遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因,能够产生新的基因组合,期望将有益基因组合在一起。
根据编码表示方法的不同,可以有以下的算法:
a)实值重组(realvaluedrecombination)
1)离散重组(discreterecombination)
2)中间重组(intermediaterecombination)
3)线性重组(linearrecombination)
4)扩展线性重组(extendedlinearrecombination)。
b)二进制交叉(binaryvaluedcrossover)
1)单点交叉(single-pointcrossover)
2)多点交叉(multiple-pointcrossover)
3)均匀交叉(uniformcrossover)
4)洗牌交叉(shufflecrossover)
5)缩小代理交叉(crossoverwithreducedsurrogate)。
3、变异
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。
依据个体编码表示方法的不同,可以有以下的算法:
a)实值变异
b)二进制变异。
一般来说,变异算子操作的基本步骤如下:
a)对群中所有个体以事先设定的编译概率判断是否进行变异
b)对进行变异的个体随机选择变异位进行变异。
例:
简单一元函数优化
求下面函数的最大值:
f(x)=xsin(10*pi*x)+2.0,-1程序:
figure
(1);
fplot('variable.*sin(10*pi*variable)+2.0',[-1,2]);%画出函数曲线
%定义遗传算法参数
nind=40;%个体数目(numberofindividuals)
maXGEn=25;%最大遗传代数(maximumnumberofgenerations)PREci=20;%变量的二进制位数(Precisionofvariables)
GGaP=0.9;%代沟(Generationgap)
trace=zeros(2,maXGEn);%寻优结果的初始值
Fieldd=[20;-1;2;1;0;1;1];%区域描述器(Buildfielddescriptor)
chrom=crtbp(nind,PREci);%初始种群
gen=0;%代计数器
variable=bs2rv(chrom,Fieldd);%计算初始种群的十进制转换objV=variable.*sin(10*pi*variable)+2.0;%计算目标函数值
whilegenFitnV=ranking(-objV);%分配适应度值(assignfitnessvalues)
Selch=select('sus',chrom,FitnV,GGaP);%选择
Selch=recombin('xovsp',Selch,0.7);%重组
Selch=mut(Selch);%变异
variable=bs2rv(Selch,Fieldd);%子代个体的十进制转换
objVSel=variable.*sin(10*pi*variable)+2.0;%计算子代的目标函数值
[chromobjV]=reins(chrom,Selch,1,1,objV,objVSel);%重插入子代的新种群
variable=bs2rv(chrom,Fieldd);
gen=gen+1;%代计数器增加
%输出最优解及其序号,并在目标函数图像中标出,Y为最优解,i为种群的序号
[Y,i]=max(objV);holdon;
plot(variable(i),Y,'bo');
trace(1,gen)=max(objV);%遗传算法性能跟踪trace(2,gen)=sum(objV)/length(objV);
end
variable=bs2rv(chrom,Fieldd);%最优个体的十进制转
holdon,grid;
plot(variable,objV,'b*');
figure
(2);
plot(trace(1,:
));
holdon;
plot(trace(2,:
),'-.');grid
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 学习心得 体会