comocma.nondominatedarchive

11 """ 12 A list of objective values in an empirical Pareto front, 13 meaning that no point strictly domminates another one in all 14 objectives. 15 16 >>> from nondominatedarchive import NonDominatedList 17 >>> a = NonDominatedList([[1,0.9], [0,1], [0,2]], [2, 2]) 18 """ 19

20 - def __init__(self, 21 list_of_f_tuples=None, 22 reference_point=None):

23 """ 24 elements of list_of_f_tuples not in the empirical front are pruned away 25 `reference_point` is also used to compute the hypervolume, with the hv 26 module of Simon Wessing. 27 28 """ 29 if list_of_f_tuples is not None and len(list_of_f_tuples): 30 try: 31 list_of_f_tuples = [tuple(e) for e in list_of_f_tuples] 32 except: 33 pass 34 list.__init__(self, list_of_f_tuples) 35 36 if reference_point is not None: 37 self.reference_point = list(reference_point) 38 else: 39 self.reference_point = reference_point 40 self.prune() # remove dominated entries, uses self.dominates 41 self._hypervolume = None 42 self._kink_points = None

43

44 - def add(self, f_tuple):

45 """add `f_tuple` in `self` if it is not dominated in all objectives. 46 """ 47 f_tuple = tuple(f_tuple) # convert array to list 48 49 if not self.dominates(f_tuple): 50 self.append(f_tuple) 51 self._hypervolume = None 52 self._kink_points = None 53 self.prune()

54

55 - def remove(self, f_tuple):

56 """remove element `f_pair`. 57 58 Raises a `ValueError` (like `list`) if ``f_pair is not in self``. 59 To avoid the error, checking ``if f_pair is in self`` first is a 60 possible coding solution, like 61 62 >>> from moarchiving import BiobjectiveNondominatedSortedList 63 >>> nda = BiobjectiveNondominatedSortedList([[2, 3]]) 64 >>> f_pair = [1, 2] 65 >>> assert [2, 3] in nda and f_pair not in nda 66 >>> if f_pair in nda: 67 ... nda.remove(f_pair) 68 >>> nda = BiobjectiveNondominatedSortedList._random_archive(p_ref_point=1) 69 >>> for pair in list(nda): 70 ... len_ = len(nda) 71 ... state = nda._state() 72 ... nda.remove(pair) 73 ... assert len(nda) == len_ - 1 74 ... if 100 * pair[0] - int(100 * pair[0]) < 0.7: 75 ... res = nda.add(pair) 76 ... assert all(state[i] == nda._state()[i] for i in [0, 2, 3]) 77 78 Return `None` (like `list.remove`). 79 """ 80 f_tuple = tuple(f_tuple) # convert array to list 81 list.remove(self, f_tuple) 82 self._hypervolume = None 83 self._kink_points = None

84 85

86 - def add_list(self, list_of_f_tuples):

87 """ 88 add list of f_tuples, not using the add method to avoid calling 89 self.prune() several times. 90 """ 91 for f_tuple in list_of_f_tuples: 92 f_tuple = tuple(f_tuple) 93 if not self.dominates(f_tuple): 94 self.append(f_tuple) 95 self._hypervolume = None 96 self._kink_points = None 97 self.prune()

98

99 - def prune(self):

100 """ 101 remove point dominated by another one in all objectives. 102 """ 103 for f_tuple in self: 104 if not self.in_domain(f_tuple): 105 list.remove(self, f_tuple) 106 i = 0 107 length = len(self) 108 while i < length: 109 for idx in range(len(self)): 110 if self[idx] == self[i]: 111 continue 112 if self.dominates_with(idx, self[i]): 113 del self[i] 114 i -= 1 115 length -= 1 116 break 117 i += 1

118 119

120 - def dominates(self, f_tuple):

121 """return `True` if any element of `self` dominates or is equal to `f_tuple`. 122 123 Otherwise return `False`. 124 125 >>> from nondominatedarchive import NonDominatedList as NDA 126 >>> a = NDA([[0.39, 0.075], [0.0087, 0.14]]) 127 >>> a.dominates(a[0]) # is always True if `a` is not empty 128 True 129 >>> a.dominates([-1, 33]) or a.dominates([33, -1]) 130 False 131 >>> a._asserts() 132 133 """ 134 if len(self) == 0: 135 return False 136 for idx in range(len(self)): 137 if self.dominates_with(idx, f_tuple): 138 return True 139 return False

140

141 - def dominates_with(self, idx, f_tuple):

142 """return `True` if ``self[idx]`` dominates or is equal to `f_tuple`. 143 144 Otherwise return `False` or `None` if `idx` is out-of-range. 145 146 >>> from nondominatedarchive import NonDominatedList as NDA 147 >>> NDA().dominates_with(0, [1, 2]) is None # empty NDA 148 True 149 150 :todo: add more doctests that actually test the functionality and 151 not only whether the return value is correct if empty 152 153 """ 154 if self is None or idx < 0 or idx >= len(self): 155 return None 156 return self.dominates_with_for(idx, f_tuple)

157

158 - def dominates_with_old(self, idx, f_tuple):

159 ''' deprecated code, now taken over by dominates_wit_for ''' 160 if all(self[idx][k] <= f_tuple[k] for k in range(len(f_tuple))): 161 return True 162 return False

163

164 - def dominates_with_for(self, idx, f_tuple):

165 ''' returns true if self[idx] weakly dominates f_tuple 166 167 replaces dominates_with_old because it turned out 168 to run quicker 169 ''' 170 for k in range(len(f_tuple)): 171 if self[idx][k] > f_tuple[k]: 172 return False 173 else: # yes, indentation is correct, else is not quite necessary in this case 174 return True

175 176

177 - def dominators(self, f_tuple, number_only=False):

178 """return the list of all `f_tuple`-dominating elements in `self`, 179 180 including an equal element. ``len(....dominators(...))`` is 181 hence the number of dominating elements which can also be obtained 182 without creating the list with ``number_only=True``. 183 184 >>> from nondominatedarchive import NonDominatedList as NDA 185 >>> a = NDA([[1.2, 0.1], [0.5, 1]]) 186 >>> len(a) 187 2 188 >>> a.dominators([2, 3]) == a 189 True 190 >>> a.dominators([0.5, 1]) 191 [(0.5, 1)] 192 >>> len(a.dominators([0.6, 3])), a.dominators([0.6, 3], number_only=True) 193 (1, 1) 194 >>> a.dominators([0.5, 0.9]) 195 [] 196 197 """ 198 res = 0 if number_only else [] 199 for idx in range(len(self)): 200 if self.dominates_with(idx, f_tuple): 201 if number_only: 202 res += 1 203 else: 204 res += [self[idx]] 205 return res

206

207 - def in_domain(self, f_tuple, reference_point=None):

208 """return `True` if `f_tuple` is dominating the reference point, 209 210 `False` otherwise. `True` means that `f_tuple` contributes to 211 the hypervolume if not dominated by other elements. 212 213 `f_tuple` may also be an index in `self` in which case 214 ``self[f_tuple]`` is tested to be in-domain. 215 216 >>> from nondominatedarchive import NonDominatedList as NDA 217 >>> a = NDA([[2.2, 0.1], [0.5, 1]], reference_point=[2, 2]) 218 >>> assert len(a) == 1 219 >>> a.in_domain([0, 0]) 220 True 221 >>> a.in_domain([2, 1]) 222 False 223 >>> all(a.in_domain(ai) for ai in a) 224 True 225 >>> a.in_domain(0) 226 True 227 228 TODO: improve name? 229 """ 230 if reference_point is None: 231 reference_point = self.reference_point 232 if reference_point is None: 233 return True 234 try: 235 f_tuple = self[f_tuple] 236 except TypeError: 237 pass 238 except IndexError: 239 raise # return None 240 if any(f_tuple[k] >= reference_point[k] for k in range(len(reference_point))): 241 return False 242 return True

243

244 - def _strictly_dominates(self, f_tuple):

245 """return `True` if any element of `self` strictly dominates `f_tuple`. 246 247 Otherwise return `False`. 248 249 >>> from nondominatedarchive import NonDominatedList as NDA 250 >>> a = NDA([[0.39, 0.075], [0.0087, 0.14]]) 251 >>> a.dominates(a[0]) # is always True if `a` is not empty 252 True 253 >>> a.dominates([-1, 33]) or a.dominates([33, -1]) 254 False 255 >>> a._asserts() 256 257 """ 258 if len(self) == 0: 259 return False 260 for idx in range(len(self)): 261 if self._strictly_dominates_with(idx, f_tuple): 262 return True 263 return False

264

265 - def _strictly_dominates_with(self, idx, f_tuple):

266 """return `True` if ``self[idx]`` strictly dominates `f_tuple`. 267 268 Otherwise return `False` or `None` if `idx` is out-of-range. 269 270 >>> from nondominatedarchive import NonDominatedList as NDA 271 >>> NDA()._strictly_dominates_with(0, [1, 2]) is None # empty NDA 272 True 273 274 """ 275 if idx < 0 or idx >= len(self): 276 return None 277 if all(self[idx][k] < f_tuple[k] for k in range(len(f_tuple))): 278 return True 279 return False

280

281 - def _projection(self, f_tuple, i, x):

282 length = len(f_tuple) 283 res = length*[0] 284 res[i] = x 285 for j in range(length): 286 if j != i: 287 res[j] = f_tuple[j] 288 return res

289

290 - def _projection_to_empirical_front(self, f_tuple):

291 """ 292 return the orthogonal projections of f_tuple on the empirical front, 293 with respect to the coodinates axis. 294 """ 295 projections_loose = [] 296 dominators = self.dominators(f_tuple) 297 for point in dominators: 298 for i in range(len(f_tuple)): 299 projections_loose += [self._projection(f_tuple, i, point[i])] 300 projections = [] 301 for proj in projections_loose: 302 if not self._strictly_dominates(proj): 303 projections += [proj] 304 return projections

305 306 @property

307 - def kink_points(self):

308 """ 309 Create the 'kink' points from elements of self. 310 If f_tuple is not None, also add the projections of f_tuple 311 to the empirical front, with respect to the axes 312 """ 313 314 if self.reference_point is None: 315 raise ValueError("to compute the kink points , a reference" 316 " point is needed (for the extremal kink points)") 317 if self._kink_points is not None: 318 return self._kink_points 319 kinks_loose = [] 320 for pair in itertools.combinations(self + [self.reference_point], 2): 321 kinks_loose += [[max(x) for x in zip(pair[0], pair[1])]] 322 kinks = [] 323 for kink in kinks_loose: 324 if not self._strictly_dominates(kink): 325 kinks += [kink] 326 self._kink_points = kinks 327 return self._kink_points

328 329 @property

330 - def hypervolume(self):

331 """hypervolume of the entire list w.r.t. the "initial" reference point. 332 333 Raise `ValueError` when no reference point was given initially. 334 335 >>> from nondominatedarchive import NonDominatedList as NDA 336 >>> a = NDA([[0.5, 0.4], [0.3, 0.7]], [2, 2.1]) 337 >>> a._asserts() 338 >>> a.reference_point == [2, 2.1] 339 True 340 >>> a._asserts() 341 342 """ 343 if self.reference_point is None: 344 raise ValueError("to compute the hypervolume a reference" 345 " point is needed (must be given initially)") 346 if self._hypervolume is None: 347 hv_fraction = HyperVolume(self.reference_point) 348 self._hypervolume = hv_fraction.compute(self) 349 return self._hypervolume

350

351 - def contributing_hypervolume(self, f_tuple):

352 """ 353 Hypervolume improvement of f_tuple with respect to self. 354 TODO: the argument should be an index, as in moarchiving. 355 """ 356 if self.reference_point is None: 357 raise ValueError("to compute the hypervolume a reference" 358 " point is needed (must be given initially)") 359 hv_fraction = HyperVolume(self.reference_point) 360 res1 = hv_fraction.compute(self + [f_tuple]) 361 res2 = self._hypervolume or hv_fraction.compute(self) 362 return res1 - res2

363

364 - def distance_to_pareto_front(self, f_tuple):

365 """ 366 Compute the distance of a dominated f_tuple to the empirical Pareto front. 367 """ 368 if self.reference_point is None: 369 raise ValueError("to compute the distance to the empirical front" 370 " a reference point is needed (was `None`)") 371 if len(self) == 0: 372 return sum([max(0, f_tuple[k] - self.reference_point[k])**2 373 for k in range(len(f_tuple)) ])**0.5 374 if not self.dominates(f_tuple): 375 if self.in_domain(f_tuple): 376 return 0 377 return sum([max(0, f_tuple[k] - self.reference_point[k])**2 378 for k in range(len(f_tuple)) ])**0.5 379 squared_distances = [] 380 for kink in self.kink_points: 381 squared_distances += [sum( (f_tuple[k] - kink[k])**2 for k in range( 382 len(f_tuple)) )] 383 for proj in self._projection_to_empirical_front(f_tuple): 384 squared_distances += [sum( (f_tuple[k] - proj[k])**2 for k in range( 385 len(f_tuple)) )] 386 return min(squared_distances)**0.5

387

388 - def hypervolume_improvement(self, f_tuple):

389 """return how much `f_tuple` would improve the hypervolume. 390 391 If dominated, return the distance to the empirical pareto front 392 multiplied by -1. 393 Else if not in domain, return distance to the reference point 394 dominating area times -1. 395 """ 396 contribution = self.contributing_hypervolume(f_tuple) 397 assert contribution >= 0 398 if contribution: 399 return contribution 400 return -self.distance_to_pareto_front(f_tuple)

401 402 @staticmethod

403 - def _random_archive(max_size=500, p_ref_point=0.5):

404 from numpy import random as npr 405 N = npr.randint(max_size) 406 ref_point = list(npr.randn(2) + 1) if npr.rand() < p_ref_point else None 407 return NonDominatedList( 408 [list(0.01 * npr.randn(2) + npr.rand(1) * [i, -i]) 409 for i in range(N)], 410 reference_point=ref_point)

411 412 @staticmethod

413 - def _random_archive_many(k, max_size=500, p_ref_point=0.5):

414 from numpy import random as npr 415 N = npr.randint(max_size) 416 ref_point = list(npr.randn(k) + 1) if npr.rand() < p_ref_point else None 417 return NonDominatedList( 418 [list(0.01 * npr.randn(k) + i*(2*npr.rand(k)-1)) 419 for i in range(N)], 420 reference_point=ref_point)

421

422 - def _asserts(self):

423 """make all kind of consistency assertions. 424 425 >>> import nondominatedarchive 426 >>> a = nondominatedarchive.NonDominatedList( 427 ... [[-0.749, -1.188], [-0.557, 1.1076], 428 ... [0.2454, 0.4724], [-1.146, -0.110]], [10, 10]) 429 >>> a._asserts() 430 >>> for p in list(a): 431 ... a.remove(p) 432 >>> assert len(a) == 0 433 >>> try: a.remove([0, 0]) 434 ... except ValueError: pass 435 ... else: raise AssertionError("remove did not raise ValueError") 436 437 >>> from numpy.random import rand 438 >>> for _ in range(120): 439 ... a = nondominatedarchive.NonDominatedList._random_archive() 440 ... if a.reference_point: 441 ... for f_tuple in rand(10, 2): 442 ... h0 = a.hypervolume 443 ... hi = a.hypervolume_improvement(list(f_tuple)) 444 ... assert a.hypervolume == h0 # works OK with Fraction 445 446 >>> for _ in range(10): 447 ... for k in range(3,10): 448 ... a = nondominatedarchive.NonDominatedList._random_archive_many(k) 449 ... if a.reference_point: 450 ... for f_tuple in rand(10, k): 451 ... h0 = a.contributing_hypervolume(list(f_tuple)) 452 ... hi = a.hypervolume_improvement(list(f_tuple)) 453 ... assert h0 >= 0 454 ... assert h0 == hi or (h0 == 0 and hi < 0) 455 456 457 458 """

Source Code for Module comocma.nondominatedarchive