1

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

  • 我有一个 30 人的名单。
  • 这些人需要分成 6 人一组。
  • 每个人都给出了他们想与他们一起参加的其他 3 个人的名字。

我想用遗传算法解决这个问题。健身功能可以评估所有组,并根据每个房间有多少人满足他们的所有偏好来分配健身分数。(或类似的评分系统)

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

我认为这个解决方案会起作用 - 有没有人看到更好的方法?

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

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

提前致谢。AK

4

4 回答 4

0

似乎对这个问题使用遗传算法最具挑战性的部分是实现交叉。这是我的做法:

首先选择一个常数,C. C 将在所有世代中保持不变,我稍后会解释它的目的。

我将使用一个比 5 组 6 组更小的例子来演示这种交叉,但前提是相同的。假设我们有 2 个父母,每个父母由 3 组 3 组成。让我们制作一个 [[1,2,3],[4,5,6],[7,8,9]],另一个 [[9, 4,3],[5,7,8],[6,1,2]]。

  1. 列出可能的数字(从 1 到总人数),在本例中为 [1,2,3,4,5,6,7,8,9]。从列表中删除 1 个随机数。假设我们删除了 2。列表变为 [1,3,4,5,6,7,8,9]

  2. 我们为每个剩余的数字分配一个概率。概率从 1 开始,与父母的任何匹配都会增加 C。例如,在父母 1 中,3 和 2 在同一组中,因此 3 的概率为 1+C。与 6 相同,因为它在父母 2 中形成匹配。1 的概率为 1+2C,因为它与父母双方的 2 在同一组中。根据这些概率,使用轮盘赌类型选择。假设我们选择 6。

  3. 现在,我们在同一组中有 2 个和 6 个。我们类似地寻找与这些数字匹配并产生概率。对于每个父母,如果它只匹配 2 或只匹配 6,我们添加 C,如果两者都匹配,则添加 2C。继续这个直到组完成(对于 3x3 这是最后一个选择,但对于 5x6 会有更多)

    4.选择一个新的没有被抽到的随机数,继续其他组

这种交叉的好处之一是它基本上已经包含了突变。有机会将未分组的人分组在他们的父母中

信用:我从 Omicron 遗传算法中改编了这个想法

于 2013-07-14T20:09:40.367 回答
0

这可以建模为广义二次分配问题(GQAP)。这个问题允许指定需要一定容量的设备(人)的数量、提供容量的位置(组)的数量以及指定设备之间的接近度的权重矩阵和指定位置之间的距离的距离矩阵。此外,还有安装成本,但这些不是您的问题所必需的。我已经在HeuristicLab中实现了这个问题。它不是主干的一部分,但如果您有兴趣(或者您自己编译),我可以将插件发送给您。

于 2013-07-07T13:49:33.690 回答
0

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

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

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

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

于 2013-07-05T16:34:56.120 回答
0

你的交叉操作是什么样的?您在描述中列出的方式,我不确定您如何干净地实现它。例如,如果您有两种解决方案:

1、2、3、4、5、……、30

1, 2, 30, 29,......,10

假设您正在使用单点交叉功能,您将有可能使用上述基因组为同一个人和其他人获得多个分配。

我将有一个具有 30 个值的基因组,其中每个值定义一个人的组分配 (1-6)。它看起来像 656324113255632....等。因此,将第 1 个人分配到第 6 组,将第 2 个人分配到第 5 组,等等。这将使交叉操作更易于实施,因为您不必确保交叉后每个新解决方案都是有效分配,无论它是否是最优的。

适应度函数将为没有适当数量的成员 (5) 的每个组分配一个惩罚,并为次优的组成员分配分配额外的惩罚。我会让第一个惩罚明显大于第二个,然后调整这些以获得您正在寻找的结果。

于 2013-07-06T14:19:53.023 回答