4

在我们的程序中，我们多年来一直使用遗传算法来解决 n 个变量的问题，每个变量都有一组固定的 m 个可能值。这通常适用于约 1,000 个变量和 10 种可能性。

现在我有一个新任务，其中每个变量只有两种可能性（开/关），但我可能需要解决具有 10,000 个或更多变量的系统。现有的 GA 确实有效，但解决方案的改进非常缓慢。

我发现的所有 EA 都是为连续或整数/浮点问题而设计的。哪一个最适合二元问题？

4

3 回答 3

4

好吧，规范形式的遗传算法是最适合二元决策问题的元启发式算法之一。我会尝试的默认配置是这样一种遗传算法，它使用 1-elitism，并配置有轮盘赌选择、单点交叉（100% 交叉率）和位翻转突变（例如 5% 突变概率）。我建议您尝试这种组合与适度的人口规模（100-200）。如果这不起作用，我建议增加人口规模，但也将选择方案更改为锦标赛选择方案（从二元锦标赛选择开始，如果您需要更大的选择压力，请增加锦标赛组规模）。原因是人口规模越大，

作为替代方案，我们开发了 GA 的高级版本，并将其命名为后代选择遗传算法。您还可以考虑尝试使用基于轨迹的算法（例如禁忌搜索或模拟退火）来解决此问题，该算法仅使用突变通过仅进行小的更改从一种解决方案移动到另一种解决方案。

我们有一个 GUI 驱动的软件 ( HeuristicLab )，它允许您在几个问题上试验一些元启发式方法。不幸的是，您的问题不包括在内，但它是 GPL 许可的，您可以在那里实现自己的问题（甚至通过 GUI，有一个方法）。

于 2011-11-01T09:22:49.900 回答
1

就像 DonAndre 所说，规范 GA 几乎是为二进制问题设计的。

然而...

没有进化算法本身就是灵丹妙药（除非它有数十亿年的运行时间）。最重要的是您的表示，以及它如何与您的变异和交叉运算符相互作用：这些共同定义了本质上是变相的启发式搜索的“智能”。目的是让每个操作员都有公平的机会产生与父母相似的后代，因此如果您拥有特定领域的知识，可以让您比随机翻转位或拼接位串做得更好，那么请使用它。

轮盘赌和锦标赛选择和精英主义都是好主意（可能保留不止 1 个，这是一种黑艺术，谁能说......）。您也可以从适应性突变中受益。旧的经验法则是 1/5 的后代应该比父母更好 - 跟踪这个数量并适当地改变突变率。如果后代的表现更差，那就少变异；如果后代一直更好，那么变异更多。但是突变率需要一个惯性分量，因此它不会适应得太快，并且与任何元参数一样，设置它是一种魔法。祝你好运！

于 2011-11-01T11:35:08.387 回答
1

为什么不尝试线性/整数程序？

于 2011-11-03T15:10:10.987 回答