algorithm - 如何将遗传算法与一些启发式算法混合

Question

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

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

---

问题描述:

1. 我有:

   • 由 ScheduleSlot 对象填充的数组
   • 由 Lesson 对象填充的数组

2. 我愿意:

   • 标准两点交叉
   • 突变(将随机类(class)移动到随机位置)
   • 粗选(只选择 n 个最好的个体到下一个种群)

@Dougal 和 @izomorphius 的其他信息:
我正在尝试构建一个大学类(class)表，该类(class)表不会在类(class)之间、重叠和地理分布的类(class)之间为小组和教授中断。
适应度函数非常简单:适应度 = -1000*numberOfOverlaps - 1000*numberOfDistrebutedLessons - 20*numberOfBreaks。 (或者类似的东西，我们可以简单地改变变量的系数)
在一开始，我创建我的个人只是在随机的房间、时间和日期上课。
变异和交叉，如上所述，一个非常微不足道的:

1. 交叉——取父调度，随机选择交叉点和交叉范围，只交换父调度的部分，生成两个子调度。
2. 突变 - 将 child 的时间表和 n 个随机类(class)移动到随机位置。

Answer 1

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

另一个想法:在得到结果后，你可以尝试暴力优化它。我的意思是以下内容 - 如果您遇到最初的问题，“愚蠢”的解决方案将回溯检查所有可能性，这通常是使用 dfs 完成的。 .现在这会很慢，但你可以尝试使用 depth first search with iterative deepening或者只是一个深度受限的 DFS。