如何将遗传算法与一些启发式算法相结合 [英] How to mix genetic algorithm with some heuristic
问题描述
我正在研究大学排课问题，并为此使用了简单的遗传算法。实际上，它的效果很好，并且可以在1小时内将目标函数值从0％优化到90％（大约）。但是随后，该过程急剧下降，并且需要几天的时间才能获得最佳解决方案。我看到很多论文，将其他算法与原始算法混合是合理的。能否请您给我一些建议，说明可以将哪种算法与遗传算法混合使用以及如何应用该算法来加快求解速度。主要问题是如何将启发式方法应用于这种复杂结构的问题？我不知道如何在这里应用，例如贪婪的启发式方法。
I'm working on university scheduling problem and using simple genetic algorithm for this. Actually it works great and optimizes the objective function value for 1 hour from 0% to 90% (approx). But then the process getting slow down drammatically and it takes days to get the best solution. I saw a lot of papers that it is reasonable to mix other algos with genetiс one. Could you, please, give me some piece of advise of what algorithm can be mixed with genetic one and of how this algorithm can be applied to speed up the solving process. The main question is how can any heuristic can be applied to such complex-structured problem? I have no idea of how can be applied there, for instance, greedy heuristics.
提前感谢大家！非常感谢您的帮助！
Thanks to everyone in advance! Really appreciate your help!
问题描述：
-
我有：
I have:
- 由ScheduleSlot对象填充的数组
- 由Lesson对象填充的数组
我这样做：
- 标准两点交叉
- 变异（将随机课程移至随机位置）
- 粗略选择（仅选择n个最佳个体作为下一个种群）
@Dougal 和 @izomorphius ：
我正在尝试构建大学课程表，该课程表的上课，重叠和地理位置都不会中断适合团体和教授的课程。
适应度函数非常简单：适应度= -1000 * numberOfOverlaps-1000 * numberOfDistrebutedLessons-20 * numberOfBreaks。 （或者类似的事情，我们可以简单地改变变量的系数）。
在开始的时候，我产生了我的个人，他们只是将课程放在随机的房间，时间和白天。
如上所述，变异和交叉真的很琐碎：
Additional information for @Dougal and @izomorphius:
I'm triyng to construct a university schedule, which will have no breaks between lessons, overlaps and geographically distributed lessons for groups and professors.
The fitness function is really simple: fitness = -1000*numberOfOverlaps - 1000*numberOfDistrebutedLessons - 20*numberOfBreaks. (or something like that, we can simply change coefficients in fron of the variables)
At the very beggining I generate my individuals just placing lessons in random room, time and day.
Mutation and crossover, as described above, a really trivial:
- 交叉-转到父排程，随机选择交叉的点和范围并交换父计划的一部分，生成两个子计划。
- 静音-取一个子计划并将n个随机课程移到随机位置。
推荐答案
我的初步观察：您选择了 numberOfOverlaps 前面的系数， numberOfDistrebutedLessons 和 numberOfBreaks 有点随机。我的经验表明，通常这些选择不是最佳选择，您最好让计算机选择它们。我建议编写第二种算法来选择它们-可以是神经网络，第二种遗传算法或爬坡。想法是-计算一定时间后您得到的结果有多好，并尝试优化这3个值的选择。
My initial observation: you have chosen the coefficients in front of the numberOfOverlaps, numberOfDistrebutedLessons and numberOfBreaks somewhat randomly. My experience shows that usually these choices are not the best one and you should better let the computer choose them. I propose writing a second algorithm to choose them - could be neural network, second genetic algorithm or a hill climbing. The idea is - compute how good a result you get after a certain amount of time and try to optimize the choice of these 3 values.
另一个想法：得到结果后您可以尝试通过蛮力优化它。我的意思是以下这些-如果您遇到了最初的问题，那么傻的解决方案将回到过去，检查所有可能性，通常使用 dfs 。现在这会非常慢，但是您可以尝试使用通过迭代加深的深度优先搜索或只是受深度限制的DFS。
Another idea: after getting the result you may try to brute-force optimize it. What I mean is the following - if you had the initial problem the "silly" solution would be back track that checks all the possibilities and this is usually done using dfs. Now this would be very slow, but you may try using depth first search with iterative deepening or simply a depth restricted DFS.
这篇关于如何将遗传算法与一些启发式算法相结合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
