OptaPlanner邻域搜索

评论

1.MoveSelector

MoveSelector主要的功能是指导从一个状态，如何获取到其邻域状态，以便优化算法遍历这些邻域状态，一次获取邻域状态的过程被称为一次Move

为了创建一个Move，一个MoveSelector需要选择一个或者多个Planning Entity或者Planning Value来Move，我们把辅助我们选择Planning Entity和Planning Value的东西分别叫做EntitySelector和ValueSelector

一个MoveSelector通常由EntitySelector和ValueSelector，以及其他的MoveSelector组合起来，例如：

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

他们构成了一个Selector Tree，这个树的根会被注入到优化算法的实现中，在每一次迭代中被调用

2.基础MoveSelector

changeMoveSelector

ChangeMove选择一个Planning Entity的一个Planning Variable，改变该Planning Variable为一个新值

e <- Select a Planning Entity
v <- Select a Planning Variable of e
e.v <- new value in range(v)

swapMoveSelector

SwapMove选择两个不同的Planning Entity，交换它们所有的Planning Variable

e1 <- Select a Planning Entity
e2 <- Select a Planning Entity
swap(e1, e2)

有时可能并不希望交换两个Planning Entity的所有Planning Variable，可以进行如下配置：

<swapMoveSelector>
    ...
    <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
    </entitySelector>
    <secondaryEntitySelector>
        <entityClass>...Lecture</entityClass>
        ...
        <nearBySelection>...</nearBySelection>
    </secondaryEntitySelector>
    <variableNameINcludes>
        <variableNameInclude>room</variableNameInclude>
        <variableNameInclude>...</variableNameInclude>
    </variableNameINcludes>
</swapMoveSelector>

secondaryEntitySelector并不一定需要，如果它没有被配置，那么两个被选中的Planning Entity都由entitySelector指定

如果一个或多个variableNameInclude被配置了，那么就不是所有的Planning Variable都会被交换，而仅仅是被variableNameInclude选中的属性会被交换

Pillar-Based MoveSelector

一个pillar是一个Planning Entity的集合，这个集合中的每个Planning Entity的Planning Variable(s)有相同的Planning Value(s)

pillarChangeMoveSelector

选择一个Entity Pillar（or subset of those），并改变其中一个Planning Variable的值

p <- Select an Entity Pillar
v <- Select a Planning Variable (in pillar)
t <- new value in range(v)
for e in p:
    e.v <- t

一个高级配置：

<pillarChangeMoveSelector>
    <subPillarType>SEQUENCE</subPillarType>
    <subPillarSequenceComparatorClass>
        ...
    </subPillarSequenceComparatorClass>
    <pillarSelector>
        <entitySelector>
            <entityClass>...ShiftAssignment</entityClass>
            ...
        </entitySelector>
        <minimumSubPillarSize>1</minimumSubPillarSize>
        <maximumSubPillarSize>1000</maximumSubPillarSize>
    </pillarSelector>
    <valueSelector variableName="room">
        ...
    </valueSelector>
</pillarChangeMoveSelector>

pillarSwapMoveSelector

MoveSelectors for List Variables

listChangeMoveSelector

一个listChangeMoveSelector从Planning List Variable的值范围中选择一个元素，并把这个元素从当前位置移动到一个新的位置上

<listChangeMoveSelector>
    ...
    <valueSelector id="valueSelector1">
        ...
    </valueSelector>
    <destinationSelector>
    <entitySelector>
        ...
    </entitySelector>
    <valueSelector>
        ...
    </valueSelector>
    <nearbySelection>
        <originValueSelector mimicSelectorRef="valueSelector1"/>
        ...
    </nearbySelection>
    </destinationSelector>
</listChangeMoveSelector>

listSwapMoveSelector

一个listSwapMoveSelector从Planning List Variable的值范围中选择两个元素，交换它们的位置

<listSwapMoveSelector>
    ...
    <valueSelector id="valueSelector1">
        ...
    </valueSelector>
    <secondaryValueSelector>
        <nearbySelection>
            <originValueSelector mimicSelectorRef="valueSelector1"/>
            ...
        </nearbySelection>
    </secondaryValueSelector>
</listSwapMoveSelector>

subListChangeMoveSelector

subListSwapMoveSelector

kOptListMoveSelector

把一个Planning List Variable当作一个图来考虑，图上的边就是Planning List Variable中连续的元素（最后一个元素和第一个元素连续）

一个kOptListMove选择一个Planning Entity，从它的Planning List Variable中删除k条边，然后加入k条新边到被删除的边的端点上

koptMove

高级配置：

<kOptListMoveSelector>
    ...
    <minimumK>2</minimumK>
    <maximumK>4</maximumK>
</kOptListMoveSelector>

MoveSelectors for Chained Variables

tailChainSwapMoveSelector

一个tailChain是一组具有Chained Planning Variable的Planning Entity，这些Planning Entity构成了某个长链的某一后缀

tailChainSwapMoveSelector选择一个tailChain，然后把它和另外一个Planning Value的tailChain进行交换（在同一条或者不同的长链中）。如果Targeted Planning Value没有tailChain，则它将与空进行交换（导致类似移动的变化），如果发生在同一个长链中，则会发生部分倒链（又叫2-opt swap）

subChainChangeMoveSelector

一个subChain是长链的一个子链，subChainChangeMoveSelector挑选一个subChain，然后把它放到别的位置上去（既可以放在别的长链上，又可以放在当前这个长链上的其他地方）

3.组合MoveSelector

unionMoveSelector

一个unionMoveSelector通过挑选其某一个儿子当作产生Move的MoveSelector

<unionMoveSelctor>
    <...MoveSelector/>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
</unionMoveSelctor>

cartesianProductMoveSelector

cartesianProductMoveSelector把每个儿子产生的Move连缀起来，构成一个新的Move

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

4.EntitySelector

<entitySelector>
    ...
    <entityClass>org.optaplanner.examples.curriculumcourse.domain.Lecture</entityClass>
</entitySelector>

如果存在很多Entity Class，无法自动推断出我要选择哪种Planning Entity的时候，才需要配置entityClass

5.ValueSelector

<valueSelector variableName="room">
    ...
</valueSelector>

对于一个Planning Entity，如果存在很多Planning Variables，无法自动推断出要使用哪一个Planning Variable的时候，才需要配置variableName

6.SelectorFeatures

cacheType

一个Selector的cacheType决定了一个selection（比如一个Move，一个Planning Entity，一个Planning Value）在什么时候被创建，以及这个selection的生命周期

基本上每个Selector都支持cacheType的设置

  • JUST_IN_TIME：默认值，在即将用到某个selection之前进行构建
  • STEP：cached，创建一个selection在一次step的开头，然后把该selection保存下来，会有额外内存开销
  • PHASE：cached，创建一个selection在一个solver phase的开头，然后把该selection保存下来，会有额外内存开销，但是有一些性能优化
  • SLVER：cached，创建一个selection在solver的开头，然后把该selection保存下来，会有额外内存开销，但是有一些性能优化

selectionOrder

whoseJam