Coverage for moptipy / operators / permutations / op1_swap_try_n.py: 43%

1""" 

2An operator trying to swap a given number of elements in a permutation. 

3 

4This operator is similar to 

5:mod:`~moptipy.operators.permutations.op1_swap_exactly_n` 

6in that it tries to swap a fixed number of elements in a permutation. It 

7implements the :class:`~moptipy.api.operators.Op1WithStepSize` interface. 

8Different from :mod:`~moptipy.operators.permutations.op1_swap_exactly_n`, 

9however, it does so less strictly. It applies a simple best-effort approach 

10and if that does not work out, then so be it. It is therefore faster, but 

11adheres less strictly to the give `step_size`. 

12 

13This operator will always swap the right number of elements on normal 

14permutations. On permutations with repetitions, it enforces the number of 

15swaps less strongly compared to 

16:mod:`~moptipy.operators.permutations.op1_swap_exactly_n`, but it will be 

17faster either way. 

18""" 

19from typing import Final 

20 

21import numba # type: ignore 

22import numpy as np 

23from numpy.random import Generator 

24from pycommons.types import type_error 

25 

26from moptipy.api.operators import Op1WithStepSize 

27from moptipy.operators.tools import exponential_step_size 

28from moptipy.spaces.permutations import Permutations 

29from moptipy.utils.nputils import DEFAULT_INT, fill_in_canonical_permutation 

30 

31 

32@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False) 

33def swap_try_n(random: Generator, dest: np.ndarray, x: np.ndarray, 

34 step_size: float, indices: np.ndarray) -> None: 

35 """ 

36 Copy `x` into `dest` and then swap several different values. 

37 

38 :param random: the random number generator 

39 :param dest: the array to receive the modified copy of `x` 

40 :param x: the existing point in the search space 

41 :param step_size: the number of elements to swap 

42 :param indices: the array with indices 

43 

44 >>> xx = np.array(range(10), int) 

45 >>> out = np.empty(len(xx), xx.dtype) 

46 >>> idxs = np.array(range(len(xx)), int) 

47 >>> gen = np.random.default_rng(10) 

48 >>> swap_try_n(gen, out, xx, 0.1, idxs) 

49 >>> print(out) 

50 [0 1 2 3 4 5 6 8 7 9] 

51 >>> swap_try_n(gen, out, xx, 0.1, idxs) 

52 >>> print(out) 

53 [0 2 1 3 4 5 6 7 8 9] 

54 >>> swap_try_n(gen, out, xx, 1.0, idxs) 

55 >>> print(out) 

56 [3 7 4 5 8 6 9 0 1 2] 

57 """ 

58 dest[:] = x[:] # First, we copy `x` to `dest`. 

59 remaining: int = len(dest) # Get the length of `dest`. 

60# Compute the real step size based on the length of the permutation. 

61 steps: int = exponential_step_size(step_size, 2, remaining) 

62 

63 ii = random.integers(0, remaining) # Select first random index. 

64 i1 = indices[ii] # Get the actual index. 

65 remaining -= 1 # There is one less remaining index. 

66 indices[remaining], indices[ii] = i1, indices[remaining] 

67 

68 last = first = dest[i1] # Get the value at the first index. 

69 continue_after: bool = True # True -> loop at least once. 

70 while continue_after: # Repeat until we should stop 

71 steps -= 1 

72 continue_after = (steps > 1) and (remaining > 1) 

73 tested: int = remaining # the indices that we can test. 

74 while True: # Loop forever until eligible element found. 

75 ii = random.integers(0, tested) # Get a new random index. 

76 i2 = indices[ii] # Get the actual index. 

77 current = dest[i2] # Get the value at the new index. 

78 if tested <= 1: # Are all remaining elements same? 

79 continue_after = False # If yes, then we quit. 

80 break 

81 if (current != last) and ( 

82 continue_after or (current != first)): 

83 remaining -= 1 

84 indices[remaining], indices[ii] = \ 

85 i2, indices[remaining] 

86 break # to stop, then it must be != first value. 

87 tested -= 1 # Now there is one fewer index. 

88 indices[tested], indices[ii] = i2, indices[tested] 

89 dest[i1] = last = current # Store value for from i2 at i1. 

90 i1 = i2 # Update i1 to now point to cell of i2. 

91 dest[i1] = first # Finally, store first element back at end. 

92 

93 

94class Op1SwapTryN(Op1WithStepSize): 

95 """An operator trying to swap a given number of elements.""" 

96 

97 def op1(self, random: Generator, dest: np.ndarray, x: np.ndarray, 

98 step_size: float = 0.0) -> None: 

99 """ 

100 Copy `x` into `dest` and then swap several different values. 

101 

102 :param random: the random number generator 

103 :param dest: the array to receive the modified copy of `x` 

104 :param x: the existing point in the search space 

105 :param step_size: the number of elements to swap 

106 """ 

107 swap_try_n(random, dest, x, step_size, self.__indices) 

108 

109 def __init__(self, perm: Permutations) -> None: 

110 """ 

111 Initialize the operator. 

112 

113 :param perm: the base permutation 

114 """ 

115 super().__init__() 

116 if not isinstance(perm, Permutations): 

117 raise type_error(perm, "perm", Permutations) 

118 #: the valid indices 

119 self.__indices: Final[np.ndarray] = np.empty( 

120 perm.dimension, DEFAULT_INT) 

121 

122 def initialize(self) -> None: 

123 """Initialize this operator.""" 

124 super().initialize() 

125 fill_in_canonical_permutation(self.__indices) 

126 

127 def __str__(self) -> str: 

128 """ 

129 Get the name of this unary operator. 

130 

131 :returns: "swaptn", the name of this operator 

132 :retval "swaptn": always 

133 """ 

134 return "swaptn"