Coverage for moptipy / algorithms / so / ffa / eafea_b.py: 98%

1""" 

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

3 

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

5the FEA, with randomized local search (RLS, also called (1+1) EA in some 

6contexts). Both algorithms get assigned alternating objective function 

7evaluations (FEs). The FEA branch remains unchanged, it is never disturbed and 

8no information flows from the RLS branch over to it. However, solutions are 

9copied from time to time from the FEA branch to the RLS branch. The solution 

10is transferred from the FEA branch to the EA branch if it's better or equally 

11good compared to the current solution in that branch. 

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 typing import Callable, Final 

20 

21from numpy.random import Generator 

22from pycommons.types import type_error 

23 

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

25from moptipy.api.algorithm import Algorithm1 

26from moptipy.api.operators import Op0, Op1 

27from moptipy.api.process import Process 

28 

29 

30class EAFEAB(Algorithm1): 

31 """An implementation of the EAFEA-B.""" 

32 

33 def __init__(self, op0: Op0, op1: Op1, log_h_tbl: bool = False) -> None: 

34 """ 

35 Create the EAFEA-B. 

36 

37 :param op0: the nullary search operator 

38 :param op1: the unary search operator 

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

40 """ 

41 super().__init__("eafeaB", op0, op1) 

42 if not isinstance(log_h_tbl, bool): 

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

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

45 self.__log_h_tbl: Final[bool] = log_h_tbl 

46 

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

48 """ 

49 Apply the EAFEA-B to an optimization problem. 

50 

51 :param process: the black-box process object 

52 """ 

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

54 x_c = process.create() # record for current solution of the EA 

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

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

57 

58 # Obtain the random number generator. 

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

60 

61 # Put function references in variables to save time. 

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

63 should_terminate: Final[Callable] = process.should_terminate 

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

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

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

67 

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

69 

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

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

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

73 xcopy(x_d, x_c) 

74 y_d: int | float = y_c 

75 use_ffa: bool = True 

76 

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

78 use_ffa = not use_ffa # toggle use of FFA 

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

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

81 

82 if use_ffa: # the FEA branch 

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

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

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

86 y_d = y_n # Store its objective value. 

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

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

89 y_c = y_n # accepted 

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

91 continue # skip rest of loop body 

92 if y_n <= y_c: # the EA/RLS branch 

93 y_c = y_n 

94 x_c, x_n = x_n, x_c 

95 

96 if not self.__log_h_tbl: 

97 return # we are done here 

98 

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

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

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

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

103 

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