Coverage for moptipy / algorithms / so / ffa / ffa_fitness.py: 94%

1""" 

2The Frequency Fitness Assignment (FFA) Process. 

3 

4Frequency Fitness Assignment (FFA) replaces all objective values with their 

5encounter frequencies in the selection decisions. The more often an 

6objective value is encountered, the higher gets its encounter frequency. 

7Therefore, local optima are slowly receiving worse and worse fitness. 

8 

9Notice that this implementation of FFA has a slight twist to it: 

10It will incorporate the iteration index 

11(:attr:`~moptipy.algorithms.so.record.Record.it`) of the solutions 

12into the fitness. 

13This index is used to break ties, in which case newer solutions are preferred. 

14 

15This can make the EA with FFA compatible with the 

16:class:`moptipy.algorithms.so.ffa.fea1plus1.FEA1plus1` if "best" selection 

17(:class:`moptipy.algorithms.modules.selections.best.Best`) is used 

18at mu=lambda=1. 

19To facilitate this, there is one special case in the FFA fitness assignment: 

20If the population consists of exactly 1 element at iteration index 0, then 

21the frequency values are not updated. 

22 

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

24 Assignment: Making Optimization Algorithms Invariant under Bijective 

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

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

27 arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. 

28 https://dx.doi.org/10.1109/TEVC.2020.3032090 

292. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency 

30 Fitness Assignment: Optimization without Bias for Good Solutions can be 

31 Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*. 

32 27(4):980-992. August 2023. 

33 doi: https://doi.org/10.1109/TEVC.2022.3191698 

343. Thomas Weise, Mingxu Wan, Ke Tang, Pu Wang, Alexandre Devert, and Xin 

35 Yao. Frequency Fitness Assignment. *IEEE Transactions on Evolutionary 

36 Computation (IEEE-EC),* 18(2):226-243, April 2014. 

37 https://dx.doi.org/10.1109/TEVC.2013.2251885 

384. Thomas Weise, Yan Chen, Xinlu Li, and Zhize Wu. Selecting a diverse set of 

39 benchmark instances from a tunable model problem for black-box discrete 

40 optimization algorithms. *Applied Soft Computing Journal (ASOC),* 

41 92:106269, June 2020. https://dx.doi.org/10.1016/j.asoc.2020.106269 

425. Thomas Weise, Xinlu Li, Yan Chen, and Zhize Wu. Solving Job Shop Scheduling 

43 Problems Without Using a Bias for Good Solutions. In *Genetic and 

44 Evolutionary Computation Conference Companion (GECCO'21 Companion),* 

45 July 10-14, 2021, Lille, France. ACM, New York, NY, USA. 

46 ISBN 978-1-4503-8351-6. https://dx.doi.org/10.1145/3449726.3463124 

476. Thomas Weise, Mingxu Wan, Ke Tang, and Xin Yao. Evolving Exact Integer 

48 Algorithms with Genetic Programming. In *Proceedings of the IEEE Congress 

49 on Evolutionary Computation (CEC'14), Proceedings of the 2014 World 

50 Congress on Computational Intelligence (WCCI'14),* pages 1816-1823, 

51 July 6-11, 2014, Beijing, China. Los Alamitos, CA, USA: IEEE Computer 

52 Society Press. ISBN: 978-1-4799-1488-3. 

53 https://dx.doi.org/10.1109/CEC.2014.6900292 

54""" 

55from typing import Final 

56 

57from numpy.random import Generator 

58from pycommons.types import type_error, type_name_of 

59 

60from moptipy.algorithms.so.ffa.ffa_h import clear_h, create_h, log_h 

61from moptipy.algorithms.so.fitness import Fitness, FRecord 

62from moptipy.api.objective import Objective, check_objective 

63from moptipy.api.process import Process 

64from moptipy.utils.logger import KeyValueLogSection 

65 

66#: The lower bound at which we switch to an offset-based backing array for 

67#: the frequency table H. 

68SWITCH_TO_OFFSET_LB: Final[int] = 8_388_608 

69 

70 

71class FFA(Fitness): 

72 """The frequency fitness assignment (FFA) process.""" 

73 

74 def __init__(self, f: Objective, log_h_tbl: bool = False) -> None: 

75 """ 

76 Create the frequency fitness assignment mapping. 

77 

78 :param f: the objective function 

79 """ 

80 super().__init__() 

81 if not isinstance(log_h_tbl, bool): 

82 raise type_error(log_h_tbl, "log_h_tbl", bool) 

83 check_objective(f) 

84 h, ofs = create_h(f) 

85 #: the internal H-table 

86 self.__h: Final = h 

87 #: the offset 

88 self.__ofs: Final[int] = ofs 

89 #: should we log the H-table? 

90 self.__log_h_tbl = log_h_tbl 

91 #: are we in the very first iteration? 

92 self.__first: bool = True 

93 

94 def __str__(self): 

95 """ 

96 Get the name (`"ffa"`) of the FFA fitness assignment process. 

97 

98 :return: the name of this process: `ffa` 

99 retval "ffa": always 

100 """ 

101 return "ffa" 

102 

103 def log_information_after_run(self, process: Process) -> None: 

104 """Write the H table.""" 

105 if self.__log_h_tbl: 

106 log_h(process, self.__h, self.__ofs) 

107 

108 def assign_fitness(self, p: list[FRecord], random: Generator) -> None: 

109 """ 

110 Assign the frequency fitness. 

111 

112 :param p: the list of records 

113 :param random: ignored 

114 

115 >>> from moptipy.examples.bitstrings.onemax import OneMax 

116 >>> fit = FFA(OneMax(200)) 

117 >>> a = FRecord(None, 1) 

118 >>> b = FRecord(None, 2) 

119 >>> c = FRecord(None, 2) 

120 >>> d = FRecord(None, 3) 

121 >>> from numpy.random import default_rng 

122 >>> rand = default_rng() 

123 >>> fit.assign_fitness([a, b, c, d], rand) 

124 >>> assert a.fitness == 1 

125 >>> assert b.fitness == 2 

126 >>> assert c.fitness == 2 

127 >>> assert d.fitness == 1 

128 >>> fit.assign_fitness([a, b, c, d], rand) 

129 >>> assert a.fitness == 2 

130 >>> assert b.fitness == 4 

131 >>> assert c.fitness == 4 

132 >>> assert d.fitness == 2 

133 """ 

134 h: Final = self.__h 

135 ofs: Final[int] = self.__ofs 

136 

137 min_it = max_it = p[0].it # the minimum and maximum iteration index 

138 for r in p: 

139 it: int = r.it # get iteration index from record 

140 if it < min_it: # update minimum iteration index 

141 min_it = it 

142 elif it > max_it: # update maximum iteration index 

143 max_it = it 

144# Compatibility with (1+1) FEA: In first generation with a population size of 

145# 1, all elements get the same fitness zero. Otherwise, we would count the 

146# very first solution in the next fitness assignment step again. 

147# This creates a small incompatibility between FFA with mu=1 and FFA with m>1. 

148# This incompatibility is not nice, but it is the only way to ensure that the 

149# (1+1) FEA and the GeneralEA with EA and mu=1, lambda=1 are identical. 

150 first = self.__first 

151 self.__first = False 

152 if first and (max_it <= 0) and (len(p) <= 1): 

153 for r in p: # same fitness: 0 

154 r.fitness = 0 

155 return 

156 for r in p: 

157 h[r.f + ofs] += 1 # type: ignore 

158 it_range: Final[int] = max_it - min_it + 1 # range of it index 

159 for r in p: 

160 r.fitness = ((int(h[r.f + ofs]) * it_range) # type: ignore 

161 + max_it - r.it) 

162 

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

164 """ 

165 Log all parameters of this component as key-value pairs. 

166 

167 :param logger: the logger for the parameters 

168 """ 

169 super().log_parameters_to(logger) 

170 logger.key_value("ofs", self.__ofs) 

171 logger.key_value("hType", type_name_of(self.__h)) 

172 

173 def initialize(self) -> None: 

174 """Initialize the algorithm.""" 

175 super().initialize() 

176 clear_h(self.__h) 

177 self.__first = True