基本遗传算法

(完整)基本遗传算法(完整)基本遗传算法基本遗传算法Holland创建的遗传算法是一种概率搜索算法,它利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程.该算法通过有组织的、然而是随机的信息交换，重新组合那些适应性好的串.在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机优化算法，它可以有效地利用已有的信息处理来搜索那些有希望改善更多的繁殖机会.

第一章遗传算法的运行过程遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象 ,从任一初始种群（Population）出发,通过随机选择、交叉和变异操作，产生一群更适应环境的个体,使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体(Individual),求得问题的最优解。一．完整的遗传算法运算流程完整的遗传算法运算流程可以用图1来描述。1）主要运算过程如下：编码:解空间中的解数据x,遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。NNN←0；设置最大进化代数T;随机生成M个个体作为初始群体P（0。P(t）中各个个体的适应度。选择：将选择算子作用于群体。交叉:将交叉算子作用于群体。变异：将变异算子作用于群体。群体P(t）经过选择、交叉、变异运算后得到下一代群体P（t+1).终止条件判断：若t≤T，则t←t+1,转到步骤（2；若t＞具有最大适应度的个体作为最优解输出,终止运算。了一个基本框架。实际问题参数编码成位串实际问题参数编码成位串位串解释得到参数计算目标函数函数值向适值映射适值调整1计算适应值三种基本遗传算子：变异算子选择与遗传随机算子12统计结果2经过优化的一个或多个参数集（由解码得到）改善或解决实际问题1遗传算法运算流程GoldbergP(t）P(0）是随机设计的，简单遗传算法的伪代码描述如下：produreGAbegint=0;initializeP（t)；evaluateP（t)；whilenotfinishedbegint=t+1；selectP（t)fromP(t-1）;reproducepairsinP(t）;evaluateP(t）;endend二．遗传算法的基本操作遗传算法有三个基本操作：选择（Selection、交叉(Crossover)和变异（Mutation)。强的个体为下一代贡献一个或多个后代的概率大.这样就体现了达尔文的适者生存原则。（2）（称为交叉概率，CrossoverRate）交换它们之间的部分染色体.交叉体现了信息交换的思想.（3)变异.变异操作首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变Rate）改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会.三．基本遗传算法的数学模型基本遗传算法可表示为SGA=（C,E,P，M,，，,T）0式中:C——个体的编码方法；E-—个体适应度评价函数；P—-初始种群；0M--种群大小；——选择算子；-—交叉算子；--变异算子；T—-遗传算法终止条件。四．基本遗传算法的步骤染色体编码（ChromosomeCoding）与解码（Decode）基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值｛0,1｝所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101n=18。(1）编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码.设某一参数的取值范围为［U1

，U],我们用长度为k的二进制编码符号来表示该参数,则2它总共产生2k种不同的编码，可使参数编码时的对应关系为：000000…0000=0→U1000000…0001=1→U+1000000…0010=2→U+21…111111…1111=2k—1→U221其中，=U U .212k1（2）bb

b…b

，则对应的解码公式为i

U

kk—1

k—2 21XU1

( bii1

1)

2 1 ①2k1X［245位二进制编码对X25=32（染色体：00000,00001,00010，00011，00100,00101,00110,0011101000,01001，01010，01011，01100，01101,01110，0111110000,10001,10010，10011，10100,10101，10110，1011111000,11001,11010，11011,11100，11101，11110,11111对于任一个二进制串，只要代入公式①，就可得到相应的解码,如X=10101,它对应的十22进制为bii1

2i1=1+0*2+1＊2+0＊23+＊2=21，则对应参数X的值为2+21＊(4—2）/(25—1）=3。3548。个体适应度的检测评估基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体C，C.(完整)基本遗传算法遗传算子基本遗传算法使用下列三种遗传算子：选择运算使用比例选择算子.比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。若设种群数为M,个体i的适应度为f,则个体i被选取的概率为iPfi i

/M fkk1当个体选择的概率给定后，产生［0，1汰。我们经常采用的是轮盘赌的原理,个体的的性能进行的一些计算.实值范围——总和是所率的总和或当前种群中所有个体原始适应度值一方式映像到范围1

选择概率是基于它们有个体期望的选择概65[0,sum]个体被选中为止。2父个体111011单点交叉11000子个体1父个体20110001111子个体2图2单点交叉示意图变异运算使用基本位变异算子或均匀变异算子。为了避免问题 过早收敛对于二进制基因码组成的个体种群，实现基因码的小概率翻转,即0变为1,而1变为0，如图3所示。(完整)基本遗传算法(完整)基本遗传算法11011 变异 1111111011变异11111图3图3变异操作示意图行参数4M,T,P,Pc mMT100~500；P为交叉概率，一般取为0.4～0.99;cP为变异概率，一般取为0。0001～0.1。m五．遗传算法的具体例证下面通过具体的例子介绍遗传算法的实际工作过程。假设目标函数为maxf(x,

)21.5

)

)13.0x

2 x

1 2 2 ②5.81 2该函数有多个局部极值点。第一步,确定决策变量和约束条件。x,x3。0≤x≤12。1，4.1≤x5.8。1 2 1 2第二步，建立优化模型.式②已给出了问题的数学模型。第三步，确定编码方法。要进行编码工作，即将变量转换成二进制串。串的长度取决于所要求的精度。例如，变量x［a，b4(bj j j ja）＊104个部分。对一个变量的二进制串位数（用mj

表示，用以下公式计算：2mj1 bj

a)*142mj1j第四步，确定解码方法。从二进制串返回一个实际的值可用下面的公式来实现：x a decimal(substring

)*bjajj j

2mj1decimal(subing)x的十进制值。j j4x1

和x可以转换为下面的串:2（12。1—（-3。0)）＊10000=151000217＜151000≤218，

=181(5。8-4.1）*10000=17000214＜17000≤215,

=152m=m

+m=18+15=331 2这样,一个染色体串是33位，如图4所示。33位18位33位18位15位4一个染色体二进制串x1

和x的实值如表1所示。表1表1染色体二进制与十进制比较较变量x1x2二进制数000001010100101001101111011111110十进制数541724318x=-3。0+5417＊（12。1（-3.0))/21-1）=2。6879691x=4。1+24318＊（5.8—。1）（215-1）=5.3616532初始种群可随机生成如下：U=[000001010100101001101111011111110］1U=[001110101110011000000010101001000]2U=［111000111000001000010101001000110]3U=［100110110100101101000000010111001］4U=［000010111101100010001110001101000]5U=［111110101011011000000010110011001]6U=[110100010011111000100110011101101]7U=[001011010100001100010110011001100］8U=［111110001011101100011101000111101]9U=[111101001110101010000010101101010]10相对应的十进制的实际值为U=［x,x］=［—2。687969，5。361653]1 1 2U=［x,x］=[0。474101，4。170144]2 1 2U=［x,x］=［10。419457,4.661461]3 1 2U=[x,x］=[6。159951，4.109598］4 1 2U=［x,x2。301286，4.477282]5 1 2U=［x，x［11.788084，4。174346]6 1 2U=[x，x］=［9。342067，5。121702］7 1 2U=[x,x]=[-0.330256,4.694977]8 1 2U=[x,x］=［11.671267，4.873501]9 1 2U=[x，x］=[11.446273,4。171908]10 1 2第五步，确定个体评价方法。对一个染色体串的适应度评价由下列三个步骤组成：将染色体串进行反编码,转换成真实值。在本例中，意味着将二进制串转换成实际值:xk=(xk，x),k=1,2,…1 2（2)评价目标函数f（xk。(3）将目标函数值转为适应度。对于极大值问题，适应度就等于目标函数值，即eval（U=f（k)，k=1,2,…k价。上述染色体的适应度值如下:eval(U

)=f（—2。687969，5。361653)=19。8051191eval（U)=f(0.474101，4.170144)=17。3708962eval（U)=f(10.419457，4。661461)=9。5905463eval(U

）=f（6。159951，4。109598）=29.4061224eval（U）=f(—2.301286,4.477282)=15。6860915eval(Ueval(Ueval(Ueval(U

)=f(11。788084，4。174346)=11.9005416）=f(9。342067,5.121702)=17.9587177）=f(—0。330256，4.694977)=19.7631908)=f(11.671267,4.873501）=26.4016699eval（U10

）=f(11.446273,4.171908）=10。252480由以上数据可以看出，上述染色体中最健壮的是U，最虚弱的是U。4 3第六步，设计遗传算子和确定遗传算法的运行参数。选择运算使用轮盘选择算子。为基础的概率分配来选择新的种群。其步骤如下：①计算各染色体U的适应度值eval（Ukkeval（U）=f(x，k=1,2,…k②计算群体的适应度值总和：popsizeF eval(U)kk1③计算对应于每个染色体Uk的选择概率Pk：eval(Uk)k F④计算每个染色体U的累计概率Q：k kkj1

P,jj在实际工作中，选择新种群的一个染色体按以下步骤完成:①生成一个[0，1］间的随机数r如果r≤QUkU（2≤k≤pop-size)，使得1 1 kQ≤k≤Qk—1 k那么,本例中种群的适应度总和为F10k1

eval(Uk

)178.135372Uk

（k=1，2,…，10)的选择概率Pk

如下:P=0.1111801

=0。0975152

=0。0538393

=0.1650774

=0。0880575P=0。0668066

=0.1008157

=0.1109458

=0.1482119

=0。05755410Uk

（k=1,2,…，10）的累计概率Qk

如下：Q=0。1111801

=0。2086952

=0.2625343

=0。4276114

=0.5156685Q=0。5824756

=0.6832907

=0.7942348

=0。9424469

=1。000000101010［0,1］间的随机数如下：0.301431 0.322062 0.766503 0。881893 0.3508710。583392 0.177618 0.343242 0.032685 0。197577第一个随机数r1

=0301431Q3

QU4

=03220622

Q

被再次选中.最终,新的种群由下列染色体组成:3 4 4U=［100110110100101101000000010111001] （U）1 4U=[100110110100101101000000010111001］ (U)2 4U=[001011010100001100010110011001100］ （U）3 8U=[111110001011101100011101000111101] （U）4 9U=［100110110100101101000000010111001] （U）5 4U=[110100010011111000100110011101101] (U）6 7U=[001110101110011000000010101001000] （U）7 2U=[100110110100101101000000010111001］ （U)8 4U=［000001010100101001101111011111110］ （U)9 1U=［001110101110011000000010101001000] (U)10 2交叉运算使用单点交叉算子。染色体如下所示(节点随机选择在染色体串的第17位基因：UU=[100110110100101101000000010111001]1U=[001011010100001100010110011001100]2P=2525％的染色体进行交叉。交叉操作的过程如0下：开始k←0；当k≤10时继续r←［0,1］之间的随机数；k如果r＜0.25，则k选择Uk结束

为交叉的一个父辈；k←k+1;结束结束假设随机数如下：0.6257210。2668230。2886440.2951140。1632740。5674610.0859400.3928650。7707140.548656那么，就意味着染色体U5

U[1,32］733）pos1染色体从第一位分割，新的子辈在第一位右端的部分互换而生成，即U=［100110110100101101000000010111001］5U=［001110101110011000000010101001000］7U05U7变异运算使用基本位变异算子U1

181，0。于是，染色体在变异后将是：U=［100110110100101101000000010111001]1U*11P=0.011%要进行变异。m33＊10=3303。3概率是相等的。因此，我们要生成一个位于[0，1rk

（k=1,2，…，330）.假设表2列出的基因将进行变异。2基因变异示例基因位置染色体位置基因位数随机数105461645321997132910320.0098570.0098570.001130。0009460.001282U=11U*=[100110110100101101000000010111001］ U