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

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

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

问题描述：

我有：
- 阵列由ScheduleSlot填充对象
- 阵列由课程填充对象
我做的：
- 斯坦达特两点交叉
- 突变（移动随机教训随机位置）
- 粗糙的选择（选择下一个人口只有n个最佳个人）

的其他信息@Dougal and @izomorphius：
我是triyng来构建一个大学时间表，这将不会中断课程，重叠和地理分布的课程为团体和教授。
健身功能非常简单：fitness = -1000 * numberOfOverlaps - 1000 * numberOfDistrebutedLessons - 20 * numberOfBreaks。（或类似的东西，我们可以简单地改变变量的系数）
在刚刚开始时，我产生了我的个人只是随机的房间，时间和日期的教训。
变异和交叉，如上文所述，真是小巫见大巫：

交叉 - 以母公司的时间表，随机选择的点和交叉的范围，只是交换父母安排的部分，产生两个子计划。
突变 - 采取一个孩子的时间表，并随机移动n随机课程的位置。

来源

2012-04-27 mr.nothing

这不是我以前做过的事情，也不知道是否标准，但是您可以考虑运行一段时间的遗传算法，得到一个体面健康的人群，然后将这些点用作梁的起点搜索或者使用标准本地搜索技术的东西。 – Dougal 2012-04-27 12:47:22

我已经成功地将遗传算法与动态规划，神经网络甚至一些数据挖掘算法混合在一起。但是，如果不了解更多关于你想要做什么的事情，你的合适功能是什么，你如何创建个人以及你如何变异，我不认为我可以给你任何关于如何将这些应用于你的问题的建议。 – 2012-04-27 13:03:27

@izomorphius，请在正确的主题中找到附加信息，在此先感谢您的帮助 – 2012-04-29 16:09:28

我最初的观察：你已经在numberOfOverlaps，numberOfDistrebutedLessons和numberOfBreaks前面稍微随机地选择了coeficients。我的经验表明，通常这些选择不是最好的选择，你最好让电脑选择它们。我建议编写第二种算法来选择它们 - 可以是神经网络，第二次遗传算法或爬山。这个想法是 - 计算一段时间后你获得的结果有多好，并尝试优化这3个值的选择。

另一个想法：得到结果后，你可以尝试蛮力优化它。我的意思是以下内容 - 如果您遇到最初的问题，那么“愚蠢的”解决方案将会回溯到所有可能性，通常使用dfs。现在这将会非常缓慢，但是您可以尝试使用depth first search with iterative deepening或者简单地深入扼杀DFS。

来源

2012-04-30 06:41:05

完全同意。你无法通过将你的头撞到墙上来学习某些东西。除了遗传算法不能学习正则和负向适应度函数术语之间如此荒谬的巨大差异的规则。 – 2012-04-30 09:25:47

@ 0x69，我不确定是否有必要找到系数。我们只是试图强调什么标准对我们更重要，哪些更少。无论如何，我会尝试从GA获得的最佳解决方案。希望它会带来好的结果。谢谢，大家，我会提供一些关于结果的信息。 – 2012-04-30 10:11:40

@izomorphius，好吧，我写了一个强力优化器，它在GA之后起作用，正如我想的那样，最困难的问题是为团队和教授同时消除课程之间的差距，它的工作非常缓慢。我真的认为，混合遗传算法可以提高生产力。 – 2012-05-02 18:53:46

对于很多问题，我发现拉马克式的遗传算法效果很好，将局部搜索结合到遗传算法中。

对于您的情况，我会尝试引入局部搜索作为局部搜索。有两种明显的方法可以做到这一点，你应该尝试两种方法。

本地搜索迭代的替代遗传算法迭代。例如，为了您的本地搜索，您可以强制在一天内分配所有课程，同时保持其他所有内容不变。另一种可能性是将随机选择的课程移至所有空闲插槽以找到最佳选择。关键是要尽量减少暴力搜索的成本，同时还有机会寻找本地改进。
添加一个新的算子，以及执行本地搜索的变异和交叉。（您可能会发现，变异算子是在混合动力方案中用处不大，所以只需更换这可能是可行的。）

在本质上，你将可以在GA的全球勘探与高效的本地搜索相结合。几个GA框架包含有助于组合的功能。例如，GAUL实现上面的替代方案1，每次迭代时可以选择全部种群或仅仅是新的后代。

来源

2012-12-19 10:38:51 Stewart

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

回答

相关问题