遗传算法的手工模拟计算示例

遗传算法的手工模拟计算示例为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。例：求下述二元函数的最大值：f(x1,x2)=x12+x22st 为仁x2 e 1,23?4?5?6?7(1)个体编码遗传算法的运算对象是表示个体的符号串，所以必须把变量x1, x2编码为一种 符号串。本题中，用无符号二进制整数来表示。因x1, x2为0 7之间的整数，所以分别用3位无符号二进制整数来表示，将 它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型X=101110所对应的表现型是：x= 5，6 。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。(2) 初始群体的产生遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体 数据。本例中，群体规模的大小取为4,即群体由4个个体组成，每个个体可通过随机 方法产生。如：011101， 101011， 011100， 111001(3) 适应度汁算遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会 的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用 目标函数值作为个体的适应度。(4) 选择运算选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗 传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体 中。本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具 体操作过程是：先计算出群体中所有个体的适应度的总和 fi ( i = 1.2,.,M );，其次计算出每个个体的相对适应度的大小fi / fi它即为每个个体被遗传到下一代 群体中的概率，每个概率值组成一个区域，全部概率值之和为1；最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率 区域内来确定各个个体被选中的次数。个阵编号初始群的(D)Ki易适值占总数的百分比果10111013 5340.24101110121010115 3340.24111100130111003 4250.17010101141110017 L500.35111001总谕143124%24%17%35%.ji 入 . 项1#2#4#(5)交叉运算交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：先对群体进行随机配对；其次随机设置交叉点位置；最后再相互交换配对染色体之间的部分基因。4他号5果Rsm况果i 3401：1101 111001 loioin 1110：011-23-41-2： 23-4： 4011001111101101001111011ft-as.可以看出，其中前产生的个体“111101”, U11Q11”的适应度较原来两个个体 的适应度艘高. r0 1(6)变异运算变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是:首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置， 其中的数字表示变异点设置在该基因座处；然后依照某一概率将变异点的原有基因值取反。个体编号果变异点变滁果1011001*011101十111101511111131010011110014111011111010体p(L) 011101 min 111001 111010对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体111111。注意需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果个体笙号初始带钵网）林适11弓鬲国）占总敬的百分比10111015防430.24101011533-if =500.2401110034蠹0.1741110017.150f=35.75035果况变异点变祸果1011101n aa011001F F F F1011101 1 cl 1 s 11iiiuui1-2X1X1UJLJ_ JLJL J. J. J_01010113-43-4： 4101001111001111001-liioii111010适值占总敬的百分比0111013s，4 W30.14min1110017 - 村7s旧0.420.211110107253 心& ：50.23有可能需要一定的循环次数才能达到这个最优结果个钵编号初始峋B）4勺适值占总数的百分比 很珏10111015于 21430.241010115334 f =500.24.0111003425 毕0.174111001J.150 1 f=35,5 |035况果变异点变襁果1r0111011 j*4011001T T T T j- x 1011101 1 丁 1 s 1iiiuui1-2x-j；： 4XXX1UXJ_ JLJL J. J. J_1010113-43-4： 4101001111001111001；;111011111010体p(l)玲*适值占总数的百分比0111013 5阳530.14111111111001(-、i-j19850卜次0.420,211110107 253f=5SJ50.23