Coverage for moptipyapps / tsp / ea1p1_revn.py: 79%

1""" 

2A (1+1) EA for the TSP using the reversal move. 

3 

4A (1+1) EA is basically a local search :mod:`~moptipy.algorithms.so.rls` 

5algorithm that starts with a random solution as the current solution `x`. In 

6each iteration, it samples one new solution from the neighborhood of `x` and 

7accepts it (as the new `x`), if it is better or equally good. 

8The algorithm here applies the reversal move, i.e., a two-opt move, as the 

9unary search operator used for sampling the neighborhood of `x`. The 

10interesting thing about this operator, when applied to the TSP, is that we 

11can compute the tour length of the new solution in `O(1)` from the tour length 

12of the current solution. This means we can very quickly decide whether the 

13move would be acceptable - and only apply it (in `O(n)`) if its. 

14 

15The algorithm implemented here is the same as the basic (1+1) EA with `rev` 

16operator in the paper [1]. 

17 

18The original version of this code has been contributed by Mr. Tianyu LIANG 

19(梁天宇), <liangty@stu.hfuu.edu.cn> a Master's student at the Institute of 

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

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

22University (合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the 

23supervision of Prof. Dr. Thomas Weise (汤卫思教授). 

24 

251. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, and Thomas Weise. 

26 Solving the Traveling Salesperson Problem using Frequency Fitness 

27 Assignment. In Hisao Ishibuchi, Chee-Keong Kwoh, Ah-Hwee Tan, Dipti 

28 Srinivasan, Chunyan Miao, Anupam Trivedi, and Keeley A. Crockett, editors, 

29 *Proceedings of the IEEE Symposium on Foundations of Computational 

30 Intelligence (IEEE FOCI'22)*, part of the *IEEE Symposium Series on 

31 Computational Intelligence (SSCI 2022)*. December 4-7, 2022, Singapore, 

32 pages 360-367. IEEE. https://doi.org/10.1109/SSCI51031.2022.10022296. 

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

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

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

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

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

38""" 

39 

40from typing import Callable, Final, cast 

41 

42import numba # type: ignore 

43import numpy as np 

44from moptipy.api.algorithm import Algorithm 

45from moptipy.api.process import Process 

46from moptipy.utils.logger import KeyValueLogSection 

47from numpy.random import Generator 

48from pycommons.types import type_error 

49 

50from moptipyapps.tsp.instance import Instance 

51from moptipyapps.utils.shared import SCOPE_INSTANCE 

52 

53 

54@numba.njit(nogil=True, cache=True, inline="always", fastmath=False, 

55 boundscheck=False) 

56def rev_if_not_worse(i: int, j: int, n_cities: int, dist: np.ndarray, 

57 x: np.ndarray, y: int) -> int: 

58 """ 

59 Check a reversal move, apply it if it is better, return new tour length. 

60 

61 :param i: the first, smaller index 

62 :param j: the second, larger index 

63 :param n_cities: the number of cities 

64 :param dist: the problem instance 

65 :param x: the candidate solution 

66 :param y: the tour length 

67 """ 

68 xi: Final[int] = x[i] # the value of x at index i 

69 xim1: Final[int] = x[i - 1] # the value of x at index i-1, wraps at 0 

70 xj: Final[int] = x[j] # the value of x at index j 

71 xjp1: Final[int] = x[(j + 1) % n_cities] # x[j + 1] with index wrap 

72 

73 # compute the difference in tour length if we would apply the move 

74 dy: Final[int] = (dist[xim1, xj] + dist[xi, xjp1] 

75 - dist[xim1, xi] - dist[xj, xjp1]) 

76 if dy <= 0: # this is not a worsening improving move? ... so apply it 

77 # reverse the sequence from i to j in the solution 

78 if i == 0: # deal with the special case that i==0 

79 x[0:j + 1:1] = x[j::-1] 

80 else: # the normal case that i > 0 

81 x[i:j + 1:1] = x[j:i - 1:-1] 

82 return int(y + dy) # return new tour length 

83 return y # return old tour length 

84 

85 

86class TSPEA1p1revn(Algorithm): 

87 """A (1+1) EA using the reversal operator for the TSP.""" 

88 

89 def __init__(self, instance: Instance) -> None: 

90 """ 

91 Initialize the RLS algorithm for the TSP with reversal move. 

92 

93 :param instance: the problem instance 

94 """ 

95 super().__init__() 

96 if not isinstance(instance, Instance): 

97 raise type_error(instance, "instance", Instance) 

98 self.instance: Final[Instance] = instance 

99 

100 def solve(self, process: Process) -> None: 

101 """ 

102 Apply an RLS = (1+1) EA optimization process with reversing operator. 

103 

104 :param process: the process instance which provides random numbers, 

105 functions for creating, copying, and evaluating solutions, as well 

106 as the termination criterion 

107 """ 

108 random: Final[Generator] = process.get_random() 

109 # set up the fast calls 

110 register: Final[Callable[[np.ndarray, int], int]] =\ 

111 cast("Callable[[np.ndarray, int], int]", process.register) 

112 should_terminate: Final[Callable[[], bool]] = process.should_terminate 

113 ri: Final[Callable[[int], int]] = random.integers 

114 

115 instance: Final[Instance] = self.instance # get the instance 

116 n: Final[int] = instance.n_cities # get the number of cities 

117 x: Final[np.ndarray] = process.create() # create the solution 

118 x[:] = range(n) # fill array with 0..n 

119 random.shuffle(x) # randomly generate an initial solution 

120 

121 y: int = cast("int", process.evaluate(x)) # get length of first tour 

122 nm1: Final[int] = n - 1 # need n-1 in the loop for the random numbers 

123 nm2: Final[int] = n - 2 # we need this to check the move indices 

124 while not should_terminate(): 

125 i = ri(nm1) # get the first index 

126 j = ri(nm1) # get the second index 

127 if i > j: # ensure that i <= j 

128 i, j = j, i # swap indices if i > j 

129 if (i == j) or ((i == 0) and (j == nm2)): 

130 continue # either a nop or a complete reversal 

131 y = rev_if_not_worse(i, j, n, instance, x, y) # apply the move 

132 register(x, y) # register the objective value 

133 

134 def __str__(self): 

135 """ 

136 Get the name of this algorithm. 

137 

138 This name is then used in the directory path and file name of the 

139 log files. 

140 

141 :returns: "tsp_ea1p1_revn" 

142 :retval "tsp_ea1p1_revn": always 

143 """ 

144 return "tsp_ea1p1_revn" 

145 

146 def log_parameters_to(self, logger: KeyValueLogSection) -> None: 

147 """ 

148 Log the parameters of the algorithm to the given logger. 

149 

150 :param logger: the logger for the parameters 

151 """ 

152 super().log_parameters_to(logger) 

153 with logger.scope(SCOPE_INSTANCE) as kv: 

154 self.instance.log_parameters_to(kv)