<commit_before>[[moveAndNeighborhoodSelection]]
= Move and Neighborhood Selection
:doctype: book
:imagesdir: ..
:sectnums:
:toc: left
:icons: font
:experimental:


[[moveAndNeighborhoodSelectionIntroduction]]
== Move and Neighborhood Introduction


[[whatIsAMove]]
=== What is a ``Move``?

A `Move` is a change (or set of changes) from a solution A to a solution B.
For example, the move below changes queen `C` from row `0` to row ``2``:

image::MoveAndNeighborhoodSelection/singleMoveNQueens04.png[align="center"]

The new solution is called a _neighbor_ of the original solution, because it can be reached in a single ``Move``.
Although a single move can change multiple queens, the neighbors of a solution should always be a very small subset of all possible solutions.
For example, on that original solution, these are all possible ``changeMove``'s:

image::MoveAndNeighborhoodSelection/possibleMovesNQueens04.png[align="center"]

If we ignore the four ``changeMove``'s that have no impact and are therefore not doable, we can see that number of moves is ``n * (n - 1) = 12``.
This is far less than the number of possible solutions, which is ``n ^ n = 256``.
As the problem scales out, the number of possible moves increases far less than the number of possible solutions.

Yet, in four ``changeMove``'s or less we can reach any solution.
For example we can reach a very different solution in three ``changeMove``'s:

image::MoveAndNeighborhoodSelection/sequentialMovesNQueens04.png[align="center"]


[NOTE]
====
There are many other types of moves besides ``changeMove``'s.
Many move types are included out-of-the-box, but you can also implement custom moves.

A `Move` can affect multiple entities or even create/delete entities.
But it must not change the problem facts.
====

All optimization algorithms use ``Move``'s to transition from one solution to a neighbor solution.
Therefore, all the optimization algorithms are confronted with `Move` selection: the craft of creating and iterating moves efficiently and the art of finding the most promising subset of random moves to evaluate first.


[[whatIsAMoveSelector]]
=== What is a ``MoveSelector``?

A ``MoveSelector``'s main function is to create `Iterator<Move>` when needed.
An optimization algorithm will iterate through a subset of those moves.

Here's an example how to configure a `changeMoveSelector` for the optimization algorithm Local Search:

[source,xml,options="nowrap"]
----
  <localSearch>
    <changeMoveSelector/>
    ...
  </localSearch>
----

Out of the box, this works and all properties of the `changeMoveSelector` are defaulted sensibly (unless that fails fast due to ambiguity). On the other hand, the configuration can be customized significantly for specific use cases.
For example: you might want to configure a <<filteredSelection,filter>> to discard pointless moves.


[[subselectingOfEntitiesValuesAndOtherMoves]]
=== Subselecting of Entities, Values and Other Moves

To create a ``Move``, a `MoveSelector` needs to select one or more planning entities and/or planning values to move.
Just like ``MoveSelector``s, ``EntitySelector``s and ``ValueSelector``s need to support a similar feature set (such as scalable just-in-time selection). Therefore, they all implement a common interface `Selector` and they are configured similarly.

A MoveSelector is often composed out of ``EntitySelector``s, ``ValueSelector``s or even other ``MoveSelector``s, which can be configured individually if desired:

[source,xml,options="nowrap"]
----
    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
          ...
        </entitySelector>
        <valueSelector>
          ...
        </valueSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
    </unionMoveSelector>
----

Together, this structure forms a `Selector` tree:

image::MoveAndNeighborhoodSelection/selectorTree.png[align="center"]

The root of this tree is a `MoveSelector` which is injected into the optimization algorithm implementation to be (partially) iterated in every step.


[[genericMoveSelectors]]
== Generic MoveSelectors


[[genericMoveSelectorsOverview]]
=== Generic MoveSelectors Overview

[cols="1,2a,2a"]
|===
|Name |Description |`toString()` example

|<<changeMoveSelector,Change move>>
|Change 1 entity's variable
|`Process-A {Computer-1 -> Computer-2}`

|<<swapMoveSelector,Swap move>>
|Swap all variables of 2 entities
|`Process-A {Computer-1} <-> Process-B {Computer-2}`

|<<pillarChangeMoveSelector,Pillar change move>>
|Change a set of entities with the same value
|`[Process-A, Process-B, Process-C] {Computer-1 -> Computer-2}`

|<<pillarSwapMoveSelector,Pillar swap move>>
|Swap 2 sets of entities with the same values
|`[Process-A, Process-B, Process-C] {Computer-1} <-> [Process-E, Process-F] {Computer-2}`

|<<tailChainSwapMoveSelector,Tail chain swap move>>
|Swap 2 tails chains
|`Visit-A5 {Visit-A4} <-tailChainSwap-> Visit-B3 {Visit-B2}`

|<<subChainChangeMoveSelector,Sub chain change move>>
|Cut a subchain and paste it into another chain
|`[Visit-A5..Visit-A8] {Visit-A4 -> Visit-B2}`

|<<subChainSwapMoveSelector,Sub chain swap move>>
|Swap 2 subchains
|`[Visit-A5..Visit-A8] {Visit-A4} <-> [Visit-B3..Visit-B9] {Visit-B2}`

|===


[[changeMoveSelector]]
=== ChangeMoveSelector

For one planning variable, the `ChangeMove` selects one planning entity and one planning value and assigns the entity's variable to that value.
<commit_msg>Disable substitutions<commit_after>[[moveAndNeighborhoodSelection]]
= Move and Neighborhood Selection
:doctype: book
:imagesdir: ..
:sectnums:
:toc: left
:icons: font
:experimental:


[[moveAndNeighborhoodSelectionIntroduction]]
== Move and Neighborhood Introduction


[[whatIsAMove]]
=== What is a ``Move``?

A `Move` is a change (or set of changes) from a solution A to a solution B.
For example, the move below changes queen `C` from row `0` to row ``2``:

image::MoveAndNeighborhoodSelection/singleMoveNQueens04.png[align="center"]

The new solution is called a _neighbor_ of the original solution, because it can be reached in a single ``Move``.
Although a single move can change multiple queens, the neighbors of a solution should always be a very small subset of all possible solutions.
For example, on that original solution, these are all possible ``changeMove``'s:

image::MoveAndNeighborhoodSelection/possibleMovesNQueens04.png[align="center"]

If we ignore the four ``changeMove``'s that have no impact and are therefore not doable, we can see that number of moves is ``n * (n - 1) = 12``.
This is far less than the number of possible solutions, which is ``n ^ n = 256``.
As the problem scales out, the number of possible moves increases far less than the number of possible solutions.

Yet, in four ``changeMove``'s or less we can reach any solution.
For example we can reach a very different solution in three ``changeMove``'s:

image::MoveAndNeighborhoodSelection/sequentialMovesNQueens04.png[align="center"]


[NOTE]
====
There are many other types of moves besides ``changeMove``'s.
Many move types are included out-of-the-box, but you can also implement custom moves.

A `Move` can affect multiple entities or even create/delete entities.
But it must not change the problem facts.
====

All optimization algorithms use ``Move``'s to transition from one solution to a neighbor solution.
Therefore, all the optimization algorithms are confronted with `Move` selection: the craft of creating and iterating moves efficiently and the art of finding the most promising subset of random moves to evaluate first.


[[whatIsAMoveSelector]]
=== What is a ``MoveSelector``?

A ``MoveSelector``'s main function is to create `Iterator<Move>` when needed.
An optimization algorithm will iterate through a subset of those moves.

Here's an example how to configure a `changeMoveSelector` for the optimization algorithm Local Search:

[source,xml,options="nowrap"]
----
  <localSearch>
    <changeMoveSelector/>
    ...
  </localSearch>
----

Out of the box, this works and all properties of the `changeMoveSelector` are defaulted sensibly (unless that fails fast due to ambiguity). On the other hand, the configuration can be customized significantly for specific use cases.
For example: you might want to configure a <<filteredSelection,filter>> to discard pointless moves.


[[subselectingOfEntitiesValuesAndOtherMoves]]
=== Subselecting of Entities, Values and Other Moves

To create a ``Move``, a `MoveSelector` needs to select one or more planning entities and/or planning values to move.
Just like ``MoveSelector``s, ``EntitySelector``s and ``ValueSelector``s need to support a similar feature set (such as scalable just-in-time selection). Therefore, they all implement a common interface `Selector` and they are configured similarly.

A MoveSelector is often composed out of ``EntitySelector``s, ``ValueSelector``s or even other ``MoveSelector``s, which can be configured individually if desired:

[source,xml,options="nowrap"]
----
    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
          ...
        </entitySelector>
        <valueSelector>
          ...
        </valueSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
    </unionMoveSelector>
----

Together, this structure forms a `Selector` tree:

image::MoveAndNeighborhoodSelection/selectorTree.png[align="center"]

The root of this tree is a `MoveSelector` which is injected into the optimization algorithm implementation to be (partially) iterated in every step.


[[genericMoveSelectors]]
== Generic MoveSelectors


[[genericMoveSelectorsOverview]]
=== Generic MoveSelectors Overview

[cols="1,2a,2a"]
|===
|Name |Description |`toString()` example

|<<changeMoveSelector,Change move>>
|Change 1 entity's variable
|`+Process-A {Computer-1 -> Computer-2}+`

|<<swapMoveSelector,Swap move>>
|Swap all variables of 2 entities
|`+Process-A {Computer-1} <-> Process-B {Computer-2}+`

|<<pillarChangeMoveSelector,Pillar change move>>
|Change a set of entities with the same value
|`+[Process-A, Process-B, Process-C] {Computer-1 -> Computer-2}+`

|<<pillarSwapMoveSelector,Pillar swap move>>
|Swap 2 sets of entities with the same values
|`+[Process-A, Process-B, Process-C] {Computer-1} <-> [Process-E, Process-F] {Computer-2}+`

|<<tailChainSwapMoveSelector,Tail chain swap move>>
|Swap 2 tails chains
|`+Visit-A5 {Visit-A4} <-tailChainSwap-> Visit-B3 {Visit-B2}+`

|<<subChainChangeMoveSelector,Sub chain change move>>
|Cut a subchain and paste it into another chain
|`+[Visit-A5..Visit-A8] {Visit-A4 -> Visit-B2}+`

|<<subChainSwapMoveSelector,Sub chain swap move>>
|Swap 2 subchains
|`+[Visit-A5..Visit-A8] {Visit-A4} <-> [Visit-B3..Visit-B9] {Visit-B2}+`

|===


[[changeMoveSelector]]
=== ChangeMoveSelector

For one planning variable, the `ChangeMove` selects one planning entity and one planning value and assigns the entity's variable to that value.

{'fraction_non_alphanumeric': 0.10677319774832032, 'fraction_numerical': 0.00798983112402397, 'mean_word_length': 4.809599156118144, 'pattern_counts': {'":': 0, '<': 71, '<?xml version=': 0, '>': 77, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 4}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2775871', 'n_tokens_mistral': 3186, 'n_tokens_neox': 3028, 'n_words': 1263}