遗传算法背包问题

排列编码

格雷编码(选择编码)

两个编码方式有差异,我个人认为排列编码会比较好一点,逻辑更加高一些。代码中为EGA模板(即带有精英选择机制的遗传算法),测试下来可能NSGA-ii模板会更优一些,可以在测试的时候选择你想要的算法及结果。data.xlsx

强化学习 Pytorch

个人强化学习过程,Q-learning(基础)-> DQN -> AC -> A2C / A3C -> DDPG -> TD3

DQN

算法简要说明:采用经验回放与神经网络对Q-learning进行优化,使其能够输入连续的数,并更好的利用数据。

参考代码

Actor Critic

算法简要说明:Actor 基于概率选行为, Critic 基于 Actor 的行为评判行为的得分, Actor 根据 Critic 的评分修改选行为的概率。

说明:现已改正 CSDN 上错误代码并经行优化。Github上代码流程为跑完一次历程再进行网络优化,并且Actor和Critic共用同一个optimizer和loss,CSDN 上代码流程为原论文流程,即一边跑历程,一边训练网络,并且Actor和Critic具有不一样的optimizer和loss。

对比:原论文流程,即 CSDN 代码流程网络训练较慢,但收敛可能较快。但在跑 CartPole-v1 的时候效果还是Github 代码优异,只能说具体问题可以都试试,选择最优的代码流程。

CSDN 参考代码

Github 参考代码

A2C A3C

网上多数认为 DDPG TD3 PPO 优于 A3C 所以我没怎么看此两种方法。简单来说就是通过多线程同时计算多个网络,返回组合来更新策略和值函数来更新网络。

DDPG

讲的非常好的一篇文章

代码地址

TD3

讲的很好的文章

强化学习算法选择

讲的很好的文章

关于GA/NSGA优化神经网络

查了网上一些论文和代码,自己写了三个版本的GA-BP优化代码。

说明:主要便于方便代入自己的数据所以写了如下代码。自己用的时候主要可以修改Net中的网络,Train中的load_data变成自己要读的文件,选用合适的损失函数等等。geatpy为国内大佬写的遗传算法库,这里假设读者已经会用。关于GA和NSGA的区别只在于代码中运用模板的区别。

代码都有注释,可以试着读一读。代码gpu支持暂没测试与优化。

可供测试data文件。测试文件说明:最后一列为label,除最后一列外为data。

三个版本对比,对上述测试文件对R^2 >= 0.96为指标,在我的破电脑上运行时间v1.0≈1min,v2.0约等于45s,v3.0≈20s,我没有测试过别的例子的速度,对于v3.0不能保证每个例子都能用,有一定缺陷,不同问题可以选用不同的版本进行使用。

利用 GA 求神经网络最优的learning rate和隐藏层的神经元个数

GA-NET v1.0

对于图片的识别,进行了相关优化

GA-NET v2.0

在神经网络中也加入GA来加快神经网络训练速度

GA-NET v3.0

以上均为回归损失计算方法,要计算分类损失只需要修改如下代码。

详情也可见该文章

分类损失

NSGA-ii 双目标遗传算法

论文原文《A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II》,可在IEEE上搜索。

简要叙述:编码交叉变异依然不变,在在此基础上加上了

  1. 快速非支配排序
  2. 拥挤度
  3. 精英策略

非支配排序

支配简述:对于一个点a,他的f1(a), f2(a)……fn(a)都比另一个点b,他的f1(b), f2(b)……fn(b)大,那么a支配b。
非支配即a他的所有值至少有一个小于b,且至少有一个大于b,那么,那么a和b非支配。

NSGA-ii 使用快速非支配排序,具体算法可见代码,根据代码思路自己去画一画。

非支配排序会最终将很多点分成不同rank的类,根据目标所需最大最小不同后续选择对rank不同的排序。

例子代码

拥挤度计算

个人认为很多时候可以用用拥挤距离替代,每个类都分别计算拥挤度,但最终很多时候在算法中只需要计算一个rank的拥挤度。

一个rank中的所有点,其中第一个点和最后一个点的拥挤距离为∞,中间点的距离即delta_y1 + delta_y2。拥挤距离可用delta_y1 / (max(y1) – min(y1)) + delta_y2 / (max(y2) – min(y2))

精英策略

每次从n个种群交叉变异后会生成2n的种群,通过精英策略选取其中前n个进行下一次迭代。策略如下:

  1. rank大/小的优先,看具体题目
  2. 如果有个rank加上后在超过了n个个体的种群,则进行拥挤度排序,选取最大/小的直到种群为n个个体。

Github上大佬的代码