Coverage for moptipy / examples / bitstrings / __init__.py: 100%

1""" 

2Example for bit-string based objective functions. 

3 

4The problems noted here are mainly well-known benchmark problems from the 

5discrete optimization community. For these problems, we designed the dedicated 

6base class :class:`~moptipy.examples.bitstrings.bitstring_problem.\ 

7BitStringProblem`. 

8 

9The following benchmark problems are provided: 

10 

111. The :mod:`~moptipy.examples.bitstrings.onemax` problem, where the 

12 goal is to find a bit string with the maximum number of ones. 

132. The :mod:`~moptipy.examples.bitstrings.leadingones` problem, 

14 where the goal is to find a bit string with the maximum number of leading 

15 ones. 

163. The :mod:`~moptipy.examples.bitstrings.linearharmonic` problem, 

17 where the goal is to find a bit string with the all ones, like in 

18 :mod:`~moptipy.examples.bitstrings.onemax`, but this time all bits have 

19 a different weight (namely their index, starting at 1). 

204. The :mod:`~moptipy.examples.bitstrings.binint` problem, 

21 is again similar to :mod:`~moptipy.examples.bitstrings.onemax`, but the 

22 bits have exponential weight. Basically, we just decode the bit string 

23 into an integer. 

245. The :mod:`~moptipy.examples.bitstrings.trap` problem, which is like 

25 OneMax, but with the optimum and worst-possible solution swapped. This 

26 problem is therefore highly deceptive. 

276. The :mod:`~moptipy.examples.bitstrings.twomax` problem has the global 

28 optimum at the string of all `1` bits and a local optimum at the string 

29 of all `0` bits. Both have basins of attraction of about the same size. 

307. :mod:`~moptipy.examples.bitstrings.ising1d`, the one-dimensional 

31 Ising model, where the goal is that all bits should have the same value as 

32 their neighbors in a ring. 

338. :mod:`~moptipy.examples.bitstrings.ising2d`, the two-dimensional 

34 Ising model, where the goal is that all bits should have the same value as 

35 their neighbors on a torus. 

369. The :mod:`~moptipy.examples.bitstrings.jump` problem is equivalent 

37 to :mod:`~moptipy.examples.bitstrings.onemax`, but has a deceptive 

38 region right before the optimum. 

3910. The :mod:`~moptipy.examples.bitstrings.plateau` problem similar to the 

40 :mod:`~moptipy.examples.bitstrings.jump` problem, but this time the 

41 optimum is surrounded by a region of neutrality. 

4211. The :mod:`~moptipy.examples.bitstrings.nqueens`, where the goal is to 

43 place `k` queens on a `k * k`-sized chess board such that no queen can 

44 beat any other queen. 

4512. The :mod:`~moptipy.examples.bitstrings.labs`, where the goal is to 

46 find a sequence with low autocorrelation and, thus, high merit factor. 

47 This problem is different from the others, because here, only for low 

48 values of `n`, the optimal solutions are actually known. 

4913. The :mod:`~moptipy.examples.bitstrings.w_model`, a benchmark 

50 problem with tunable epistasis, uniform neutrality, and 

51 ruggedness/deceptiveness. 

5214. The :mod:`~moptipy.examples.bitstrings.zeromax` problem, where the 

53 goal is to find a bit string with the maximum number of zeros. This is the 

54 opposite of the OneMax problem. 

55 

56Parts of the code here are related to the research work of 

57Mr. Jiazheng ZENG (曾嘉政), a Master's student at the Institute of Applied 

58Optimization (应用优化研究所) of the School of 

59Artificial Intelligence and Big Data (人工智能与大数据学院) at 

60Hefei University (合肥大学) in 

61Hefei, Anhui, China (中国安徽省合肥市) under the supervision of 

62Prof. Dr. Thomas Weise (汤卫思教授). 

63""" 

64from itertools import chain 

65from typing import Callable, Iterable, Iterator, cast 

66 

67from moptipy.examples.bitstrings.binint import BinInt 

68from moptipy.examples.bitstrings.bitstring_problem import BitStringProblem 

69from moptipy.examples.bitstrings.ising1d import Ising1d 

70from moptipy.examples.bitstrings.ising2d import Ising2d 

71from moptipy.examples.bitstrings.jump import Jump 

72from moptipy.examples.bitstrings.labs import LABS 

73from moptipy.examples.bitstrings.leadingones import LeadingOnes 

74from moptipy.examples.bitstrings.linearharmonic import LinearHarmonic 

75from moptipy.examples.bitstrings.nqueens import NQueens 

76from moptipy.examples.bitstrings.onemax import OneMax 

77from moptipy.examples.bitstrings.plateau import Plateau 

78from moptipy.examples.bitstrings.trap import Trap 

79from moptipy.examples.bitstrings.twomax import TwoMax 

80from moptipy.examples.bitstrings.w_model import WModel 

81 

82 

83def default_instances( 

84 class_scales: Callable[[ 

85 type], Iterable[int]] = lambda _: cast("Iterable[int]", ())) \ 

86 -> Iterator[Callable[[], BitStringProblem]]: 

87 """ 

88 Get the default bit-string based benchmark instances. 

89 

90 :param class_scales: a function that can override the minimum and 

91 maximimum problem scales on a per-benchmark-function-class 

92 basis. If this function returns an empty iterator, then the default 

93 scales are used. 

94 :return: an :class:`Iterable` with the default bit-string 

95 benchmark instances 

96 

97 >>> len(list(default_instances())) 

98 1044 

99 

100 >>> from moptipy.examples.bitstrings.binint import BinInt 

101 >>> from moptipy.examples.bitstrings.bitstring_problem import \ 

102BitStringNKProblem 

103 >>> def clazz_scales(clazz) -> tuple[int, int]: 

104 ... if issubclass(clazz, BinInt): 

105 ... return 2, 30 

106 ... if issubclass(clazz, BitStringNKProblem): 

107 ... return 6, 16 

108 ... return 8, 48 

109 >>> len(list(default_instances(clazz_scales))) 

110 331 

111 """ 

112 return chain( 

113 BinInt.default_instances(*class_scales(BinInt)), # type: ignore 

114 Ising1d.default_instances(*class_scales(Ising1d)), # type: ignore 

115 Ising2d.default_instances(*class_scales(Ising2d)), # type: ignore 

116 Jump.default_instances(*class_scales(Jump)), # type: ignore 

117 LeadingOnes.default_instances( # type: ignore 

118 *class_scales(LeadingOnes)), 

119 LinearHarmonic.default_instances( # type: ignore 

120 *class_scales(LinearHarmonic)), 

121 NQueens.default_instances(*class_scales(NQueens)), # type: ignore 

122 OneMax.default_instances(*class_scales(OneMax)), # type: ignore 

123 Plateau.default_instances(*class_scales(Plateau)), # type: ignore 

124 Trap.default_instances(*class_scales(Trap)), # type: ignore 

125 TwoMax.default_instances(*class_scales(TwoMax)), # type: ignore 

126 LABS.default_instances(*class_scales(LABS)), # type: ignore 

127 WModel.default_instances(*class_scales(WModel))) # type: ignore