Coverage for moptipy / examples / bitstrings / binint.py: 68%

1""" 

2The BinInt problem maximizes the binary value of a bit string. 

3 

4The BinInt problem is similar to the OneMax and LinearHarmonic in that it 

5tries to maximize the number of `True` bits in a string. 

6Different from these problems, however, it assigns exponentially increasing 

7weights to the bits. 

8The bit at index `1` has weight `2 ** (n - 1)`. 

9The bit at the last position has weight 1. 

10The upper bound for the objective function, reached when all bits are `False`, 

11therefore is `2 ** n - 1`. The lower bound, reached when all bits are `True`, 

12is `0`. 

13 

141. William Michael Rudnick. Genetic Algorithms and Fitness Variance with an 

15 Application to the Automated Design of Artificial Neural Networks. 

16 PhD thesis, Oregon Graduate Institute of Science & Technology: Beaverton, 

17 OR, USA, 1992. UMI Order No.: GAX92-22642. 

182. Dirk Thierens, David Edward Goldberg, and Ângela Guimarães Pereira. Domino 

19 Convergence, Drift, and the Temporal-Salience Structure of Problems. In 

20 CEC'98, pages 535-540, 1998. 

21 doi: https://doi.org/10.1109/ICEC.1998.700085. 

223. Kumara Sastry and David Edward Goldberg. Let's Get Ready to Rumble Redux: 

23 Crossover versus Mutation Head to Head on Exponentially Scaled Problems. 

24 In GECCO'07-I, pages 1380-1387, 2007. 

25 doi: https://doi.org10.1145/1276958.1277215. 

264. Kumara Sastry and David Edward Goldberg. Let's Get Ready to Rumble Redux: 

27 Crossover versus Mutation Head to Head on Exponentially Scaled Problems. 

28 IlliGAL Report 2007005, Illinois Genetic Algorithms Laboratory (IlliGAL), 

29 Department of Computer Science, Department of General Engineering, 

30 University of Illinois at Urbana-Champaign: Urbana-Champaign, IL, USA, 

31 February 11, 2007. 

32""" 

33 

34from typing import Callable, Final, Iterator, cast 

35 

36import numba # type: ignore 

37import numpy as np 

38 

39from moptipy.examples.bitstrings.bitstring_problem import BitStringProblem 

40 

41 

42@numba.njit(nogil=True, cache=True) 

43def binint(x: np.ndarray) -> int: 

44 """ 

45 Get the binint objective value: decode the inverted bit string as integer. 

46 

47 :param x: the np array 

48 :return: the inverted bit string represented as integer 

49 

50 >>> binint(np.array([0])) 

51 1 

52 >>> binint(np.array([1])) 

53 0 

54 

55 >>> binint(np.array([0, 0])) 

56 3 

57 >>> binint(np.array([0, 1])) 

58 2 

59 >>> binint(np.array([1, 0])) 

60 1 

61 >>> binint(np.array([1, 1])) 

62 0 

63 

64 >>> binint(np.array([0, 0, 0])) 

65 7 

66 >>> binint(np.array([0, 0, 1])) 

67 6 

68 >>> binint(np.array([0, 1, 0])) 

69 5 

70 >>> binint(np.array([0, 1, 1])) 

71 4 

72 >>> binint(np.array([1, 0, 0])) 

73 3 

74 >>> binint(np.array([1, 0, 1])) 

75 2 

76 >>> binint(np.array([1, 1, 0])) 

77 1 

78 >>> binint(np.array([1, 1, 1])) 

79 0 

80 """ 

81 n: Final[int] = len(x) 

82 weight: int = 1 << n 

83 result: int = weight - 1 

84 for xx in x: 

85 weight >>= 1 

86 if xx: 

87 result -= weight 

88 return result 

89 

90 

91class BinInt(BitStringProblem): 

92 """Maximize the binary value of a bit string.""" 

93 

94 def __init__(self, n: int) -> None: 

95 """ 

96 Initialize the binint objective function. 

97 

98 :param n: the dimension of the problem 

99 

100 >>> print(BinInt(2).n) 

101 2 

102 >>> print(BinInt(4).evaluate(np.array([True, True, False, True]))) 

103 2 

104 """ 

105 super().__init__(n) 

106 self.evaluate = binint # type: ignore 

107 

108 def __str__(self) -> str: 

109 """ 

110 Get the name of the binint objective function. 

111 

112 :return: `binint_` + length of string 

113 

114 >>> BinInt(13) 

115 binint_13 

116 """ 

117 return f"binint_{self.n}" 

118 

119 def upper_bound(self) -> int: 

120 """ 

121 Get the upper bound of the :class:`BinInt` problem. 

122 

123 :returns: `(1 << n) - 1` 

124 

125 >>> BinInt(4).upper_bound() 

126 15 

127 >>> BinInt(4).evaluate(np.array([0, 0, 0, 0])) 

128 15 

129 """ 

130 return (1 << self.n) - 1 

131 

132 @classmethod 

133 def default_instances( 

134 cls: type, scale_min: int = 2, scale_max: int = 30) \ 

135 -> Iterator[Callable[[], "BinInt"]]: 

136 """ 

137 Get the 29 default instances of the :class:`BinInt` problem. 

138 

139 :param scale_min: the minimum permitted scale, by default `2` 

140 :param scale_max: the maximum permitted scale, by default `32` 

141 :returns: a sequence of default :class:`BinInt` instances 

142 

143 >>> len(list(BinInt.default_instances())) 

144 29 

145 

146 >>> [x() for x in BinInt.default_instances()] 

147 [binint_2, binint_3, binint_4, binint_5, binint_6, binint_7, \ 

148binint_8, binint_9, binint_10, binint_11, binint_12, binint_13, binint_14, \ 

149binint_15, binint_16, binint_17, binint_18, binint_19, binint_20, binint_21, \ 

150binint_22, binint_23, binint_24, binint_25, binint_26, binint_27, binint_28, \ 

151binint_29, binint_30] 

152 """ 

153 return cast("Iterator[Callable[[], BinInt]]", 

154 super().default_instances( # type: ignore 

155 scale_min, scale_max))