进化算法

• 遗传算法 Genetic Algorithms
• 进化策略 Evolution Strategy
• 神经网络进化 Neuro-Evolution
  • NEAT算法
  • ES与强化学习

通用算法：

• init：集合$A(s=0)$
• repeat：
  • evaluate：集合$A(s)$中每个元素$a_i$的适应度$\phi_i$
  • select：依据适应度$\phi_i$按概率挑选$B(s)$
  • reproduce：从$B(s)$继承得到$C(s)$
  • $A(s+1)=C(s)$
• 满足条件时break

遗传算法 Genetic Algorithms

pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))   # 种群DNA

fitness = get_fitness(pop)      # 得到种群适应度
pop = select(pop, fitness)      # 按适应度根据概率选 pop
pop_copy = pop.copy()
for parent in pop:
    child = crossover(parent, pop_copy)     # 从 pop_copy 中随机选一个与 parent 进行基因交叉配对
    child = mutate(child)                   # 变异，随机0-1变换
    parent[:] = child

Microbial GA：挑选两个pop，对比fitness，胜者不变，败者进行crossover和mutate。

进化策略 Evolution Strategy

GA与ES的差别：

• GA用二进制DNA; ES用实数DNA（均值+标准差）
• GA通过0-1变换进行变异；ES通过标准差变异
• GA选优秀父母进行繁殖; ES繁殖后选优秀孩子

for _ in range(N_GENERATIONS):
    kids = crossover(pop)
    kids = mutate(pop)
    pop = kill_bad(pop, kids)

Natural ES：将kid的梯度作为fitness的权重进行优化，指导向适合的方向进化

神经网络进化 Neuro-Evolution

利用GA、ES算法改变神经网络的结构

NEAT算法

Evolving Neural Networks through Augmenting Topologies

1. 对网络编码，表示成Node Genes+Connect Genes
2. crossover：根据ID对齐，遗传一方的信息
3. mutate，对connect或node

ES与强化学习

参考Parameter Noise与Evolution Strategies，ES对网络参数扰动，能提升RL网络结果。