Coverage for moptipy / algorithms / so / hill_climber_with_restarts.py: 100%

1""" 

2The implementation of the hill climbing algorithm with restarts `hcr`. 

3 

4This algorithm basically works like the normal hill climber `hc` 

5(:class:`~moptipy.algorithms.so.hill_climber.HillClimber`), but it will 

6restart automatically if no move was successful for 

7`max_moves_without_improvement` iterative steps. It therefore maintains an 

8internal counter `count` which is set to zero at the beginning of each restart 

9and which is also set to zero again any time a move successfully improved the 

10best-so-far solution of the current restart. If a search move, i.e., an 

11application of the unary operator, yielded a new solution which is not better 

12than the best-so-far solution of the current restart, `count` is incremented. 

13If `count >= max_moves_without_improvement`, the algorithm begins a new 

14restart with a new random solution. 

15 

161. Thomas Weise. *Optimization Algorithms.* 2021. Hefei, Anhui, China: 

17 Institute of Applied Optimization (IAO), School of Artificial Intelligence 

18 and Big Data, Hefei University. http://thomasweise.github.io/oa/ 

19""" 

20from typing import Callable, Final 

21 

22from numpy.random import Generator 

23from pycommons.types import check_int_range 

24 

25from moptipy.api.algorithm import Algorithm1 

26from moptipy.api.operators import Op0, Op1 

27from moptipy.api.process import Process 

28from moptipy.utils.logger import KeyValueLogSection 

29 

30 

31# start book 

32class HillClimberWithRestarts(Algorithm1): 

33 """ 

34 The stochastic hill climbing algorithm only accepts improving moves. 

35 

36 In each step, a hill climber creates a modified copy `new_x` of the 

37 current best solution `best_x`. If `new_x` is better than `best_x`, 

38 it becomes the new `best_x`. Otherwise, it is discarded. If no 

39 improvement is made for `max_moves_without_improvement` steps, the 

40 algorithm restarts. 

41 """ 

42 

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

44 """ 

45 Apply the hill climber with restarts to an optimization problem. 

46 

47 :param process: the black-box process object 

48 """ 

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

50 best_x = process.create() # record for best-so-far solution 

51 new_x = process.create() # record for new solution 

52 # Obtain the random number generator. 

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

54 

55 # Put function references in variables to save time. 

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

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

58 should_terminate: Final[Callable] = process.should_terminate 

59 limit: Final[int] = self.max_moves_without_improvement 

60 

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

62 self.op0.op0(random, best_x) # Create random solution and 

63 best_f: int | float = evaluate(best_x) 

64 count: int = 0 # The counter of unsuccessful moves = 0. 

65 

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

67 op1(random, new_x, best_x) # new_x=neighbor of best_x 

68 new_f: int | float = evaluate(new_x) 

69 if new_f < best_f: # new_x is _better_ than best_x? 

70 best_f = new_f # Store its objective value. 

71 best_x, new_x = new_x, best_x # Swap best and new. 

72 count = 0 # Reset unsuccessful move counter. 

73 else: # The move did not lead to an improvement!? 

74 count += 1 # Increment unsuccessful move counter. 

75 if count >= limit: # Too many unsuccessful moves? 

76 break # Break inner loop, start again randomly. 

77# end book 

78 

79 def __init__(self, op0: Op0, op1: Op1, 

80 max_moves_without_improvement: int) -> None: 

81 """ 

82 Create the hill climber. 

83 

84 :param op0: the nullary search operator 

85 :param op1: the unary search operator 

86 :param max_moves_without_improvement: the maximum number of 

87 moves without improvement before a restart 

88 """ 

89 super().__init__( 

90 f"hcr_{max_moves_without_improvement}", op0, op1) 

91 #: the maximum moves without improvement 

92 self.max_moves_without_improvement: Final[int] = \ 

93 check_int_range( 

94 max_moves_without_improvement, 

95 "max_moves_without_improvement", 1, 1_000_000_000_000) 

96 

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

98 """ 

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

100 

101 :param logger: the logger for the parameters 

102 """ 

103 super().log_parameters_to(logger) 

104 logger.key_value("maxMovesWithoutImprovement", 

105 self.max_moves_without_improvement)