一,概述
遗传算法 (Genetic Algorithm) 遵循自然界 "适者生存,优胜劣汰" 的原则,是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法.
二,算法流程
1,基因编码
对一些个体的基因做一个编码操作,描述出这些基因的结构.
根据常识,在生物的每个细胞中,都存在相同的一套染色体(chromosome),即 DNA 组合的聚合体.
因此,我们可以将这些染色体由数字 0 和 1 组成的字符串来表达.
2,初始化种群
需要造出一个种群,这个种群有多个生物个体,但是其基因却都不相同.
3,种群选择(适应度计算)
需要制造出一些苛刻的条件来淘汰一些不能适应这些条件的个体,不让其产生后代.
这是因为,这些淘汰掉的个体和最终筛选出的个体差异很大,如果保留,他的后代只会让计算量增大而距离目标没有显著增近.
4,产生下一代
这个过程通常有三种方式:直接选择,基因重组(种群交叉),基因突变(种群变异).
之后的过程,则会一直重复步骤 3-4,直到找到最优解.
三,背包问题
我们通过求解背包问题的最优解来描述遗传算法的步骤.
假设有这样一个背包,可以放置 30 公斤的东西.现在我们有以下物品,其 <重量, 价值> 有如下关系:
怎么能在不超过最大 30 公斤的限制,选取的物品价值最大呢?
item weight value
11515
237
3210
455
598
62017
1,基因编码
这 6 种物品,我们可以采用 bit 位进行编码.
共使用 6 位分别表示是否选取了此 Item.1 表示选取,0 则表示未选取.
item1 item2 item3 item4 item5 item6 chromosome
111111111111
假设只有物品 1,3,5, 则染色体表示为 101010.
2,初始化种群
我们随机产生 4 个生物个体,其染色体如下:
100110:对应物品 1,4,5
001110:对应物品 3,4,5
010100:对应物品 2,4
011001:对应物品 2,3,6
3,种群选择
从最初的这 4 个个体上,我们可以得到如下表格:
染色体 对应物品 总质量 总价值
** 这里我们将总价值这个指标作为染色体的适应度分数,在不超过限制条件的条件下,
1001101,4,52928
0011103,4,51623
0101002,4812
0110012,3,62534
其值越大,他的适应性也就越强.**
除去苛刻条件的筛选过程(上例是重量超标这个条件),我们还需要一次遴选的过程.即共分为筛选评估和遴选两个过程
我们从总体中选择适合的染色体,让其基因重组,产生下一代.但是这样将会导致染色体在数代之后差异减小,失去了基因的多样性.
一般的,我们会通过轮盘赌这种方式进行选择.
轮盘赌(Roulette Wheel):一种赌博游戏,如下图,可进行旋转.轮盘上刻着很多小格子,轮盘开始旋转后,放入一个小球,待轮盘静止后,小球掉入的所对应的号码即为获胜号码.
想象一下,在一个分割了 97(总适应分数)部分的轮盘,各个染色体的占有率如下:
染色体 适应分数 占有率
1001102928.9%
0011101623.7%
010100812.4%
0110012535.1%
我们转动 4 次,中奖的染色体允许繁殖一次,通过计算染色体 1 和染色 4 进入下一轮,各繁殖 2 次.
将这种方法称为:随机普遍选择法(Stochastic Universal Selection method).
4,产生下一代
4.1 基因重组
我们将上一步中的染色体 1 和染色体 4 进行交叉重组,这里我们选择单点交叉方式.
我们随机选择一个位置,将 2 个染色体分离并进行重组.
其基因重组过程为下表:
个体 染色体 配对 交叉点位置 重组结果
4.2 基因变异
100 1101-23100 001
011 0011-23011 110
1001 103-441001 01
0110 013-440110 10
在后代的生长过程中,它们体内的基因会发生一些变化,使得它们与父母不同.这个过程我们称为 "变异",它可以被定义为染色体上发生的随机变化,正是因为变异,种群中才会存在多样性.
变异完成后,即得到了新为个体,进化也就完成了,整个过程如下图:
在生产完下一代之后,我们仍然需要对这些后代进行适应度计算.如果发现出现了连续几代适应度几乎不增加甚至反而减少的情况,
说明函数已经收敛.
因此,一般的,有以下几个终止条件:
- 在进行 N 次迭代之后,总体适应度没有太大变化.
- 算法事先定义好了进化的次数.
- 适应度函数已经达到了预先设定的值.
四,算法可调参数
1,初始群体
上面的背包问题,我们设定了初始群体个数为 4 个.当然,针对这 6 个物品,最多有 2^6 个个体.一般情况下,我们可以设定初始群体数量为 N 个,N 为当前计算机最大可并行计算数量.
2,适应度函数
上面例子中,我们使用轮盘赌算法.当然也可以选择其他方法.
3,基因重组
上面例子中,我们设定的交叉点为 3 和 4,当然可以选择其他的交叉点.
4,终止条件
上面曾列举了常见的 3 中终止条件,当然还有其他,目的都是当适应函数收敛后终止.
来源: http://blog.csdn.net/f59130/article/details/79059324