基本遗传算法.docx

《基本遗传算法.docx》由会员分享，可在线阅读，更多相关《基本遗传算法.docx（11页珍藏版）》请在第一文库网上搜索。

1、基本遗传算法Holland创建的遗传算法是一种概率搜寻算法，它采用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程。该算法通过有组织的、然而是随机的信息交换，重新组合那些适应性好的串。在每一代中,采用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外增加，间或也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机优化算法，它可以有效地采用已有的信息处理来搜寻那些有盼望改善解质量的串。类似于自然进化，遗传算法通过作用于染色体上的基因，查找好的染色体来求解问题。与自然界相像，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色

2、体进行评价，并基于适应度值来转变染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。第一章遗传算法的运行过程遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群(Population)动身，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜寻空间中越来越好的区域，这样一代一代地不断繁衍进化，最终收敛到一群最适应环境的个体(Individual),求得问题的最优解。完整的遗传算法运算流程可以用图1来描述。由图1可以看出，使用上述三种遗传算子(选择算子、交叉算子和变异算子)的遗传算法的主要运算过程如下：(1)编码：解空间中的解数据X,作为遗传算法

3、的表现形式。从表现型到基因型的映射称为编码。遗传算法在进行搜寻之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。(2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开头迭代。设置进化代数计数器t-0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。(3)适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题,适应度函数的定义方式不同。依据详细问题，计算群体P(t)中各个个体的适应度。(4)选择：将选择算子作用于群体。(5)交叉：将交叉算子作用于群

4、体。(6)变异：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)0(7) 终止条件推断：若tWT,则t-t+l,转到步骤(2)；若tT,则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简洁，简洁理解，它给其他各种遗传算法供应了 一个基本框架。图1遗传算法运算流程一个简洁的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示，初始种群P(0)是随机设计的，简洁遗传算法的伪代码描述如下：produre GAbegint=0;initialize P(t

5、);evaluate P(t);while not finished dobegint=t+l;select P(t) from P(t-1);reproduce pairs in P(t);evaluate P(t);endend二.遗传算法的基本操作遗传算法有三个基本操作：选择(Selection) 交叉(Crossover)和变异(Mutation)o(1)选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。依据各个个体的适应度值，依据肯定的规章或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则

6、是适应性强的个体为下一代贡献一个或多个后代的概率大。这样就体现了达尔文的适者生存原则。(2)交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，Crossover Rate)交换它们之间的部分染色体。交叉体现了信息交换的思想。(3)变异。变异操作首先在群体中随机选择一个个体，对于选中的个体以肯定的概率随机转变串结构数据中某个串的值，即对群体中的每一个个体，以某一概率(称为变异概率，Mutation Rate)转变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样

7、遗传算法中变异发生的概率很低。变异为新个体的产生供应了机会。三.基本遗传算法的数学模型基本遗传算法可表示为SGA= (C, E, P0,M, , , ,T)式中：C个体的编码方法；E个体适应度评价函数；Po初始种群；M种群大小；选择算子；交叉算子；一一变异算子；遗传算法终止条件。四.基本遗传算法的步骤1 .染色体编码(Chromosome Coding)与解码(Decode)(1)编码：变量x作为实数，可以视为遗传算法的表现型形式。从表现型到基因型的映射称为编码。设某一参数的取值范围为U, U，我们用长度为k的二进制编码符号来表示该参数，则它总共产生少种不同的编码，可使参数编码时的对应关系为：

8、oooooooooo=ou1ooooooooo=-u1+000000 0010=2-U+25llllllllll=2k-lu2其中，吟苧(2)解码：假设某一个体的编码为bkbkbk2b2b,则对应的解码公式为H+(/*2-)* 等学/=1Z - 例如：设有参数X2, 4,现用5位二进制编码对X进行编码，得25二32个二进制串(染色体)：00000, 00001, 00010, 00011, 00100, 00101,00110,0011101000,01001,01010,01011,01100,01101,01110,0111110000, 10001, 10010, 10011, 1010

9、0, 10101,10110,1011111000, 11001, 11010, 11011, 11100, 11101, 11110, 11111对于任一个二进制串，只要代入公式，就可得到相应的解码，如5X22= 10101,它对应的十进制为Z * 2T = 1 +0*2+1 *22+0*2、1 *2匚21,则对应参数/=1X 的值为 2+21*(4-2)(25-l)=3. 3548o2 .个体适应度的检测评估基本遗传算法按与个体适应度成正比的概率来打算当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估量这个概率，要求全部个体的适应度必需为非负数。所以，依据不同种类的问题，需要预先确

10、定好由目标函数值到个体适应度之间的转换规律，特殊是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数C,使个体的适应度为目标函数值加上正数Co基本遗传算法使用下列三种遗传算子：(1)选择运算使用比例选择算子。比例选择因子是采用比例于各个个体适应度的概率打算其子孙的遗传可能性。若设种群数为M,个体i的适应度为fi,则个体i被选取的概率为MPi = fifkk=当个体选择的概率给定后，产生0, 1之间的匀称随机数来打算哪个个体参与交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大;若个体的选择概率小，则被淘汰。我们常常采纳的是轮盘赌的原理，个体的选择概率是

11、基于它们的性能进行的一些计算。实值范围一一总和是全部个体期望的选择概率的总和或当前种群中图1轮盘赌选择全部个体原始适应度值的总和。个体采纳一对一方式映像到范围0, sum的一连续区间，每一个体区间的大小与对应个体的适应度值相匹配。如图1所示，轮盘赌轮的周长是6个个体适应度值的总和，个体5是最大适应度个体，它占有最大的区间。选择一个个体，用在0, sum间产生随机数，看此随机数在哪个个体的区间上，则此个体被选中。重复此过程，直到所需数量个体被选中为止。父个体1父个体2110()11;单点交叉11()011()0子个体1子个体2（2）交叉运算使用单点交叉算子。只有一个交叉点位置，任意选择经过选择操

12、作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体，如图2所示。图2单点交叉示意图（3）变异运算使用基本位变异算子或匀称变异算子。为了避开问题过早收敛,对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1,而1变为0,如图3所示。图3变异操作示意图4.基本遗传算法的运行参数基本遗传算法有下列4个运行参数需要预先设定，即M, T, % PmM为群体大小，即群体中所含个体的数量，一般取为20100；T为遗传算法的终止进化代数，一般取为100500；为交叉概率,一般取为0.40.99;匕为变异概率，一般取为0.0000.1。下面

13、通过详细的例子介绍遗传算法的实际工作过程。假设目标函数为max f(xl,)=21.5 + X sin(4cr1) + x2 sin(20%)-3.0xl 12.1,4.1 25.8该函数有多个局部极值点。下面介绍求解该优化问题的遗传算法的构造过程。第一步，确定决策变量和约束条件。式给出,决策变量为治2,约束条件为-3.0忘*|忘12.1,4.1W*2或5.8.其次步，建立优化模型。式已给出了问题的数学模型。第三步，确定编码方法。要进行编码工作，即将变量转换成二进制串。串的长度取决于所要求的精度。例如，变量Xj的区间是aj,b要求的精度是小数点后4位，也就意味着每个变量应当被分成至少（bj-a

14、j）*l（个部分。对一个变量的二进制串位数（用Ri表示）,用以下公式计算：2吗-y-%）*1（）42吗-1第四步，确定解码方法。从二进制串返回一个实际的值可用下面的公式来实现:2吗一xj = a. + decimal substring )J其中，dec汕H(s疝g/)代表变量xj的十进制值。不妨设要求的精度为小数点后4位，则目标函数的两个变量x和X2可以转换为下面的串：(12. 1-(-3. 0) *10000=151000217151000218,m1=18(5. 8-4. 1)10000=170002,4170002,5,m2=15m=m1+m2=l 8+15=33这样，一个染色体串是33位，如图4所示。r33 位18 位H 15 位图4 一个染色体二进制串对应的变量x和X2的实值如表1所示。表1染色体二进制与十进制比较变量二进制数十进制数Xi5417X224318x1=-3. 0+5417*(12. 1-(-3. 0)(218-1)=-2. 687969X2=4. 1+24318*(5. 8-4. 1)(2,5-1)=5. 361653初始种群可随机生成如下：U1u2u3u4u5u6u7u8u9u10相对应的十进制的实际值为U1=x1, x2 = -2.