遗传算法之经典案例

走进遗传算法(一)中讲了遗传算法的背景知识和解题思路,让大家对遗传算法有一个基本的概念。但是好的例题无疑能让你更快的入门遗传算法,这一章我们来讲几个遗传算法的经典案例:

求二元函数的最大值:

1
2
3
f(x1, x2) = x1^2 + x2^2
0 < x1 < 8 //是整数
0 < x2 < 8 //是整数
(1) 个体编码

遗传算法的运算对象是表示个体的符号串,所以必须把变量 x1, x2 编码为一列符号串。
因 x1, x2 为 0 ~ 7之间的整数,所以每个数分别用3位无符号二进制整数来表示(000-111),将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型(包括x1和x2),表示一个可行解。
例如,基因型 X=101110 所对应的表现型是:x=[ 5,6 ]。
个体的表现型x和基因型X之间可通过编码和解码程序相互转换。

(2) 初始群体的产生

遗传算法是对群体进行的进化操作,需要给其淮备一些表示起始搜索点的初始群体数据。
本例中,群体规模的大小取为4,即群体由4个个体组成,每个个体可通过随机方法产生。
如:011101,101011,011100,111001

(3) 适应度汁算

遗传算法中以个体适应度的大小来评定各个个体的优劣程度,从而决定其遗传机会的大小。
本例中,目标函数总取非负值,并且是以求函数最大值为优化目标,故可直接利用目标函数值f(x1, x2) = x1^2 + x2^2的值作为个体的适应度。

(4) 选择运算

选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。
本例中,我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是:
• 先计算出群体中所有个体的适应度的总和 fi ( i=1.2,…,M );
• 其次计算出每个个体的相对适应度的大小 fi / fi ,它即为每个个体被遗传到下一代群体中的概率。
• 每个概率值组成一个区域,全部概率值之和为1;
• 最后再产生一个0到1之间的随机数,依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。

(5)

参考:

非常好的理解遗传算法的例子