大型离散宇宙中的寻优算法

Question

我目前正在寻找一种算法，它可以返回给定大小和范围（一般在50个中的10-15个之间）的项目的最佳（或至少一个最佳次最佳）组合，所以大概有几十亿种可能性……）和一个评分函数，它给出了过去每个组合的性能（根据我选择的复杂度，要优化的函数需要2秒到1秒之间运行）。 对我来说，主要的问题是如果我必须测试所有可能的组合（我甚至不能将所有可能的组合存储在一个列表中），那么要处理的迭代次数。。。如果我不想耗尽内存，每次评估都必须使用generator）。 不幸的是，对于某些函数，我不能使用所谓的基于迭代的“遗传”算法（从2的最佳值开始，从3的最佳值开始，。。一篮子n等等。。。添加新项目时对子篮进行一些检查）。 这种算法速度很快，大多数情况下都能给出很好的结果。你知道吗

我已经试过模拟退火了(西皮.巴辛霍普版本或自定义版本），但如果我超过25-30中的15个，则每次迭代都会花费太多时间，因为我无法在算法开始时存储所有组合，并且每次评估都必须使用生成器。此外，有时我对给定的最佳值并不十分满意。你知道吗

如果你有想法、建议或暗示，我会接受一切。如果你想看我的模拟退火函数，请尽管问我。你知道吗

非常感谢！你知道吗

Answer 1

我知道你的问题没有单一的最佳解决方案，但这里有一些建议：

• 分支定界（如果你能设计一个好的定界函数）
• 模拟退火（尝试不同的冷却速率和邻域大小）
• 蚁丘群（通常比SA效率低）
• 大都会（通常比SA效率低）
• 禁忌搜索（虽然没有很大的改进，但即使对于困难的问题也很好）
• 线性规划（如果问题可以用这些术语表示）

在一个非常困难的问题上结合几种技术也是很常见的。 还有一个python库实现了许多这样的方法（以及许多其他方法）or-tools。不幸的是，它没有很好的记录

我不认为你需要一整套模拟退火的组合，因为它是一种局部搜索技术。在一个典型的场景中，您生成一个新的状态（例如，通过向一个随机参数添加随机增量，或者在问题空间的半径范围内选择一个随机点），然后使用概率公式决定是否接受此更改。也就是说，它的一个优点就是内存占用非常小