Coverage for moptipy / api / mo_problem.py: 85%

1""" 

2The base classes for multi-objective optimization problems. 

3 

4This class provides the ability to evaluate solutions according to multiple 

5criteria. The evaluation results are stored in a numpy array and also are 

6scalarized to a single value. 

7 

8Basically, a multi-objective problem provides three essential components: 

9 

101. It can evaluate a candidate solution according to multiple optimization 

11 objectives. Each objective returns one value, subject to minimization, 

12 and all the values are stored in a single numpy array. 

13 This is done by :meth:`~moptipy.api.mo_problem.MOProblem.f_evaluate` 

142. It provides a criterion deciding whether one such objective vector 

15 dominates (i.e., is strictly better than) another one. This is done by 

16 :meth:`~moptipy.api.mo_problem.MOProblem.f_dominates`. The default 

17 definition adheres to the standard "domination" definition in 

18 multi-objective optimization: A vector `a` dominates a vector `b` if it 

19 is not worse in any objective value and better in at least one. But if 

20 need be, you can overwrite this behavior. 

213. A scalarization approach: When evaluating a solution, the result is not 

22 just the objective vector itself, but also a single scalar value. This is 

23 needed to create compatibility to single-objective optimization. Matter of 

24 fact, a :class:`~moptipy.api.mo_problem.MOProblem` is actually a subclass 

25 of :class:`~moptipy.api.objective.Objective`. This means that via this 

26 scalarization, all multi-objective problems can also be considered as 

27 single-objective problems. This means that single-objective algorithms can 

28 be applied to them as-is. It also means that log files are compatible. 

29 Multi-objective algorithms can just ignore the scalarization result and 

30 focus on the domination relationship. Often, a weighted sum approach 

31 (:class:`~moptipy.mo.problem.weighted_sum.WeightedSum`) may be the method 

32 of choice for scalarization. 

33""" 

34from typing import Any, Final 

35 

36import numpy as np 

37from pycommons.types import type_error 

38 

39from moptipy.api.logging import KEY_SPACE_NUM_VARS, SCOPE_OBJECTIVE_FUNCTION 

40from moptipy.api.mo_utils import dominates 

41from moptipy.api.objective import Objective, check_objective 

42from moptipy.utils.logger import KeyValueLogSection 

43from moptipy.utils.nputils import ( 

44 DEFAULT_FLOAT, 

45 DEFAULT_INT, 

46 DEFAULT_UNSIGNED_INT, 

47 KEY_NUMPY_TYPE, 

48 int_range_to_dtype, 

49 numpy_type_to_str, 

50) 

51 

52 

53class MOProblem(Objective): 

54 """ 

55 The base class for multi-objective optimization problems. 

56 

57 A multi-objective optimization problem is defined as a set of 

58 :class:`~moptipy.api.objective.Objective` functions. Each candidate 

59 solution is evaluated using each of the objectives, i.e., is rated by a 

60 vector of objective values. This vector is the basis for deciding which 

61 candidate solutions to keep and which to discard. 

62 

63 In multi-objective optimization, this decision is based on "domination." 

64 A solution `a` dominates a solution `b` if it is not worse in any 

65 objective and better in at least one. This comparison behavior is 

66 implemented in method 

67 :meth:`~moptipy.api.mo_problem.MOProblem.f_dominates` and can be 

68 overwritten if need be. 

69 

70 In our implementation, we prescribe that each multi-objective optimization 

71 problem must also be accompanied by a scalarization function, i.e., a 

72 function that represents the vector of objective values as a single scalar 

73 value. The whole multi-objective problem can then be viewed also as a 

74 single objective function itself. The method 

75 :meth:`~moptipy.api.mo_problem.MOProblem.evaluate` first evaluates all of 

76 the objective functions and obtains the vector of objective values. It then 

77 scalarizes the result into a single scalar quality and returns it. 

78 Multi-objective algorithms may instead use the method 

79 :meth:`~moptipy.api.mo_problem.MOProblem.f_evaluate`, which also allows 

80 a vector to be passed in which will then be filled with the results of the 

81 individual objective functions. 

82 

83 This makes multi-objective optimization with moptipy compatible with 

84 single-objective optimization. In other words, all optimization methods 

85 implemented for single-objective processes 

86 :class:`~moptipy.api.process.Process` will work out-of-the-box with the 

87 multi-objective version :class:`~moptipy.api.mo_process.MOProcess`. 

88 

89 Warning: We use instances of :class:`numpy.ndarray` to represent the 

90 vectors of objective values. This necessitates that each objective 

91 function has, if it is integer-valued 

92 (:meth:`~moptipy.api.objective.Objective.is_always_integer` is `True`) 

93 a range that fits well into at least a 64-bit integer. Specifically, it 

94 must be possible to compute "a - b" without overflow or loss of sign for 

95 any two objective values "a" and "b" within the confines of a numpy 

96 signed 64-bit integer. 

97 """ 

98 

99 def f_create(self) -> np.ndarray: 

100 """ 

101 Create a vector to receive the objective values. 

102 

103 This array will be of the length returned by :meth:`f_dimension` and 

104 of the `dtype` of :meth:`f_dtype`. 

105 

106 :returns: a vector to receive the objective values 

107 """ 

108 return np.empty(self.f_dimension(), self.f_dtype()) 

109 

110 def f_dtype(self) -> np.dtype: 

111 """ 

112 Get the data type used in :meth:`f_create`. 

113 

114 This data type will be an integer data type if all the objective 

115 functions are integer-valued. If the bounds of the objective values 

116 are known, then this type will be "big enough" to allow the 

117 subtraction "a - b" of any two objective vectors "a" and "b" to be 

118 computed without overflow or loss of sign. At most, however, this 

119 data type will be a 64-bit integer. 

120 If any one of the objective functions returns floating point data, 

121 this data type will be a floating point type. 

122 

123 :returns: the data type used by :meth:`f_create`. 

124 """ 

125 

126 def f_dimension(self) -> int: 

127 """ 

128 Obtain the number of objective functions. 

129 

130 :returns: the number of objective functions 

131 """ 

132 

133 def f_validate(self, x: np.ndarray) -> None: 

134 """ 

135 Validate the objective vector. 

136 

137 :param x: the numpy vector 

138 :raises TypeError: if the string is not an element of this space. 

139 :raises ValueError: if the shape of the vector is wrong or any of its 

140 element is not finite. 

141 """ 

142 if not isinstance(x, np.ndarray): 

143 raise TypeError(x, "x", np.ndarray) 

144 shape = x.shape 

145 if len(shape) != 1: 

146 raise ValueError( 

147 f"{x} cannot have more than one dimension, but has {shape}!") 

148 dim = self.f_dimension() # pylint: disable=E1111 

149 if shape[0] != dim: 

150 raise ValueError( 

151 f"{x} should have length {dim} but has {shape[0]}!") 

152 dt = self.f_dtype() # pylint: disable=E1111 

153 if x.dtype != dt: 

154 raise ValueError(f"{x} should have dtype {dt} but has {x.dtype}!") 

155 

156 def f_evaluate(self, x, fs: np.ndarray) -> int | float: 

157 """ 

158 Perform the multi-objective evaluation of a solution. 

159 

160 This method fills the objective vector `fs` with the results of the 

161 objective functions evaluated on `x`. It then returns the scalarized 

162 result, i.e., a single scalar value computed based on all values 

163 in `fs`. 

164 

165 :param x: the solution to be evaluated 

166 :param fs: the array to receive the objective values 

167 :returns: the scalarization result 

168 """ 

169 

170 # noinspection PyMethodMayBeStatic 

171 def f_dominates(self, a: np.ndarray, b: np.ndarray) -> int: 

172 """ 

173 Check if an objective vector dominates or is dominated by another one. 

174 

175 Usually, one vector is said to dominate another one if it is not worse 

176 in any objective and better in at least one. This behavior is 

177 implemented in :func:`moptipy.api.mo_utils.dominates` and this is also 

178 the default behavior of this method. However, depending on your 

179 concrete optimization task, you may overwrite this behavior. 

180 

181 :param a: the first objective vector 

182 :param b: the second objective value 

183 :returns: an integer value indicating the domination relationship 

184 :retval -1: if `a` dominates `b` 

185 :retval 1: if `b` dominates `a` 

186 :retval 2: if `b` equals `a` 

187 :retval 0: if `a` and `b` are mutually non-dominated, i.e., if neither 

188 `a` dominates `b` not `b` dominates `a` and `b` is also different 

189 from `a` 

190 """ 

191 return dominates(a, b) 

192 

193 def evaluate(self, x) -> float | int: 

194 """ 

195 Evaluate a solution `x` and return its scalarized objective value. 

196 

197 This method computes all objective values for a given solution and 

198 then returns the scalarized result. The objective values themselves 

199 are directly discarted and not used. It makes a multi-objective 

200 problem compatible with single-objective optimization. 

201 

202 :param x: the candidate solution 

203 :returns: the scalarized objective value 

204 """ 

205 return self.f_evaluate(x, self.f_create()) 

206 

207 def __str__(self) -> str: 

208 """ 

209 Get the string representation of this multi-objective problem. 

210 

211 :returns: the string representation of this multi-objective problem 

212 """ 

213 return "moProblem" 

214 

215 

216def check_mo_problem(mo_problem: Any) -> MOProblem: 

217 """ 

218 Check whether an object is a valid instance of :class:`MOProblem`. 

219 

220 :param mo_problem: the multi-objective optimization problem 

221 :return: the mo-problem 

222 :raises TypeError: if `mo_problem` is not an instance of 

223 :class:`MOProblem` 

224 

225 >>> check_mo_problem(MOProblem()) 

226 moProblem 

227 >>> try: 

228 ... check_mo_problem(1) 

229 ... except TypeError as te: 

230 ... print(te) 

231 multi-objective optimziation problem should be an instance of moptipy.\ 

232api.mo_problem.MOProblem but is int, namely 1. 

233 

234 >>> try: 

235 ... check_mo_problem(None) 

236 ... except TypeError as te: 

237 ... print(te) 

238 multi-objective optimziation problem should be an instance of moptipy.\ 

239api.mo_problem.MOProblem but is None. 

240 """ 

241 if isinstance(mo_problem, MOProblem): 

242 return mo_problem 

243 raise type_error(mo_problem, 

244 "multi-objective optimziation problem", MOProblem) 

245 

246 

247class MOSOProblemBridge(MOProblem): 

248 """A bridge between multi-objective and single-objective optimization.""" 

249 

250 def __init__(self, objective: Objective) -> None: 

251 """Initialize the bridge.""" 

252 super().__init__() 

253 check_objective(objective) 

254 

255 self.evaluate = objective.evaluate # type: ignore 

256 self.lower_bound = objective.lower_bound # type: ignore 

257 self.upper_bound = objective.upper_bound # type: ignore 

258 self.is_always_integer = objective.is_always_integer # type: ignore 

259 

260 dt: np.dtype 

261 if self.is_always_integer(): 

262 lb: int | float = self.lower_bound() 

263 ub: int | float = self.upper_bound() 

264 dt = DEFAULT_INT 

265 if isinstance(lb, int): 

266 if isinstance(ub, int): 

267 dt = int_range_to_dtype(lb, ub) 

268 elif lb >= 0: 

269 dt = DEFAULT_UNSIGNED_INT 

270 else: 

271 dt = DEFAULT_FLOAT 

272 

273 #: the data type of the objective array 

274 self.__dtype: Final[np.dtype] = dt 

275 #: the objective function 

276 self.__f: Final[Objective] = objective 

277 self.f_create = lambda dd=dt: np.empty(1, dd) # type: ignore 

278 self.f_dimension = lambda: 1 # type: ignore 

279 

280 def initialize(self) -> None: 

281 """Initialize the MO-problem bridge.""" 

282 super().initialize() 

283 self.__f.initialize() 

284 

285 def f_evaluate(self, x, fs: np.ndarray) -> int | float: 

286 """ 

287 Evaluate the candidate solution. 

288 

289 :param x: the solution 

290 :param fs: the objective vector, will become `[res]` 

291 :returns: the objective value `res` 

292 """ 

293 res: Final[int | float] = self.evaluate(x) 

294 fs[0] = res 

295 return res 

296 

297 def f_dtype(self) -> np.dtype: 

298 """Get the objective vector dtype.""" 

299 return self.__dtype 

300 

301 def f_validate(self, x: np.ndarray) -> None: 

302 """ 

303 Validate the objective vector. 

304 

305 :param x: the numpy array with the objective values 

306 """ 

307 if not isinstance(x, np.ndarray): 

308 raise type_error(x, "x", np.ndarray) 

309 if len(x) != 1: 

310 raise ValueError(f"length of x={len(x)}") 

311 lb = self.lower_bound() 

312 ub = self.upper_bound() 

313 if not (lb <= x[0] <= ub): 

314 raise ValueError(f"failed: {lb} <= {x[0]} <= {ub}") 

315 

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

317 """ 

318 Log the parameters of this function to the provided destination. 

319 

320 :param logger: the logger for the parameters 

321 """ 

322 super().log_parameters_to(logger) 

323 logger.key_value(KEY_SPACE_NUM_VARS, "1") 

324 logger.key_value(KEY_NUMPY_TYPE, numpy_type_to_str(self.__dtype)) 

325 with logger.scope(f"{SCOPE_OBJECTIVE_FUNCTION}{0}") as scope: 

326 self.__f.log_parameters_to(scope)