Coverage for moptipyapps / binpacking2d / instgen / hardness.py: 94%

1""" 

2An objective function assessing the hardness of an instance. 

3 

4>>> from moptipyapps.binpacking2d.instgen.instance_space import InstanceSpace 

5>>> orig = Instance.from_resource("a04") 

6>>> space = InstanceSpace(orig) 

7>>> print(f"{space.inst_name!r} with {space.n_different_items}/" 

8... f"{space.n_items} items with area {space.total_item_area} " 

9... f"in {space.min_bins} bins of " 

10... f"size {space.bin_width}*{space.bin_height}.") 

11'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220. 

12 

13>>> from moptipyapps.binpacking2d.instgen.inst_decoding import InstanceDecoder 

14>>> decoder = InstanceDecoder(space) 

15>>> import numpy as np 

16>>> x = np.array([ 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9, 

17... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9, 

18... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9, 

19... 0.0, 0.2, ]) 

20>>> y = space.create() 

21>>> decoder.decode(x, y) 

22>>> space.validate(y) 

23>>> res: Instance = y[0] 

24>>> print(f"{res.name!r} with {res.n_different_items}/" 

25... f"{res.n_items} items with area {res.total_item_area} " 

26... f"in {res.lower_bound_bins} bins of " 

27... f"size {res.bin_width}*{res.bin_height}.") 

28'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220. 

29 

30>>> print(space.to_str(y)) 

31a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;\ 

32441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122 

33 

34>>> hardness = Hardness(max_fes=1000) 

35>>> hardness.lower_bound() 

360.0 

37>>> hardness.upper_bound() 

381.0 

39>>> hardness.evaluate(y) 

400.6688894353015722 

41 

42>>> y[0] = orig 

43>>> hardness.evaluate(y) 

440.9298025539793962 

45 

46>>> z = Instance.from_compact_str( 

47... "cl04_020_01n;19;100;100;1,10;2,38;2,62;1,4,2;3,38;1,7;27,93;1,62;1," 

48... "3;13,38;1,38;1,17;1,45;36,62;39,3;1,2;20,10;3,24;12,4") 

49>>> hardness.evaluate(z) 

500.998823040627722 

51""" 

52from math import fsum, isfinite 

53from typing import Callable, Final, Iterable 

54 

55from moptipy.algorithms.so.rls import RLS 

56from moptipy.api.execution import Execution 

57from moptipy.api.objective import Objective 

58from moptipy.operators.signed_permutations.op0_shuffle_and_flip import ( 

59 Op0ShuffleAndFlip, 

60) 

61from moptipy.operators.signed_permutations.op1_swap_2_or_flip import ( 

62 Op1Swap2OrFlip, 

63) 

64from moptipy.spaces.signed_permutations import SignedPermutations 

65from moptipy.utils.logger import KeyValueLogSection 

66from moptipy.utils.nputils import rand_seeds_from_str 

67from pycommons.types import check_int_range 

68 

69from moptipyapps.binpacking2d.encodings.ibl_encoding_1 import ( 

70 ImprovedBottomLeftEncoding1, 

71) 

72from moptipyapps.binpacking2d.instance import ( 

73 Instance, 

74) 

75from moptipyapps.binpacking2d.objectives.bin_count import BinCount 

76from moptipyapps.binpacking2d.objectives.bin_count_and_last_skyline import ( 

77 BinCountAndLastSkyline, 

78) 

79from moptipyapps.binpacking2d.packing_space import PackingSpace 

80 

81 

82def setup_rls_f7(instance: Instance) -> tuple[Execution, Objective]: 

83 """ 

84 Set up the randomized local search for an instance. 

85 

86 :param instance: the instance 

87 :return: the execution and upper bound of the objective 

88 """ 

89 search_space = SignedPermutations( 

90 instance.get_standard_item_sequence()) # Create the search space. 

91 solution_space = PackingSpace(instance) # Create the space of packings. 

92 objective: Final[BinCountAndLastSkyline] = BinCountAndLastSkyline(instance) 

93 

94 # Build a single execution of a single run of a single algorithm and 

95 # return the upper bound of the objective value 

96 return (Execution() 

97 .set_search_space(search_space) 

98 .set_solution_space(solution_space) 

99 .set_encoding(ImprovedBottomLeftEncoding1(instance)) 

100 .set_algorithm( # This is the algorithm: Randomized Local Search. 

101 RLS(Op0ShuffleAndFlip(search_space), Op1Swap2OrFlip())) 

102 .set_objective(objective), objective) 

103 

104 

105def setup_rls_f1(instance: Instance) -> tuple[Execution, Objective]: 

106 """ 

107 Set up the randomized local search for an instance. 

108 

109 :param instance: the instance 

110 :return: the execution 

111 """ 

112 search_space = SignedPermutations( 

113 instance.get_standard_item_sequence()) # Create the search space. 

114 solution_space = PackingSpace(instance) # Create the space of packings. 

115 objective: Final[BinCount] = BinCount(instance) 

116 

117 # Build a single execution of a single run of a single algorithm and 

118 # return the lower bound of the objective value 

119 return (Execution() 

120 .set_search_space(search_space) 

121 .set_solution_space(solution_space) 

122 .set_encoding(ImprovedBottomLeftEncoding1(instance)) 

123 .set_algorithm( # This is the algorithm: Randomized Local Search. 

124 RLS(Op0ShuffleAndFlip(search_space), Op1Swap2OrFlip())) 

125 .set_objective(objective), objective) 

126 

127 

128#: the default executors 

129DEFAULT_EXECUTORS: Final[tuple[Callable[[Instance], tuple[ 

130 Execution, Objective]], ...]] = (setup_rls_f1, setup_rls_f7) 

131 

132 

133class Hardness(Objective): 

134 """Compute the hardness of an instance.""" 

135 

136 def __init__( 

137 self, max_fes: int = 1_000_000, n_runs: int = 3, 

138 executors: Iterable[Callable[[Instance], tuple[ 

139 Execution, Objective]]] = DEFAULT_EXECUTORS) -> None: 

140 """ 

141 Initialize the hardness objective function. 

142 

143 :param max_fes: the maximum FEs 

144 :param n_runs: the maximum runs 

145 :param executors: the functions creating the executions 

146 """ 

147 super().__init__() 

148 #: the maximum FEs per setup. 

149 self.max_fes: Final[int] = check_int_range( 

150 max_fes, "max_fes", 2, 1_000_000_000_000) 

151 #: the maximum FEs per setup. 

152 self.n_runs: Final[int] = check_int_range( 

153 n_runs, "n_runs", 1, 1_000_000) 

154 #: the executors 

155 self.executors: Final[tuple[Callable[[Instance], tuple[ 

156 Execution, Objective]], ...]] = tuple(executors) 

157 

158 #: the last instance name 

159 self.__last_inst: str | None = None 

160 #: the last seeds name 

161 self.__last_seeds: tuple[int, ...] | None = None 

162 #: the internal results list 

163 self.__results: Final[list[float]] = [] 

164 

165 def evaluate(self, x: list[Instance] | Instance) -> float: 

166 """ 

167 Compute the hardness of an instance. 

168 

169 :param x: the instance 

170 :return: the hardness 

171 """ 

172 instance: Final[Instance] = x[0] if isinstance(x, list) else x 

173 seeds: tuple[int, ...] 

174 

175 name: str = instance.name 

176 if (self.__last_seeds is None) or (self.__last_inst is None) or ( 

177 self.__last_inst != name): 

178 self.__last_seeds = seeds = tuple(rand_seeds_from_str( 

179 f"seed for {instance.name}", self.n_runs)) 

180 self.__last_inst = name 

181 else: 

182 seeds = self.__last_seeds 

183 

184 max_fes: Final[int] = self.max_fes 

185 runs: int = 0 

186 results: Final[list[float]] = self.__results 

187 results.clear() 

188 for executor in self.executors: 

189 execs, f = executor(instance) 

190 lb: int | float = f.lower_bound() 

191 ub: int | float = f.upper_bound() 

192 if not (isfinite(lb) and isfinite(ub) and (lb < ub)): 

193 raise ValueError(f"Invalid lower and upper bound {lb}, {ub}.") 

194 execs.set_max_fes(max_fes) 

195 for seed in seeds: 

196 execs.set_rand_seed(seed) 

197 with execs.execute() as proc: 

198 runs += 1 

199 quality: int | float = proc.get_best_f() 

200 if not (isfinite(quality) and (lb <= quality <= ub)): 

201 raise ValueError( 

202 f"quality={quality} invalid, must be in " 

203 f"[{lb}, {ub}] for objective {f}.") 

204 runtime: int | float = proc.get_last_improvement_fe() 

205 if not (0 < runtime <= max_fes): 

206 raise ValueError(f"invalid FEs {runtime}, must " 

207 f"be in 1..{max_fes}.") 

208 runtime = (max_fes - runtime) / max_fes 

209 if not (0.0 <= runtime < 1.0): 

210 raise ValueError( 

211 f"invalid normalized runtime {runtime}.") 

212 quality = ((ub - quality) + runtime) / (ub - lb + 1) 

213 if not (0.0 <= quality <= 1.0): 

214 raise ValueError( 

215 f"invalid normalized quality {quality} " 

216 f"for objective {f}.") 

217 results.append(quality ** 4) 

218 ret: Final[float] = max(0.0, min(1.0, fsum(results) / runs)) 

219 results.clear() 

220 return ret 

221 

222 def lower_bound(self) -> float: 

223 """ 

224 Get the lower bound of the instance hardness. 

225 

226 :return: the lower bound for the instance hardness 

227 :returns 0.0: always 

228 """ 

229 return 0.0 

230 

231 def upper_bound(self) -> float: 

232 """ 

233 Get the upper bound of the instance hardness. 

234 

235 :return: the upper bound for the instance hardness 

236 :returns 1.0: always 

237 """ 

238 return 1.0 

239 

240 def is_always_integer(self) -> bool: 

241 """ 

242 Return `False` because the hardness function returns `float`. 

243 

244 :retval False: always 

245 """ 

246 return False 

247 

248 def __str__(self) -> str: 

249 """ 

250 Get the name of the hardness objective function. 

251 

252 :return: `hardness` 

253 :retval "hardness": always 

254 """ 

255 return "hardness" 

256 

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

258 """ 

259 Log the parameters of this instance. 

260 

261 :param logger: the logger 

262 """ 

263 super().log_parameters_to(logger) 

264 logger.key_value("nRuns", self.n_runs) 

265 logger.key_value("maxFEs", self.max_fes) 

266 logger.key_value("nExecutors", len(self.executors))