Coverage for moptipy / operators / tools.py: 50%

1"""Some tools for optimization.""" 

2 

3from math import exp, log 

4 

5import numba # type: ignore 

6 

7 

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

9def exponential_step_size(step_size: float, 

10 min_steps: int, max_steps: int) -> int: 

11 """ 

12 Translate a step size in `[0,1]` to an integer in `min_steps..max_steps`. 

13 

14 The idea is that we would like to have step-size dependent operators of 

15 type :class:`~moptipy.api.operators.Op1WithStepSize`. These operators 

16 allow algorithms to tune the amount of change to be applied to a solution 

17 between `0` and `1` (inclusively). As described in the documentation of 

18 :meth:`~moptipy.api.operators.Op1WithStepSize.op1`, `0` means that the 

19 smallest possible change should be applied and `1` means that the largest 

20 possible change should be applied. 

21 

22 Now for many search spaces, we need to translate this step size from 

23 `[0,1]` to an integer. For instance, if we have `n`-dimensional 

24 :mod:`~moptipy.spaces.bitstrings` as search space, then we can flip 

25 anything between `1` and `n` bits. Straightforwardly, one would linearly 

26 scale the step size from `[0,1]` to `1..n`. Unfortunately, if we do that, 

27 then different values of `step_size` will have very different meaning 

28 depending on `n`. For example, `step_size=0.05` would translate to 

29 `round(1 + step_size * (n-1)) = 1` bits to be flipped if `n=10`, to 

30 `6` bit flips for `n=100`, and to `501` bit flips for `n=10_000`. While 

31 flipping one bit is a very small move and flipping six bits may be a 

32 medium-size move in discrete optimization, flipping over 500 bits is 

33 actually always quite a lot. 

34 

35 What we would like is to have scale-independent small moves but still be 

36 able to make large moves. We can get this by exponentially transforming 

37 the `step_width`. Most `step_size` values will result in small integer 

38 steps and only `step_size` values close to `1` will yield really big 

39 results. 

40 

41 And for a `step_size=0.05`, we get for different `n`: 

42 

43 >>> exponential_step_size(0.05, 1, 10) 

44 1 

45 >>> exponential_step_size(0.05, 1, 100) 

46 1 

47 >>> exponential_step_size(0.05, 1, 10_000) 

48 2 

49 >>> exponential_step_size(0.05, 1, 1_000_000) 

50 2 

51 >>> exponential_step_size(0.05, 1, 1_000_000_000) 

52 3 

53 >>> exponential_step_size(0.05, 1, 1_000_000_000_000) 

54 4 

55 

56 For different values of `step_size` and a fixed `n`, we can still obtain 

57 the whole spectrum of possible changes. For `n=10`, for example, we get: 

58 

59 >>> exponential_step_size(0.0, 1, 10) 

60 1 

61 >>> exponential_step_size(0.1, 1, 10) 

62 1 

63 >>> exponential_step_size(0.2, 1, 10) 

64 2 

65 >>> exponential_step_size(0.3, 1, 10) 

66 2 

67 >>> exponential_step_size(0.4, 1, 10) 

68 3 

69 >>> exponential_step_size(0.5, 1, 10) 

70 3 

71 >>> exponential_step_size(0.6, 1, 10) 

72 4 

73 >>> exponential_step_size(0.7, 1, 10) 

74 5 

75 >>> exponential_step_size(0.8, 1, 10) 

76 6 

77 >>> exponential_step_size(0.85, 1, 10) 

78 7 

79 >>> exponential_step_size(0.9, 1, 10) 

80 8 

81 >>> exponential_step_size(0.95, 1, 10) 

82 9 

83 >>> exponential_step_size(1.0, 1, 10) 

84 10 

85 

86 So we can still reach the whole range of possible steps from `1` to `n`. 

87 

88 >>> isinstance(exponential_step_size(0.5, 1, 9), int) 

89 True 

90 >>> exponential_step_size(0.0, 1, 100) 

91 1 

92 >>> exponential_step_size(1.0, 1, 100) 

93 100 

94 >>> exponential_step_size(1.0 / 3.0, 1, 10) 

95 2 

96 >>> exponential_step_size(1.0 / 3.0, 1, 100) 

97 5 

98 >>> exponential_step_size(1.0 / 3.0, 1, 10_000) 

99 22 

100 >>> exponential_step_size(0.0, 2, 10) 

101 2 

102 >>> exponential_step_size(0.0, 9, 10) 

103 9 

104 >>> exponential_step_size(0.0, 10, 10) 

105 10 

106 >>> exponential_step_size(1.0, 10, 10) 

107 10 

108 

109 :param step_size: the step size from `[0,1]` to be transformed to an 

110 integer 

111 :param min_steps: the minimum (inclusive) value for the returned integer 

112 :param max_steps: the maximum (inclusive) value for the returned integer 

113 """ 

114 return round(min_steps + exp(step_size * log( 

115 max_steps - min_steps + 1))) - 1 

116 

117 

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

119def inv_exponential_step_size(int_val: int, 

120 min_steps: int, max_steps: int) -> float: 

121 """ 

122 Compute the inverse of :func:`exponential_step_size`. 

123 

124 This routine exists mainly to make testing easier. 

125 

126 :param int_val: the return value of :func:`exponential_step_size`. 

127 :param min_steps: the minimum (inclusive) value any `int_val` 

128 :param max_steps: the maximum (inclusive) value any `int_val` 

129 

130 >>> exponential_step_size(0.47712125471966244, 1, 10) 

131 3 

132 >>> inv_exponential_step_size(3, 1, 10) 

133 0.47712125471966244 

134 >>> inv_exponential_step_size(1, 1, 10) 

135 0.0 

136 >>> inv_exponential_step_size(10, 1, 10) 

137 1.0 

138 >>> inv_exponential_step_size(33, 6, 673) 

139 0.5123088678224029 

140 >>> exponential_step_size(0.5123088678224029, 6, 673) 

141 33 

142 >>> inv_exponential_step_size(3, 3, 3) 

143 1.0 

144 >>> inv_exponential_step_size(3, 3, 10) 

145 0.0 

146 >>> inv_exponential_step_size(10, 3, 10) 

147 1.0 

148 """ 

149 if int_val >= max_steps: 

150 return 1.0 

151 if int_val <= min_steps: 

152 return 0.0 

153 return float(log(int_val - min_steps + 1) / log( 

154 max_steps - min_steps + 1))