java - 遗传算法 - 分组人 : Only find solutions containing criteria X, Y 和 Z

Question

我正在尝试解决以下问题:

• 我有一份 30 人的名单。
• 这些人需要分成 6 人一组。
• 每个人都给出了另外 3 个人的名字，他们希望与之同组。

我想用遗传算法解决这个问题。适应度函数可以评估所有组，并根据每个房间有多少人的所有偏好都得到满足来分配适应度分数。 (或类似的评分系统)

例子:生成的解决方案之一是:1,3,19,5,22,2,7,8,11,12,13,14,15,13,​​17....等我会假设前 5 个人在第一组，接下来的 5 个人在下一组，并从中计算一个适应值。

我认为这个解决方案会奏效 - 有没有人看到更好的方法？

我的主要问题是:如果我想确保 A 和 B 肯定在同一组中，我可以实现适应度函数来检查这一点，如果不满足此条件，则分配一个糟糕的适应度。这是最好的方法吗？看起来效率很低。有没有办法“锁定”解决方案的某些部分(“某些基因”)并只解决或解决其余部分？

任何帮助或见解将不胜感激。

提前致谢。AK

Answer 1

稍微澄清一下，您的问题不在于遗传编程，而在于遗传算法，这是两件不同的事情。遗传编程是关于生成(使用进化算法)可执行个体，这些个体将生成您的解决方案，而遗传算法个体直接代表您的解决方案。

话虽如此，您的两个假设是正确的。数据表示通常是进化算法的关键要素，糟糕的表示可能会阻碍有效的解决方案空间探索。您当前的数据表示对我来说似乎是正确的，因为组只允许恰好有 5 个人。您对执行某些标准的方式的第二个想法也是正确的。设置一个大的适应度值(最好是不能代表一个潜在有效的即使是糟糕的解决方案)如无穷大(如果你的图书馆/语言允许它很容易)是在文献中表达无效解决方案的首选方式。与简单地删除无效个体相比，这具有多个优点:在选择阶段，不会选择不良个体，因此他们所代表的解决方案空间不会像有趣的个体那样被探索，这在计算上是好的，因为它肯定不会包含最优解。毕竟，知道解决方案不好就是好知识。同时，为了避免停滞，遗传多样性在进化算法中非常重要。为了遗传多样性，至少应该保留一些不良个体，以便探索当前代表区域之间的解决方案空间。

遗传算法的目标是计算不可能或太难以分析或蛮力计算的解决方案。尝试使用启发式方法动态锁定某些基因将需要对问题的内部工作以及潜在的进化机制有很多了解，并且会破坏使用进化算法的目的。进化算法的有效目标是锁定看似正确的基因。

事实上，如果您先验绝对肯定某些给定基因必须具有给定值，请不要在您的个体中代表它们。例如，如果您确定其他 2 个人必须具有某个给定值，则让您的第一组 3 个人长。然后，您可以对评估函数进行编码，就好像第一组中有 5 个人一样，但不会进化/搜索以替换 2 个固定的人。