Coverage for moptipy / operators / permutations / op1_swapn.py: 42%
31 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2An operator swapping several elements in a permutation.
4This operator works similarly to
5:class:`~moptipy.operators.permutations.op1_swap2.Op1Swap2`, but instead of
6swapping two elements (i.e., performing 1 swap), it will perform a random
7number of swaps.
9First, the operator copies the source string `x` into the destination `dest`.
10It then chooses a random index `i1`. It remembers the element at that index
11in two variables, `last` and `first`. (`last` will always be the value of the
12element will next be overwritten and `first` will never change and remember
13the first overwritten element, i.e., the value that we need to store again
14into the array in the end.) We also initialize a variable `continue_after`
15with `True`. This variable will always tell us if we need to continue and
16draw another random index.
18We then begin with the main loop, which is iterated as long as
19`continue_after` is `True`. Directly as first action in this loop, we set
20`continue_after = ri(2) <= 0`. `ri(2)` will return a random integer in
21`{0, 1}`. `ri(2) <= 0` will therefore be `True` with probability 0.5.
23We now will draw a new random index `i2`. We load the element at index `i2`
24into variable `current`. If `current == last`, we immediately go back and
25draw another random `i2`. The reason is that we want to store `current` at
26`i1`, i.e., where `last` is currently stored. If `current == last`, this
27would change nothing. Furthermore, if `continue_after` is `False`, then
28`current` must also be different from `first`: If we exit the main loop,
29then we will store `first` into the place where we found `current`. Remember,
30we will overwrite the element at index `i1` with `current`, so the very first
31element we overwrite must eventually be stored back into the array.
33OK, if we have obtained an index `i2` whose corresponding element `current`
34fulfills all requirements, we can set `dest[i1] = last = current`, i.e.,
35remember `current` in `last` and also store it at index `i1`. Next, we will
36overwrite the element at index `i2`, so we set `i1 = i2`. If `continue_after`
37is `True`, the loop will continue. Otherwise, it will stop.
39In the latter case, we store `first` back into the array at the last index
40`i1` and do `dest[i1] = first`.
42As a result, the operator will swap exactly 2 elements with probability 0.5.
43With probability 0.25, it will swap three elements, with 0.125 probability, it
44will swap 4 elements, and so on.
461. Thomas Weise. *Optimization Algorithms.* 2021. Hefei, Anhui, China:
47 Institute of Applied Optimization (IAO), School of Artificial Intelligence
48 and Big Data, Hefei University. http://thomasweise.github.io/oa/
49"""
50from typing import Callable, Final
52import numba # type: ignore
53import numpy as np
54from numpy.random import Generator
56from moptipy.api.operators import Op1
59@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
60def swap_n(random: Generator, dest: np.ndarray, # +book
61 x: np.ndarray) -> None: # +book
62 """
63 Copy `x` into `dest` and then swap several different values.
65 :param random: the random number generator
66 :param dest: the array to receive the modified copy of `x`
67 :param x: the existing point in the search space
69 >>> rand = np.random.default_rng(10)
70 >>> xx = np.array(range(10), int)
71 >>> out = np.empty(len(xx), int)
72 >>> swap_n(rand, out, xx)
73 >>> print(out)
74 [0 1 7 3 4 5 6 2 8 9]
75 >>> swap_n(rand, out, xx)
76 >>> print(out)
77 [0 1 8 3 4 5 6 7 2 9]
78 >>> swap_n(rand, out, xx)
79 >>> print(out)
80 [0 5 2 3 4 8 6 7 1 9]
81 """
82 # start book
83 dest[:] = x[:] # First, we copy `x` to `dest`.
84 length: Final[int] = len(dest) # Get the length of `dest`.
85 rint: Callable[[int, int], int] = random.integers # fast call
87 i1 = rint(0, length) # Get the first random index.
88 last = first = dest[i1] # Get the value at the first index.
89 continue_after: bool = True # True -> loop at least once.
90 while continue_after: # Repeat until we should stop
91 continue_after = rint(0, 2) <= 0 # 50/50 chance
92 while True: # Loop forever until eligible element found.
93 i2 = rint(0, length) # new random index.
94 current = dest[i2] # Get the value at the new index.
95 if current == last: # If it is the same as the
96 continue # previous value, continue.
97 if continue_after or (current != first): # If we want
98 break # to stop, then it must be != first value.
99 dest[i1] = last = current # Store value for from i2 at i1.
100 i1 = i2 # Update i1 to now point to cell of i2.
101 dest[i1] = first # Finally, store first element back at end.
104class Op1SwapN(Op1):
105 """
106 A unary search operation that swaps several (different) elements.
108 It is similar to `swap2`, but instead may perform a random number
109 of swaps. After each swap, it decides with probability 0.5 whether
110 or not to perform another swap.
111 """
113 def __init__(self) -> None:
114 """Initialize the object."""
115 super().__init__() # -book
116 self.op1 = swap_n # type: ignore # use function directly
117 # end book
119 def __str__(self) -> str:
120 """
121 Get the name of this unary operator.
123 :returns: "swapn", the name of this operator
124 :retval "swapn": always
125 """
126 return "swapn"