哪种进化算法可以优化二元问题？
在我们的程序中，我们多年来一直使用遗传算法来解决 n 个变量的问题，每个变量都有一组固定的 m 个可能值。这通常适用于约 1,000 个变量和 10 种可能性。
现在我有一个新任务，其中每个变量仅存在两种可能性（开/关），但我可能需要解决具有 10,000 个或更多变量的系统。现有的遗传算法确实有效，但解决方案的改进非常缓慢。
我发现的所有 EA 都是针对连续或整数/浮点问题而设计的。哪一种最适合解决二元问题？
In our program we use a genetic algorithm since years to sole problems for n variables, each having a fixed set of m possible values. This typically works well for ~1,000 variables and 10 possibilities.
Now i have a new task where only two possibilities (on/off) exist for each variable, but i'll probably need to solve systems with 10,000 or more variables. The existing GA does work but the solution improves only very slowly.
All the EA i find are designed rather for continuous or integer/float problems. Which one is best suited for binary problems?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
正如 DonAndre 所说，规范遗传算法几乎是为二元问题而设计的。
然而......
没有任何进化算法本身是灵丹妙药（除非它有数十亿年的运行时间）。最重要的是你的表示，以及它如何与你的突变和交叉运算符相互作用：这些一起定义了本质上是伪装的启发式搜索的“智能”。目的是让每个运算符都有公平的机会产生与父母相似的后代，因此，如果您拥有特定领域的知识，可以让您比随机翻转位或拼接位串做得更好，那么请使用它。
轮盘赌、锦标赛选择和精英主义都是好主意（也许保留超过 1 个，这是一门黑术，谁能说……）。您也可能受益于适应性突变。旧的经验法则是 1/5 的后代应该比父母更好 - 跟踪这个数量并适当改变突变率。如果后代的表现更差，那就减少变异；如果后代始终表现得更好，那么变异就会更多。但突变率需要一个惯性组件，因此它不会适应太快，并且与任何元参数一样，设置它是一种黑魔法。祝你好运！
Like DonAndre said, canonical GA was pretty much designed for binary problems.
However...
No evolutionary algorithm is in itself a magic bullet (unless it has billions of years runtime). What matters most is your representation, and how that interacts with your mutation and crossover operators: together, these define the 'intelligence' of what is essentially a heuristic search in disguise. The aim is for each operator to have a fair chance of producing offspring with similar fitness to the parents, so if you have domain-specific knowledge that allows you to do better than randomly flipping bits or splicing bitstrings, then use this.
Roulette and tournament selection and elitism are good ideas (maybe preserving more than 1, it's a black art, who can say...). You may also benefit from adaptive mutation. The old rule of thumb is that 1/5 of offspring should be better than the parents - keep track of this quantity and vary the mutation rate appropriately. If offspring are coming out worse then mutate less; if offspring are consistently better then mutate more. But the mutation rate needs an inertia component so it doesn't adapt too rapidly, and as with any metaparameter, setting this is something of a black art. Good luck!
为什么不尝试线性/整数程序呢？
Why not try a linear/integer program?
嗯，规范形式的遗传算法是最适合二元决策问题的元启发式算法之一。我会尝试的默认配置是这样一种遗传算法，它使用 1-精英主义，并配置轮盘赌选择、单点交叉（100% 交叉率）和位翻转突变（例如 5% 突变概率）。我建议您在人口规模适中（100-200）的情况下尝试这种组合。如果这效果不好，我建议增加人口规模，但也将选择方案更改为锦标赛选择方案（从二元锦标赛选择开始，如果需要更大的选择压力，则增加锦标赛组规模）。原因是，随着人口规模的增加，适应度比例选择方案可能无法施加必要的选择压力来推动搜索向最佳区域发展。
作为替代方案，我们开发了 GA 的高级版本，并将其命名为 后代选择遗传算法。您还可以考虑尝试使用基于轨迹的算法（例如禁忌搜索或模拟退火）来解决此问题，这些算法仅通过进行微小的更改就可以从一种解决方案移动到另一种解决方案。
我们有一个 GUI 驱动的软件 (HeuristicLab)，可让您针对多个问题尝试多种元启发法。不幸的是，你的问题没有包括在内，但它是 GPL 许可的，你可以在那里实现你自己的问题（甚至只通过 GUI，有一个说明）。
Well, the Genetic Algorithm in its canonical form is among the best suited metaheuristics for binary decision problems. The default configuration that I would try is such a genetic algorithm that uses 1-elitism and that is configured with roulette-wheel selection, single point crossover (100% crossover rate) and bit flip mutation (e.g. 5% mutation probability). I would suggest you try this combination with a modest population size (100-200). If this does not work well, I would suggest to increase the population size, but also change the selection scheme to a tournament selection scheme (start with binary tournament selction and increase the tournament group size if you need even more selection pressure). The reason is that with a higher population size, the fitness-proportional selection scheme might not excert the necessary amount of selection pressure to drive the search towards the optimal region.
As an alternative, we have developed an advanced version of the GA and termed it Offspring Selection Genetic Algorithm. You can also consider trying to solve this problem with a trajectory-based algorithm like Tabu Search or Simulated Annealing that just uses mutation to move from one solution to another by just making small changes.
We have a GUI-driven software (HeuristicLab) that allows you to experiment with a number of metaheuristics on several problems. Your problem is unfortunately not included, but it's GPL licensed and you can implement your own problem there (through just the GUI even, there's a howto for that).