Coverage for moptipyapps / tsp / fea1p1_revn.py: 74%

1""" 

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

3 

4A (1+1) FEA is the same as the (1+1) EA with Frequency Fitness Assignment. 

5The (1+1) EA using the same search operator as this algorithm here is 

6implemented in module :mod:`~moptipyapps.tsp.ea1p1_revn`. 

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

8operator in the paper [1]. 

9 

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

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

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

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

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

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

16 

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

18 Solving the Traveling Salesperson Problem using Frequency Fitness 

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

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

21 *Proceedings of the IEEE Symposium on Foundations of Computational 

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

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

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

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

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

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

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

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

30""" 

31 

32from typing import Callable, Final, cast 

33 

34import numba # type: ignore 

35import numpy as np 

36from moptipy.algorithms.so.ffa.ffa_h import log_h 

37from moptipy.api.algorithm import Algorithm 

38from moptipy.api.process import Process 

39from moptipy.utils.logger import KeyValueLogSection 

40from moptipy.utils.nputils import DEFAULT_INT 

41from numpy.random import Generator 

42from pycommons.types import type_error 

43 

44from moptipyapps.tsp.instance import Instance 

45from moptipyapps.utils.shared import SCOPE_INSTANCE 

46 

47 

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

49 boundscheck=False) 

50def rev_if_h_not_worse(i: int, j: int, n_cities: int, dist: np.ndarray, 

51 h: np.ndarray, x: np.ndarray, y: int) -> int: 

52 """ 

53 Apply a reversal move if its tour length frequency is not worse. 

54 

55 :param i: the first, smaller index 

56 :param j: the second, larger index 

57 :param n_cities: the number of cities 

58 :param dist: the problem instance 

59 :param h: the frequency table 

60 :param x: the candidate solution 

61 :param y: the tour length 

62 """ 

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

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

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

66 xjp1: Final[int] = x[(j + 1) % n_cities] # x[j + 1], but index wrapped 

67 

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

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

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

71 y2: Final[int] = int(y + dy) # and compute the new tour length 

72 h[y] += 1 # update frequency of the tour length of the current solution 

73 h[y2] += 1 # update frequency of the tour length of the new solution 

74 if h[y2] <= h[y]: # this move does not make the frequency worse? 

75 # so we reverse the sequence from i to j in the solution 

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

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

78 else: # the normal case that i > 0 

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

80 return y2 # return new tour length 

81 return y # return old tour length 

82 

83 

84class TSPFEA1p1revn(Algorithm): 

85 """A (1+1) FEA using the reversal operator for the TSP.""" 

86 

87 def __init__(self, instance: Instance, 

88 do_log_h: bool = False) -> None: 

89 """ 

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

91 

92 :param instance: the problem instance 

93 :param do_log_h: shall we log the `h`-table? 

94 """ 

95 super().__init__() 

96 if not isinstance(instance, Instance): 

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

98 #: the instance 

99 self.instance: Final[Instance] = instance 

100 #: shall we log the `h`-table`? 

101 self.do_log_h: Final[bool] = do_log_h 

102 

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

104 """ 

105 Apply a (1+1) FEA optimization process with reversing operator. 

106 

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

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

109 as the termination criterion 

110 """ 

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

112 # set up the fast calls 

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

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

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

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

117 

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

119 h: Final[np.ndarray] = np.zeros( # allocate the frequency table 

120 instance.tour_length_upper_bound + 1, DEFAULT_INT) 

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

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

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

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

125 

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

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

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

129 while not should_terminate(): 

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

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

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

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

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

135 continue # either a nop or a complete reversal 

136 y = rev_if_h_not_worse(i, j, n, instance, h, x, y) # move 

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

138 

139 if self.do_log_h: 

140 # we log the frequency table at the very end of the run 

141 if h[y] == 0: 

142 h[y] = 1 

143 log_h(process, h, 0) 

144 

145 def __str__(self): 

146 """ 

147 Get the name of this algorithm. 

148 

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

150 log files. 

151 

152 :returns: "tsp_fea1p1_revn" 

153 :retval "tsp_fea1p1_revn": always 

154 """ 

155 return "tsp_fea1p1_revn" 

156 

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

158 """ 

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

160 

161 :param logger: the logger for the parameters 

162 """ 

163 super().log_parameters_to(logger) 

164 logger.key_value("doLogH", self.do_log_h) 

165 with logger.scope(SCOPE_INSTANCE) as kv: 

166 self.instance.log_parameters_to(kv)