如何将遗传算法与一些启发式算法相结合

Question

我正在研究大学排课问题，并使用简单的遗传算法来解决。实际上，它能很好地优化目标函数值，在一个小时内从0%优化到90%（左右）。但之后其过程会急剧减缓，需要几天时间才能得到最佳解。我看了很多论文，发现将其他算法与遗传算法混合使用是有道理的。请您给我一些建议，哪些算法可以与遗传算法混用以加速求解过程？主要的问题是如何将启发式应用于这样复杂的问题中？比如贪心启发式，我不知道该如何应用。谢谢各位提前帮助！

---

问题描述：

1. 我有：
• 由ScheduleSlot对象填充的数组
• 由Lesson对象填充的数组
2. 我做了以下工作：
• 标准两点交叉
• 突变（将随机的课程移动到随机位置）
• 粗略选择（仅选择n个最佳个体进入下一个种群）

额外信息：
我正在构建一份大学课表，其中课程没有间隔、重叠和散布在不同地点，适用于不同的小组和教授。
适应度函数非常简单：适应度= -1000*重叠数量-1000*分散的课程数量-20*间隔数量（或类似的公式，我们可以在变量前简单地更改系数）。
一开始我会随机将课程安排在房间、时间和日期中。突变和交叉如上所述，非常平凡：

1. 交叉-取两个亲代课表，随机选择交叉点和交叉范围，交换亲代课表部分，生成两个子代课表。
2. 突变-取一个子代课表，并将n个随机课程移动到随机位置。

- mr.nothing

---

这不是我以前做过或者知道是否标准的事情，但你可以考虑运行GA一段时间，得到一个具有良好适应度的种群，然后将这些点作为起始点用于梁搜索或其他使用标准局部搜索技术的算法。 - Danica

我已成功地将遗传算法与动态规划、神经网络甚至一些数据挖掘算法相结合。但是，如果我不了解你要做什么，你的适应函数是什么，如何创建个体以及如何变异，我认为我无法为你的问题提供任何建议。 - Ivaylo Strandjev

如果经过X次迭代后适应性没有提高，你可以尝试添加模拟退火算法（可能要考虑前N个个体）：增加温度并打乱局面。 - wildplasser

你说“*..课程之间没有休息时间，组和教授之间存在重叠和地理分布的课程”。我知道什么是教授，但在这个上下文中，“组*”是什么意思？ - RBarryYoung

@RBarryYoung，抱歉，“group”在这里的意思是一组学生。我想这只适用于俄罗斯和其他前苏联国家。 - mr.nothing

Answer 1

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

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

- Ivaylo Strandjev

---

完全同意。你不能通过撞墙来学习某些东西。同样，遗传算法也无法在正负适应度函数之间存在如此巨大的差异时学习规则。 - Agnius Vasiliauskas

@0x69，我不确定是否需要找到系数。通过自己设置它们，我们只是试图强调什么标准对我们更重要，什么标准不那么重要。无论如何，我将尝试在GA得到的最佳解上进行暴力搜索。希望能取得好结果。谢谢大家，我会提供一些结果信息。 - mr.nothing

@izomorphius，我写了一个暴力优化器，它在遗传算法之后工作，正如我所想的那样，最困难的问题是同时为组和教授消除课程之间的空隙，它运行得非常缓慢。我真的认为混合遗传算法可能更有效率。 - mr.nothing

Answer 2

对于许多问题，我发现 Lamarckian 遗传算法的方式是有效的，将局部搜索与遗传算法相结合。

对于你的情况，我建议采用部分系统性搜索作为局部搜索。有两种明显的方法可以实现这一点，你应该尝试两种方法。

1. 使用迭代交替的遗传算法和局部搜索。例如，对于你的局部搜索，可以暴力地搜索所有在一天内分配的课程，而其他内容保持不变。另一个可能是将随机选择的课程移动到所有空闲时间段，以找到最佳选择。关键是最小化暴力搜索的成本，同时仍有机会找到局部改进。

2. 添加一个新的操作符，除了突变和杂交之外，还执行你的局部搜索。(你可能会发现，在混合方案中，突变操作符不太有用，因此只需替换即可。)

实质上，你将把 GA 的全局探索与高效的局部搜索相结合。几个 GA 框架包括了辅助这种组合的功能。例如，GAUL 实现了上述备选方案1，每次迭代时使用整个群体或只是新后代。

- Stewart