Coverage for moptipy / operators / bitstrings / op1_flip_m.py: 100%

1""" 

2A unary operator flipping a pre-defined number of bits. 

3 

4This is a unary operator with step size, i.e., an instance of 

5:class:`~moptipy.api.operators.Op1WithStepSize`. As such, it also receives 

6a parameter `step_size` when it is applied, which is from the closed range 

7`[0.0, 1.0]`. If `step_size=0`, then exactly 1 bit will be flipped. If 

8`step_size=1`, then all bits will be flipped. For all values of 

9`0<step_size<1`, we use the function 

10:func:`~moptipy.operators.tools.exponential_step_size` to extrapolate the 

11number of bits to flip. 

12 

13Unary operators like this are often used in (1+1)-EAs or even in 

14state-of-the-art EAs such as the Self-Adjusting (1+(lambda,lambda)) GA. 

15 

161. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency 

17 Fitness Assignment: Optimization without Bias for Good Solutions can be 

18 Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*. 2022. 

19 doi: https://doi.org/10.1109/TEVC.2022.3191698, 

20 https://arxiv.org/pdf/2112.00229.pdf. 

212. Eduardo Carvalho Pinto and Carola Doerr. *Towards a More Practice-Aware 

22 Runtime Analysis of Evolutionary Algorithms,* 2018, 

23 arXiv:1812.00493v1 [cs.NE] 3 Dec 2018. https://arxiv.org/abs/1812.00493. 

24""" 

25from typing import Final 

26 

27import numpy as np 

28from numpy.random import Generator 

29 

30from moptipy.api.operators import Op1WithStepSize 

31from moptipy.operators.tools import exponential_step_size 

32 

33 

34class Op1FlipM(Op1WithStepSize): 

35 """A unary search operation that flips a specified number of `m` bits.""" 

36 

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

38 step_size: float = 0.0) -> None: 

39 """ 

40 Copy `x` into `dest` and flip exactly `m` bits. 

41 

42 `step_size=0.0` will flip exactly `1` bit, `step_size=1.0` will flip 

43 all `n` bits. All other values are extrapolated by function 

44 :func:`~moptipy.operators.tools.exponential_step_size`. In between 

45 the two extremes, an exponential scaling 

46 (:func:`~moptipy.operators.tools.exponential_step_size`) is performed, 

47 meaning that for `n=10` bits, a step-size of `0.2` means flipping 

48 two bits, `0.4` means flipping three bits, `0.6` means flipping four 

49 bits, `0.7` means flipping five bits, `0.9` means flipping eight bits, 

50 `0.95` means flipping nine bits, and `1.0` means flipping all bits. 

51 In other words, a larger portion of the `step_size` range corresponds 

52 to making small changes while the large changes are all condensed at 

53 the higher end of the scale. 

54 

55 :param self: the self pointer 

56 :param random: the random number generator 

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

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

59 :param step_size: the number of bits to flip 

60 

61 >>> op1 = Op1FlipM() 

62 >>> from numpy.random import default_rng as drg 

63 >>> rand = drg() 

64 >>> import numpy as npx 

65 >>> src = npx.zeros(10, bool) 

66 >>> dst = npx.zeros(10, bool) 

67 >>> for ss in [0.0, 0.2, 0.4, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95, 1.0]: 

68 ... op1.op1(rand, dst, src, ss) 

69 ... print(sum(dst != src)) 

70 1 

71 2 

72 3 

73 4 

74 5 

75 6 

76 7 

77 8 

78 9 

79 10 

80 """ 

81 np.copyto(dest, x) # copy source to destination 

82 n: Final[int] = len(dest) # get the number of bits 

83 dest[random.choice(n, exponential_step_size( 

84 step_size, 1, n), False)] ^= True # flip the selected bits via xor 

85 

86 def __str__(self) -> str: 

87 """ 

88 Get the name of this unary operator. 

89 

90 :return: "flipm" 

91 """ 

92 return "flipm"