时间表的遗传算法与模拟退火
我正在开发一个时间表应用程序。遗传算法与模拟退火相比有哪些相对优势？
针对我的具体情况，我有以下几点：
一次，我们最多分配 （3 名教师 X 6 小时）X（3 节课 X 35 小时工作周）一次，我们迭代制定时间表。
必须通知不可能的状态和任何不可能的时间表，而不会使应用程序陷入困境 - 我们希望该应用程序能够达到其极限。
它必须在恒定时间内返回结果或报告失败。
I am developing a timetabling application. What are the relative advantages of genetic algorithms vs simulated annealing?
I have these points specific to my situation:
At a single time, we are allocating a maximum of
(3 teachers X 6 hours)X(3 classes X 35 hour workweek) at a single go, we are iteratively building the timetable.There will be impossible states and any impossible timetables must be notified without the application getting stuck- we expect this application to be pushed to it's limits.
It must return results in a constant time or report that it failed.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，我不得不说，这似乎是一个相当小的解决方案空间：您是否确信蛮力不是您最简单的前进方法？
其次，你的意思是说你需要在某个恒定时间内得到“相当好的”结果，还是你需要算法为 O(1) ？我不会说这是不可能的，但是……好吧，我很确定这是不可能的。
在具体点上，GA 和 SA 之间的主要区别在于，SA 本质上是一种爬山算法，从解空间的最后一点“向外”搜索，而 GA 是概率性的，在解空间内搜索超平面。
你说了两件事让我认为 SA 更适合你的问题：“迭代构建”和“不可能的状态”。由于 GA 在解空间中跨超平面重新组合“相当好的”解，因此它们倾向于“重新发现”解空间中的死区。如果您确信可以从一个相当好的解决方案迭代构建一个更好的解决方案，那么您就处于爬山领域，而 SA 可能更适合。
一般来说，遗传算法的相对优势在于它们可以快速处理大量的解决方案空间，但它们依赖于该解决方案空间中存在简短编码的“好想法”。 SA 的相对优势在于它在其初始解“周围”搜索局部解空间，这往往会有效地找到局部改进。缺点是 SA 是随机播种的，因此在探索大型解空间时效率不高。
First, I have to say that it seems like a pretty small solution space: are you confident that brute-force isn't your easiest way forward?
Second, do you mean to say that you need a "pretty good" result in some constant time or that you need the algorithm to be O(1)? I won't say that's impossible, but... well, I'm pretty sure it's impossible.
On the specific point, the major difference between GAs and SA is that SA is essentially a hill-climbing algorithm that searches "outward" from the last point in the solution space, while GAs are probabilistic and search hyperplanes within the solution space.
You say two things that make me think SA is a better fit for your problem: "iteratively building" and "impossible states." Since GAs recombine "pretty good" solutions across hyperplanes in the solution space, they tend to "re-discover" dead zones in the solution space. If you're convinced that a better solution can be iteratively built from a pretty good solution, you're in hill-climbing territory and SA could fit better.
To be very general, the relative advantage of GAs is that they quickly process very large volumes of the solution space, but they rely on there being briefly-encoded "good ideas" within that solution space. The relative advantage of SA is that it searches the local solution space "around" its initial solution, which tends to find local improvements efficiently. The disadvantage is that SA is seeded randomly and so is not efficient in exploring large solution spaces.