遗传算法生成的模型如何避免过拟合？

[nealot]

假定我们有如下的对象:

Dataset trainset;
Dataset testset;

// 通过随机演化的方法，可以得到一个模型 (以 score 作为筛选条件)
Model model = evolve(trainset);

// 一个模型可以在一个数据集上跑出一个分数 (score)
int score1 = run(trainset, model);
int score2 = run(testset, model);

运行时发现，score1 异常地高，而 score2 异常地低。看起来存在严重过拟合。请问需要如何调整设计来避免过拟合呢？

[VoidChen]

前排插眼，顺便问下大佬可以分享下源码吗，我做的东西下一步也要用到遗传算法

[Issacx]

具体陈述一下问题，大部分优化问题和模型都能套这个伪代码。

[nealot]

@VoidChen 是类似图像演化的算法，可以参考这篇文章 https://chriscummins.cc/s/genetics/

[nealot]

@Issacx 现在的核心问题，其实和具体业务是无关的。我来具体解释下矛盾在哪里

传统的机器学习任务，比如用决策树做分类，如果我们在 trainset 上建立一颗尽量精细的决策树 (model)，然后把这个 model 用于 testset，通常效果是不太好的，因为有过拟合，这是个典型的错误

因为是典型的问题，所以也有典型的解法，对于决策树分类问题，解法是这样的:

我们把 trainset 分为两个子集: trainset_1_of_2, trainset_2_of_2

接下来的重点是，我们不是直接构建一个最佳的 model，而是构建一个最佳的 model 的生成参数 (比如 max_depth)

```C++
int best_depth = -1;
int best_score = -1;

for (int max_depth = 1; max_depth < 10; max_depth++) {
tree1 = construct(trainset_1_of_2, max_depth);
score1 = run(trainset_2_of_2, tree1);
tree2 = construct(trainset_2_of_2, max_depth);
score2 = run(trainset_1_of_2, tree2);
score = (score1 + score2) / 2;

if (score > best_score) {
best_score = score;
best_depth = max_depth;
}
}
```

这样我们就得到了 best_depth，然后在整个 trainset 上用这个参数来构建决策树

```C++
tree = construct(trainset, best_depth);
```

接下来这颗树在 testset 上效果就比较好了

但是如果我们搜索的，不是模型生成参数，而是模型本身 (使用遗传算法)，这套方法还成立吗？

PS: 目前使用的是类似图像演化的遗传算法，得到是一个类似 BMP 的图像

[shm7]

都是用一个分布尽量和 test 保持一样的 val/dev 来选择出模型，最后在 test 上测试泛化能力的。我看这里并没有提到 dev/val 。这都是所谓 ml 的最基本概念。

[nealot]

@shm7 验证集可以用来搜索最佳的模型生成参数。如果一定要套用到遗传算法上，我们是要让种群数量减小，演化次数减少，以便不进行充分的演化？这感觉和遗传算法的本意是相违背的

[Issacx]

@nealot 我来整理一下：使用遗传算法来找到最优的超参数以节约调参时间。这个在现在的深度学习里算是 neural architecture search 。但是你们不打算这么做，而是直接用遗传算法当作模型，找最优解，那这个结果不好可能就是遗传不适合你的问题。我以前拿遗传做过 tsp 问题，遗传算法的调参比较 tricky，不知道你们什么问题需要上遗传，这个东西其实现在用的人很少了。

[VoidChen]

@nealot 看了下还挺有意思的。。我这是给培训机构做排课算法，后续打算用遗传算法来找到满足最多约束的组合。。解决过拟合我以前看随机森林的时候好像是从训练集随机抽取子集来解决的，用遗传算法好像不太对路，遗传算法本身就是去找最满足训练集的解。。或者参考下随机森林的思路，去找一个解，对于多个训练集子集的平均适应度最高？

[nealot]

@VoidChen 感觉这是个比较好的解法，值得一试

打个比方，假设这个图像演化算法是用来生成美女的脸型的，第一个训练子集生成出来的是赵薇的脸，第二个训练子集输出的是刘亦菲的脸……

最后把这些明星脸平均一下，就是 “平均美人脸”，这个很可能就是最终需要的模型

(那么为什么不把训练集合在一起训练呢？我也不知道为什么，总之实验效果不好，毕竟这不是简单的加减算术题)

[VoidChen]

@nealot 因为随机抽样出来的多个子集其实是变相地扩充了原本地训练集地样本数量。。而扩充训练集其实也是解决过拟合的办法之一

[northisland]

问题复杂的话，遗传算法收敛很慢的。。。

你用的是具体的哪套？

[vindurriel]

楼主的问题和模型本身无关 是调参 数据使用和停止条件的选择 目前没有通解 都是有策略地瞎试 纯机器调参的思路 可以试试 GAN

[laminux29]

@VoidChen

我建议你还是以最大盈利为原则，来做算法。比如：

1.新顾客，未付费，体验中，这类排课优先级最高。
2.新顾客，已付费，排课高等优先。
3.老顾客，未付费，排课中等优先。
4.老顾客，已付费，排课优先级最低。
5.以上 4 类，同一类中，上课次数越少，注册时间越短，排课优先级越高。

按照已上 5 条原则进行排课，不需要特别麻烦的算法。

[VoidChen]

@laminux29 实际不止，比如说同一个教师教的要在上午或者下午一起上，比如说数学英语组合连堂，有很多类似的软约束= =所以我也是越做越头疼。。一开始以为只是高校排课排一周就行了，这培训班时间周期都不是固定的。。。