基本遗传算法及改进

第二章基本遗传算法及其改进霍兰德制作的遗传算法利用一种编码技术作用于染色体这几条线，其基本思想是模拟由这些线组成的个体的进化过程。该算法有组织，但随机进行信息交换，重新组合适应性好的字符串。在每一代中，使用上一代字符串结构中适应良好的位和段创建新的字符串组。另外，有时您想用新的位和段替换字符串结构中的原始部分。遗传算法是一种随机优化算法，但不是简单地随机漫步，而是搜索可以有效利用现有信息处理提高解决方案质量的字符串。与自然进化一样，遗传算法通过作用于染色体的基因寻找好的染色体，解决问题。与自然相似，遗传算法在不知道问题解决本身的情况下，评估算法生成的每条染色体，根据适应性图改变染色体，使适应性好的染色体比适应性差的染色体有更多的生殖机会。2.1遗传算法工作过程遗传算法模拟了自然选择和遗传中发生的复制、交叉、突变等现象，通过任意初始群体(population)中的随机初始群体、交叉、突变操作创建了更适合环境的对象组，从而将组从搜索空间演化到越来越好的领域，世代相传，最终聚合到最适合环境的对象组(Individual)中，寻求问题的最佳答案。2.1.1完全遗传算法运算流交叉遗传算法的一般步骤如图2.1所示。解决方案100100011001100100解密累积计算10010001解决方案跑步者编码选择评价变异00图2.1遗传算法的一般步骤完整的遗传算法运算流可以用图2.2描述。按位字符串编码实际问题参数集计算自适应值人口1统计结果选择和遗传解码优化的一个或多个参数集多个参数集人口2改进或解决实际问题组2随机运算符1)位字符串解释获得参数2)计算目标函数3)将函数值映射到自适应值4)阈值调整三个基本遗传运算符：选择运算符交集运算子变异运算子从郡1种郡2图2.2遗传算法运算流图1.3遗传算法计算流程如图2.2所示，使用上述三种遗传运算符(选择运算符、交叉运算符、变异运算符)的遗传算法的主要计算过程如下：(1)编码：以遗传算法的表达式形式解决空间的解决方案数据。从表型到基因型的映射称为编码。遗传算法在执行搜索之前用遗传空间的基因型字符串结构数据表示空间的解，这些字符串结构数据的不同组合构成了不同的点。(2)创建初始群体：随机生成n个初始字符串结构数据，每个字符串结构数据称为一个实体，n个实体构成一个组。遗传算法使用这n个字符串结构作为初始点开始迭代。进化代数计数器设置t0；最大进化代数t集；随机创建m个对象作为初始组P(0)。(3)适宜性评估测试：适宜性函数表示单个或解决方案的优缺点。自适应函数因问题而异。根据特定问题计算组P(t)中个人的适合性。(4)选择：将选择运算符应用于组。(5)交集：将交集运算子套用至群组。(6)转移：将转移运算子套用至群组。群组P(t)经过选取、相交、变异运算，得到下一代群组P(t 1)。(7)判断终止条件：如果是TT，则转至tt 1，步骤(2)；如果是TT，则运算结束，使用进化过程中获得的最适应性强的对象作为最佳解决方案输出。从遗传算法计算过程可以看出，进化计算简单易懂，为其他各种遗传算法提供了基本框架。简单的遗传算法被Goldberg用于轮廓描述，并举例说明遗传算法的基本配置。t代群体用变量P(t)表示，初始群体是随机设计的P(0)。简单遗传算法的伪代码描述如下：2.1.2遗传算法的三个基本操作步骤正式提供Begint=0；初始化P(t)；evaluate P(t)；While not finished doBegint=t 1；select P(t)from P(t-1)；reproduce pairs in P(t)；evaluate P(t)；EndEnd .遗传算法有三种基本操作：“选取”(Selection)、“相交”(Crossover)和“过渡”(Mutation)。选择(1)。选择目的是从现组中挑选优秀的个体，给后代代代繁衍后代的机会。根据每个人的适合值，根据特定的规则或方法从上一代组中选择一些优秀的个体，遗传到下一代。遗传算法通过选择运算具体化和选择这种想法的原则是适应性强的个体向下一代投稿一个或多个后代的概率很大。这反映了达尔文适者生存的原则。(2)相交。交叉操作是遗传算法中最重要的遗传操作。通过交叉操作可以得到新一代的对象，新的对象可以组合爸爸对象的特性。将组中的每个对象随机配对，以固定的概率(称为交叉概率)交换它们之间的部分染色体。交叉反映信息交换的想法。(3)转移。突变首先从对象中随机选择对象，然后对选定对象以特定概率随机更改串结构数据的值，即对组中的每个对象以特定概率(变异概率，mutation rate)将特定基因座的基因值更改为另一个等位基因。和生物界一样，遗传算法中发生变异的概率很低。变异为新个体的出现提供了机会。2.2基本遗传算法基本遗传算法(也称为标准或简单遗传算法，SGA)是以组中所有对象为目标的群体体形操作。仅使用预设遗传运算子：选取运算子、相交运算子和变异运算子。oraction Operator，以及Mutation Operator，均使用预设遗传运算子(Genetic Operator)作为选取运算子，Mutation Operator和Mutation选择、交叉和变异是遗传算法的3个主要操作运算符，通过构造所谓的遗传运算，将其他传统方法不存在的特性赋予遗传算法。2.2.1基本遗传算法的数学模型基本遗传算法可以表示为：(2.1)格式：个人编码方法；个人适宜性评价功能；早期人口；人口大小；选择运算符；相交运算符；变异算子；油田运算终止条件。图2.3是基本遗传算法的流程图。创建编码和初始群体人口个体适应性检测与评价选择交叉变异图2.3遗传算法的基本流程图2.2.2基本遗传算法阶段1.染色体编码和解码基本遗传算法使用固定长度的二进制符号字符串表示组的对象，其等位基因由2值0，1组成。早期群体中个别个体的基因可以用均匀分布的随机数生成。例如，X=101可以表示染色体长度为n=18的对象。00000000=000000001=10000000 0010=211111111 1111=(1)编码：如果将参数的值范围设置为，并将该参数表示为长度的二进制编码符号，则在对参数进行编码时，将生成各种可以创建该关系的编码，如下所示：在这里，(2)解码：假设一个主体的编码如下，则相应的解码公式为：(2.2)例如：参数、活动5位二进制代码对编码、二进制字符串(染色体):00000、00001、00010、00011、00100、00101、0010、0010101000、01001、01010、01011、01100、0111、0110、011110000、10001、10010、10011、10100、10101、10110、1011111000、11001、11010、11011、11100、11101、11101、11110、1111对于任何二进制字符串，替换公式(2.2)即可对其进行解码。例如，如果相应的小数是，则该参数的值为。2.个人适应性的检测与评价基本遗传算法是与个体适应度成比例的概率，决定了现在组内的个别个体将会给下一代留下多少机会。要正确估计这个概率，所有对象的适应性必须不是负的。因此，根据不同种类的问题，必须事先确定从目标函数值到个体适合性的转换规律。特别是在目标函数值为负的情况下，需要提前确定如何处理。例如，可以选择适当的大正数，以使对象的适应性与目标函数值相加。3.遗传运算符基本遗传算法使用三种遗传运算符：(1)选择操作使用比例选择运算符。比例选择因子是利用与每个人的适应能力成比例的概率来确定其后代的可继承性。如果人口数为，对象的适应性为，则选择对象的概率为。给定对象选择概率后，生成介于0，1之间的均匀随机数，以确定哪个对象参加交配。如果个体的选择概率大，可以多次选择，其遗传基因将在群体中扩大；个人选择概率低的话，就会被淘汰。(2)交集运算使用单点交集运算子。仅随机选择一个交叉位置，然后选择群体中的两个对象作为交叉对象随机生成一个交叉位置，两个对象在交叉位置交换一些遗传密码，形成两个子对象，如图2.4所示。子对象1子对象2父对象1父对象2110 11011 00110 00011 11单点交集图2.4单点交集(3)变异操作使用基本位变异操作符或统一变异操作符。为了避免问题过早收敛，对于由二进制遗传代码组成的个体群体，实现遗传代码的小概率反转，如图2.5所示。也就是说，0变成1，1变成0。1101111001变异图2.5变异操作4.基本遗传算法的操作参数预设遗传演算法有四个执行参数需要预先设定：组大小，即组中包含的对象数通常为20到100。遗传算法的终止进化代数一般为100 500。交叉概率通常为0.4到0.99。变异概率一般为0.00010.1。2.2.3遗传算法的具体示例下面通过具体的例子介绍遗传算法的实际操作过程。假设目标函数如下：(2.3)(2.4)如图2.6所示，该函数有多个局部极值点。图2.6目标函数图像下面是解决此优化问题的遗传算法的配置过程。第一步是确定决策变量和约束条件。格式(2.4)是决定变量，约束条件是，是。第二步是建立优化模型。类型(2.3)给出了问题的数学模型。第三步是确定编码方法。要使用编码，请将变量转换为二进制字符串。字符串的长度取决于所需的精度。例如，变量的范围为，需要小数点后4位的精度。也就是说，每个变量必须至少分成部分。针对一个变量的二进制字符串位数(以表示)，按以下公式计算：第四步是确定解码方法。从二进制字符串返回为实际值可以使用以下公式完成：(2.5)其中表示变量的十进制值。如果将所需精度设置为小数点后4位，则可以转换为目标函数的两个变量和下一个字符串。这样的染色体字符串是33位，如图2.7所示。33个字符000001018个字15个字图2.7染色体二进制字符串相应变量和的实际值见表2.1。表2.1染色体二进制和十进制比较二进制数字十进制0000010541724318起始群体可以随机生成，如下所示：u1=000011 l 10U2=000000U3=l 000l l0U4=001u5=0000011000 l l 0