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

1""" 

2The SAFEA-A 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 H-value is 1, i.e., if it represents a 

11completely new objective value. 

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 SAFEAA(Algorithm1): 

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

35 

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

37 log_h_tbl: bool = False) -> None: 

38 """ 

39 Create the SAFEA-A. 

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"safeaA_{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-A 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 h_n = h[y_n] # type: ignore 

98 if h_n <= h[y_d]: # type: ignore 

99 y_d = y_n # Store its objective value. 

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

101 if h_n <= 1: # if solution is new, then transfer it to 

102 xcopy(x_c, x_d) # the SA branch 

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

104 r01() < exp((y_c - y_n) / temperature(tau))): # the SA 

105 y_c = y_n 

106 x_c, x_n = x_n, x_c 

107 tau += 1 # Step the iteration index. 

108 

109 if not self.__log_h_tbl: 

110 return # we are done here 

111 

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

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

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

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

116 

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

118 

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

120 """ 

121 Log all parameters of the SAFEA-A algorithm. 

122 

123 :param logger: the logger for the parameters 

124 """ 

125 super().log_parameters_to(logger) 

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

127 self.schedule.log_parameters_to(ts)