Hi guys,
In Planner, I am going to do some structural improvements on the
selectors.
Below are some of the idea's on how to do that. All of these are
ideas are still very volatile.
Feed-back is welcome, especially if you don't like a particular
naming or semantic.
Global design objectives:
- 1) Make selectors and generic
MoveFactories faster, scalable and use less memory: by optionally
not generating all the moves
- 2) Make selectors and generic
MoveFactories more configurable: filter on entities, variables,
moveFilter, ...
- 3) Unify entity, variable and value
selectors under the same system, to also make them faster,
scalable, memory-efficient and more configurable
Let's focus on 1) MoveSelector only for
now, on terminology and semantics.
What does a MoveSelector need to have?
Terminology of methods/attributes on
MoveSelector. How would you name them?
- Iterator<Move> moveIterator:
-
iterates over all the moves in the selector, based on the
configuration of the MoveSelector
- long moveSize or size:
- how
many moves in this MoveSelector.
- The
MoveSelector interface probably doesn't need to expose this
- boolean continuous:
- Some
value ranges, for example double x with (1.0 < x <
2.0) are continuous.
- For
example, a value can be 1.23435455444.
- When
true, then MoveSelector.size returns -1 or throws exception
(because it is infinity really :)
- Not
all features will be able to combine with continuous true.
- If
it's not compatible, it fails-fast during configuration.
- boolean cacheableBetweenSteps
- enum orderType:
- The
order in which the moveIterator generates Moves
- DEFAULT
(or FROM_SOLUTION?)
- not
cached
- The
Moves are generated in real-time (at each move scope)
- A1, A2, A3, ... A9, B1, B2, ... F9
- 100%
cached
- The
Moves are generated in advance (at each step scope) and
iterated in generated order.
- A1, A2, A3, ... A9, B1, B2, ... F9
- Not
compatible with continuous == true
- DECREASING_DIFFICULTY
(experimental)
- B1,
B2, … B9, F1, F2, … F9, A1, A2 …, C9
- This
is really DEFAULT for the MoveSelector with
DECREASING_DIFFICULTY for the entitySelector and
DEFAULT/DECREASING_STRENGTH/... for the valueSelector
- RANDOM_COMPLETE
- The
Moves are generated in advanced (at each step scope) and
shuffled, so iterated in random order.
- Not
compatible with continuous == true
- RANDOM_SCALABLE
- The
moves are generated in real-time (at each move scope)
randomly.
- Will
sometimes generate the same Move twice, before some other
Move is generated once.
- boolean hasFiniteMoveSize
- Other
names:
- hasFiniteAmountOfMoves
- knowsWhenAllMovesHaveBeenIterated
- true
if moveIterator.hasNext() will ever return false
- It's
false in the following cases:
- orderType
== RANDOM_SCALABLE
- boolean roundRobinSelection
- true
if it should try to round robin selection between steps
- If
orderType == IN_ORDER
- Suppose
the moves are (A1, A2, A3, A4, A5)
- if
the first step stops after 3 move selections, it gets [A1,
A2, A3]
- then
the next step will get [A4, A5, A1, A2, A3].
- so if
it stops after the 3 move selections, it gets [A4, A5,
A1]
- with roundRobinSelection == false it would
get [A1, A2, A3] again
- If
orderType == RANDOM_COMPLETE
- This
is a bit tricker - ignore for now
- Not
compatible with orderType == RANDOM_SCALABLE
- Not
compatible with continuous == true
- long randomSelectionWeight
- If
this MoveSelector is put into a composition with another
MoveSelector, how high is the chance that this MoveSelector
is chosen?
- See
below on composition for more info.
- Can
default to 1 or can default to size.
- Currently,
Planner 5.4 implementation default it to 1.
MoveSelector composition: Local Search
can only have 1 direct MoveSelector, but that one can be
CompositeMoveSelector of other MoveSelectors. There are several
forms of composition:
- Summed composition: UNION:
- If
X(A1, A2, A3) and Y(B1, B2) are summed, we get (A1, A2, A3,
B1, B2)
- If
this composition is called with RANDOM (complete or
scalable), how high is the change that A1 will be selected?
- if
randomSelectionWeight = 1 for each, so on X = 1 and Y = 1:
- (1/2)
* (1/3) = 1/6 chance to select A1
- if
randomSelectionWeight = size for each, so on X = 3 and Y =
2:
- 1/(3 +
2) = 1/5 chance to select A1
- Think
about it: currently randomSelectionWeight = 1,
- so if
you have 100 change moves and 1000 swap moves,
- then every change move has 10 times more chance to
be selected then a swap move
- Multiplied composition:
CARTESIAN_PRODUCT:
- If
X(A1, A2, A3) and Y(B1, B2) are multiplied, we get (A1-B1,
A1-B2, A2-B1, A2-B2, A3-B1, A3-B2)
- So
you get composite moves: even though X and Y only move 1
entity, the composite move moves 2 at the same time
- If
multiplied composition is useful is yet to be determined
- If
this composition is called with RANDOM (complete or
scalable), how high is the change that A1-B1 will be
selected?
- Always
(1/3) * (1/2) = 1/6 chance to select A1-B1
- The
randomSelectionWeight doesn't matter!
- if randomSelectionWeight = 1 , so on X = 1
and Y = 1:
- (1/3) * (1/2) = 1/6 chance to select A1-B1
- if randomSelectionWeight = size, so on X =
3 and Y = 2:
- (1/3) * (1/2) = 1/6 chance to select A1-B1
I hope this makes sense :) What do you
think? Naming, semantics, usage, ...
MoveFilters, entity
inclusion/exclusion, etc are for phase 2 (by much easier to do
once this stuff in in place)
--
With kind regards,
Geoffrey De Smet