第7章 Move と近傍選択

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

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

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

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

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

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

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

  <localSearch>
    <changeMoveSelector/>
    ...
  </localSearch>

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

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

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

    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
          ...
        </entitySelector>
        <valueSelector>
          ...
        </valueSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
    </unionMoveSelector>

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

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

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

最も簡単な設定方法:

    <changeMoveSelector/>

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

高度な設定方法:

    <changeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>room</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </changeMoveSelector>

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

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

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

最も簡単な設定方法:

    <swapMoveSelector/>

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

高度な設定方法:

    <swapMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <secondaryEntitySelector>
        <entityClass>...Lecture</entityClass>
        ...
        <nearbySelection>...</nearbySelection>
      </secondaryEntitySelector>
      <variableNameInclude>room</variableNameInclude>
      <variableNameInclude>...</variableNameInclude>
    </swapMoveSelector>

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

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

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

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

最も簡単な設定方法:

    <pillarChangeMoveSelector/>

高度な設定方法:

    <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>

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

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

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

最も簡単な設定方法:

    <pillarSwapMoveSelector/>

高度な設定方法:

    <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>

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

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

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

最も簡単な設定方法:

    <tailChainSwapMoveSelector/>

高度な設定方法:

    <subChainChangeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Customer</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>previousStandstill</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </subChainChangeMoveSelector>

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

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

最も簡単な設定方法:

    <subChainChangeMoveSelector/>

高度な設定方法:

    <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>

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

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

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

最も簡単な設定方法:

    <subChainSwapMoveSelector/>

高度な設定方法:

    <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>

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

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

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

最も簡単な設定方法:

    <unionMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </unionMoveSelector>

高度な設定方法:

    <unionMoveSelector>
      ... <!-- Normal selector properties -->
      <selectorProbabilityWeightFactoryClass>...ProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </...MoveSelector>
      ...
    </unionMoveSelector>

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

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

    <unionMoveSelector>
      <changeMoveSelector>
        <fixedProbabilityWeight>1.0</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>2.0</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
    </unionMoveSelector>

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

    <unionMoveSelector>
      <selectorProbabilityWeightFactoryClass>org.optaplanner.core.impl.heuristic.selector.common.decorator.FairSelectorProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>

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

最も簡単な設定方法:

    <cartesianProductMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </cartesianProductMoveSelector>

高度な設定方法:

    <cartesianProductMoveSelector>
      ... <!-- Normal selector properties -->
      <ignoreEmptyChildIterators>true</ignoreEmptyChildIterators>
      <changeMoveSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        ...
      </...MoveSelector>
      ...
    </cartesianProductMoveSelector>

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

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

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

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

    <changeMoveSelector>
      <cacheType>PHASE</cacheType>
      ...
    </changeMoveSelector>

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

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

    <unionMoveSelector>
      <cacheType>PHASE</cacheType>
      <changeMoveSelector/>
      <swapMoveSelector/>
      ...
    </unionMoveSelector>

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

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

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

    <changeMoveSelector>
      ...
      <selectionOrder>RANDOM</selectionOrder>
      ...
    </changeMoveSelector>

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

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

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

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

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

public interface SelectionFilter<T> {

    boolean accept(ScoreDirector scoreDirector, T selection);

}

不要な 選択 に対して 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());
    }

}

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

    <swapMoveSelector>
      <filterClass>org.optaplanner.examples.curriculumcourse.solver.move.DifferentCourseSwapMoveFilter</filterClass>
    </swapMoveSelector>

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

    <changeMoveSelector>
      <entitySelector>
        <filterClass>...EntityFilter</filterClass>
      </entitySelector>
    </changeMoveSelector>

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

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

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

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();
    }

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterComparatorClass>...CloudProcessDifficultyComparator</sorterComparatorClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>

public interface SelectionSorterWeightFactory<Sol extends Solution, T> {

    Comparable createSorterWeight(Sol solution, T selection);

}

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();
        }

    }

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterWeightFactoryClass>...QueenDifficultyWeightFactory</sorterWeightFactoryClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>

public interface SelectionSorter<T> {

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

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterClass>...MyEntitySorter</sorterClass>
    </entitySelector>

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

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

public interface SelectionProbabilityWeightFactory<T> {

    double createProbabilityWeight(ScoreDirector scoreDirector, T selection);

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>PROBABILISTIC</selectionOrder>
      <probabilityWeightFactoryClass>...MyEntityProbabilityWeightFactoryClass</probabilityWeightFactoryClass>
    </entitySelector>

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

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

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

    <changeMoveSelector>
      <selectedCountLimit>100</selectedCountLimit>
    </changeMoveSelector>

模倣選択時に、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>

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

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

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

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

public interface NearbyDistanceMeter<O, D> {

    double getNearbyDistance(O origin, D destination);

}

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

public class CustomerNearbyDistanceMeter implements NearbyDistanceMeter<Customer, Standstill> {

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

}

近傍選択を設定するには、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>

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

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

  <nearbySelection>
    <nearbySelectionDistributionType>PARABOLIC_DISTRIBUTION</nearbySelectionDistributionType>
  </nearbySelection>

次の NearbySelectionDistributionTypes に対応します。

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

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

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

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

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

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

カスタムの 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();

}

クイーン 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

}

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
    }

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

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

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

    public boolean isMoveDoable(ScoreDirector scoreDirector) {
        return !ObjectUtils.equals(queen.getRow(), toRow);
    }

境界の外にクイーンを動かす 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());
    }

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);
    }

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());
    }

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();
    }

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

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

    public String toString() {
        return queen + " {" + queen.getRow() + " -> " + toRow + "}";
    }

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

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

public interface MoveListFactory<S extends Solution> {

    List<Move> createMoveList(S solution);

}

例:

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;
    }

}

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

    <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

高度な設定方法:

    <moveListFactory>
      ... <!-- Normal moveSelector properties -->
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

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

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

public interface MoveIteratorFactory {

    long getSize(ScoreDirector scoreDirector);

    Iterator<Move> createOriginalMoveIterator(ScoreDirector scoreDirector);

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

}

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

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

    <moveIteratorFactory>
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>

高度な設定方法:

    <moveIteratorFactory>
      ... <!-- Normal moveSelector properties -->
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>