Coverage for moptipy / operators / permutations / op1_insert1.py: 32%
41 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2An operator deleting an element from a permutation and inserting it elsewhere.
4The operator is similar to a combination of the `rol` and `ror` operators
5in [1]. If the permutation represents, e.g., a tour in the Traveling
6Salesperson Problem (TSP), then a rotation replaces two edges (if two
7neighboring elements are rotated = swapped) or three edges (if at least three
8elements take part in the rotation). It may therefore be considered as a
9possible 3-opt move on the TSP.
11An alternative way to look at this is given in [2, 3, 4], where the operator
12is called "Insertion Mutation": An element of the permutation is removed from
13its current position (`i1`) and inserted at another position (`i2`). The
14operator is therefore called "position based mutation operator" in [5].
161. Thomas Weise, Raymond Chiong, Ke Tang, Jörg Lässig, Shigeyoshi Tsutsui,
17 Wenxiang Chen, Zbigniew Michalewicz, and Xin Yao. Benchmarking Optimization
18 Algorithms: An Open Source Framework for the Traveling Salesman Problem.
19 *IEEE Computational Intelligence Magazine (CIM)* 9(3):40-52, August 2014.
20 https://doi.org/10.1109/MCI.2014.2326101
212. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, I. Inza, and
22 S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A
23 Review of Representations and Operators. *Artificial Intelligence Review,*
24 13(2):129-170, April 1999. Kluwer Academic Publishers, The Netherlands.
25 https://doi.org/10.1023/A:1006529012972
263. David B. Fogel. An Evolutionary Approach to the Traveling Salesman Problem.
27 *Biological Cybernetics* 60(2):139-144, December 1988.
28 https://doi.org/10.1007/BF00202901
294. Zbigniew Michalewicz. *Genetic Algorithms + Data Structures = Evolution
30 Programs,* Berlin, Germany: Springer-Verlag GmbH. 1996. ISBN:3-540-58090-5.
31 https://doi.org/10.1007/978-3-662-03315-9
325. Gilbert Syswerda. Schedule Optimization Using Genetic Algorithms. In
33 Lawrence Davis, (ed.), *Handbook of Genetic Algorithms,* pages 332-349.
34 1991. New York, NY, USA: Van Nostrand Reinhold.
356. Yuezhong Wu, Thomas Weise, and Raymond Chiong. Local Search for the
36 Traveling Salesman Problem: A Comparative Study. In *Proceedings of the
37 14th IEEE Conference on Cognitive Informatics & Cognitive Computing
38 (ICCI*CC'15),* July 6-8, 2015, Beijing, China, pages 213-220, Los Alamitos,
39 CA, USA: IEEE Computer Society Press, ISBN: 978-1-4673-7289-3.
40 https://doi.org/10.1109/ICCI-CC.2015.7259388
417. Dan Xu, Thomas Weise, Yuezhong Wu, Jörg Lässig, and Raymond Chiong. An
42 Investigation of Hybrid Tabu Search for the Traveling Salesman Problem. In
43 *Proceedings of the 10th International Conference on Bio-Inspired Computing
44 — Theories and Applications (BIC-TA'15),* September 25-28, 2015,
45 Hefei, Anhui, China, volume 562 of Communications in Computer and
46 Information Science. Berlin/Heidelberg: Springer-Verlag, pages 523-537,
47 ISBN 978-3-662-49013-6. https://doi.org/10.1007/978-3-662-49014-3_47
488. Weichen Liu, Thomas Weise, Yuezhong Wu, and Raymond Chiong. Hybrid Ejection
49 Chain Methods for the Traveling Salesman Problem. In *Proceedings of the
50 10th International Conference on Bio-Inspired Computing — Theories
51 and Applications (BIC-TA'15),* September 25-28, 2015, Hefei, Anhui, China,
52 volume 562 of Communications in Computer and Information Science.
53 Berlin/Heidelberg: Springer-Verlag, pages 268-282, ISBN 978-3-662-49013-6.
54 https://doi.org/10.1007/978-3-662-49014-3_25
559. Yuezhong Wu, Thomas Weise, and Weichen Liu. Hybridizing Different Local
56 Search Algorithms with Each Other and Evolutionary Computation: Better
57 Performance on the Traveling Salesman Problem. In *Proceedings of the 18th
58 Genetic and Evolutionary Computation Conference (GECCO'16),* July 20-24,
59 2016, Denver, CO, USA, pages 57-58, New York, NY, USA: ACM.
60 ISBN: 978-1-4503-4323-7. https://doi.org/10.1145/2908961.2909001
61"""
62from typing import Final
64import numba # type: ignore
65import numpy as np
66from numpy.random import Generator
68from moptipy.api.operators import Op1
71@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
72def rotate(random: Generator, dest: np.ndarray, x: np.ndarray) -> None:
73 """
74 Copy `x` into `dest` and then rotate a subsequence by one step.
76 The function repeatedly tries to rotate a portion of an array to the left
77 or right in place. It will continue trying until something changed.
78 In each step, it draws two indices `i1` and `i2`.
80 If `i1 < i2`, then a left rotation by one step is performed. In other
81 words, the element at index `i1 + 1` goes to index `i1`, the element at
82 index `i1 + 2` goes to index `i1 + 1`, and so on. The lst element, i.e.,
83 the one at index `i2` goes to index `i2 - 1`. Finally, the element that
84 originally was at index `i1` goes to index `i2`. If any element in the
85 array has changed, this function is done, otherwise it tries again.
87 If `i1 > i2`, then a right rotation by one step is performed. In other
88 words, the element at index `i1 - 1` goes to index `i1`, the element at
89 index `i1 - 2` goes to index `i1 - 1`, and so on. Finally, the element
90 that originally was at index `i1` goes to index `i2`. If any element in
91 the array has changed, this function tries again, otherwise it stops.
93 This corresponds to extracting the element at index `i1` and re-inserting
94 it at index `i2`.
96 :param random: the random number generator
97 :param dest: the array to receive the modified copy of `x`
98 :param x: the existing point in the search space
100 >>> rand = np.random.default_rng(10)
101 >>> xx = np.array(range(10), int)
102 >>> out = np.empty(len(xx), int)
103 >>> rotate(rand, out, xx)
104 >>> print(out)
105 [0 1 2 3 4 5 6 8 9 7]
106 >>> rotate(rand, out, xx)
107 >>> print(out)
108 [0 1 2 3 4 5 6 8 7 9]
109 >>> rotate(rand, out, xx)
110 >>> print(out)
111 [0 5 1 2 3 4 6 7 8 9]
112 >>> rotate(rand, out, xx)
113 >>> print(out)
114 [0 1 2 3 4 8 5 6 7 9]
115 """
116 dest[:] = x[:]
117 length: Final[int] = len(dest) # Get the length of `dest`.
118 unchanged: bool = True
119 # try to rotate the dest array until something changes
120 while unchanged:
121 i1 = random.integers(0, length)
122 i2 = random.integers(0, length)
123 if i1 == i2: # nothing to be done
124 continue # array will not be changed
126 if i1 < i2: # rotate to the left: move elements to lower indices?
127 first = dest[i1] # get the element to be removed
128 while i1 < i2: # iterate the indices
129 i3 = i1 + 1 # get next higher index
130 cpy = dest[i3] # get next element at that higher index
131 unchanged &= (cpy == dest[i1]) # is a change?
132 dest[i1] = cpy # store next element at the lower index
133 i1 = i3 # move to next higher index
134 unchanged &= (first == dest[i2]) # check if change
135 dest[i2] = first # store removed element at highest index
136 continue
138 last = dest[i1] # last element; rotate right: move elements up
139 while i2 < i1: # iterate over indices
140 i3 = i1 - 1 # get next lower index
141 cpy = dest[i3] # get element at that lower index
142 unchanged &= (cpy == dest[i1]) # is a change?
143 dest[i1] = cpy # store element at higher index
144 i1 = i3 # move to next lower index
145 unchanged &= (last == dest[i2]) # check if change
146 dest[i2] = last # store removed element at lowest index
149class Op1Insert1(Op1):
150 """
151 Delete an element from a permutation and insert it elsewhere.
153 This operation keep drawing to random numbers, `i1` and `i2`. If
154 `i1 < i2`, then the permutation is rotated one step to the left between
155 `i1` and `i2`. If `i1 > i2`, then it is rotated one step to the right
156 between `i1` and `i2`. If the permutation has changed, the process is
157 stopped. This corresponds to extracting the element at index `i1` and
158 re-inserting it at index `i2`. This operator also works for permutations
159 with repetitions.
160 """
162 def __init__(self) -> None:
163 """Initialize the object."""
164 super().__init__()
165 self.op1 = rotate # type: ignore # use function directly
167 def __str__(self) -> str:
168 """
169 Get the name of this unary operator.
171 :returns: "rot1", the name of this operator
172 :retval "rot1": always
173 """
174 return "rot1"