发帖
雷达卡
一、手工模拟遗传算法
为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。
例：求下述二元函数的最大值：
javascript:;
1、个体编码
遗传算法的运算对象是表示个体的符号串，所以必须把变量x1, x2编码为一种符号串。本例中，用无符号二进制整数来表示。
因x1，x2为0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。
例如，基因型 X＝101110 所对应的表现型是：X＝[ 5，6 ]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。
2、初始群体的产生
遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始群体数据。
本例中，群体规模的大小取为M=4，即群体由4个个体组成，每个个体可通过随机方法产生。
例如：011101，101011，011100，111001。
3、适应度计算
遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。
4、选择运算
选择运算（或称为复制运算）把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。
本例中，我们采用轮盘赌选择方法。轮盘赌选择法是依据个体的适应度值计算每个个体在子代中出现的概率，并按照此概率随机选择个体构成子代种群。轮盘赌选择策略的出发点是适应度值越好的个体被选择的概率越大。因此，在求解最大化问题的时候，我们可以直接采用适应度值来进行选择。但是在求解最小化问题的时候，我们必须首先将问题的适应度函数进行转换，以将问题转化为最大化问题。
其具体操作过程是：
• 先计算出群体中所有个体的适应度的总和 ；
• 其次计算出每个个体的相对适应度的大小 ，它即为每个个体被遗传到下一代群体中的概率；
• 每个概率值组成一个区域，全部概率值之和为1；
• 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。
例如设从区间［0, 1］中产生4个随机数：r1 = 0.110347 ， r2 = 0.98503 ，r3 = 0.450126, r4 = 0.702496 。
javascript:;
5、交叉运算
交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率Pc相互交换某两个个体之间的部分染色体。
本例采用单点交叉的方法，其具体操作过程是：
• 先对群体进行随机配对；
• 其次随机设置交叉点位置；
• 最后再相互交换配对染色体之间的部分基因。
javascript:;
6、变异运算
变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率Pm进行改变，它也是产生新个体的一种操作方法。
本例中，我们采用基本变异的方法来进行变异运算，其具体操作过程是：
• 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；
• 然后依照某一概率将变异点的原有基因值取反。
javascript:;
对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体P(t+1)。
javascript:;
从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。
注意：需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。
二、编码策略
上例，变量x1, x2都是整数，容易编码，那对于小数怎么办呢？例如x1, x2∈[-1,2]，该如何编码？
编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把-1到2这个区间内的数用计算机语言表示出来。编码就是表现型到基因型的映射，编码时要注意以下三个原则：
1、完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）表现型；
2、健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；
3、非冗余性：染色体和潜在解必须一一对应。
我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串。当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为2-（-1）＝3，则必须将闭区间[-1，2]分为3×106等分。
因为2097152=221＜3×106＜222=4194304 ，所以编码的二进制串至少需要22位。将一个二进制串（b21b20b19…b1b0）转化为区间[-1，2]内对应的实数值很简单，只需采取以下两步：
javascript:;
二进制串<0000000000000000000000>，<1111111111111111111111>，则分别表示区间的两个端点值-1和2。
利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则。
京公网安备 11010802022788号
