我正在开发一个时间表应用程序。遗传算法与模拟退火的相对优势是什么？
对于我的情况，我有以下几点：
一次，我们一次最多分配（3 名教师 X 6 小时）X（3 节课 X 35 小时工作周），我们正在迭代地构建时间表。
将会有不可能的状态，并且必须通知任何不可能的时间表而不会卡住应用程序——我们希望这个应用程序被推到它的极限。
它必须在恒定时间内返回结果或报告失败。
问问题
3317 次
1 回答
6
首先，我不得不说这似乎是一个非常小的解决方案空间：您是否确信蛮力不是您最简单的前进方式？
其次，您的意思是说您需要在某个恒定时间内获得“相当不错”的结果，还是您需要算法为 O(1)？我不会说这是不可能的，但是……嗯，我很确定这是不可能的。
在具体点上，GAs 和 SA 之间的主要区别在于，SA 本质上是一种爬山算法，从解空间中的最后一个点“向外”搜索，而 GAs 是概率性的，在解空间内搜索超平面。
你说了两件事让我认为 SA 更适合你的问题：“迭代构建”和“不可能的状态”。由于 GA 在解决方案空间中跨超平面重新组合“相当不错”的解决方案，因此它们倾向于“重新发现”解决方案空间中的死区。如果您确信可以从一个非常好的解决方案迭代地构建一个更好的解决方案，那么您就处于爬山领域，SA 可能更适合。
概括地说，GAs 的相对优势在于它们可以快速处理大量的解空间，但它们依赖于在该解空间中存在简短编码的“好主意”。SA 的相对优势在于它搜索“围绕”其初始解的局部解空间，这往往会有效地找到局部改进。缺点是 SA 是随机播种的，因此在探索大型解决方案空间时效率不高。
于 2011-12-30T01:58:18.947 回答