Jes*_*ose 4 simulated-annealing genetic-algorithm
我正在开发一个时间表应用程序.遗传算法与模拟退火的相对优势是什么？
我有这些针对我的情况的要点:
在一次,我们一次性分配最多(3名教师X 6小时)X(3班X每周工作35小时),我们正在迭代地建立时间表.
将会有不可能的状态,并且必须在没有应用程序卡住的情况下通知任何不可能的时间表 - 我们希望将此应用程序推向极限.
它必须以恒定时间返回结果或报告失败.
首先,我不得不说这似乎是一个非常小的解决方案空间:你有信心蛮力不是你最简单的前进方式吗？
第二,你的意思是说你需要在某个恒定的时间内获得"相当不错"的结果,或者你需要算法是O(1)吗？我不会说这是不可能的,但是......好吧,我很确定这是不可能的.
在特定点上,GAs和SA之间的主要区别在于SA本质上是一种爬山算法,它从解空间中的最后一点"向外"搜索,而GA是概率性的并且在解空间内搜索超平面.
你说两件事让我觉得SA更适合你的问题:"迭代建立"和"不可能的状态".由于GAs在解决方案领域中跨越超平面重新组合了"相当不错"的解决方案,因此它们倾向于"重新发现"解决方案领域中的死区.如果你确信一个更好的解决方案可以通过一个非常好的解决方案迭代构建,那么你就处于爬山的领域,SA可以更好地适应.
非常一般,GA的相对优势在于它们可以快速处理非常大量的解决方案空间,但它们依赖于在该解决方案空间中简要编码的"好主意".SA的相对优势在于它在"初始"解决方案周围搜索本地解决方案空间,这有助于有效地找到本地改进.缺点是SA是随机播种的,因此在探索大型解空间方面效率不高.