Coverage for moptipy / operators / permutations / op1_swap2.py: 54%

1""" 

2An operator swapping two elements in a permutation. 

3 

4This is a unary search operator which first copies the source string `x` to 

5the destination string `dest`. Then it draws an index `i1` randomly. 

6It keeps drawing a second random index `i2` until `dest[i1] != dest[i2]`, 

7i.e., until the elements at the two indices are different. This will always 

8be true for actual permutations if `i1 != i2`, but for permutations with 

9repetitions, even if `i1 != i2`, sometimes `dest[i1] == dest[i2]`. Anyway, 

10as soon as the elements at `i1` and `i2` are different, they will be swapped. 

11 

12This operator is very well-known for permutations and has been used by many 

13researchers, e.g., for the Traveling Salesperson Problem (TSP). In the papers 

14by Larrañaga et al. (1999) and Banzhaf (1990), it is called "Exchange 

15Mutation." It is also referred to as the "swap mutation" (Oliver et al. 1987), 

16point mutation operator (Ambati et al. 1991), the reciprocal exchange mutation 

17operator (Michalewicz 1992), or the order based mutation operator by Syswerda 

18(1991). 

19 

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

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

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

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

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

252. Wolfgang Banzhaf. The "Molecular" Traveling Salesman. *Biological 

26 Cybernetics*, 64(1):7-14, November 1990, https://doi.org/10.1007/BF00203625 

273. I.M. Oliver, D.J. Smith, and J.R.C. Holland. A Study of Permutation 

28 Crossover Operators on the Traveling Salesman Problem. In *Proceedings of 

29 the Second International Conference on Genetic Algorithms and their 

30 Application* (ICGA'87), October 1987, pages 224-230, 

31 https://dl.acm.org/doi/10.5555/42512.42542 

324. Balamurali Krishna Ambati, Jayakrishna Ambati, and Mazen Moein Mokhtar. 

33 Heuristic Combinatorial Optimization by Simulated Darwinian Evolution: A 

34 Polynomial Time Algorithm for the Traveling Salesman Problem. *Biological 

35 Cybernetics,* 65(1):31-35, May 1991, https://doi.org/10.1007/BF00197287 

365. Zbigniew Michalewicz. *Genetic Algorithms + Data Structures = Evolution 

37 Programs,* Berlin, Germany: Springer-Verlag GmbH. 1996. ISBN:3-540-58090-5. 

38 https://doi.org/10.1007/978-3-662-03315-9 

396. Gilbert Syswerda. Schedule Optimization Using Genetic Algorithms. In 

40 Lawrence Davis, (ed.), *Handbook of Genetic Algorithms,* pages 332-349. 

41 1991. New York, NY, USA: Van Nostrand Reinhold. 

427. Thomas Weise. *Optimization Algorithms.* 2021. Hefei, Anhui, China: 

43 Institute of Applied Optimization (IAO), School of Artificial Intelligence 

44 and Big Data, Hefei University. http://thomasweise.github.io/oa/ 

45 

46This operator performs one swap. It is similar to :class:`~moptipy.operators.\ 

47permutations.op1_swapn.Op1SwapN`, which performs a random number of swaps. 

48""" 

49from typing import Final 

50 

51import numba # type: ignore 

52import numpy as np 

53from numpy.random import Generator 

54 

55from moptipy.api.operators import Op1 

56 

57 

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

59def swap_2(random: Generator, dest: np.ndarray, 

60 x: np.ndarray) -> None: 

61 """ 

62 Copy `x` into `dest` and swap two different values in `dest`. 

63 

64 :param random: the random number generator 

65 :param dest: the array to receive the modified copy of `x` 

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

67 

68 >>> rand = np.random.default_rng(10) 

69 >>> xx = np.array(range(10), int) 

70 >>> out = np.empty(len(xx), int) 

71 >>> swap_2(rand, out, xx) 

72 >>> print(out) 

73 [0 1 2 3 4 5 6 9 8 7] 

74 >>> int(sum(out != xx)) 

75 2 

76 >>> swap_2(rand, out, xx) 

77 >>> print(out) 

78 [0 1 7 3 4 5 6 2 8 9] 

79 >>> int(sum(out != xx)) 

80 2 

81 >>> swap_2(rand, out, xx) 

82 >>> print(out) 

83 [0 1 2 3 4 8 6 7 5 9] 

84 >>> int(sum(out != xx)) 

85 2 

86 """ 

87 # start book 

88 dest[:] = x[:] # First, we copy `x` to `dest`. 

89 length: Final[int] = len(dest) # Get the length of `dest`. 

90 

91 i1: Final = random.integers(0, length) # first random index 

92 v1: Final = dest[i1] # Get the value at the first index. 

93 while True: # Repeat until we find a different value. 

94 i2 = random.integers(0, length) # second random index 

95 v2 = dest[i2] # Get the value at the second index. 

96 if v1 != v2: # If both values different... 

97 dest[i2] = v1 # store v1 where v2 was 

98 dest[i1] = v2 # store v2 where v1 was 

99 return # Exit function: we are finished. 

100 

101 

102class Op1Swap2(Op1): 

103 """ 

104 A unary search operation that swaps two (different) elements. 

105 

106 In other words, it performs exactly one swap on a permutation. 

107 It spans a neighborhood of a rather limited size but is easy 

108 and fast. 

109 """ 

110 

111 def __init__(self) -> None: 

112 """Initialize the object.""" 

113 super().__init__() # -book 

114 self.op1 = swap_2 # type: ignore # use function directly 

115 # end book 

116 

117 def __str__(self) -> str: 

118 """ 

119 Get the name of this unary operator. 

120 

121 :returns: "swap2", the name of this operator 

122 :retval "swap2": always 

123 """ 

124 return "swap2"