4

我正在研究大学调度问题并为此使用简单的遗传算法。实际上它工作得很好，并将目标函数值从 0% 优化到 90%（大约）1 小时。但是随后该过程会急剧变慢，并且需要数天才能获得最佳解决方案。我看到很多论文认为将其他算法与基因混合是合理的。请你给我一些建议，告诉我什么算法可以与遗传算法混合，以及如何应用这种算法来加快求解过程。主要问题是如何将任何启发式方法应用于这种复杂结构的问题？我不知道如何在那里应用，例如贪婪启发式。

提前感谢大家！非常感谢您的帮助！

问题描述：

  1. 我有：

    • 由 ScheduleSlot 对象填充的数组
    • 由课程对象填充的数组

  2. 我愿意：

    • 标准两点分频器
    • 突变（将随机课程移动到随机位置）
    • 粗选（仅选择 n 个最佳个体进入下一个种群）

@Dougal和@izomorphius的附加信息：
我正在尝试构建一个大学时间表，该课程表在课程、重叠和针对团体和教授的地理分布课程之间没有中断。
适应度函数非常简单：适应度 = -1000*numberOfOverlaps - 1000*numberOfDistrebutedLessons - 20*numberOfBreaks。（或类似的东西，我们可以简单地改变变量的系数）
在开始的时候，我生成我的个人只是将课程放在随机的房间、时间和日期。
如上所述，突变和交叉非常简单：

  1. 交叉- 取父调度，随机选择交叉点和交叉范围，只交换父调度的部分，生成两个子调度。
  2. 突变 - 采用儿童时间表并将 n 个随机课程移动到随机位置。
4

2 回答 2

4

我最初的观察：您选择了 前面的系数numberOfOverlaps，numberOfDistrebutedLessons而且numberOfBreaks有些随机。我的经验表明，通常这些选择都不是最好的选择，您最好让计算机选择它们。我建议编写第二种算法来选择它们——可以是神经网络、第二种遗传算法或爬山算法。这个想法是 - 计算一段时间后你得到的结果有多好，并尝试优化这 3 个值的选择。

另一个想法：得到结果后，你可以尝试暴力优化它。我的意思是以下 - 如果您遇到最初的问题，“愚蠢”的解决方案将是检查所有可能性的回溯，这通常使用dfs完成。现在这会很慢，但您可以尝试使用深度优先搜索和迭代加深，或者简单地使用深度受限的 DFS。

于 2012-04-30T06:41:05.900 回答
0

对于许多问题，我发现 Lamarckian 风格的 GA 效果很好，将局部搜索结合到 GA 算法中。

对于您的情况，我会尝试引入部分系统搜索作为本地搜索。有两种明显的方法可以做到这一点，您可能应该同时尝试这两种方法。

  1. 与局部搜索迭代交替的 GA 迭代。例如，对于您的本地搜索，您可以暴力破解一天内分配的所有课程，同时保持其他所有内容不变。另一种可能性是将随机选择的课程移动到所有空闲位置以找到最佳选择。关键是最小化暴力搜索的成本，同时仍然有机会找到局部改进。

  2. 在执行本地搜索的突变和交叉旁边添加一个新运算符。（您可能会发现变异算子在混合方案中不太有用，因此只需替换它可能是可行的。）

本质上，您将把 GA 的全局探索与有效的局部搜索结合起来。一些 GA 框架包含有助于这种组合的功能。例如，GAUL实现了上面的替代方案 1，在每次迭代中使用全部种群或仅使用新的后代。

于 2012-12-19T10:38:51.453 回答