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

1""" 

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

3 

4The algorithm has two branches: (1) the EA branch, which performs randomized 

5local search (RLS), which is in some contexts also called (1+1) EA. (2) the 

6FEA branch, which performs RLS but uses frequency fitness assignment (FFA) 

7as optimization criterion. No flow of information takes place between the two 

8branches. 

9 

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

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

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

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

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

15""" 

16from collections import Counter 

17from typing import Callable, Final 

18 

19from numpy.random import Generator 

20from pycommons.types import type_error 

21 

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

23from moptipy.api.algorithm import Algorithm1 

24from moptipy.api.operators import Op0, Op1 

25from moptipy.api.process import Process 

26 

27 

28class EAFEA(Algorithm1): 

29 """An implementation of the EAFEA.""" 

30 

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

32 """ 

33 Create the EAFEA. 

34 

35 :param op0: the nullary search operator 

36 :param op1: the unary search operator 

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

38 """ 

39 super().__init__("eafea", op0, op1) 

40 if not isinstance(log_h_tbl, bool): 

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

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

43 self.__log_h_tbl: Final[bool] = log_h_tbl 

44 

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

46 """ 

47 Apply the EAFEA to an optimization problem. 

48 

49 :param process: the black-box process object 

50 """ 

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

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

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

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

55 

56 # Obtain the random number generator. 

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

58 

59 # Put function references in variables to save time. 

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

61 should_terminate: Final[Callable] = process.should_terminate 

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

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

64 

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

66 

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

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

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

70 process.copy(x_d, x_c) 

71 y_d: int | float = y_c 

72 use_ffa: bool = True 

73 

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

75 use_ffa = not use_ffa # toggle use of FFA 

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

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

78 

79 if use_ffa: # the FEA branch 

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

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

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

83 y_d = y_n # Store its objective value. 

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

85 elif y_n <= y_c: # the EA/RLS branch 

86 y_c = y_n 

87 x_c, x_n = x_n, x_c 

88 

89 if not self.__log_h_tbl: 

90 return # we are done here 

91 

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

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

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

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

96 

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