optaplanner - 在本地搜索的联合中有更多移动选择器的优点和缺点

Question

我想就本地搜索中移动选择器的数量发表意见。在大多数用例中，添加新的移动选择器(具有给定的移动类型)是否比消极的更积极。这意味着它是否有助于算法更快地摆脱局部最优，或者它是否会因具有额外的移动类型而更多地分散算法的注意力？

还有没有一种方法可以根据解决方案的当前状态和存在的约束违规来控制哪些移动类型比其他移动类型更多？

Answer 1

如果您的运行时间超过几秒钟，通常会更好，因为它提供了更多的多样性。默认配置只有更改和交换移动，因此可以说它需要支柱更改、支柱交换、2opt ......但这取决于用例。例如，背包需要支柱交换，车辆路线需要 2opt，但反之亦然，它们没用。我确实希望 future 的版本能够识别链式变量，因此默认配置将包含 2opts。

至于控制移动类型:您静态地使一种移动类型的选择次数是另一种移动类型的两倍。或者使用概率选择器，您甚至可以根据移动实例对其进行区分(尽管您需要能够缓存所有移动，因此不适用于大数据集)。

但开箱即用的方法无法根据解决方案的状态动态更改移动类型。这确实是超启发式:如果最佳分数在 100 步内未得到改进，则切换到第二个 moveSelector 等。尽管可能可以对多个求解器阶段和未改进的步骤终止执行类似的操作，一旦我们开箱即用地支持超启发式算法，它就会变得更好。

另请注意，基于约束匹配 - 以及很快的起诉图(这是约束匹配总图的反向图)，我们将研究选定实体的Guided Local Search与其他实体相比，起诉计数更高(= 涉及更多的约束违规)。