Coverage for moptipy / evaluation / ertecdf.py: 91%

1""" 

2Approximate the ECDF over the ERT to reach certain goals. 

3 

4The empirical cumulative distribution function (ECDF, see 

5:mod:`~moptipy.evaluation.ecdf`) is a function that shows the fraction of runs 

6that were successful in attaining a certain goal objective value over the 

7time. The (empirically estimated) Expected Running Time (ERT, see 

8:mod:`~moptipy.evaluation.ert`) is a function that tries to give an estimate 

9how long a given algorithm setup will need (y-axis) to achieve given solution 

10qualities (x-axis). It uses a set of runs of the algorithm on the problem to 

11make this estimate under the assumption of independent restarts. 

12 

13Now in the ERT-ECDF we combine both concepts to join several different 

14optimization problems or problem instances into one plot. The goal becomes 

15"solving the problem". For each problem instance, we compute the ERT, i.e., 

16estimate how long a given algorithm will need to reach the goal. This becomes 

17the time axis. Over this time axis, the ERT-ECDF displays the fraction of 

18instances that were solved. 

19 

201. Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness 

21 Assignment: Making Optimization Algorithms Invariant under Bijective 

22 Transformations of the Objective Function Value. *IEEE Transactions on 

23 Evolutionary Computation* 25(2):307-319. April 2021. Preprint available at 

24 arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. http://arxiv.org/abs/2001.01416. 

25 doi: https://doi.org/10.1109/TEVC.2020.3032090 

26""" 

27 

28from dataclasses import dataclass 

29from typing import Any, Callable, Iterable 

30 

31from moptipy.evaluation.ecdf import Ecdf 

32from moptipy.evaluation.ert import compute_single_ert 

33from moptipy.evaluation.progress import Progress 

34 

35 

36@dataclass(frozen=True, init=False, order=False, eq=False) 

37class ErtEcdf(Ecdf): 

38 """The ERT-ECDF.""" 

39 

40 def time_label(self) -> str: 

41 """ 

42 Get the time axis label. 

43 

44 :return: the time key 

45 """ 

46 return f"ERT\u2009[{self.time_unit}]" 

47 

48 def _time_key(self) -> str: 

49 """ 

50 Get the time key. 

51 

52 :return: the time key 

53 """ 

54 return f"ert[{super()._time_key()}]" 

55 

56 @staticmethod 

57 def _compute_times(source: list[Progress], 

58 goal: int | float) -> list[float]: 

59 """ 

60 Compute the times for the given goals. 

61 

62 Warning: `source` must only contain progress objects that contain 

63 monotonously improving points. It must not contain runs that may get 

64 worse over time. 

65 

66 :param source: the source array 

67 :param goal: the goal value 

68 :return: a list of times 

69 """ 

70 return [compute_single_ert(source, goal)] 

71 

72 # noinspection PyUnusedLocal 

73 @staticmethod 

74 def _get_div(n: int, n_insts: int) -> int: 

75 """ 

76 Get the divisor. 

77 

78 :param n: the number of runs 

79 :param n_insts: the number of instances 

80 :return: the divisor 

81 """ 

82 del n 

83 return n_insts 

84 

85 

86def create(source: Iterable[Progress], 

87 goal_f: int | float | Callable[[str], int | float] | None = None, 

88 use_default_goal_f: bool = True) -> Ecdf: 

89 """ 

90 Create one single Ert-Ecdf record from an iterable of Progress records. 

91 

92 :param source: the set of progress instances 

93 :param goal_f: the goal objective value 

94 :param use_default_goal_f: should we use the default lower bounds as 

95 goals? 

96 :return: the Ert-Ecdf record 

97 """ 

98 return ErtEcdf._create(source, goal_f, use_default_goal_f) 

99 

100 

101def from_progresses( 

102 source: Iterable[Progress], consumer: Callable[[Ecdf], Any], 

103 f_goal: int | float | Callable[[str], int | float] 

104 | Iterable[int | float | Callable] | None = None, 

105 join_all_algorithms: bool = False, 

106 join_all_objectives: bool = False, 

107 join_all_encodings: bool = False) -> None: 

108 """ 

109 Compute one or multiple Ert-ECDFs from a stream of end results. 

110 

111 :param source: the set of progress instances 

112 :param f_goal: one or multiple goal values 

113 :param consumer: the destination to which the new records will be 

114 passed, can be the `append` method of a :class:`list` 

115 :param join_all_algorithms: should the Ecdf be aggregated over all 

116 algorithms 

117 :param join_all_objectives: should the Ecdf be aggregated over all 

118 objective functions 

119 :param join_all_encodings: should the Ecdf be aggregated over all 

120 encodings 

121 """ 

122 return ErtEcdf._from_progresses( 

123 source, consumer, f_goal, join_all_algorithms, 

124 join_all_objectives, join_all_encodings)