Partition Search 的最终成绩为什么下降的很厉害

Question

我是 Optaplanner 的新手。我试图通过分区策略取得好成绩。这是我非常基本的求解器配置：

<solutionClass>com.my.package.SolutionClass</solutionClass>
  <entityClass>com.my.package.EntityClass</entityClass>
  <scoreDirectorFactory>
    <constraintProviderClass>com.my.package.ConstraintsClass</constraintProviderClass>
  </scoreDirectorFactory>

  <partitionedSearch>
    <solutionPartitionerClass>com.my.package.PartitionerClass</solutionPartitionerClass>
    <localSearch>
      <termination>
        <secondsSpentLimit>60</secondsSpentLimit>
      </termination>
    </localSearch>
  </partitionedSearch>
</solver>

为了测试它，我将我的问题分成了两个子问题。当我查看单个分区获得的最佳分数时，它们还不错（-3hard/10soft，-2hard/15soft）。然而，一般的“降低”分数似乎如下：

[org.opt.cor.imp.par.DefaultPartitionedSearchPhase] (executor-thread-0) Partitioned Search phase (0) ended: time spent (60104), best score (-29hard/15soft), score calculation speed (7735/sec), step total (29), partCount (2), runnablePartThreadLimit (6).

这是为什么？我错过了什么吗？

Answer 1

这就是分区搜索的本质。每个分区都将单独优化，因此这些单独的分区将获得不错的分数。然而，这两个分区随后需要合并，合并到最终解决方案中。此步骤未优化，因此会产生一些额外的低效率。

您可能想在最终解决方案上尝试运行非分区求解器，看看它能帮到您。但如果你能做到这一点，你可能一开始就不会使用分区搜索。

请参阅 OptaPlanner documentation on Partitioned Search 讨论效率低下的原因。

Answer 2

[补充 Lukas 的精彩回答]

分区搜索仅在您的分区与您的约束兼容时才有效。在你的情况下，我相信你的分区程序不是。

例如，在员工排班中，假设存在硬约束，即每个员工最多分配 10 个班次。现在，如果您在 1000 个班次的分区中划分了 8000 个班次，但不划分 300 个员工 - 每个分区都包含所有 300 个员工（这是错误的）。然后分区 1 可以为 Ann 分配 9 个班次，而不会破坏硬约束 (0hard)。类似地，分区 2 可以为 Ann 分配 8 个班次，而不会破坏硬约束 (0hard)。然而，合并后，将有 17 个班次分配给 Ann，硬性分数为 -7hard。

我认为这就是您在 -3hard/10soft + -2hard/15soft = -29hard/15soft

中看到的情况

Partition Search 的最终成绩为什么下降的很厉害

Why does the final score of Partition Search drop badly

planning

partitioning

optaplanner

quarkus