遗传算法

11 Dec 2019

Reading time ~1 minute

考虑背包问题(knapsack problem)，给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

1. 遗传算法

1.1 字符串表示

遗传算法(GA)使用字符串(string)，字符串的每个元素相当于基因，从某些字母表(alphabet)中选择。背包问题的字母表可以类似表示为字符串：(0, 1, 1, 0)，表示选择中间两个物品带走。

这个字符串不一定是正确并最优的，需要确定每个字符串满足问题标准的程度，也就是字符串的适应度。

1.2 评价适应度

适应度函数(fitness function)可以被看成一个预测，作用于字符串且返回值来评价字符串。对于背包问题来说，适应度函数最好的方案就是能把物品全放进包里，所以需要检查，如果不能，这个方案的适应度就降低。如果一个字符串即一个方案中，所有物品都不能放进背包，它的适应度就是0。

1.3 种群

GA作用于由种群组成的字符串，第一代种群通常随机产生，然后评价字符串适应度，再生成第二代……

背包问题的初始种群可以用随机数生成器创建长度为L的随机二进制字符串：

pop = np.random.rand(popSize,stringLength)

pop = np.where(pop<0.5,0,1)

现在需要的是从种群中选择父母，开始繁殖

1.4 产生后代：选择父母

联赛选择：反复从种群中挑选四个字符串，替换并将最适合的两个字符串放入交配池。

截断选择：仅按比例f挑出适应最好的一部分并忽略其他的。例如f=0.5，前50%的字符串将被放入交配池，并且被等可能地选择。

适应度比例选择：按概率选择字符串，每个字符串被选择等概率与它们等适应度成比例，通常选择函数：

$$p^a=\frac{F^a}{\sum_{a'}F^{a'}}$$ (1.1)

这里是$F^a$是适应度，如果不是正数，那么F需要在整个过程中被exp(sF)替换，其中s为选择强（selection strength）参数，类似于softmax激活函数。

$$p^a=\frac{exp(sF^a)}{\sum_{a'}exp(sF^{a'})}$$ (1.2)

可以对于适应度高的字符串加入更多copy，使之被选择的概率更大。

j=0

while np.round(fitness[j])<1:

    j = j+1
    
newPop = np.kron(np.ones((np.round(fitness[j]),1)),pop[j,:])

for i in range(j+1,self.popSize):

    if np.round(fitness[i])>=1:
    
    newPop = np.concatenate((newPop,np.krno(np.ones((np.round(fitness[i]),1)),pop[i,:])),axis=0)
    
indices = range(np.shape(newPop)[0])

up.random.shulffle(indices)

newPop = newPop[indices[:popSize],:]

return newPop

使用NumPy函数，用第一个数组里每个元素乘以第二个数组里的所有元素，并把所有结果放在一起作为多维数组输出，填充新的并包含更多字符串拷贝的种群(newPopulation)数组。

2 产生后代：遗传算子

选好培育双方后，需要把两个字符串结合从而产生后代。

2.1 交叉

最常用的方法是在字符串中随机找一个点，在这个点之前到部分用字符串1的，在交叉点之后，用字符串2剩下的部分。这实际上产生了2个后代。这种方式称为单点交叉，它的扩展是多点交叉，均匀交叉是让字符串中每个元素都选自父母双方。

2.2 变异

字符串的进化可以由变异实现，达到局部随机搜索。字符串中每个元素的值以概率p（通常较小）改变，通常p约等于1/L，也就是说每个字符串大约会发生一次变异。

1 0 0 1 1 0

变异效果：

1 0 1 1 1 0

2.3 精英法、比赛法和小生境

精英法：从一代中获取一些最合适的字符串并将它们直接放入下一个种群，替换已经存在的字符串，或者选择最不适合的替换掉。每次迭代时种群始终保持相同大小。

比赛法：两位父母和它们的两个后代参加比赛，四个个体中最适合的两个被投入到新的种群中。

这两种方法都可能导致过早收敛（premature convergence），也就是未找到最优解，算法会停止在一个不变的种群上。GA偏爱优良成员，搜索容易被淡化，算法优先考虑达到局部最大值，使大多数字变得容易被替换，最终结果难以代表全局最大值。

解决过早收敛的方法是小生境（niching），将种群分为几个子群，让它们独立演化一段时间，收敛出不同的局部最大值，并且让一个子种群中的少部分成员跑到其他子种群。还有一个方法是适应度共享（fitness sharing），一个特殊字符串的适应度将根据这个字符串在种群中出现的次数来平均，使适应度函数不撇下不常见的字符串。

以上几个步骤简单放在一起就可以组成完整的GA。

基本遗传算法：

初始化：

通过选择的字母表产生N个长度为L的字符串。

学习：

重复：

生成一个（开始为空）的新种群。

重复：

1 通过适应度在当前种群中选择两个字符串

2 重组它们产生两个新字符串

3 让后代变异

4 要么把两个后代加入种群，要么用精英法和比赛法。

5 保持记录种群中最好的字符串

直到新种群中产生N个字符串。

可选性地，使用精英法从父代中挑选最合适的字符串，替换子代中的一些其他字符串。

追踪新种群中最好的字符串。

用新种群代替当前种群。
直到到达停止标准

References:

Marsland S. Machine learning: an algorithmic perspective[M]. Chapman and Hall/CRC, 2014.

机器学习进化学习