基本遗传算法

基本遗传算法Holland创建的遗传算法是一种概率搜索算法，它利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程.该算法通过有组织的、然而是随机的信息交换，重新组合那些适应性好的串.在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机优化算法，它可以有效地利用已有的信息处理来搜索那些有希望改善解质量的串.类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题.与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来改变染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会.第一章遗传算法的运行过程遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象 ，从任一初始种群(Population)出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体(Individual),求得问题的最优解。完整的遗传算法运算流程完整的遗传算法运算流程可以用图1来描述。由图1可以看出，使用上述三种遗传算子(选择算子、交叉算子和变异算子)的遗传算法的主要运算过程如下：编码：解空间中的解数据x,作为遗传算法的表现形式。从表现型到基因型的映射称为编码.遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t(完整)基本遗传算法■0;设置最大进化代数T；随机生成M个个体作为初始群体P(0)。适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同.根据具体问题，计算群体P(t)中各个个体的适应度。选择：将选择算子作用于群体。交叉:将交叉算子作用于群体。变异：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1).终止条件判断：若tWT,则t<-t+1,转到步骤(2)；若t>T,则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。图1遗传算法运算流程(完整)基本遗传算法一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成.t代种群用变量P(t)表示，初始种群P(0)是随机设计的，简单遗传算法的伪代码描述如下：produreGAbegint=0;initializeP(t)；evaluateP(t)；whilenotfinisheddobegint=t+1；selectP(t)fromP(t-1);reproducepairsinP(t);evaluateP(t);endend遗传算法的基本操作遗传算法有三个基本操作：选择(Selection)、交叉(Crossover)和变异(Mutation)。选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大.这样就体现了达尔文的适者生存原则。交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个概率（完整）基本遗传算法（称为交叉概率，CrossoverRate）交换它们之间的部分染色体.交叉体现了信息交换的思想.（3）变异.变异操作首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构数据中某个串的值，即对群体中的每一个个体，以某一概率（称为变异概率，MutationRate）改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会.基本遗传算法的数学模型基本遗传算法可表示为SGA=（C,E,P0,M,①，r,甲,T）式中：C——个体的编码方法；E 个体适应度评价函数；P0——初始种群；M--种群大小；① 选择算子；r-—交叉算子；甲--变异算子；T 遗传算法终止条件。基本遗传算法的步骤染色体编码（ChromosomeCoding）与解码（Decode）基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值{0,1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：x=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。（1）编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码.设某一参数的取值范围为[U1,U2],我们用长度为k的二进制编码符号来表示该参数，则它总共产生2k种不同的编码，可使参数编码时的对应关系为:000000・・・0000=0TU1000000・・・0001=1TU1+S000000-0010=2^U1+2S111111・・・1111=2k—1TU2(2)解码：假设某一个体的编码为bbb・・・bb，则对应的解码公式为kk—1k—2 21温_ _一U-UX=U+Gb*2i-1)* ——1i=1例如：设有参数XE[2,4],现用5位二进制编码对X进行编码，得25=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对于任一个二进制串，只要代入公式①，就可得到相应的解码，如X22=10101,它对应的十进制为25b-2i-1=1+0*2+1大22+0大23+1大24=21，则对应参数X的值为2+21大(4—2)/(25—1)i=1二3。3548。个体适应度的检测评估基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估计这个概率，要求所有个体的适应度必须为非负数.所以，根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律，特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数C,使个体的适应度为目标函数值加上正数C.

遗传算子基本遗传算法使用下列三种遗传算子:(1)选择运算使用比例选择算子.比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗传可能性。若设种群数为M,个体i的适应度为f.,则个体i被选取的概率为P=门丈fk=1当个体选择的概率给定后，产生［0,1］之间的均匀随机数来决定哪个个体参加交配.若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰。图1轮盘赌选择选择概率是基于它们有个体期望的选择概的总和。个体采用一对一个体区间的大小与赌轮的周长是6个个我们经常采用的是轮盘赌的原理，个体的的性能进行的一些计算.实值范围——总和是所率的总和或当前种群中所有个体原始适应度值一方式映像到范围［0,sum］的一连续区间，每对应个体的适应度值相匹配.如图图1轮盘赌选择选择概率是基于它们有个体期望的选择概的总和。个体采用一对一个体区间的大小与赌轮的周长是6个个交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体，如图2所示。父个体1父个体2图父个体1父个体2图2单点交叉示意图子个体1子个体2变异运算使用基本位变异算子或均匀变异算子。为了避免问题过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1,而1变为0,如图3所示。

变异图3变异操作示意图 4.基本遗传算法的运行参数基本遗传算法有下列4个运行参数需要预先设定，即M,T,Pc，Pm。M为群体大小，即群体中所含个体的数量，一般取为20~100；T为遗传算法的终止进化代数，一般取为100~500;P为交叉概率，一般取为0.4〜0.99；P为变异概率，一般取为0。0001〜0.1。五.遗传算法的具体例证下面通过具体的例子介绍遗传算法的实际工作过程。假设目标函数为maxf(x,x)=21.5+xsin(4^x)+xsin(20Kx)1 2 1 1 2 2 ②-3.0<气<12.1,4.1<x2<5.8该函数有多个局部极值点。下面介绍求解该优化问题的遗传算法的构造过程。第一步，确定决策变量和约束条件。式②给出，决策变量为x1,x2，约束条件为一3。0Wx1W12。1,4.1Wx2W5.8。第二步，建立优化模型.式②已给出了问题的数学模型。第三步，确定编码方法。要进行编码工作，即将变量转换成二进制串。串的长度取决于所要求的精度。例如，变量x」的区间是】a「bj，要求的精度是小数点后4位，也就意味着每个变量应该被分成至少邕一a,大104个部分。对一个变量的二进制串位数(用m」表示)，用以下公式计算：2mj-1(b—a,)*104<2mj—1第四步，确定解码方法。从二进制串返回一个实际的值可用下面的公式来实现:x=a+decimal(substring)* %-jj j2mj—1其中，decimal(subing)代表变量x.的十进制值。不妨设要求的精度为小数点后4位，则目标函数的两个变量x1和x2可以转换为下面的串:(12。1—(-3。0))大10000=151000TOC\o"1-5"\h\z2i7V151000W2i8, m1=18(5。8-4.1)*10000=170002mV17000W215, m2=15m=m1+m2=18+15=33这样，一个染色体串是33位，如图4所示。r 33位 r000001010100101001 1011110111111101—18位 —15位—*图4一个染色体二进制串对应的变量x1和x2的实值如表1所示。表1染色体二进制与十进制比立.较变量二进制数十进制数x 1 0000010101001010015417x 2 10111101111111024318x1=-3。0+5417大(12。1-(-3.0))/(218-1)=—2。687969x2=4。1+24318大(5.8—4。1)/(215-1)=5.361653初始种群可随机生成如下：U1=[000001010100101001101111011111110]U2=[001110101110011000000010101001000]U3=[111000111000001000010101001000110]U4=[100110110100101101000000010111001]U5=[000010111101100010001110001101000]U6=[111110101011011000000010110011001]U7=[110100010011111000100110011101101]U=[001011010100001100010110011001100]8U9=[111110001011101100011101000111101]U10=[111101001110101010000010101101010]相对应的十进制的实际值为U1=[x1,x2]=[—2。687969,5。361653]U2=[x1,x2]=[0。474101,4。170144]U3=[x1,x2]=[10。419457,4.661461]U4=[x1,x2]=[6。159951,4.109598]U5=[x1,x2]=[-2。301286,4.477282]U6=[x1,x2]=[11.788084,4。174346]U7=[x1,x2]=[9。342067,5。121702]U8=[x1，x2]=[-0.330256,4.694977]U9=[x1,x2]=[11.671267,4.873501]U10=[x1,七]=[11.446273,4。171908]第五步，确定个体评价方法。对一个染色体串的适应度评价由下列三个步骤组成：将染色体串进行反编码，转换成真实值。在本例中，意味着将二进制串转换成实际值:xk=(x1k,x2k),k=1,2,^(2)评价目标函数f(xk)。(3)将目标函数值转为适应度。对于极大值问题，适应度就等于目标函数值，即eval(七)=f(xk)，k=1,2，…在遗传算法中，评价函数起着自然进化中环境的角色，它通过染色体的适应度对其进行评价。上述染色体的适应度值如下：eval(U1)=f(—2。687969，5。361653)=19。805119eval(U2)=f(0.474101，4.170144)=17。370896eval(U3)=f(10.419457，4。661461)=9。590546eval(U4)=f(6。159951，4。109598)=29.406122eval(U5)=f(—2.301286,4.477282)=15。686091eval(U)=f(11。788084，4。174346)=11.9005416eval(U7)=f(9。342067,5.121702)=17.958717eval(U8)=f(—0。330256，4.694977)=19.763190eval(U)=f(11.671267,4.873501)=26.4016699eval(U10)=f(11.446273,4.171908)=10。252480由以上数据可以看出，上述染色体中最健壮的是U4，最虚弱的是U3。第六步，设计遗传算子和确定遗传算法的运行参数。(1)选择运算使用轮盘选择算子。为基础的概率分配来选择新的种群。其步骤如下：计算各染色体七的适应度值eval(Uk)：eval(七)=f(xk)，k=1,2，…计算群体的适应度值总和：poprsizeF=尤eval(U)k=1计算对应于每个染色体Uk的选择概率Pk：

p_eval(U)kF''计算每个染色体Uk的累计概率Q「Qk=丈P.，j=1,2,...j_i在实际工作中，选择新种群的一个染色体按以下步骤完成:①生成一个［0，1］间的随机数r②如果rWQ1，就选择染色体U1；否则，选择第k个染色体Uk(2WkWpop-size),使得Qk—iWkWQk那么，本例中种群的适应度总和为F=i°eval(U)=178.135372k=1对应于每个染色体Uk(k=1,2,…，10)的选择概率Pk如下：Pi=0.111180P2=0o097515P3=0o053839P4=0.165077P5=0o088057P6=0o066806P7=0.100815P8=0.110945P9=0.148211P10=0o057554对应于每个染色体Uk(k=1,2，…，10)的累计概率Qk如下：Q=0.5156685Q1=0o111180Q2=0o208695Q3=0.262534Q4Q=0.5156685Q=0o5824756Q=0.6832907Q=0.794234Q=0o5824756Q=0.6832907Q=0.7942348Q=0o9424469Q10=1o000000现在，我们转动轮盘10次，每次选择一个新种群中的染色体.假设这10次中生成的】0,1］间的随机数如下：0.301431 0.322062 0.766503 0°881893 0.3508710o583392 0.177618 0.343242 0.0326850o197577第一个随机数r=0o301431大于。小于Q,这样染色体U被选中；第二个随机数r=0o322062TOC\o"1-5"\h\z1 3 4 4 2也大于Q3小于Q4,于是染色体U4被再次选中.最终，新的种群由下列染色体组成：U1=[100110110100101101000000010111001] (U4)U2=[100110110100101101000000010111001] (U4)U3=[001011010100001100010110011001100] (U8)U4=[111110001011101100011101000111101] (U9)U5=[100110110100101101000000010111001] (U4)U6=[110100010011111000100110011101101] (U7)U7=[001110101110011000000010101001000] (U2)U8=[100110110100101101000000010111001] (U4)U=[000001010100101001101111011111110] (U )9 1U10=[001110101110011000000010101001000] (U2)（2）交叉运算使用单点交叉算子。随机选择一个染色体串的节点，然后交换两个父辈节点右端部分来产生子辈.假设两个父辈染色体如下所示（节点随机选择在染色体串的第17位基因）：U=[100110110100101101000000010111001]U「[001011010100001100010110011001100]假设交叉概率为P0=25%,即在平均水平上有25%的染色体进行交叉。交叉操作的过程如下：开始k・0;当kW10时继续rk・[0,1]之间的随机数；如果rk<0.25，则选择Uk为交叉的一个父辈；结束ki+1；结束结束假设随机数如下：0.625721 0。266823 0。288644 0.295114 0。1632740。567461 0.085940 0.392865 0。770714 0.548656那么，就意味着染色体U5和U7被选中作为交叉的父辈.在这里，我们随机选择一个[1,32]间的整数(因为33是整个染色体串的长度)作为交叉点。假设生成的整数pos为1,那么两个染色体从第一位分割，新的子辈在第一位右端的部分互换而生成，即U5=[100110110100101101000000010111001]U=[001110101110011000000010101001000]7IU5*=[101110101110011000000010101001000]U「=[000110110100101101000000010111001]变异运算使用基本位变异算子假设染色体U1的第18位基因被选作变异，即如果该位基因是1,则变异后就为0。于是，染色体在变异后将是：U1=[100110110100101101000000010111001]U「二[100110110100101100000000010111001]将变异概率设为P=0.01,就是说，希望在平均水平上，种群内所有基因的1%要进行变异。m在本例中，共有33大10=330个基因，希望在每一代中有3。3个变异的基因，每个基因变异的概率是相等的。因此，我们要生成一个位于[0,1]之间的随机数系列rk(k=1,2,…，330).假设表2列出的基因将进行变异。表2基因变异示例基因位置染色体位置基因位数随机数105460.0098571645320.00113199710。00094632910320.001282在变异完成后，得到了最终的下一代种群：U*=[100110110100101101000000010111001]1U*=[10011011010010110100000001