13.6. スコアトラップ

どのスコア制約もスコアトラップを引き起こさないようにしてください。トラップされたスコア制約は、複数の制約の一致に同じ重みを適用します。これを行うと、制約一致がグループ化され、その制約に対して平坦化されたスコア関数が作成されます。これにより、その 1 つの制約の重みを解決または下げるために複数の操作を実行する必要がある解決状態が発生する可能性があります。次の例はスコアトラップを示しています。

  • 各手術台には 2 人の医師が必要ですが、一度に移動するのは 1 人の医師だけです。ソルバーには、医師がいないテーブルに医師を移動させる動機がありません。これを修正するには、スコア関数のスコア制約において、医師が 1 人もいないテーブルに対して、医師が 1 人だけいるテーブルよりも多くのペナルティを課します。
  • 2 つの試験を同時に実施する必要がありますが、一度に実行できるのは 1 つの試験だけです。ソルバーは、これらの試験の 1 つを同じ移動で他の試験を移動することなく、別のタイムスロットに移動する必要があります。これを修正するには、両方の試験を同時に移動する粗粒度の移動を追加します。

次の図はスコアトラップを示しています。

スコアトラップのイラスト

青色のアイテムが過負荷のコンピューターから空のコンピューターに移動すると、ハードスコアが向上するはずです。しかし、トラップスコアの実装ではそれができません。ソルバーは最終的にこの罠から抜け出す必要がありますが、特に過負荷になったコンピューター上にさらに多くのプロセスがある場合には、多大な労力がかかります。そうすることによるペナルティがないため、実際には、その過負荷状態のコンピューターにさらに多くのプロセスを移動し始める可能性があります。

注記

スコアトラップを回避しても、スコア関数がローカルオプティマを回避できるほど賢くなければならないという意味ではありません。ローカルオプティマの処理は最適化アルゴリズムに任せます。

スコアトラップを回避するということは、スコア制約ごとに、フラットライン化されたスコア関数を個別に回避することを意味します。

重要

実行不可能性の程度を必ず指定してください。ビジネスでは、解決策が実行不可能であれば、それがどれほど実行不可能であっても問題ではないとよく言われます。 これはビジネスには当てはまりますが、スコア計算には当てはまりません。スコア計算は、ソリューションがどれほど実行不可能であるかを知ることでメリットが得られるからです。実際には、通常、ソフト制約ではこれが自然に行われ、ハード制約でも同様に行うだけで済みます。

スコアトラップに対処する方法はいくつかあります。

  • スコアの重みを区別できるようにスコア制約を改善しました。たとえば、CPU が不足している場合に -1hard だけのペナルティを科すのではなく、不足している CPU ごとに -1hard ペナルティを科します。
  • ビジネスの観点からスコア制約の変更が許可されていない場合は、そのような区別を行うスコア制約を使用して、より低いスコアレベルを追加します。たとえば、CPU が不足している場合は -1hard に加えて、不足している CPU ごとに -1subsoft のペナルティを科します。ビジネスはサブソフトスコアレベルを無視します。
  • 粗粒度の移動を追加し、既存の粒度の細かい移動と union-select します。粗粒度の移動は、複数の移動を効果的に実行して、1 回の移動でスコアトラップから直接抜け出します。たとえば、複数のアイテムを同じコンテナーから別のコンテナーに移動します。