第二章 基本遗传算法及改进

9第二章基本遗传算法及改进Holland创建的遗传算法是一种概率搜索算法，它利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些串组成的个体进化过程。该算法通过有组织地、然而是随机地进行信息交换，重新组合那些适应性好的串。在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。遗传算法是一类随机优化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来改变染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。2.1遗传算法的运行过程遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群(population)出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体(Individual)，求得问题的最优解。2.1.1完整的遗传算法运算流程遗传算法的一般步骤如图2.1所示。图2.1遗传算法的一般步骤解110010101010110111010011001010101011000111001010101011011101110010111010110110010011001010译码适值计算1100101010101101110100110010101010110001解转轮编码选择评估变异0011011010交叉10完整的遗传算法运算流程可以用图2.2来描述。由图2.2可以看出，使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下：(1)编码：解空间中的解数据x，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。(2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t←0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。(3)适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t)中各个个体的适应度。(4)选择：将选择算子作用于群体。(5)交叉：将交叉算子作用于群体。(6)变异：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。(7)终止条件判断：若t≤T，则t←t+1，转到步骤（2）；若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。一个简单的遗传算法被Goldberg用来进行轮廓描述，并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示，初始种群是随机设计的P(0)。简单遗传算法的伪代码描述如下：编码成位串实际问题参数集计算适应值种群1统计结果选择与遗传经过优化的一个或多个参数集（由解码得到）多个参数集合种群2改善或解决实际问题群2随机算子1）位串解释得到参数2）计算目标函数3）函数值向适值映射4）适值调整三种基本遗传算子：选择算子交叉算子变异算子种群1种群2图2.2遗传算法运算流程图1.3遗传算法运算流程112.1.2遗传算法的三个基本操作遗传算法有三个基本操作：选择(Selection)、交叉(Crossover)和变异(Mutation)。(1)选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。这样就体现了达尔文的适者生存原则。(2)交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，CrossoverRate)交换它们之间的部分染色体。交叉体现了信息交换的思想。(3)变异。变异操作首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构数据中某个串的值，即对群体中的每一个个体，以某一概率(称为变异概率，mutationrate)改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样，遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。2.2基本遗传算法基本遗传算法(也称标准遗传算法或简单遗传算法，SimpleGeneticAlgorithm，SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(GeneticOperator)：选择算子(SelectionOperator)、交叉算子(CrossoverOperator)和变异算子(MutationOperator)，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是遗传算法3个主要操作算子，它们构成了所谓的遗传操作，使遗传算法具有了其它传统方法没有的特点。2.2.1基本遗传算法的数学模型基本遗传算法可表示为：procedureGAbegint=0;initializeP(t);evaluateP(t);whilenotfinisheddobegint=t+1;selectP(t)fromP(t-1);reproducepairsinP(t);evaluateP(t);endend.12),,,,,,,(0TΦMPECSGA(2.1)式中：C——个体的编码方法；E——个体适应度评价函数；0P——初始种群；M——种群大小；Φ——选择算子；——交叉算子；——变异算子；T——遗传运算终止条件。图2.3为基本遗传算法的流程图。2.2.2基本遗传算法的步骤1．染色体编码与解码基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值{0，1}所组成。初始群体中各个个体的基因可用均匀分布的随机数来生成。例如：X=100111001000101101就可表示一个个体，该个体的染色体长度是n=18。(1)编码：设某一参数的取值范围为[12,UU]，我们用长度为k的二进制编码符号来表示该参数，则它总共产生k2种不同的编码，可使参数编码时的对应关系为：其中，1212kUU。(2)解码：假设某一个体的编码为1221bbbbbkkk，则对应的解码公式为：0000000000=01U0000000001=11U0000000010=221U1111111111=12k2U编码和初始种群的生成种群中个体适应度的检测评估选择交叉变异图2.3遗传算法的基本流程图1312)2(12111kkiiiUUbUX(2.2)例如：设有参数]4,2[X，现用5位二进制编码对X进行编码，得3225个二进制串(染色体)：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对于任一个二进制串，只要代入公式(2.2)，就可得到对应的解码，如1010122x，它对应的十进制为212120212012432511iiib，则对应参数X的值为3548.312242125。2．个体适应度的检测评估基本遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到下一代群体中的机会多少。为了正确估计这个概率，要求所有个体的适应度必须为非负数。所以，根据不同种类的问题，需要预先确定好由目标函数值到个体适应度之间的转换规律。特别是要预先确定好当目标函数值为负数时的处理方法。例如，可选取一个适当大的正数c，使个体的适应度为目标函数值加上正数c。3．遗传算子基本遗传算法使用下列三种遗传算子：(1)选择运算使用比例选择算子。比例选择因子是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若设种群数为M，个体i的适应度为if，则个体i被选取的概率为MkkiiffP1/。当个体选择的概率给定后，产生[0，1]之间的均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则能被多次选中，它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰。(2)交叉运算使用单点交叉算子。只有一个交叉点位置，任意挑选经过选择操作后种群中两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体，如图2.4所示。图2.4单点交叉(3)变异运算使用基本位变异算子或均匀变异算子：为了避免问题过早收敛，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即0变为1，而1变为0，如图2.5所示。子个体1子个体2父个体1父个体211011011001100001111单点交叉１１０１１１１００１变异14图2.5变异操作4.基本遗传算法的运行参数基本遗传算法有下列4个运行参数需要预先设定,即mcPPTM,,,。M为群体大小，即群体中所含个体的数量，一般取为20~100；T为遗传算法的终止进化代数，一般取为100~500；cP为交叉概率，一般取为0.4~0.99；mP为变异概率，一般取为0.0001~0.1。2.2.3遗传算法的具体例证下面通过具体的例子介绍遗传算法的实际工作过程。假设目标函数为：)20sin()4sin(5.21),(max221121xxxxxxf(2.3)123.012.14.15.8xx(2.4)如图2.6所示，该函数有多个局部极值点。图2.6目标函数的图像下面介绍求解该优化问题的遗传算法的构造过程。第一步，确定决策变量和约束条件。式(2.4)给出，决策变量为21,xx，约束条件为0.3≤1x≤1.12，1.4≤2x≤8.5。第二步，建立优化模型。式(2.3)已给出了问题的数学模型。第三步，确定编码方法。要进行编码工作，即将变量转换成二进制串。串的长度取决于所要求的精度。例如，变量1x的区间是[11,ba]，要求的精度是小数点后4位，也就是意味者每个变量应该被分成至少41110)(ab个部分。对一个变量的二进制串位数(用jm表示)，用以下公式计算：4110)(2jjmabj≤12jm15第四步，确定解码方法。从二进制串返回为一个实际的值可用下面的公式来实现：12)(jmjjjjjabsubstringdecimalax(2.5)其中，)(jsubstringdecimal代表变量jx的十进位值。不妨设要求的精度为小数点后4位，则目标函数的两个变量1x和2x可以转换为下面的串：00015100010))0.3(1.12(18,2000151211817m0001700010)1.48.5(15,200017221514m33151821mmm这样，一个染色体串是33位，如图2.7所示。图2.7一个染色体二进制串对应的变量1x和2x的实值如表2.1所示。表2.1染色体二进制与十进制比较二进制数十进制数1x00000101