Coverage for moptipy / algorithms / so / ffa / safea_b.py: 97%

1""" 

2The SAFEA-B is hybrid of the (1+1)FEA and the SA with Solution Transfer. 

3 

4The algorithm combines frequency fitness assignment based local search, i.e., 

5the FEA, with simulated annealing (SA). Both algorithms get assigned 

6alternating objective function evaluations (FEs). The FEA branch remains 

7unchanged, it is never disturbed and no information flows from the simulated 

8annealing branch over to it. However, solutions are copied from time to time 

9from the FEA branch to the SA branch. The solution is transferred from the FEA 

10branch to the SA branch if its better than the current solution in that 

11branch. 

12 

131. Tianyu Liang, Zhize Wu, Jörg Lässig, Daan van den Berg, Sarah Louise 

14 Thomson, and Thomas Weise. Addressing the Traveling Salesperson Problem 

15 with Frequency Fitness Assignment and Hybrid Algorithms. *Soft Computing.* 

16 2024. https://dx.doi.org/10.1007/s00500-024-09718-8 

17""" 

18from collections import Counter 

19from math import exp 

20from typing import Callable, Final 

21 

22from numpy.random import Generator 

23from pycommons.types import type_error 

24 

25from moptipy.algorithms.modules.temperature_schedule import TemperatureSchedule 

26from moptipy.algorithms.so.ffa.ffa_h import create_h, log_h 

27from moptipy.api.algorithm import Algorithm1 

28from moptipy.api.operators import Op0, Op1 

29from moptipy.api.process import Process 

30from moptipy.utils.logger import KeyValueLogSection 

31 

32 

33class SAFEAB(Algorithm1): 

34 """An implementation of the SAFEA-B.""" 

35 

36 def __init__(self, op0: Op0, op1: Op1, schedule: TemperatureSchedule, 

37 log_h_tbl: bool = False) -> None: 

38 """ 

39 Create the SAFEA-B. 

40 

41 :param op0: the nullary search operator 

42 :param op1: the unary search operator 

43 :param schedule: the temperature schedule to use 

44 :param log_h_tbl: should we log the H table? 

45 """ 

46 if not isinstance(schedule, TemperatureSchedule): 

47 raise type_error(schedule, "schedule", TemperatureSchedule) 

48 if not isinstance(log_h_tbl, bool): 

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

50 super().__init__(f"safeaB_{schedule}", op0, op1) 

51 #: True if we should log the H table, False otherwise 

52 self.__log_h_tbl: Final[bool] = log_h_tbl 

53 #: the temperature schedule 

54 self.schedule: Final[TemperatureSchedule] = schedule 

55 

56 def solve(self, process: Process) -> None: 

57 """ 

58 Apply the SAFEA-B to an optimization problem. 

59 

60 :param process: the black-box process object 

61 """ 

62 # Create records for old and new point in the search space. 

63 x_c = process.create() # record for current solution of the SA 

64 x_d = process.create() # record for current solution of the FEA 

65 x_n = process.create() # record for new solution 

66 

67 # Obtain the random number generator. 

68 random: Final[Generator] = process.get_random() 

69 

70 # Put function references in variables to save time. 

71 evaluate: Final[Callable] = process.evaluate # the objective 

72 should_terminate: Final[Callable] = process.should_terminate 

73 temperature: Final[Callable[[int], float]] = self.schedule.temperature 

74 r01: Final[Callable[[], float]] = random.random # random from [0, 1) 

75 xcopy: Final[Callable] = process.copy # copy(dest, source) 

76 op0: Final[Callable] = self.op0.op0 # the nullary operator 

77 op1: Final[Callable] = self.op1.op1 # the unary operator 

78 

79 h, ofs = create_h(process) # Allocate the h-table 

80 

81 # Start at a random point in the search space and evaluate it. 

82 op0(random, x_c) # Create 1 solution randomly and 

83 y_c: int | float = evaluate(x_c) + ofs # evaluate it. 

84 xcopy(x_d, x_c) 

85 y_d: int | float = y_c 

86 use_ffa: bool = True 

87 tau: int = 0 # The iteration index, needs to be 0 at first cmp. 

88 

89 while not should_terminate(): # Until we need to quit... 

90 use_ffa = not use_ffa # toggle use of FFA 

91 op1(random, x_n, x_d if use_ffa else x_c) 

92 y_n: int | float = evaluate(x_n) + ofs 

93 

94 if use_ffa: # the FEA branch 

95 h[y_n] += 1 # type: ignore # Increase the frequency 

96 h[y_d] += 1 # type: ignore # of new_f and cur_f. 

97 if h[y_n] <= h[y_d]: # type: ignore 

98 y_d = y_n # Store its objective value. 

99 x_d, x_n = x_n, x_d # Swap best and new. 

100 if y_n <= y_c: # check transfer if solution was 

101 y_c = y_n # accepted 

102 xcopy(x_c, x_d) # copy the solution over 

103 continue # skip rest of loop body 

104 if (y_n <= y_c) or ( # Accept if <= or if SA criterion 

105 (not use_ffa) and ( # Only for SA, not FEA 

106 r01() < exp((y_c - y_n) / temperature(tau)))): 

107 y_c = y_n 

108 x_c, x_n = x_n, x_c 

109 tau += 1 # Step the iteration index. 

110 

111 if not self.__log_h_tbl: 

112 return # we are done here 

113 

114 # After we are done, we want to print the H-table. 

115 if h[y_c] == 0: # type: ignore # Fix the H-table for the case 

116 h = Counter() # that only one FE was performed: In this case, 

117 h[y_c] = 1 # make Counter with only a single 1 value inside. 

118 

119 log_h(process, h, ofs) # log the H-table 

120 

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

122 """ 

123 Log all parameters of the SAFEA-B algorithm. 

124 

125 :param logger: the logger for the parameters 

126 """ 

127 super().log_parameters_to(logger) 

128 with logger.scope("ts") as ts: 

129 self.schedule.log_parameters_to(ts)