笔记:NEAT-增强遗传拓扑有效的原因

根据NEAT论文,写出的程序出现了各种各样的问题,重新静下心来阅读后,标注下其中的关键点,并记录遇到的问题。

如下:


NEAT增强遗传拓扑有效的原因有以下三个方面,缺一不可(参见论文末尾的排除法验证)。

  1.  历史标记:突变形成的全局唯一的创新ID(innovation ID)
  2.  物种形成:通过计算两个个体的基因差异,  在某个阈值内的为同一个物种,物种内部竞争。用来保护拓扑结构。
  3.  最小结构的增量增长:从最小维度的空间进行搜索。初始时全连接(或无连接),输入直连输出,即无隐藏节点。统一从此开始。

笔者实现该算法时遇到的问题,及可能产生的情况:

  • 同一代的同一结构的多个独立个体突变时, 相同的突变分配相同的创新编号,避免创新数量的爆炸式增长(初次就遇到了该问题)
  • 种群里出现过某个创新(innovation ID),突变时,再次发生了该创新, 则复制原先的基因ID(gen id),也就是基因长度不变。
  • 族群的适应度,取的是该族群里最优个体的适应度。【PS 使用族群平均值来排序,发现解决不了xor问题, 大规模情况下待确认】。
  • 年龄标记, 如果不标记年龄,淘汰较老的个体。则会遇到新生代适应度一直低于老龄代的问题。 导致进化停滞。
  • 种群多样性在跳过局部最优时,有很大的作用。【一味的淘汰低适应度个体,陷入了该情况】

改动1:

笔者的计算方式为正向传递计算, 当长度不一致时,一个节点会计算多次。 每次有输入都会计算一次。在输出节点,最后统一计算。

如下:

计算完Node2后,Node2的输出又指向向了Node3, 则,Node3 会计算两次。 第一次Node1、Node3一起计算,第二次Node2激活后输出到Node3,又计算一次。

而输出节点,统一收集所有的结果,统一计算一次。计算方式目前测试对成功率无影响。

改动2:

笔者使用正态分布进行选择个体,虽然能较快的收敛。但几十代后出现了族群消失的问题, 只剩一个族群。 改为轮盘赌算法后,在xor测试案例上,100代内的成功率由97.7% 提升到 99.3%。

确认【族群】多样性对整个种群的提升是必要的。也就是说淘汰个体时,并不能一味的淘汰掉末尾适应度低的个体。 否则很可能陷入跨越局部最优解。

 

 

评论列表: