第9章 Construction Heuristics (構築ヒューリスティック)

9.1. 概要

構築ヒューリスティックは、時間が限られている中でかなり良い初期解を構築します。構築された解が常に実行可能とは限りませんが、すぐに見つけることができるため、メタヒューリスティックがジョブを終了できます。

構築ヒューリスティックは自動的に終了するため、構築ヒューリスティックフェーズに Termination を明示的に設定する必要はありません。

9.2. First Fit (FF)

9.2.1. アルゴリズムの説明

FF (First Fit) アルゴリズムは、すべてのプランニングエンティティーを (デフォルトの順番で) 繰り返します。一度に初期化するプランニングエンティティーは 1 つです。これは、プランニングエンティティーを、利用できる最適なプランニングエンティティーに割り当て、すでに初期化されているプランニングエンティティーを考慮します。プランニングエンティティーがすべて初期化されると終了します。プランニングエンティティーを割り当てたら変更しません。

これは、クイーン A を行 0 で開始 (そしてその後は移動しない) していることに注意してください。これが最適解に到達することはできません。メタヒューリスティックを使用してこの構築ヒューリスティックにサフィックスを追加すると、これが改善できます。

9.2.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.3. First Fit Decreasing (FFD)

9.3.1. アルゴリズムの説明

FF (First Fit) と同じですが、より難しいプランニングエンティティーを最初に割り当てます。おそらく、残ったものが適合する可能性はないためです。したがって、難易度順にプランニングエンティティーをソートします。

モデルがプランニングエンティティーの難易度比較に対応している必要があります。

注記

このアルゴリズムは、通常、FF (First Fit) よりも良い結果が得られると期待される場合もありますが、常に得られるとは限りません。

9.3.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.4. Weakest Fit (WF)

9.4.1. アルゴリズムの説明

FF (First Fit) と同じですが、計画値が弱いものを最初に使用します。計画値が高い方が、あとでプランニングエンティティーを提供する可能性が高いためです。したがって、弱いものから順に計画値をソートします。

モデルがプランニングエンティティーの強度比較に対応している必要があります。

注記

このアルゴリズムが FF (First Fit) よりも良い結果が得られることはあまりありません。

9.4.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.5. Weakest Fit Decreasing (WFD)

9.5.1. アルゴリズムの説明

FFD (First Fit Decreasing) と WF (Weakest Fit) を組み合わせています。したがって、難易度が高く、強度が低いものからプランニングエンティティーをソートします。

モデルが、プランニングエンティティーの難易度比較および計画値の強度比較に対応している必要があります。

注記

このアルゴリズムが、FFD (First Fit Decreasing) よりも良い結果を得られることはほとんどありませんが、通常は WF (Weakest Fit) よりも良い結果となります。

9.5.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.6. Strongest Fit (SF)

9.6.1. アルゴリズムの説明

FF (First Fit) と同じですが、計画値が強いものを最初に使用します。計画値が強い方が、おそらく使用するソフトコストが低いためです。したがって、強度が高いものから順に計画値をソートします。

モデルがプランニングエンティティーの強度比較に対応している必要があります。

注記

このアルゴリズムが、FF (First Fit) または WF (Weakest Fit) よりも良い結果を得られることはあまりありません。

9.6.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.7. Strongest Fit Decreasing (SFD)

9.7.1. アルゴリズムの説明

FFD (First Fit Decreasing) と SF (Strongest Fit) を組み合わせます。したがって、プランニングエンティティーの難易度が高く、計画値の強度が高い順にソートします。

モデルが、プランニングエンティティーの難易度比較および計画値の強度比較に対応している必要があります。

注記

このアルゴリズムが、FFD (First Fit Decreasing) または WFD (Weakest Fit Decreasing) よりも良い結果を得られることはほとんどありませんが、通常は SF (Strongest Fit) よりも良い結果となります。

9.7.2. 設定

次の Solver フェーズを設定します。

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定については、キューからのエンティティーの割り当てを参照してください。

9.8. Allocate Entity From Queue (AEFQ)

9.8.1. アルゴリズムの説明

AEFQ (Allocate Entity From Queue) は、FF (First Fit)、FFD (First Fit Decreasing)、WF (Weakest Fit) および WFD (Weakest Fit Decreasing) に関する、用途が広い、一般的な形式です。以下のように振舞います。

すべてのエンティティーをキューに追加する。
(そのキューの) 最初のエンティティーを、最適値に割り当てる。
すべてのエンティティーが割り当てられるまで繰り返す。

9.8.2. 設定

簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>

詳細で簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

entitySorterManner オプションは、以下のようになります。

DECREASING_DIFFICULTY: 難しいプランニングエンティティーが最初に初期化されます。これにより、通常は、枝刈りが改善 (したがってスケーラビリティーが改善) します。モデルがプランニングエンティティーの難易度比較に対応している必要があります。
DECREASING_DIFFICULTY_IF_AVAILABLE (デフォルト): モデルがプランニングエンティティーの難易度比較に対応してる場合は DECREASING_DIFFICULTY と同じ動作になり、対応していない場合は NONE と同じになります。
NONE: 元の順番で、プランニングエンティティーを初期化します。

valueSorterManner オプションは、以下のようになります。

INCREASING_STRENGTH: 計画値の強度が小さいものから順に評価します。モデルが計画値の強度比較に対応している必要があります。
INCREASING_STRENGTH_IF_AVAILABLE (デフォルト): モデルが計画値の強度比較に対応している場合は INCREASING_STRENGTH と同じ動作になり、対応していない場合は NONE と同じになります。
DECREASING_STRENGTH: 計画値の強度が大きいものから順に評価します。モデルが計画値の強度比較に対応している必要があります。
DECREASING_STRENGTH_IF_AVAILABLE: モデルが計画値の強度比較に対応している場合は DECREASING_STRENGTH と同じ動作になります。対応していない場合は NONE と同じになります。
NONE: 元の順番で、計画値を試します。

高度で詳細な設定方法 (たとえば、1 つのエンティティークラスに 1 つの変数がある場合の WFD (Weakest Fit Decreasing) 設定):

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>DECREASING_DIFFICULTY</sorterManner>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>INCREASING_STRENGTH</sorterManner>
        </valueSelector>
      </changeMoveSelector>
    </queuedEntityPlacer>
  </constructionHeuristic>

ステップごとに、QueuedEntityPlacer は、EntitySelector から初期化されていないエンティティーを 1 つ選択し、(MoveSelector が生成したエンティティーに対するすべての Move から) 勝利 Move を適用します。模倣選択は、勝利 Move が、選択したエンティティー (だけ) を変更します。

エンティティーまたは値のソートをカスタマイズするには、ソートした選択を参照してください。その他の セレクター のカスタマイズ (filtering や limiting など) も対応しています。

9.8.3. 複数の変数

複数の変数を扱う方法が 2 つあります。 ChangeMove の組み合わせ方法が異なります。

ChangeMove のデカルト積 (デフォルト): 選択したエンティティーの変数はすべて一緒に割り当てます。(特に時間割ユースケースで) 結果がはるかに改善されます。
一連の ChangeMove: 一度に 1 つの変数が割り当てられます。特に 3 つ以上の変数がある場合に、スケールがはるかに良くなります。

たとえば、「コースの時間割」の例で、部屋が 200、時間帯が 40 あるとします。

変数が 2 つある 1 つのエンティティークラスの場合、この FF (First Fit) 設定は、ChangeMove のデカルト積を使用して、エンティティーごとに Move を 8000 個選択します。

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <variableName>room</variableName>
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <variableName>period</variableName>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

警告

それぞれ 1000 個の値が含まれる変数を 3 つ使用して、デカルト積が、1 つのエンティティーにつき値を 1 000 000 000 個選択するため、時間がかかります。

変数が 2 つある 1 つのエンティティークラスに対するこの FF (First Fit) 設定は、順次的な ChangeMove を使用して、エンティティーごとに Move を 240 個選択します。

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <variableName>period</variableName>
        </valueSelector>
      </changeMoveSelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <variableName>room</variableName>
        </valueSelector>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

重要

特に順次的な ChangeMove の場合は、変数の順番は重要です。上記の例では、時間帯を、後ではなく先に選択することが推奨されます。講義室には関係ないハード制約が多くあるためです (たとえば、教師が授業を同時に 2 つ受け持つことはできない)。ベンチマーカーが指針となります。

変数が 3 つ以上ある場合は、デカルト積と逐次方式を組み合わせることができます。

  <constructionHeuristic>
    <queuedEntityPlacer>
      ...
      <cartesianProductMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
      </cartesianProductMoveSelector>
      <changeMoveSelector>...</changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

9.8.4. 複数のエンティティークラス

複数のエンティティークラスを扱う最も簡単な方法は、各エンティティークラスに対して異なる構築ヒューリスティックを実行することです。

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <entityClass>...DogEntity</entityClass>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <entityClass>...CatEntity</entityClass>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

9.8.5. 早期発見のタイプ

構築ヒューリスティックには、早期発見のタイプがいくつかあります。

NEVER: 変数を初期化するのに選択した Move をすべて評価します。これは、InitializingScoreTrend が ONLY_DOWN に設定されていない場合のデフォルトです。
```
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>NEVER</pickEarlyType>
    </forager>
  </constructionHeuristic>
```
FIRST_NON_DETERIORATING_SCORE: スコアを下げない最初の Move で変数を初期化します。選択した残りの Move は無視します。これは、InitializingScoreTrend が ONLY_DOWN である場合のデフォルトです。
```
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType>
    </forager>
  </constructionHeuristic>
```
注記
否定的な制約だけがあり、厳密に言うと InitializingScoreTrend は ONLY_DOWN ではない場合に、FIRST_NON_DETERIORATING_SCORE を適用するのが理にかなっている可能性があります。スコアの品質が失われると時間が短くなるかどうかを判断するにはベンチマーカーを使用します。
FIRST_FEASIBLE_SCORE: 適切なスコアがある最初の Move で変数を初期化します。
```
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE</pickEarlyType>
    </forager>
  </constructionHeuristic>
```
InitializingScoreTrend が ONLY_DOWN の場合は、FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD を代わりに使用してください。この方が速く、デメリットもありません。

FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD: スコアの実現可能性を低下しない最初の Move で変数を初期化します。

  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD</pickEarlyType>
    </forager>
  </constructionHeuristic>

9.9. Allocate To Value From Queue (ATVFQ)

9.9.1. アルゴリズムの説明

ATVFQ (Allocate To Value From Queue) は、以下のように働きます。

すべての値をラウンドロビンキューにおきます。
(キューから) 最初の値に最適なエンティティーを割り当てます。
すべてのエンティティーが割り当てられるまで繰り返す。

9.9.2. 設定

簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>

詳細で簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

高度で詳細な設定方法: (たとえば、変数が 1 つある 1 つのエンティティークラスへの設定)

  <constructionHeuristic>
    <queuedValuePlacer>
      <valueSelector id="placerValueSelector">
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>INCREASING_STRENGTH</sorterManner>
      </valueSelector>
      <changeMoveSelector>
        <entitySelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector mimicSelectorRef="placerValueSelector"/>
      </changeMoveSelector>
    </queuedValuePlacer>
  </constructionHeuristic>

9.10. Cheapest Insertion (CI)

9.10.1. アルゴリズムの説明

CI (Cheapest Insertion) アルゴリズムは、すべてのプランニングエンティティーに対して、すべての計画値を繰り返します。一度に 1 つのプランニングエンティティーを初期化します。(すべてのプランニングエンティティーおよび値から) 利用可能で最適な計画値を割り当て、すでに初期化されているプランニングエンティティーを考慮します。すべてのプランニングエンティティーが初期化されたら終了します。割り当ててからプランニングエンティティーが変更することはありません。

注記

CI (Cheapest Insertion) のスケールは、FF (First Fit) などに比べるとかなり悪いです。

9.10.2. 設定

CI (Cheapest Insertion) の最も簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>CHEAPEST_INSERTION</constructionHeuristicType>
  </constructionHeuristic>

注記

InitializingScoreTrend を ONLY_DOWN にすると、このアルゴリズムは速くなります。エンティティーの場合は、そのスコアが直前のステップのスコアを悪化させない最初の Move を選択し、その後の Move は無視します。

高度な設定方法は、プールからの割り当てを参照してください。

9.11. Regret Insertion (RI)

9.11.1. アルゴリズムの説明

RI (Regret Insertion) アルゴリズムは、CI (Cheapest Insertion) アルゴリズムと同じように振舞います。すべてのプランニングエンティティーに、すべての計画値を繰り返します。一度に 1 つのプランニングエンティティーを初期化します。ただし、最高スコアを持つエンティティーと値の組み合わせを選択せず、最適解を割り当てるタイミングと次に最適な解を割り当てるタイミングの間でスコアロスが一番大きいエンティティーを選択します。次に、エンティティーを最適解に割り当てます。

9.11.2. 設定

このアルゴリズムは現在実装されていません。

9.12. Allocate From Pool (AFP)

9.12.1. アルゴリズムの説明

AFP (Allocate From Pool) は、CI (Cheapest Insertion) および RI (Regret Insertion) に関する、用途が広い、一般的な形式です。以下のように振舞います。

プールに、エンティティーと値の組み合わせを追加する。
最適エンティティーを最適値に割り当てる。
すべてのエンティティーが割り当てられるまで繰り返す。

9.12.2. 設定

簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
  </constructionHeuristic>

詳細で簡単な設定方法:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

entitySorterManner オプションと valueSorterManner オプションについては、キューからエンティティーの割り当てを参照してください。

高度で詳細な設定方法: (変数を 1 つ持つエンティティークラス 1 つに CI (Cheapest Insertion) を設定):

  <constructionHeuristic>
    <pooledEntityPlacer>
      <changeMoveSelector>
        <entitySelector id="placerEntitySelector">
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>INCREASING_STRENGTH</sorterManner>
        </valueSelector>
      </changeMoveSelector>
    </pooledEntityPlacer>
  </constructionHeuristic>

ステップごとに、PooledEntityPlacer は、(MoveSelector が生成したそのエンティティーのすべての Move から) 勝利 Move を適用します。

エンティティーまたは値のソートをカスタマイズするには、ソートした選択を参照してください。その他の セレクター のカスタマイズ (filtering や limiting など) も対応しています。

第9章 Construction Heuristics (構築ヒューリスティック)

9.1. 概要

9.2. First Fit (FF)

9.2.1. アルゴリズムの説明

9.2.2. 設定

9.3. First Fit Decreasing (FFD)

9.3.1. アルゴリズムの説明

9.3.2. 設定

9.4. Weakest Fit (WF)

9.4.1. アルゴリズムの説明

9.4.2. 設定

9.5. Weakest Fit Decreasing (WFD)

9.5.1. アルゴリズムの説明

9.5.2. 設定

9.6. Strongest Fit (SF)

9.6.1. アルゴリズムの説明

9.6.2. 設定

9.7. Strongest Fit Decreasing (SFD)

9.7.1. アルゴリズムの説明

9.7.2. 設定

9.8. Allocate Entity From Queue (AEFQ)

9.8.1. アルゴリズムの説明

9.8.2. 設定

9.8.3. 複数の変数

9.8.4. 複数のエンティティークラス

9.8.5. 早期発見のタイプ

9.9. Allocate To Value From Queue (ATVFQ)

9.9.1. アルゴリズムの説明

9.9.2. 設定

9.10. Cheapest Insertion (CI)

9.10.1. アルゴリズムの説明

9.10.2. 設定

9.11. Regret Insertion (RI)

9.11.1. アルゴリズムの説明

9.11.2. 設定

9.12. Allocate From Pool (AFP)

9.12.1. アルゴリズムの説明

9.12.2. 設定

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Red Hat legal and privacy links

Red Hat legal and privacy links