Coverage for moptipy / operators / permutations / op2_gap.py: 45%

1""" 

2A binary operator that merges two permutations by adding elements in sequence. 

3 

4Assume we have two permutations `x0` and `x1`. For each position `i` in the 

5destination string `dest`, we randomly select the permutation `x` from which 

6the value should come (so either `x=x0` or `x=x1`). We then store the first 

7value not yet marked as done from `x` in `dest[i]`, mark that value as 

8done both in `x0` and `x1`. 

9 

10This operator may be considered as a generalized version of the Alternating 

11Position Crossover operator (AP) for the Traveling Salesperson Problem by 

12Larrañaga et al. (1997). The original AP operator, as described by Larrañaga 

13et al., simply creates an offspring by selecting alternately the next element 

14of the fist parent and the next element of the second parent, omitting the 

15elements already present in the offspring. For example, if `x0` is `12345678` 

16and `x1` is `37516824`, the AP operator gives the following offspring 

17`13275468`. Exchanging the parents results in `31725468`. 

18 

19Our generalized version randomly decides which of the two parent permutations 

20to use each time, hopefully resulting in a greater variety of possible results. 

21It also does not skip over a parent if its next element is already used, but 

22instead picks the next not-yet-used element from that parent. 

23As mnemonic for the operator, we use `gap`. Larrañaga et al. used `AP` for the 

24version of the operator that strictly alternates between parents. 

25 

261. Pedro Larrañaga, Cindy M. H. Kuijpers, Mikel Poza, and Roberto H. Murga. 

27 Decomposing Bayesian Networks: Triangulation of the Moral Graph with Genetic 

28 Algorithms, *Statistics and Computing,* 7(1):19-34, March 1997, 

29 https://doi.org/10.1023/A:1018553211613 

302. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and 

31 S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A 

32 Review of Representations and Operators. *Artificial Intelligence Review,* 

33 13(2):129-170, April 1999. Kluwer Academic Publishers, The Netherlands. 

34 https://doi.org/10.1023/A:1006529012972 

35""" 

36from typing import Final 

37 

38import numba # type: ignore 

39import numpy as np 

40from numpy.random import Generator 

41from pycommons.types import type_error 

42 

43from moptipy.api.operators import Op2 

44from moptipy.spaces.permutations import Permutations 

45from moptipy.utils.nputils import DEFAULT_BOOL 

46 

47 

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

49def _op2_gap(r: np.ndarray, dest: np.ndarray, 

50 x0: np.ndarray, x1: np.ndarray, 

51 x0_done: np.ndarray, x1_done: np.ndarray) -> None: 

52 """ 

53 Apply a sequence mix from `x0` and `x1` to `dest`. 

54 

55 :param r: the random numbers, of length `n - 1` (!!) 

56 :param dest: the array to receive the result 

57 :param x0: the first existing point in the search space 

58 :param x1: the second existing point in the search space 

59 :param x0_done: a boolean array marking the elements in `x0` that have 

60 been used 

61 :param x1_done: a boolean array marking the elements in `x1` that have 

62 been used 

63 """ 

64 x0_done.fill(False) # all values in x0 are available 

65 x1_done.fill(False) # all values in x1 are available 

66 length: Final[int] = len(x0) 

67 

68 desti: int = 0 # writing to dest starts at index 0 

69 x0i: int = 0 # first valid value in x0 is at index 0 

70 x1i: int = 0 # first valid value in x1 is at index 0 

71 for rr in r: # repeat until dest is filled, i.e., desti=length 

72 # randomly chose a source point and pick next operation 

73 value = x0[x0i] if rr == 0 else x1[x1i] 

74 dest[desti] = value # store the value in the destination 

75 desti += 1 # step destination index 

76 

77 for x0j in range(x0i, length): # mark value as done in x0 

78 if (x0[x0j] == value) and (not x0_done[x0j]): # find 

79 x0_done[x0j] = True # value is found and not done 

80 break # so we mark it as done and break the loop 

81 while x0_done[x0i]: # now we find the next not-yet-done 

82 x0i += 1 # value in x0 

83 

84 for x1j in range(x1i, length): # mark value as done in x1 

85 if (x1[x1j] == value) and (not x1_done[x1j]): # find 

86 x1_done[x1j] = True # value is found and not done 

87 break # so we mark it as done and break the loop 

88 while x1_done[x1i]: # now we find the next not-yet-done 

89 x1i += 1 # value in x1 

90 

91 dest[desti] = x0[x0i] # = x1[x1i]: the final missing value 

92 

93 

94class Op2GeneralizedAlternatingPosition(Op2): 

95 """A binary operator trying to preserve the value sequence.""" 

96 

97 def op2(self, random: Generator, dest: np.ndarray, 

98 x0: np.ndarray, x1: np.ndarray) -> None: 

99 """ 

100 Apply a sequence mix from `x0` and `x1` to `dest`. 

101 

102 :param random: the random number generator 

103 :param dest: the array to receive the result 

104 :param x0: the first existing point in the search space 

105 :param x1: the second existing point in the search space 

106 """ 

107 _op2_gap(random.integers(low=2, high=None, size=len(dest) - 1), 

108 dest, x0, x1, self.__x0_done, self.__x1_done) 

109 

110 def __init__(self, space: Permutations) -> None: 

111 """ 

112 Initialize the GAP crossover operator. 

113 

114 :param space: the permutation space 

115 """ 

116 super().__init__() 

117 if not isinstance(space, Permutations): 

118 raise type_error(space, "space", Permutations) 

119 #: the elements that are done in `x0` 

120 self.__x0_done: Final[np.ndarray] = np.ndarray( 

121 (space.dimension,), DEFAULT_BOOL) 

122 #: the elements that are done in `x1` 

123 self.__x1_done: Final[np.ndarray] = np.ndarray( 

124 (space.dimension,), DEFAULT_BOOL) 

125 

126 def __str__(self) -> str: 

127 """ 

128 Get the name of this binary operator. 

129 

130 :returns: "gap" for "generalized alternating position crossover", 

131 the name of this operator 

132 :retval "gap": always 

133 """ 

134 return "gap"