Red Hat Summit Red Hat Summitサポートコンソール開発者トライアルの開始お問い合わせ

第7章 Move と近傍選択

7.1. Move および近傍の概要
リンクのコピー

7.1.1. Move について
リンクのコピー

Move は、解 A から解 B への変更 (または一連の変更) です。たとえば、以下の Move では、クイーン C が行 0 から行 2 に変更します。

singleMoveNQueens04
View larger image
singleMoveNQueens04

新しい解は、1 つの Move で到達できるため、元の解の近傍と呼ばれます。1 つの Move で複数のクイーンを変更できたしても、解の近傍値は、常にすべての可能解の、非常に小さいサブセットとなります。たとえば、その元の解から見ると、可能なすべての changeMove です。

possibleMovesNQueens04
View larger image
possibleMovesNQueens04

4 つの changeMove は影響を及ぼさず、実行可能ではないため、この 4 つを無視した場合の Move の数は n * (n - 1) = 12 です。これは、可能解の数 (nn = 256) に比べてはるかに少なくなります。問題の増え方と比較した、可能な Move の数は、可能解の数に比べてはるかに少なくなります。

にもかかわらず、changeMove が 4 以下の場合は、どの解にも到達できます。たとえば、3 個の changeMove で到達できる解は大変異なります。

sequentialMovesNQueens04
View larger image
sequentialMovesNQueens04
注記

changeMove 以外にも、Move には多くの種類があります。多くの Move はデフォルトで追加されていますが、カスタムの Move も実装できます。

Move は、複数のエンティティーに影響を与え、エンティティーの作成または削除も可能ですが、問題ファクトは変更しないでください。

すべての最適化アルゴリズムは、Move を使用して、ある解から近傍解に移行します。したがって、最適解アルゴリズムは、Move の選択を迫られます。効果的に Move を作成および反復する技術と、最初に評価するランダムの Move サブセットの中から、最も見込みのあるものを見つける技術になります。

7.1.2. MoveSelector について
リンクのコピー

MoveSelector の主な機能は、必要に応じて Iterator<Move> を作成することです。最適化アルゴリズムは、この Move のサブセットの繰り返しとなります。

以下は、最適化アルゴリズムの局所探索法に changeMoveSelector を設定する方法になります。 

  <localSearch>
    <changeMoveSelector/>
    ...
  </localSearch>
Copy to Clipboard Toggle word wrap

これは、何も設定しなくても機能し、changeMoveSelector の全プロパティーのデフォルトは実用的です (曖昧さによるフェイルファーストは除きます)。一方、設定は特定のユースケースに合わせてかなりカスタマイズできます。たとえば、意味のない Move を破棄するフィルターを設定することもできます。

7.1.3. エンティティ、値、およびその他の Move のサブセレクト
リンクのコピー

MoveSelector は 、Move を作成するために、移動するプランニングエンティティーまたは計画値を 1 つ以上選択する必要があります。MoveSelectors と同様、EntitySelectors および ValueSelectors は、同様の機能セット (スケーラブルな ジャストインタイム選択など) に対応する必要があります。したがって、このすべてに共通する Selector インターフェースを実装し、同じように設定します。

MoveSelector は、多くの場合、EntitySelectors、ValueSelectors、その他の MoveSelectors で構成されますが、各セレクターは、必要に応じて個別に設定できます。 

    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
          ...
        </entitySelector>
        <valueSelector>
          ...
        </valueSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

まとめて、この構造が Selector ツリーを形成します。

selectorTree
View larger image
selectorTree

このツリーのルートは MoveSelector で、ステップ毎に (部分的に) 反復する最適化アルゴリズムの実装に注入します。

7.2. 一般的な MoveSelector
リンクのコピー

7.2.1. changeMoveSelector
リンクのコピー

ChangeMove は、1 つのプランニング変数に対してプランニングエンティティーを 1 つ、計画値を 1 つ選択し、エンティティーの変数をその値に割り当てます。

changeMove
View larger image
changeMove

最も簡単な設定方法: 

    <changeMoveSelector/>
Copy to Clipboard Toggle word wrap

1 つのエンティティークラスに、複数のエンティティークラスまたは複数のプランニング変数がある場合は、1 つの設定が、自動的にすべてのプランニング変数に対する ChangeMove の 共用体 に展開されます。

高度な設定方法: 

    <changeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>room</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </changeMoveSelector>
Copy to Clipboard Toggle word wrap

ChangeMove は、粒度が最も細かい Move となります。

重要

メタヒューリスティックアルゴリズムに入るほぼすべての moveSelector 設定に、changeMoveSelector またはカスタムの実装が含まれるはずです。これにより、複数の Move を順番に適用して、考えられるすべての 解 (ソリューション) に確実に到達できます (スコアトラップ は考慮しない)。当然ながら、通常ではより粗い他の Move セレクターと結合されます。

7.2.2. swapMoveSelector
リンクのコピー

SwapMove は、2 つの異なるプランニングエンティティーを選択し、すべてのプランニング変数の計画値を交換します。

swapMove
View larger image
swapMove

1 つの変数における SwapMove は、基本的に 2 つの ChangeMove になりますが、そのうちの最初の ChangeMove が勝利ステップにならないことがしばしばあります。なぜなら、このソリューションでは、ハード制約に違反した状態になるためです。たとえば、両方の授業が同じ部屋で、ハード制約に違反している場合に、2 つの授業の部屋を交換しても、ソリューションは中間状態にはなりません。

最も簡単な設定方法: 

    <swapMoveSelector/>
Copy to Clipboard Toggle word wrap

エンティティークラスが複数ある場合は、1 つの設定が、すべてのエンティティークラスに対して、SwapMove セレクターの 結合体 に自動的に展開されます。

高度な設定方法: 

    <swapMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <secondaryEntitySelector>
        <entityClass>...Lecture</entityClass>
        ...
        <nearbySelection>...</nearbySelection>
      </secondaryEntitySelector>
      <variableNameInclude>room</variableNameInclude>
      <variableNameInclude>...</variableNameInclude>
    </swapMoveSelector>
Copy to Clipboard Toggle word wrap

secondaryEntitySelector が必要になることはほとんどありません。指定しない場合は、同じ entitySelector のエンティティーが交換されます。

variableNameInclude プロパティーを 1 つ以上指定すると、すべてのプランニング変数が交換されるわけではなく、指定したものだけが交換されます。たとえば、「コースの時間割」の例では、variableNameInclude の部屋だけを指定し、期間ではなく、部屋だけを交換します。

7.2.3. pillarChangeMoveSelector
リンクのコピー

pillar は、プランニング変数に対して同じ計画値を持つ、プランニングエンティティーのセットです。PillarChangeMove は、エンティティーのピラーを 1 つ (もしくはそのサブセット) を選択し、1 つの変数の値 (すべてのエンティティーに同じ) を、別の値に変更します。

pillarChangeMove
View larger image
pillarChangeMove

上の例では、クイーン A とクイーン C には同じ値 (行 0) があり、行 2 に移動しました。また、黄色と青のプロセスには同じ値 (コンピューター Y) があり、コンピューター X に移動しました。

最も簡単な設定方法: 

    <pillarChangeMoveSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <pillarSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <pillarSelector>
        <entitySelector>
          <entityClass>...Lecture</entityClass>
          ...
        </entitySelector>
        <subPillarEnabled>true</subPillarEnabled>
        <minimumSubPillarSize>1</minimumSubPillarSize>
        <maximumSubPillarSize>1000</maximumSubPillarSize>
      </pillarSelector>
      <valueSelector>
        <variableName>room</variableName>
        ...
      </valueSelector>
    </pillarSwapMoveSelector>
Copy to Clipboard Toggle word wrap

サブピラーは、その変数に対して同じ値を共有するエンティティーのサブセットです。たとえば、クイーン A、クイーン B、クイーン C、クイーン D がすべて行 0 に置かれている場合、そのクイーンはピラーであり、[A, D] は多くのサブピラーの 1 つになります。subPillarEnabled (デフォルトは true) が false の場合、サブピラーは選択されません。サブピラーが有効になると、ピラーそのものも含まれ、minimumSubPillarSize プロパティー (デフォルトは 1) と maximumSubPillarSize プロパティー (デフォルトは infinity) が、選択した (サブ) ピラーのサイズを制限します。

注記

ピラーのサブピラーの数は、ピラーのサイズの指数です。たとえば、ピラーのサイズが 32 の場合のサブピラーは (232 - 1) です。したがって、pillarSelector は JIT ランダム選択 (デフォルト) だけをサポートします。

その他のプロパティーは、changeMoveSelector で説明します。

7.2.4. pillarSwapMoveSelector
リンクのコピー

pillar は、プランニング変数に対して同じ計画値を持つ、プランニングエンティティーのセットです。PillarSwapMove は、2 つの異なるエンティティーピラーを選択し、そのすべてのエンティティーに対する、すべての変数の値を交換します。

pillarSwapMove
View larger image
pillarSwapMove

最も簡単な設定方法: 

    <pillarSwapMoveSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <pillarSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <pillarSelector>
        <entitySelector>
          <entityClass>...Lecture</entityClass>
          ...
        </entitySelector>
        <subPillarEnabled>true</subPillarEnabled>
        <minimumSubPillarSize>1</minimumSubPillarSize>
        <maximumSubPillarSize>1000</maximumSubPillarSize>
      </pillarSelector>
      <secondaryPillarSelector>
        <entitySelector>
          ...
        </entitySelector>
        ...
      </secondaryPillarSelector>
      <variableNameInclude>room</variableNameInclude>
      <variableNameInclude>...</variableNameInclude>
    </pillarSwapMoveSelector>
Copy to Clipboard Toggle word wrap

secondaryPillarSelector が必要になることはほとんどありません。指定していない場合は、同じ pillarSelector のエンティティーが交換されます。

その他のプロパティーは、swapMoveSelector および pillarChangeMoveSelector で説明しています。

7.2.5. tailChainSwapMoveSelector または 2-opt (連鎖変数のみ)
リンクのコピー

tailChain は、連鎖のプランニング変数を持つプランニングエンティティーのセットです。この変数は、連鎖の最後の部分を形成します。tailChainSwapMove は、テール連鎖を選択し、(同じまたは別のアンカー連鎖にある) 別の計画値のテール連鎖と交換します。対象となる計画値にテール連鎖がない場合は、交換は行われません (その結果、変更のような Move が発生します)。これが、同じアンカー連鎖内で起きた場合は、部分的に連鎖の逆転が発生します。学術論文では、これは、しばしば 2-opt Move と呼ばれます。

最も簡単な設定方法: 

    <tailChainSwapMoveSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <subChainChangeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Customer</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>previousStandstill</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </subChainChangeMoveSelector>
Copy to Clipboard Toggle word wrap

entitySelector は、移動するテール連鎖の開始を選択します。valueSelector は、テール連鎖の移動先を選択します。それ自身にテール連鎖がある場合は、元のテール連鎖の場所に移動します。これは、secondaryEntitySelector の代わりに valueSelector を使用して、可能な 2-opt Move (たとえばテールの最後に移動) をすべて含み、近傍選択 と適切に連鎖するようにします (不均衡な距離と、交換したエンティティーの距離により、選択の確率は正しくなくなります)。

注記

subChainChangeMoveSelector および subChainSwapMoveSelector には、ほぼすべての可能な tailChainSwapMove が含まれますが、実験の結果、tailChainSwapMoves に重点を置くと効率が上がります。

7.2.6. subChainChangeMoveSelector (連鎖変数のみ)
リンクのコピー

subChain は、連鎖の一部を形成する連鎖付きプランニング変数がある、一連のプランニングエンティティーになります。subChainChangeMoveSelector は subChain を選択し、(同じまたは別のアンカー連鎖にある) 別の場所に動かします。

最も簡単な設定方法: 

    <subChainChangeMoveSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <subChainChangeMoveSelector>
      ... <!-- Normal selector properties -->
      <entityClass>...Customer</entityClass>
      <subChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </subChainSelector>
      <valueSelector>
        <variableName>previousStandstill</variableName>
        ...
      </valueSelector>
      <selectReversingMoveToo>true</selectReversingMoveToo>
    </subChainChangeMoveSelector>
Copy to Clipboard Toggle word wrap

subChainSelector が多数のエンティティー (minimumSubChainSize (デフォルトは 1) より多く、maximumSubChainSize (デフォルトは infinity) より少ない) を選択します。

注記

minimumSubChainSize が 1 (デフォルト) の場合に、(デフォルトでは、各 Move タイプ の選択の可能性は同じで (すべての Move インスタンスではない)、ChangeMove インスタンスよりも SubChainChangeMove インスタンスの方がはるかに多いため)、このセレクターは選択の可能性ははるかに低いですが、ChangeMoveSelector と同じ Move を選択する可能性があります。ただし、実験の結果、ChangeMoves にフォーカスすると良いことが分かっているので、ChangeMoveSelector だけを削除しないでください。

さらに、SubChainSwapMoveSelector に minimumSubChainSize を設定すると、サイズが 1 のサブ連鎖を、2 以上のサブ連鎖と交換しなくなります。

selectReversingMoveToo プロパティー (デフォルトは true) は、すべてのサブ連鎖の反対を選択することを有効にします。

7.2.7. subChainSwapMoveSelector (連鎖変数のみ)
リンクのコピー

subChainSwapMoveSelector は 2 つの異なるサブ連鎖を選択し、同一または異なるアンカー連鎖の別の場所に動かします。

最も簡単な設定方法: 

    <subChainSwapMoveSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <subChainSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <entityClass>...Customer</entityClass>
      <subChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </subChainSelector>
      <secondarySubChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </secondarySubChainSelector>
      <selectReversingMoveToo>true</selectReversingMoveToo>
    </subChainSwapMoveSelector>
Copy to Clipboard Toggle word wrap

secondarySubChainSelector が必要になることはほとんどありません。指定していない場合は、同じ subChainSelector のエンティティーを交換します。

その他のプロパティーについては subChainChangeMoveSelector で説明しています。

7.3. 複数の MoveSelector の組み合わせ
リンクのコピー

7.3.1. unionMoveSelector
リンクのコピー

unionMoveSelector は 、次の Move を提供する MoveSelector の子を 1 つ選択して Move を選択します。

最も簡単な設定方法: 

    <unionMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <unionMoveSelector>
      ... <!-- Normal selector properties -->
      <selectorProbabilityWeightFactoryClass>...ProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </...MoveSelector>
      ...
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

selectorProbabilityWeightFactory が、selectionOrder RANDOM で、次の Move を提供するために MoveSelector の子が選択される頻度を決定します。デフォルトでは、MoveSelector の子がそれぞれ選択される可能性は同じになります。

selectorProbabilityInUnion
View larger image
selectorProbabilityInUnion

このような子の fixedProbabilityWeight を選択する頻度を上げます。たとえば、unionMoveSelector が SwapMove を返す頻度を ChangeMove の 2 倍にします。 

    <unionMoveSelector>
      <changeMoveSelector>
        <fixedProbabilityWeight>1.0</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>2.0</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

可能な ChangeMove の数は、可能な SwapMove の数とは大きく異なり、さらに、これは問題に依存しています。(各 MoveSelector とは異なり) 各 Move に同じ選択可能性を付与するには、FairSelectorProbabilityWeightFactory を使用します。 

    <unionMoveSelector>
      <selectorProbabilityWeightFactoryClass>org.optaplanner.core.impl.heuristic.selector.common.decorator.FairSelectorProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

7.3.2. cartesianProductMoveSelector
リンクのコピー

cartesianProductMoveSelector は新しい CompositeMove を選択します。これにより、その CompositeMove を構築します。これは、MoveSelector の子ごとに Move を 1 つ選択して CompositeMove に追加します。

最も簡単な設定方法: 

    <cartesianProductMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </cartesianProductMoveSelector>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <cartesianProductMoveSelector>
      ... <!-- Normal selector properties -->
      <ignoreEmptyChildIterators>true</ignoreEmptyChildIterators>
      <changeMoveSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        ...
      </...MoveSelector>
      ...
    </cartesianProductMoveSelector>
Copy to Clipboard Toggle word wrap

ignoreEmptyChildIterators プロパティー (デフォルトでは true) は、何らかの move が返されるように、空の childMoveSelector をすべて無視します。たとえば、changeMoveSelector の A および B のデカルト積で、(すべてのエンティティーが動かせないため) B が空であれば、ignoreEmptyChildIterators が false の場合は Move を返さず、ignoreEmptyChildIterators が true の場合は A の Move を返します。

その 2 つの子セレクターが、同じエンティティーまたは値を効果的に使用するには、 Move フィルタリングではなく、模倣選択 を使用します。

7.4. EntitySelector
リンクのコピー

最も簡単な設定方法: 

      <entitySelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

      <entitySelector>
        ... <!-- Normal selector properties -->
        <entityClass>org.optaplanner.examples.curriculumcourse.domain.Lecture</entityClass>
      </entitySelector>
Copy to Clipboard Toggle word wrap

entityClass プロパティーには、エンティティークラスが複数あるため、自動的に推測できない場合にのみ必要になります。

7.5. ValueSelector
リンクのコピー

最も簡単な設定方法: 

      <valueSelector/>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

      <valueSelector>
        ... <!-- Normal selector properties -->
        <variableName>room</variableName>
      </valueSelector>
Copy to Clipboard Toggle word wrap

variableName プロパティーは、(関連するエンティティークラスに対して) 変数が複数あるため、自動的に推測できない場合に限り必要になります。

新型の構築ヒューリスティック設定において、EntitySelector の entityClass のダウンキャストが必要になる場合があります。これは downcastEntityClass プロパティーから行えます。 

      <valueSelector>
        <downcastEntityClass>...LeadingExam</downcastEntityClass>
        <variableName>period</variableName>
      </valueSelector>
Copy to Clipboard Toggle word wrap

選択したエンティティーをダウンキャストできない場合は、そのエンティティーに対して ValueSelector が空になります。

7.6. Selector の一般的な機能
リンクのコピー

7.6.1. CacheType: Create Moves Ahead of Time または Just In Time
リンクのコピー

セレクター の cacheType は、選択 (Move、エンティティー、値など) がいつ作成され、どのぐらい存続するかを決定します。

ほぼすべての セレクター で cacheType の設定に対応しています。 

    <changeMoveSelector>
      <cacheType>PHASE</cacheType>
      ...
    </changeMoveSelector>
Copy to Clipboard Toggle word wrap

次の cacheTypes はサポートされます。

  • JUST_IN_TIME (デフォルト): キャッシュは作成されません。各選択 (Move など) を使用する直前に構築します。これにより、メモリーフットプリントが十分な大きさになります。
  • STEP: キャッシュされます。ステップの初めに各選択 (Move など) を作成し、残りのステップに使用するために、その選択をリストにキャッシュします。これにより、メモリーフットプリントが著しく大きくなります。
  • PHASE: キャッシュされます。Solver フェーズの初めに各選択 (Move など) を作成し、残りのステップに使用するために、その選択をリストにキャッシュします。一部の選択では、各ステップでリストが変更になるため、フェーズをキャッシュすることはできません。これにより、メモリーフットプリントが著しく大きくなりますが、パフォーマンスがわずかに向上します。
  • SOLVER: キャッシュされます。Solver の初めに各選択(Move など) を作成し、残りの Solver 用に、リストにキャッシュします。各ステップでリストが変更になるため、一部の選択では Solver のキャッシュを取得することができません。これにより、メモリーフットプリントが著しく大きくなりますが、パフォーマンスがわずかに向上します。

また、複合セレクターに cacheType を設定できます。 

    <unionMoveSelector>
      <cacheType>PHASE</cacheType>
      <changeMoveSelector/>
      <swapMoveSelector/>
      ...
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

cacheType を高くした場合を除いて、キャッシュ済セレクターにネストされたセレクターをキャッシュするように設定することができません。たとえば、ステップ をキャッシュする unionMoveSelector は、フェーズ をキャッシュする changeMoveSelector を保持しますが、ステップ をキャッシュする changeMoveSelector は保持しません。

7.6.2. SelectionOrder: Original、Sorted、Random、Shuffled、または Probabilistic
リンクのコピー

セレクター の selectionOrder は、選択 (Moves、エンティティー、値など) が反復する順番を決定します。最適化アルゴリズムは、通常、はじめから、MoveSelector の選択のサブセットを通してのみ反復しますが、selectionOrder が、実際に評価する Move を決定することが重要になります。

ほぼすべての セレクター は、selectionOrder の設定をサポートします。 

    <changeMoveSelector>
      ...
      <selectionOrder>RANDOM</selectionOrder>
      ...
    </changeMoveSelector>
Copy to Clipboard Toggle word wrap

以下の selectionOrders がサポートされます。

  • ORIGINAL: デフォルトの順に、選択項目 (Moves、エンティティー、値など) が選択されます。各選択項目が選択されるのは、一度だけです。

    • 例: A0、A1、A2、A3...、B0、B1、B2、B3...、C0、C1、C2、C3... です。

  • SORTED: ソートした順番に、選択項目 (Moves、エンティティー、値など) が選択されます。各選択項目が選択されるのは、一度だけです。cacheType ≥ STEP は必須で、多くの場合、構築ヒューリスティックの entitySelector または valueSelector で使用されます。ソートされた選択 を参照してください。

    • 例: A0、B0、C0…​、A2、B2、C2…、A1、B1、C1…​

  • RANDOM (デフォルト): シャッフルしていないランダムの順番で、選択項目 (Moves、エンティティー、値など) が選択されます。各選択項目は複数回選択できます。キャッシュを必要としないため、パフォーマンスが十分に上がります。

    • 例: C2、A3、B1、C2、A0、C0…​

  • SHUFFLED: シャッフルしたランダム順で、選択項目 (Moves、エンティティー、値など​) が選択されます。各選択項目が選択されるのは一度だけです。cacheType ≥ STEP が必要です。これにより、パフォーマンスが著しく上がりますが、キャッシュが必須であるだけでなく、選択されてなくても、各要素に対して乱数が生成されているためです (これは、拡大するときの主要な大多数になります)。

    • 例: C2、A3、B1、A0、C0…​

  • PROBABILISTIC: 各要素の選択可能性に基づいて、ランダム順で選択項目 (Moves、エンティティー、値など​) が選択されます。可能性が高い選択項目は、可能性が低い要素よりも選択される可能性が高くなります。選択項目は、複数回選択される可能性があります。cacheType ≥ STEP が必要です。ほとんどの場合、entitySelector または valueSelector で使用されます。確立的選択 を参照してください。

    • 例: B1、B1、A1、B2、B1、C2、B1、B1…​

selectionOrder は、複合セレクターにも設定できます。

注記

セレクター がキャッシュされると、そのネストされたすべての セレクター は、必然的に selectionOrder ORIGINAL にデフォルト設定されます。そのネストされた セレクター の selectionOrder を上書きしないようにします。

7.6.3. CacheType と SelectionOrder で推奨される組み合わせ
リンクのコピー

7.6.3.1. Just in Time ランダム選択 (デフォルト)
リンクのコピー

この組み合わせは、メモリーフットプリントおよびパフォーマンスが十分に増えるため、ユースケースが大きい (10 000 以上のエンティティー) 場合に重要になります。サイズがこのぐらいになると、他の組み合わせでは実行できない場合もしばしばあります。また、サイズがこれよりも小さいユースケースでも有効なので、試しに使用するのに適しています。これはデフォルトであるため、実際には、cacheType および selectionOrder を明示的に設定することはなくなりました。 

    <unionMoveSelector>
      <cacheType>JUST_IN_TIME</cacheType>
      <selectionOrder>RANDOM</selectionOrder>

      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

この動作は次のようになります。Iterator<Move>.next() が呼び出されると、子の MoveSelector がランダムに選択され (1)、それが Move (2、3、4) をランダムに作成し、返されます (5)。

jitRandomSelection
View larger image
jitRandomSelection

Move のリストは作成されず、実際に選択された Move に対する乱数を生成します。

7.6.3.2. キャッシュしたシャッフル選択
リンクのコピー

小規模や中規模のユースケース (5000 エンティティー以下) で、この組み合わせがしばしば勝利します。サイズがこれよりも大きくなると、メモリーフットプリントとパフォーマンスが著しく大きくなります。 

    <unionMoveSelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SHUFFLED</selectionOrder>

      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

この動作は次のようにします。フェーズ (または cacheType で決まるステップ) の開始時にすべての Move が作成され (1)、キャッシュされます (2)。MoveSelector.iterator() が呼び出されると、Move はシャッフルされます (3)。Iterator<Move>.next() が呼び出されると、シャッフルされたリストで次の要素が返されます (4)。

cachedShuffledSelection
View larger image
cachedShuffledSelection

各 Move は、ランダム順ではありますが、一度だけ選択されます。

(おそらくネストされている) セレクター で ステップ が必要ない場合は、cacheType の PHASE を使用します。それ以外の場合は、以下のようになります。 

    <unionMoveSelector>
      <cacheType>STEP</cacheType>
      <selectionOrder>SHUFFLED</selectionOrder>

      <changeMoveSelector>
        <cacheType>PHASE</cacheType>
      </changeMoveSelector>
      <swapMoveSelector/>
        <cacheType>PHASE</cacheType>
      </swapMoveSelector>
      <pillarSwapMoveSelector/><!-- Does not support cacheType PHASE -->
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

7.6.3.3. キャッシュしたランダム選択
リンクのコピー

この組み合わせは、中規模のユースケース (特に、焼きなまし法など、ステップが速い最適化アルゴリズム) でしばしば有効です。キャッシュされるシャッフル選択とは異なり、各ステップの初めに Move リストをシャッフルし、時間を無駄にしません。 

    <unionMoveSelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>RANDOM</selectionOrder>

      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

7.6.4. フィルターをかけた選択
リンクのコピー

以下の理由により、特定の Move を選択しない場合があります。

  • Move が無意味で、CPU 時間を無駄にしているだけの場合。たとえば、同じコースの 2 つの授業を交換すると、1 つのコースの授業はすべて交換できるため、同じスコア、同じスケジュールになります (同じ教師、同じ生徒、同じテーマ)。

  • Move を行うと 、組み込みハード制約 が壊れ、ソリューションは実行できなくなりますが、(パフォーマンスを上げるため) スコア関数による組み込みのハード制約の確認はありません。たとえば、体育の授業が体育室以外の部屋には変更されないなどです。

    注記

    組み込みハード制約は、すべての Solver フェーズのすべての Move タイプに、フィルターを適切に設定する必要があります。たとえば、局所探索法の変更 Move にフィルターを設定する場合は、交換する Move にフィルターを設定する必要があります。この Move では、体育の授業の部屋を、元の部屋が体育室ではない別の授業と交換します。さらに、構築ヒューリスティックの変更 Move にもフィルターを設定する必要があります (これには、高度な設定が必要です)。

セレクターツリーのすべてのセレクター (MoveSelector、EntitySelector、ValueSelector を含む) で、フィルター選択が発生する可能性があります。これは、cacheType および selectionOrder と連携します。

filteredSelection
View larger image
filteredSelection

フィルタリングは、SelectionFilter インターフェースを使用します。 

public interface SelectionFilter<T> {

    boolean accept(ScoreDirector scoreDirector, T selection);

}
Copy to Clipboard Toggle word wrap

不要な 選択 に対して false を返す accept メソッドを実装します。承認されない Move は選択されず、doMove メソッドは呼び出されません。 

public class DifferentCourseSwapMoveFilter implements SelectionFilter<SwapMove> {

    public boolean accept(ScoreDirector scoreDirector, SwapMove move) {
        Lecture leftLecture = (Lecture) move.getLeftEntity();
        Lecture rightLecture = (Lecture) move.getRightEntity();
        return !leftLecture.getCourse().equals(rightLecture.getCourse());
    }

}
Copy to Clipboard Toggle word wrap

できる限り低いレベルで、このフィルターを適用します。多くの場合は、関連のエンティティーと値の両方を知る必要があり、moveSelector に filterClass を適用する必要があります。 

    <swapMoveSelector>
      <filterClass>org.optaplanner.examples.curriculumcourse.solver.move.DifferentCourseSwapMoveFilter</filterClass>
    </swapMoveSelector>
Copy to Clipboard Toggle word wrap

ただし、可能な場合は、さらに低いレベル (たとえば、entitySelector や valueSelector の filterClass) で適用します。 

    <changeMoveSelector>
      <entitySelector>
        <filterClass>...EntityFilter</filterClass>
      </entitySelector>
    </changeMoveSelector>
Copy to Clipboard Toggle word wrap

1 つのセレクターに、複数の filterClass 要素を設定できます。

7.6.5. ソートした選択
リンクのコピー

ソートした選択は、セレクターツリーにあるすべての セレクター で発生する可能性があります (MoveSelector、EntitySelector、ValueSelector など)。これは、cacheType JUST_IN_TIME では使用できませんが、selectionOrder SORTED で使用できます。

これは、主に構築ヒューリスティックで使用されています。

注記

選択した構造ヒューリスティックにソートが含まれる場合 (たとえば FIRST_FIT_DECREASING では EntitySelector がソートされることを示しています) は、ソートを使用して Selector を明示的に設定する必要はありません。セレクター を明示的に設定する場合は、構築ヒューリスティックのデフォルト設定が上書きされます。

7.6.5.1. SorterManner でソートした選択
リンクのコピー

一部の セレクター では、追加設定しなくても SorterManner が実装されています。

  • EntitySelector は以下に対応します。

    • DECREASING_DIFFICULTY: プランニングエンティティーの難易度 に従って、プランニングエンティティーを降順でソートします。ドメインモデルに、プランニングエンティティーの難易度をアノテートする必要があります。 

          <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterManner>DECREASING_DIFFICULTY</sorterManner>
    </entitySelector>
      Copy to Clipboard Toggle word wrap

  • ValueSelector は以下に対応します。

    • INCREASING_STRENGTH: プランニングエンティティー値の強度 に従って、計画値を昇順でソートします。ドメインモデルに、計画値の強度をアノテートする必要があります。 

          <valueSelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterManner>INCREASING_STRENGTH</sorterManner>
    </valueSelector>
      Copy to Clipboard Toggle word wrap

    • DECREASING_STRENGTH: 計画値の強度に従って計画値を降順でソートします。ドメインモデルに、計画値の強度をアノテートする必要があります。 

          <valueSelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterManner>DECREASING_STRENGTH</sorterManner>
    </valueSelector>
      Copy to Clipboard Toggle word wrap

7.6.5.2. Comparator でソートした選択
リンクのコピー

セレクター は、Plain Old Comparator を使用すると、簡単にソートできます。 

public class CloudProcessDifficultyComparator implements Comparator<CloudProcess> {

    public int compare(CloudProcess a, CloudProcess b) {
        return new CompareToBuilder()
                .append(a.getRequiredMultiplicand(), b.getRequiredMultiplicand())
                .append(a.getId(), b.getId())
                .toComparison();
    }

}
Copy to Clipboard Toggle word wrap

また、Comparator を設定する必要があります (ドメインモデルにアノテートされており、最適化アルゴリズムによって自動的に適用される場合は除きます)。 

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterComparatorClass>...CloudProcessDifficultyComparator</sorterComparatorClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>
Copy to Clipboard Toggle word wrap

sorterOrder 要素は任意です。デフォルト値は ASCENDING になります。

7.6.5.3. SelectionSorterWeightFactory でソートした選択
リンクのコピー

ソリューション全体で セレクター をソートする必要がある場合は、代わりに SelectionSorterWeightFactory を使用します。 

public interface SelectionSorterWeightFactory<Sol extends Solution, T> {

    Comparable createSorterWeight(Sol solution, T selection);

}
Copy to Clipboard Toggle word wrap 
public class QueenDifficultyWeightFactory implements SelectionSorterWeightFactory<NQueens, Queen> {

    public Comparable createSorterWeight(NQueens nQueens, Queen queen) {
        int distanceFromMiddle = calculateDistanceFromMiddle(nQueens.getN(), queen.getColumnIndex());
        return new QueenDifficultyWeight(queen, distanceFromMiddle);
    }

    // ...

    public static class QueenDifficultyWeight implements Comparable<QueenDifficultyWeight> {

        private final Queen queen;
        private final int distanceFromMiddle;

        public QueenDifficultyWeight(Queen queen, int distanceFromMiddle) {
            this.queen = queen;
            this.distanceFromMiddle = distanceFromMiddle;
        }

        public int compareTo(QueenDifficultyWeight other) {
            return new CompareToBuilder()
                    // The more difficult queens have a lower distance to the middle
                    .append(other.distanceFromMiddle, distanceFromMiddle) // Decreasing
                    // Tie breaker
                    .append(queen.getColumnIndex(), other.queen.getColumnIndex())
                    .toComparison();
        }

    }

}
Copy to Clipboard Toggle word wrap

また、Comparator を設定する必要があります (ドメインモデルにアノテートされており、最適化アルゴリズムによって自動的に適用される場合は除きます)。 

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterWeightFactoryClass>...QueenDifficultyWeightFactory</sorterWeightFactoryClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>
Copy to Clipboard Toggle word wrap

sorterOrder 要素は任意です。デフォルト値は ASCENDING になります。

7.6.5.4. SelectionSorter でソートした選択
リンクのコピー

または、SelectionSorter インターフェースを直接使用することもできます。 

public interface SelectionSorter<T> {

    void sort(ScoreDirector scoreDirector, List<T> selectionList);

}
Copy to Clipboard Toggle word wrap 
    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterClass>...MyEntitySorter</sorterClass>
    </entitySelector>
Copy to Clipboard Toggle word wrap

7.6.6. 確率的な選択
リンクのコピー

確率的な選択 は、セレクターツリーのどの セレクター でも発生します。これには、MoveSelector、EntitySelector、または ValueSelector が含まれます。これは、cacheType JUST_IN_TIME では使用できず、selectionOrder PROBABILISTIC で使用できます。

probabilisticSelection
View larger image
probabilisticSelection

各選択には probabilityWeight があります。これは、選択が行われる可能性を決定します。 

public interface SelectionProbabilityWeightFactory<T> {

    double createProbabilityWeight(ScoreDirector scoreDirector, T selection);

}
Copy to Clipboard Toggle word wrap 
    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>PROBABILISTIC</selectionOrder>
      <probabilityWeightFactoryClass>...MyEntityProbabilityWeightFactoryClass</probabilityWeightFactoryClass>
    </entitySelector>
Copy to Clipboard Toggle word wrap

たとえば、プロセス A (probabilityWeight 2.0)、プロセス B (probabilityWeight 0.5)、プロセス C (probabilityWeight 0.5) の 3 つのエンティティーがある場合、プロセス A が選択される回数は、B および C の 4 倍となります。

7.6.7. 制限された選択
リンクのコピー

特に (acceptedCountLimit に対応しない) 構築ヒューリスティックの場合は、可能な Move をすべて選択しても十分にスケーリングするわけではありません。

各ステップで行う選択の数を制限するには、セレクターに selectedCountLimit を適用します。 

    <changeMoveSelector>
      <selectedCountLimit>100</selectedCountLimit>
    </changeMoveSelector>
Copy to Clipboard Toggle word wrap
注記

局所探索法を増減するには、通常は、selectedCountLimit よりも acceptedCountLimit を設定することが推奨されます。

7.6.8. 模倣選択 (記録/再現)
リンクのコピー

模倣選択時に、1 つの通常のセレクターは、その選択を記録し、他の特別セレクター 1 つまたは複数が、その選択を再現します。記録するセレクターは通常のセレクターとして動作し、その他の設定プロパティーすべてに対応します。再現するセレクターは、記録する選択を模倣し、その他の設定プロパティーはサポートしません。

記録するセレクターには ID が必要です。再現するセレクターは、mimicSelectorRef で、記録したセレクターの ID を参照する必要があります。 

      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector id="entitySelector"/>
          <valueSelector>
            <variableName>period</variableName>
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="entitySelector"/>
          <valueSelector>
            <variableName>room</variableName>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>
Copy to Clipboard Toggle word wrap

模倣選択は、同じエンティティーに影響する 2 つの Move から 複合 Move を作成するのに便利です。

7.6.9. 近傍選択
リンクのコピー

ユースケースの中には (TSP や VRP など、そして連鎖がない変数を使用している場合)、エンティティーを近傍値に変更するか、近傍エンティティーを交換すると、スケーラビリティーと、ソリューションの品質が大幅に向上します。

nearbySelectionMotivation
View larger image
nearbySelectionMotivation

近傍選択は、最初に移動したエンティティーに近いエンティティーまたは値を選択する可能性が上がります。

nearbySelectionRandomDistribution
View larger image
nearbySelectionRandomDistribution

2 つのエンティティーまたは値の間の距離はドメインによって異なります。したがって、NearbyDistanceMeter インターフェースを実装します。 

public interface NearbyDistanceMeter<O, D> {

    double getNearbyDistance(O origin, D destination);

}
Copy to Clipboard Toggle word wrap

これは、距離を示す double を返します。 

public class CustomerNearbyDistanceMeter implements NearbyDistanceMeter<Customer, Standstill> {

    public double getNearbyDistance(Customer origin, Standstill destination) {
        return origin.getDistanceTo(destination);
    }

}
Copy to Clipboard Toggle word wrap

近傍選択を設定するには、entitySelector または valueSelector に nearbySelection 要素を追加し、模倣選択 を使用して、選択から、どのエンティティーが近いかを指定します。 

    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector id="entitySelector1"/>
        <valueSelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector1"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </valueSelector>
      </changeMoveSelector>
      <swapMoveSelector>
        <entitySelector id="entitySelector2"/>
        <secondaryEntitySelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector2"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </secondaryEntitySelector>
      </swapMoveSelector>
      <tailChainSwapMoveSelector>
        <entitySelector id="entitySelector3"/>
        <valueSelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector3"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </valueSelector>
      </tailChainSwapMoveSelector>
    </unionMoveSelector>
Copy to Clipboard Toggle word wrap

distributionSizeMaximum パラメーターは 1 にすべきではありません。理由は、最も近い値がすでに、現在のエンティティーの計画値である場合に、唯一選択できる Move は実行できないからです。

すべての要素を選択するには、エンティティーの数にかかわらず、ディストリビューションの種類だけを選択します (したがって distributionSizeMaximum パラメーターはありません)。 

  <nearbySelection>
    <nearbySelectionDistributionType>PARABOLIC_DISTRIBUTION</nearbySelectionDistributionType>
  </nearbySelection>
Copy to Clipboard Toggle word wrap

次の NearbySelectionDistributionTypes に対応します。

  • BLOCK_DISTRIBUTION: 可能性が同じ中で最も近い n だけが選択されます。たとえば、最も近い 20 を選択します。 

      <nearbySelection>
    <blockDistributionSizeMaximum>20</blockDistributionSizeMaximum>
  </nearbySelection>
    Copy to Clipboard Toggle word wrap

  • LINEAR_DISTRIBUTION: 最も近い要素の中で可能性が高いものを選択します。可能性は線形的に減ります。 

      <nearbySelection>
    <linearDistributionSizeMaximum>40</linearDistributionSizeMaximum>
  </nearbySelection>
    Copy to Clipboard Toggle word wrap

  • PARABOLIC_DISTRIBUTION (推奨): 最も近い要素の中で、可能性の高いものを選択します。 

      <nearbySelection>
    <parabolicDistributionSizeMaximum>80</parabolicDistributionSizeMaximum>
  </nearbySelection>
    Copy to Clipboard Toggle word wrap

  • BETA_DISTRIBUTION: ベータディストリビューション に従って選択します。Solver の速度は著しく遅くなります。 

      <nearbySelection>
    <betaDistributionAlpha>1</betaDistributionAlpha>
    <betaDistributionBeta>5</betaDistributionBeta>
  </nearbySelection>
    Copy to Clipboard Toggle word wrap

必要であれば、いつでも ベンチマーカー を使用して値を調整します。

7.7. カスタムの Move
リンクのコピー

7.7.1. 実装に必要な Move のタイプ
リンクのコピー

お使いの実装に不足している Move のタイプを判断するには、ベンチマーカー を 短期間 実装し、ディスクに最適解を書き込むように設定 します。この最適解を見てください。おそらく局所最適条件になるでしょう。局所最適条件からより早く抜け出せる Move があるかどうか探してみてください。

見つけたら、粒度の粗い Move を実装し、既存の Move と混ぜて、以前の設定に対してベンチマークを設定して評価し、維持するかどうかを確認します。

7.7.2. カスタム Move の導入
リンクのコピー

一般の Move (ChangeMove など) を再利用する代わりに、カスタムの Move を実装できます。汎用およびカスタムの MoveSelectors は、自由に組み合わせることができます。

カスタムの Move は、制約を使用して調整できます。たとえば、試験の時間割で、試験 A の時間帯を変更すると、試験 A と同時に行われるすべての試験の時間帯が変更になります。

カスタム Move は一般の Move よりもわずかに速くなります。ただし、実装に必要な作業ははるかに多く、バグを回避するのもはるかに難しくなります。カスタムの Move を実装したら、environmentMode FULL_ASSERT を有効にして、スコアが壊れていないか確認します。

7.7.3. Move インターフェース
リンクのコピー

カスタムの Move には、Move インターフェースが実装されている必要があります。 

public interface Move {

    boolean isMoveDoable(ScoreDirector scoreDirector);

    Move createUndoMove(ScoreDirector scoreDirector);
    void doMove(ScoreDirector scoreDirector);

    Collection<? extends Object> getPlanningEntities();
    Collection<? extends Object> getPlanningValues();

}
Copy to Clipboard Toggle word wrap

クイーン 4 個の Move 実装を見てみましょう。クイーンを別の行に移動します。 

public class RowChangeMove extends AbstractMove {

    private Queen queen;
    private Row toRow;

    public RowChangeMove(Queen queen, Row toRow) {
        this.queen = queen;
        this.toRow = toRow;
    }

    // ... see below

}
Copy to Clipboard Toggle word wrap

RowChangeMove のインスタンスは、クイーンを、現在の行から別の行に移動します。

Planner は、doMove(ScoreDirector) メソッドを呼び出して Move を行い、それが doMoveOnGenuineVariables(ScoreDirector) を呼び出します。Move 実装は、ScoreDirector に、プランニングエンティティーの変数に行った変更を通知する必要があります。 

    public void doMoveOnGenuineVariables(ScoreDirector scoreDirector) {
        scoreDirector.beforeVariableChanged(queen, "row"); // before changes are made to the queen.row
        queen.setRow(toRow);
        scoreDirector.afterVariableChanged(queen, "row"); // after changes are made to the queen.row
    }
Copy to Clipboard Toggle word wrap

エンティティーの修正前後に、scoreDirector.beforeVariableChanged(Object, String) メソッドと scoreDirector.afterVariableChanged(Object, String) メソッドをそれぞれ直接呼び出す必要があります。

注記

1 つの Move で複数のエンティティーを変更して、大きな Move (粒度の粗い Move とも呼ばれています) を効果的に作成できます。

警告

Move は、プランニングエンティティーの変更、追加、または削除だけが可能です。問題ファクトを変更することはできません。

Planner は、Move で isMoveDoable(ScoreDirector) メソッドを呼び出し、実行できない Move にフィルターを自動的に設定して排除することができます。実行できない Move は、以下のようになります。

  • 現在のソリューションで何も変更しない Move。たとえば、B0 のクイーンはすでに行 0 にいるため、行 0 に移動することはできません。
  • 現在のソリューションで実行できない Move。たとえば、B0 のクイーンを行 10 に移動すると境界を越えてしまうため、行 10 に移動することはできません。

N クィーンの例では、現在の行と同じ行にクイーンを動かすことはできません。 

    public boolean isMoveDoable(ScoreDirector scoreDirector) {
        return !ObjectUtils.equals(queen.getRow(), toRow);
    }
Copy to Clipboard Toggle word wrap

境界の外にクイーンを動かす Move は生成しないため、それを確認する必要はありません。現在実行できない Move は、後のステップで使用している ソリューション を実行可能にできます。

それぞれの Move には 取り消しの Move があります。正反対のことを行う (通常は同じタイプの) Move です。上の例では、C0 から C2 の Move に対する取り消しの Move は C2 から C0 です。取り消しの Move は、現在のソリューションで Move が行われる前に、Move から作成されます。 

    public Move createUndoMove(ScoreDirector scoreDirector) {
        return new RowChangeMove(queen, queen.getRow());
    }
Copy to Clipboard Toggle word wrap

C0 がすでに C2 に移動してしまったら、取り消しの Move は、C2 から C0 ではなく、C2 から C2 への移動が作成されます。

Solver フェーズは、同じ Move の実行とその取り消しを複数回行う可能性があります。つまり、Solver フェーズの多くは、Move を評価するために何度も Move の実行と取り消しを行ってから、そのうちの 1 つを選択して Move を行います (この時は取り消しは行われません)。

Move には、getPlanningEntities() メソッドおよび getPlanningValues() メソッドが実装されている必要があります。このメソッドは、エンティティーのタブーと値のタブーにそれぞれ使用されます。Move が行われると、このメソッドが呼び出されます。 

    public List<? extends Object> getPlanningEntities() {
        return Collections.singletonList(queen);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Collections.singletonList(toRow);
    }
Copy to Clipboard Toggle word wrap

Move が複数のプランニングエンティティーを変更した場合は、getPlanningEntities() でそのすべてを返し、getPlanningValues() で、そのすべての値を (変更しているものに) 返します。 

    public Collection<? extends Object> getPlanningEntities() {
        return Arrays.asList(leftCloudProcess, rightCloudProcess);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Arrays.asList(leftCloudProcess.getComputer(), rightCloudProcess.getComputer());
    }
Copy to Clipboard Toggle word wrap

Move は、equals() メソッドと hashCode() メソッドを実装する必要があります。ソリューションで同じ変更を作成する 2 つの Move は同等である必要があります。 

    public boolean equals(Object o) {
        if (this == o) {
            return true;
        } else if (o instanceof RowChangeMove) {
            RowChangeMove other = (RowChangeMove) o;
            return new EqualsBuilder()
                    .append(queen, other.queen)
                    .append(toRow, other.toRow)
                    .isEquals();
        } else {
            return false;
        }
    }

    public int hashCode() {
        return new HashCodeBuilder()
                .append(queen)
                .append(toRow)
                .toHashCode();
    }
Copy to Clipboard Toggle word wrap

これは、別の Move が、同じ Move タイプのインスタンスかどうかを確認していることに注意してください。この instanceof チェックは、1 つ以上の Move タイプを使用している場合に、Move を別の Move タイプと比較するため、重要になります。

toString() メソッドを実装して、Planner のログが簡単に読めるようにします。 

    public String toString() {
        return queen + " {" + queen.getRow() + " -> " + toRow + "}";
    }
Copy to Clipboard Toggle word wrap

カスタムの Move を 1 つだけ実装できます。このようなカスタムの Move を生成してみましょう。

7.7.4. MoveListFactory: カスタム Move を簡単に生成する方法
リンクのコピー

カスタム Move を生成する一番簡単な方法は、MoveListFactory インターフェースを実装することです。 

public interface MoveListFactory<S extends Solution> {

    List<Move> createMoveList(S solution);

}
Copy to Clipboard Toggle word wrap

例: 

public class RowChangeMoveFactory implements MoveListFactory<NQueens> {

    public List<Move> createMoveList(NQueens nQueens) {
        List<Move> moveList = new ArrayList<Move>();
        for (Queen queen : nQueens.getQueenList()) {
            for (Row toRow : nQueens.getRowList()) {
                moveList.add(new RowChangeMove(queen, toRow));
            }
        }
        return moveList;
    }

}
Copy to Clipboard Toggle word wrap

簡単な設定方法 (その他の MoveSelector と同様、unionMoveSelector にネストできます): 

    <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <moveListFactory>
      ... <!-- Normal moveSelector properties -->
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>
Copy to Clipboard Toggle word wrap

MoveListFactory は、List<Move> ですべての Move を一度に生成するため、cacheType の JUST_IN_TIME には対応しません。したがって、moveListFactory は cacheType STEP をデフォルトで使用するため、メモリーフットプリントが著しく増えます。

7.7.5. MoveIteratorFactory: カスタム Move の Just in Time を生成
リンクのコピー

この高度な構造を使用して、MoveIteratorFactory インターフェースを実装して、カスタム Move を生成します。 

public interface MoveIteratorFactory {

    long getSize(ScoreDirector scoreDirector);

    Iterator<Move> createOriginalMoveIterator(ScoreDirector scoreDirector);

    Iterator<Move> createRandomMoveIterator(ScoreDirector scoreDirector, Random workingRandom);

}
Copy to Clipboard Toggle word wrap

getSize() メソッドは、サイズの概算を取得します。正確である必要はありません。selectionOrder が ORIGINAL の場合、もしくはキャッシュされる場合は、createOriginalMoveIterator メソッドが呼び出されます。selectionOrder RANDOM が cacheType JUST_IN_TIME とともに使用されている場合は、createRandomMoveIterator メソッドが呼び出されます。

重要

Iterator<Move> の作成時には、Move コレクション (リスト、アレイ、マップ、セット) は作成されません。MoveListFactory における MoveIteratorFactory の一番の目的は、Iterator の next() メソッドの Move ジャストインタイムを作成できるようにすることです。

簡単な設定方法 (その他の MoveSelector と同様、unionMoveSelector にネストできます): 

    <moveIteratorFactory>
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>
Copy to Clipboard Toggle word wrap

高度な設定方法: 

    <moveIteratorFactory>
      ... <!-- Normal moveSelector properties -->
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>
Copy to Clipboard Toggle word wrap
トップに戻る
Red Hat logoGithubredditYoutubeTwitter

詳細情報

試用、購入および販売

コミュニティー

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

Red Hat をお使いのお客様が、信頼できるコンテンツが含まれている製品やサービスを活用することで、イノベーションを行い、目標を達成できるようにします。 最新の更新を見る.

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

Red Hat では、コード、ドキュメント、Web プロパティーにおける配慮に欠ける用語の置き換えに取り組んでいます。このような変更は、段階的に実施される予定です。詳細情報: Red Hat ブログ.

会社概要

Red Hat は、企業がコアとなるデータセンターからネットワークエッジに至るまで、各種プラットフォームや環境全体で作業を簡素化できるように、強化されたソリューションを提供しています。

Theme

© 2025 Red Hat