Coverage for moptipy / operators / bitstrings / op1_m_over_n_flip.py: 57%

1"""A unary operator flipping each bit with probability m/n.""" 

2from typing import Final 

3 

4import numba # type: ignore 

5import numpy as np 

6from numpy.random import Generator 

7from pycommons.types import check_int_range, type_error 

8 

9from moptipy.api.operators import Op1 

10from moptipy.utils.nputils import ( 

11 fill_in_canonical_permutation, 

12 int_range_to_dtype, 

13) 

14 

15 

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

17def _op1_movern(m: int, none_is_ok: bool, permutation: np.ndarray, 

18 random: Generator, dest: np.ndarray, x: np.ndarray) -> None: 

19 """ 

20 Copy `x` into `dest` and flip each bit with probability m/n. 

21 

22 This method will first copy `x` to `dest`. Then it will flip each bit 

23 in `dest` with probability `m/n`, where `n` is the length of `dest`. 

24 Regardless of the probability, at least one bit will always be 

25 flipped if self.at_least_1 is True. 

26 

27 :param m: the value of m 

28 :param none_is_ok: is it OK to flip nothing? 

29 :param permutation: the internal permutation 

30 :param random: the random number generator 

31 :param dest: the destination array to receive the new point 

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

33 """ 

34 dest[:] = x[:] # copy source to destination 

35 length: Final[int] = len(dest) # get n 

36 p: Final[float] = m / length # probability to flip bit 

37 

38 flips: int # the number of bits to flip 

39 while True: 

40 flips = random.binomial(length, p) # get the number of bits to flip 

41 if flips > 0: 

42 break # we will flip some bit 

43 if none_is_ok: 

44 return # we will flip no bit 

45 

46 i: int = length 

47 end: Final[int] = length - flips 

48 while i > end: # we iterate from i=length down to end=length-flips 

49 k = random.integers(0, i) # index of next bit index in permutation 

50 i -= 1 # decrease i 

51 idx = permutation[k] # get index of bit to flip and move to end 

52 permutation[i], permutation[k] = idx, permutation[i] 

53 dest[idx] = not dest[idx] # flip bit 

54 

55 

56class Op1MoverNflip(Op1): 

57 """ 

58 A unary search operation that flips each bit with probability of `m/n`. 

59 

60 For bit strings of length `n`, draw the number `z` of bits to flip from a 

61 binomial distribution with `p=m/n`. If `at_least_1` is set to `True`, then 

62 we repeat drawing `z` until `z>0`. 

63 """ 

64 

65 def __init__(self, n: int, m: int = 1, at_least_1: bool = True): 

66 """ 

67 Initialize the operator. 

68 

69 :param n: the length of the bit strings 

70 :param m: the factor for computing the probability of flipping 

71 the bits 

72 :param at_least_1: should at least one bit be flipped? 

73 """ 

74 super().__init__() 

75 check_int_range(n, "n", 1) 

76 #: the value of m in p=m/n 

77 self.__m: Final[int] = check_int_range(m, "m", 1, n) 

78 if not isinstance(at_least_1, bool): 

79 raise type_error(at_least_1, "at_least_1", bool) 

80 #: is it OK to not flip any bit? 

81 self.__none_is_ok: Final[bool] = not at_least_1 

82 #: the internal permutation 

83 self.__permutation: Final[np.ndarray] = np.empty( 

84 n, dtype=int_range_to_dtype(0, n - 1)) 

85 

86 def initialize(self) -> None: 

87 """Initialize this operator.""" 

88 super().initialize() 

89 fill_in_canonical_permutation(self.__permutation) 

90 

91 def op1(self, random: Generator, dest: np.ndarray, x: np.ndarray) -> None: 

92 """ 

93 Copy `x` into `dest` and flip each bit with probability m/n. 

94 

95 This method will first copy `x` to `dest`. Then it will flip each bit 

96 in `dest` with probability `m/n`, where `n` is the length of `dest`. 

97 Regardless of the probability, at least one bit will always be 

98 flipped if self.at_least_1 is True. 

99 

100 :param self: the self pointer 

101 :param random: the random number generator 

102 :param dest: the destination array to receive the new point 

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

104 """ 

105 _op1_movern(self.__m, self.__none_is_ok, self.__permutation, 

106 random, dest, x) 

107 

108 def __str__(self) -> str: 

109 """ 

110 Get the name of this unary operator. 

111 

112 :return: "fileB" + m + "n" if none-is-ok else "" 

113 """ 

114 return f"flipB{self.__m}{'n' if self.__none_is_ok else ''}"