机器学习笔记之遗传算法(GA)

遗传算法是一种大致基于模拟进化的学习方法,假设常被描述为二进制串。在遗传算法中,每一步都根据给定的适应度评估准则去评估当前的假设,然后用概率的方法选择适应度最高的假设作为产生下一代的种子。产生下一代的办法有交叉和变异两种方法。

遗传算法和遗传编程是进化计算的两种普遍方法。

遗传算法原理

在遗传算法中各个假设首先表示成二进制位串。用if-then的编码规则将某个属性转换为二进制串。假设一个属性

Outlook可以取Sunny、Overcast和Rain,则该属性可以通过三个二进制位来描述,相应的位表示取某个值的属性。

例子:

(Outlook属性 = Overcast||Rain)&&(Wind属性=Strong)则二进制表示为

Outlook        Wind

011              10

表示了假设以后,再应用下面的迭代函数。

 GA(Fitness,Fitness_threshold,p,r,m)
Fitness:适应度评分函数;
Fitness_threshold:指定终止迭代的门限;
p:群体中假设的数量;
r:每一步通过交叉取代群体成员的比例;
m:变异率;

算法的每一次迭代都从概率的方法选择(具体选择那些个体,与个体的适应度有关)(1-r)p直接进入下一代群体,rp个体通过交叉产生群体进入下一代。然后再从下一代选择mp的成员变异,得到这一轮迭代的下一代群体。

机器学习笔记之遗传算法(GA)

个体选择:适应度比例选择,锦标赛选择和排序选择。

交叉算子:两点交叉,多点交叉和均匀交叉。(可以自定义交叉规则)。

变异算子:从父亲位串中选择一位取反。(当然也可以选择多位)。

机器学习笔记之遗传算法(GA)
      遗传算法实现难题:拥挤问题,群体中某个体适应度大大高于其他个体,因此它迅速繁殖,降低了群体的多样性。解法办法:修改选择函数、适应度共享等。

遗传编程(GP)

遗传编程是遗传算法的一种应用,只不过现在的个体计算机程序,通过GA学习可以得到那种算法的适应性最强。在遗传编程的实现中,GP操作的程序被表示为解析树,然后遗传交叉的时候,交叉解析数的某个子树节点。

机器学习笔记之遗传算法(GA)

进化和学习模型

拉马克进化:如果个体在生命周期内学会了避开某种有毒食物,它能把这种特性遗传给后代。科学证明这种理论冲突,但是它可以提高计算机遗传算法的效率。

鲍德温效应:如果个体具有学习的性能,则个体就会较少地依赖遗传中“基因的不足”,这种个体容易生存下来;如果没有学习能力的个体则单靠遗传的基因,会处于劣势。因此,个体的学习能力间接加速群体适应性进化。Hinton&Nowlan对一个简单的神经网络,运用鲍德温效应进行了实践,即让一些权值固定,另一些权值可以通过样本训练的。实验中,允许学习的时候,群体适应度迅速提高。

并行遗传算法

     GA算法适合并行实现。并行方法把群体细分成相对独立的个体群,每个群成为一个类属(deme),每个类属分配一个计算节点,在这些节点上应用GA算法。类属与类属之间可以通过迁移来复制或交换其他特性,但是将这种概率设置的比类属内部的基因交换概率比低。

上一篇:用遗传算法GA改进CloudSim自带的资源调度策略


下一篇:HDU 2188 悼念512汶川大地震遇难同胞——选拔志愿者(基础巴什博奕)