文档介绍：(完整)基本遗传算法
基本遗传算法
Holland创建的遗传算法是一种概率搜索算法,它利用某种编码技术作用于称为染色体的数串，、然而是随机的信息交换，重新组合那些适应性好的串
0
式中:C个体的编码方法；
E个体适应度评价函数；
P—-初始种群；
0
M--种群大小；
①选择算子；
r-一交叉算子；
屮一变异算子；
T遗传算法终止条件。
四．基本遗传算法的步骤
（ChromosomeCoding）与解码（Decode）
基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值
{0,1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。
（1）编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码•设某一参数的取值范围为[U，U],我们用长度为k的二进制编码符号来表示该参数，则12
它总共产生2k种不同的编码，可使参数编码时的对应关系为：
(完整)基本遗传算法
OOOOOO・・・OOOO=OTU
1
000000・・・0001=1TU+s
1
000000・・・0010=2TU+2S
1
•••
111111…1111=2k—1TU
2
其中，S=U2-U1.
2k-1
(2)解码：假设某一个体的编码为bbb・・・bb，则对应的解码公式为
kk—1k—221
X=U+(fb*2i-1)*U2-Ui①
ii2k—1
i=1
例如：设有参数xw[2,4],现用5位二进制编码对X进行编码，得25=32个二进制串(染色体)：
00000,00001,00010，00011，00100,00101,00110,00111
01000,01001，01010，01011，01100，01101,01110，01111
10000,10001,10010，10011，10100,10101，10110，1011111000,11001,11010，11011,11100，11101，11110,11111
对于任一个二进制串，只要代入公式①，就可得到相应的解码，如X=10101,它对应的十
22
进制为丈b-2i-1=1+0*2+1*22+0*23+1*24=21，则对应参数X的值为2+21*(4—2)/(25—1)
i
i=1
=3。3548。
2．个体适应度的检测评估
基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估计这个概率，,根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数C，使个体的适应度为目标函数值加上正数C.
(完整)基本遗传算法
3・遗传算子
基本遗传算法使用下列三种遗传算子：
(1)
孙的遗传可能性。若设种群数为M,个体i的适应度为f.,则个体i被选取的概率为
I
k=1
当个体选择的概率给定后，产生［0,1］
选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘
汰。
我们经常采用的是轮盘赌的原理，
率的总和或当前种群中所有个体原始适应度值一方式映像到范围［0,sum］的一连续区间，，轮盘
图1枪盘赌选择
选择概率是基于它们
有个体期望的选择概
的总和。个体采用一对
一个体区间的大小与
赌轮的周长是6个个
体适应度值的总和，个体5是最大适应度个体，，用在［0,sum］
间产生随机数，看此随机数在哪个个体的区间上，则此个体被选中。重复此过程，直到所需数量
个体被选中为止。
交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个
个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两
个子个体，如图2所示。
父个体1
父个体2
图2单点交叉示意图
P0
00
子个体1
子个体2
变异运算使用基本位变异算子或均匀变异算子。为了避免问题过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1