Coverage for moptipyapps / tests / on_tsp.py: 63%

1"""Perform tests on the Traveling Salesperson Problem.""" 

2 

3from time import monotonic_ns 

4from typing import Callable, Final, Iterable 

5 

6import numpy as np 

7from moptipy.api.algorithm import Algorithm 

8from moptipy.api.objective import Objective 

9from moptipy.spaces.permutations import Permutations 

10from moptipy.tests.algorithm import validate_algorithm 

11from moptipy.tests.objective import validate_objective 

12from numpy.random import Generator, default_rng 

13from pycommons.types import type_error 

14 

15from moptipyapps.tsp.instance import Instance 

16from moptipyapps.tsp.tour_length import TourLength 

17 

18#: the internal random number generator 

19__RANDOM: Final[Generator] = default_rng() 

20 

21 

22def tsp_instances_for_tests( 

23 random: Generator = __RANDOM, 

24 symmetric: bool = True, 

25 asymmetric: bool = True) -> Iterable[str]: 

26 """ 

27 Get a sequence of TSP instances to test on. 

28 

29 :param random: the random number generator to use 

30 :param symmetric: include symmetric instances 

31 :param asymmetric: include asymmetric instances 

32 :returns: an iterable of TSP instance names 

33 """ 

34 if not isinstance(symmetric, bool): 

35 raise type_error(symmetric, "symmetric", bool) 

36 if not isinstance(asymmetric, bool): 

37 raise type_error(asymmetric, "asymmetric", bool) 

38 

39 instances: tuple[str, ...] 

40 if symmetric and asymmetric: 

41 instances = Instance.list_resources(True, True) 

42 elif symmetric: 

43 instances = Instance.list_resources(True, False) 

44 elif asymmetric: 

45 instances = Instance.list_resources(False, True) 

46 else: 

47 raise ValueError( 

48 "at least of one symmetric or asymmetric must be TRUE") 

49 use_insts = list(instances) 

50 while len(use_insts) > 20: 

51 del use_insts[random.integers(len(use_insts))] 

52 random.shuffle(use_insts) 

53 return use_insts 

54 

55 

56def make_tour_valid(random: Generator, y: np.ndarray) -> np.ndarray: 

57 """ 

58 Create valid TSP tours. 

59 

60 :param random: the random number generator to use 

61 :param y: the input tour 

62 :returns: the valid version of `y` 

63 """ 

64 y[0:len(y)] = range(len(y)) 

65 random.shuffle(y) 

66 return y 

67 

68 

69def make_tour_invalid(random: Generator, y: np.ndarray) -> np.ndarray: 

70 """ 

71 Create invalid tours. 

72 

73 :param random: the random number generator to use 

74 :param y: the input tour 

75 :returns: the invalid version of `y` 

76 """ 

77 ly: Final[int] = len(y) 

78 y[0:ly] = range(ly) 

79 random.shuffle(y) 

80 yorig = np.copy(y) 

81 

82 ri = random.integers 

83 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

84 while np.all(y == yorig): 

85 if monotonic_ns() >= end_time: 

86 y[0] = y[1] 

87 return y 

88 if ri(2) <= 0: 

89 z1 = z2 = ri(ly) 

90 while z1 == z2: 

91 if monotonic_ns() >= end_time: 

92 y[0] = y[1] 

93 return y 

94 z2 = ri(ly) 

95 y[z1] = y[z2] 

96 if ri(2) <= 0: 

97 y[ri(ly)] = ri(ly, 10 * ly) 

98 if ri(2) <= 0: 

99 y[ri(ly)] = ri(-2 * ly, -1) 

100 return y 

101 

102 

103def validate_algorithm_on_1_tsp( 

104 algorithm: Algorithm | Callable[ 

105 [Instance, Permutations], Algorithm], 

106 instance: str | None = None, max_fes: int = 256, 

107 random: Generator = __RANDOM) -> None: 

108 """ 

109 Check the validity of a black-box algorithm on one TSP instance. 

110 

111 :param algorithm: the algorithm or algorithm factory 

112 :param instance: the instance name, or `None` to randomly pick one 

113 :param max_fes: the maximum number of FEs 

114 :param random: the default random generator to use 

115 """ 

116 if not (isinstance(algorithm, Algorithm) or callable(algorithm)): 

117 raise type_error(algorithm, "algorithm", Algorithm, True) 

118 if instance is None: 

119 instance = str(random.choice(Instance.list_resources())) 

120 if not isinstance(instance, str): 

121 raise type_error(instance, "TSP instance name", (str, None)) 

122 inst = Instance.from_resource(instance) 

123 if not isinstance(inst, Instance): 

124 raise type_error(inst, f"loaded bin TSP instance {instance!r}", 

125 Instance) 

126 

127 search_space = Permutations.standard(inst.n_cities) 

128 objective = TourLength(inst) 

129 if callable(algorithm): 

130 algorithm = algorithm(inst, search_space) 

131 if not isinstance(algorithm, Algorithm): 

132 raise type_error(algorithm, "algorithm", Algorithm, call=True) 

133 

134 validate_algorithm(algorithm=algorithm, 

135 solution_space=search_space, 

136 objective=objective, 

137 max_fes=max_fes) 

138 

139 

140def validate_algorithm_on_tsp( 

141 algorithm: Callable[[Instance, Permutations], Algorithm], 

142 symmetric: bool = True, asymmetric: bool = True, 

143 max_fes: int = 256, random: Generator = __RANDOM) -> None: 

144 """ 

145 Validate an algorithm on a set of TSP instances. 

146 

147 :param algorithm: the algorithm factory 

148 :param symmetric: include symmetric instances 

149 :param asymmetric: include asymmetric instances 

150 :param max_fes: the maximum FEs 

151 :param random: the random number generator 

152 """ 

153 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

154 for i in tsp_instances_for_tests(random, symmetric, asymmetric): 

155 if monotonic_ns() >= end_time: 

156 return 

157 validate_algorithm_on_1_tsp(algorithm, i, max_fes, random) 

158 

159 

160def validate_objective_on_1_tsp( 

161 objective: Objective | Callable[[Instance], Objective], 

162 instance: str | None = None, 

163 random: Generator = __RANDOM) -> None: 

164 """ 

165 Validate an objective function on 1 TSP instance. 

166 

167 :param objective: the objective function or a factory creating it 

168 :param instance: the instance name 

169 :param random: the random number generator 

170 """ 

171 if instance is None: 

172 instance = str(random.choice(Instance.list_resources())) 

173 if not isinstance(instance, str): 

174 raise type_error(instance, "TSP instance name", (str, None)) 

175 inst = Instance.from_resource(instance) 

176 if not isinstance(inst, Instance): 

177 raise type_error(inst, f"loaded TSP instance {instance!r}", 

178 Instance) 

179 

180 if callable(objective): 

181 objective = objective(inst) 

182 

183 validate_objective( 

184 objective=objective, 

185 solution_space=Permutations.standard(inst.n_cities), 

186 make_solution_space_element_valid=make_tour_valid, 

187 is_deterministic=True) 

188 

189 

190def validate_objective_on_tsp( 

191 objective: Objective | Callable[[Instance], Objective], 

192 symmetric: bool = True, asymmetric: bool = True, 

193 random: Generator = __RANDOM) -> None: 

194 """ 

195 Validate an objective function on TSP instances. 

196 

197 :param objective: the objective function or a factory creating it 

198 :param symmetric: include symmetric instances 

199 :param asymmetric: include asymmetric instances 

200 :param random: the random number generator 

201 """ 

202 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

203 for i in tsp_instances_for_tests(random, symmetric, asymmetric): 

204 if monotonic_ns() >= end_time: 

205 return 

206 validate_objective_on_1_tsp(objective, i, random)