基本遗传算法及应用举例

基本遗传算法及应用举例遗传算法(GeneticAlgorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。1．1．1编码方法用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L称为染色体的长度或称为符号串的长度。一般染色体的长度L为一固定的数，如X=10011100100011010100表示一个个体，该个体的染色体长度L=20。二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a，b]，我们用长度为L的二进制编码符号串来表示该参数，总共能产生L2种不同的编码，若参数与编码的对应关系为00000000000……00000000=0→a00000000000……00000001=1→a+δ•••111111111111……11111111=L2-1→b则二进制编码的编码精度12Lab假设某一个个体的编码是klkkkaaax21，则对应的解码公式为)2(121LjjLkjLkaabax例如，对于x[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：x=0010101111就表示一个个体，它对应的参数值是x=175.此时的编码精度为1.二进制编码方法相对于其它编码方法的优点，首先是编码、解码操作简单易行；其次是交叉遗传操作便于实现；另外便于对算法进行理论分析。2.个体适应度函数在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。设所求解的问题为：max()fx，xD.对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的问题，即min()max(()).fxfx当优化问题是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度函数值()Fx就等于相应的目标函数值()fx，即()()Fxfx.但实际目标优化问题中的目标函数有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求，必须寻求出一种通用且有效的由目标函数值到适应度之间的转换关系，有它来保证个体适应度总取非负值。为满足适应度取负值的要求,基本遗传算法一般采用下面方法将目标函数值()fx变换为个体的适应度().Fx对于求目标函数最大值的优化方法问题，变换方法为min(),fxCmin()0fxC时，()Fx0min()0fxC时，式中，minC为一个适当的相对比较小的数，它可以是预先指定的一个较小的数，或进化到当前代为止的最小目标函数值，又或当前代或最近几代群体中的最小目标函数值。3.基本遗传操作方法（1）比例选择：选择或称复制，建立在对个体适应度进行评价的基础之上。其作用是从当前群体中选择出一些比较优良的个体，并将其复制到下一代群体中。基本遗传算法采用比例选择的方法，所谓比例选择，是指个体在选择操作中被选中的概率与该个体的适应度大小成正比。（2）单点交叉。单点交叉又称简单交叉，是遗传算法所使用的交叉操作方法。（3）基本位变异。基本位变异石最简单和最基本的变异操作，也是基本遗传算法中所使用的变异操作方法。对于基本遗传算法中用二进制编码符号串所表示的个体，对需要进行变异操作的某一基因，若原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0.4.基本遗传算法的运行参数执行基本遗传算法时，有4个参数需要事先指定。它们是群体的大小M、交叉概率cp、变异概率mp及终止的代数T.（1）群体大小M.群体的大小M表示群体中所含个体的数量。当M取值较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而当M取值较大时，又会使得遗传算法的运行效率偏低。一般建议范围是20~100.（2）交叉概率cp。交叉操作室遗传算法产生新个体的主要方法，所以交叉概率一般应取较大值。但若取值过大的话，它又会破坏群体活动的优良模式，对进化运算反而产生不利影响；若取值过小的话，产生新个体的速度有太慢。一般建议的取值范围是0.4~1.00.（3）变异概率mp。若变异概率mp取值较大的话，虽能够产生出较多的新个体，但也有可能破坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率mp取值太小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议的取值范围是0.001~0.1.（4）终止代数T.终止代数T式表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议的取值范围是100~1000.至于遗传算法的终止条件，还可以利用某种判定准则，当判定出群体已经进化成熟且不再有进化趋势时就可终止算法的运行过程。如连续几代个体平均适应度的差异小于某一个极小的值；或者群体中所有个体适应度的方差小于某一个极小的值。这4个参数对遗传算法的搜索结果及搜索效率都有一定的影响，目前尚无合理选择它们的理论根据在遗传算法的实际应用中，往往需要经过多次的试算后才能确定出这些参数合理的取值范围或取值大小。基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择操作、交叉操作、变异操作作用与群体，最终可得到问题的最优解或近似最优解。虽然算法的思想比较简单，但它却具有一定的实用价值，能够解决一些复杂系统的优化计算问题。遗传算法的应用步骤如下；遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法。第一步：建立优化模型，即确定出目标函数、决策变量及各种约束条件以及数学描述形式或量化方法。第二步：确定表示可行解的染色体编码方法，也即确定出个体的基因型x及遗传算法的搜索空间。第三步：确定解码方法，即确定出个体基因型x到个体表现型x的对应关系或转换方法。第四步：确定个体适应度的量化评价方法，即确定出由目标函数值xf到个体适应度xF的转换规则。第五步：设计遗传操作方法，即确定出选择运算、交叉运算、变异运算等具体操作方法。第六步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、cp、mp等参数。由上述构造步骤可以看出，可行解的编码方法、遗传操作的设计是构造遗传算法时需要考虑的两个主要问题，也是设计遗传算法时的两个关键步骤。对不同的优化问题需要使用不同的编码方法和不同的遗传操作，它们与所求解的具体问题密切相关，因而对所求解问题的理解程度是遗传算法应用成功与否的关键。例1．1．1求解规划问题,,max222121xxxxfs.t.,7,,2,1,01x.7,,2,1,02x解主要运算过程如表7-3所示。（1）个体编码.遗传算法的运算对象是表示个体的符号串，所以必须把变量1．1基本遗传算法的构成要素1x，2x编码为一种符号串。该例题中，1x和2x取0～7之间的整数，可分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了个体的基因型，表示一个可行解。例如，基因型x=101110所对应的表现型是x=（5，6）T。个体的表现型x和基因型x之间可以通过编码和解码相互转换。（2）初始群体的产生。遗传算法是对群体进行遗传操作，需要准备一些表示起始搜索点的初始群体数据。本例中群体规模的大小M取为4，即群体由4个个体组成，每个个体可通过随机方法产生。一个随机产生的初始群体如表7-3中第2栏所示。（3）适应度计算。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度，即Fxfx。为计算函数的目标值，需先对个体基因型x进行解码。表7-3中第3、第4栏所示为初始群体各个个体的解码结果，第5栏所示为各个个体所对应的目标函数值，它也是个体的适应度，第5栏中还给出了群体中适应度的最大值和平均值。表7-31个体编号i2初始群体P(0)31x42x512,ifxx6/iiff10111013534143if0.242101011530.2430111003434max50f2535.75f500.174111001710.357选择次数8选择结果9配对情况10交叉点位置11交叉结果12变异点13变异结果10111011-23-41-2：23-4：4011001501100111110011111011111110101011101001101001211100111101111101114子代群体P（1）151x162x1712,ifxx0110013110192if98max98f2648f58111111771010015111101173(4)选择操作.其具体操作过程是先计算出群体中所有个体的适应度的总和if及每个个体的相对适应度的大小/iiff，如表7-3中5、6栏所示。表7-3中第7、8栏表示随机产生的选择结果。（5）交叉操作。本例中采用单点交叉的方法，并取交叉概率cp=1.00。表7-3中第11栏所示为交叉运算的结果。（6）变异操作。为了能显示变异操作，取变异概率mp=0.25,并采用基本位变异的方法进行变异运算。表7-3第13栏所示为变异运算的结果。对群体P（t）进行一轮选择、交叉、变异操作之后得到新一轮群体P(t+1)。如表7-3第14栏所示。表中第15、16、17栏分别表示出了新群体的解码值、适应度和适应度的最大值及平均值等。从表7-3中可以看出群体经过一代进化以后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。需要说明的是，表中第2、7、9、10、12栏的数据时随机产生的。这里为了说明问题我们特意选择了一些较好数值以便能够得到较好的结果。在实际运算过程中有可能需要一定的循环次数才能达到这个结果。