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

1""" 

2The modified Greedy (2+1) EAmod Evolutionary Algorithm. 

3 

4The Greedy (2+1) EAmod maintains a population of two individuals. Both 

5solutions, `x0` and `x1`, are intiially sampled independently and at random. 

6Each iteration consists of two steps, a crossover step and a mutation step. 

7The binary operator (crossover) is only applied if `x0` and `x1` have the 

8same objective value to produce offspring `z1`. If `x0` and `x1` have 

9different objective values, then `z1` is set to be the better of the two 

10parents. Then, the final offspring `z2` is derived by applying the unary 

11mutation operator. If `z2` is at least as good as the better one of `x0` 

12and `x1`, then it will be accepted. If `x1` and `x0` are as same as 

13good, one of them is randomly chosen to be replaced by `z2`. Otherwise, 

14the worse one is replaced. 

15 

16This is the implementation of a general black-box version of the 

17Greedy (2+1) GAmod by Carvalho Pinto and Doerr. The original algorithm is a 

18genetic algorithm, i.e., an EA with a bit string-based search space and a 

19mutation operator flipping a Binomially distributed number of bits and 

20performing uniform crossover. Here we implement is a general EA where you can 

21plug in any crossover or mutation operator. Furthermore, the algorithm by 

22Carvalho Pinto and Doerr is, in turn, a modified version of Sudhold's 

23Greedy (2+1) GA, with some improvements for efficiency. 

24 

251. Eduardo Carvalho Pinto and Carola Doerr. Towards a More Practice-Aware 

26 Runtime Analysis of Evolutionary Algorithms. 2017. arXiv:1812.00493v1 

27 [cs.NE] 3 Dec 2018. [Online]. http://arxiv.org/pdf/1812.00493.pdf. 

282. Dirk Sudholt. Crossover Speeds up Building-Block Assembly. In Proceedings 

29 of the 14th Annual Conference on Genetic and Evolutionary Computation 

30 (GECCO'12), July 7-11, 2012, Philadelphia, Pennsylvania, USA, 

31 pages 689-702. ACM, 2012. https://doi.org/10.1145/2330163.2330260. 

32""" 

33from typing import Callable, Final 

34 

35from numpy.random import Generator 

36 

37from moptipy.api.algorithm import Algorithm2 

38from moptipy.api.operators import Op0, Op1, Op2 

39from moptipy.api.process import Process 

40 

41 

42class GreedyTwoPlusOneEAmod(Algorithm2): 

43 """The modified Greedy (2+1) Evolutionary Algorithm.""" 

44 

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

46 """ 

47 Apply the EA to an optimization problem. 

48 

49 :param process: the black-box process object 

50 """ 

51 # Omitted for brevity: store function references in variables 

52 random: Final[Generator] = process.get_random() # random gen 

53 create: Final[Callable] = process.create # create x container 

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

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

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

57 op2: Final[Callable] = self.op2.op2 # the binary operator 

58 should_terminate: Final[Callable] = process.should_terminate 

59 equals: Final[Callable] = process.is_equal 

60 ri: Final[Callable] = random.integers 

61 

62 x0 = create() # allocate record for first solution 

63 op0(random, x0) # randomly initialize first solution 

64 f0: int | float = evaluate(x0) # evaluate first solution 

65 if should_terminate(): # should we quit? 

66 return # yes. 

67 

68 x1 = create() # allocate record for first solution 

69 op0(random, x1) # randomly initialize second solution 

70 f1: int | float = evaluate(x1) # evaluate 2nd solution 

71 

72 z1 = create() # create record for result of binary operation 

73 z2 = create() # create record for result of unary operation 

74 

75 while not should_terminate(): # loop until budget is used up 

76 if f0 == f1: # only perform binary operation if f0 == f1 

77 op2(random, z1, x0, x1) # recombination 

78 p = z1 # input of unary operation comes from binary op 

79 else: 

80 if f0 > f1: # swap x0 and x1 if x1 is better 

81 f0, f1 = f1, f0 # swap objective values 

82 x0, x1 = x1, x0 # swap solutions 

83 p = x0 # input of unary operation is best-so-far x 

84 op1(random, z2, p) # apply unary operation 

85 if not (equals(z2, x0) or equals(z2, x1)): # is z2 new? 

86 fnew = evaluate(z2) # only then evaluate it 

87 if fnew <= f0: # is it better or equal than x1 

88 if (f1 > f0) or (ri(2) == 0): 

89 z2, x1 = x1, z2 # swap z2 with x1 and 

90 f1 = fnew # and remember its quality 

91 else: # f1 == f2 and probability = 0.5 

92 z2, x0 = x0, z2 # swap z2 with x0 

93 f0 = fnew # and remember its quality 

94 

95 def __init__(self, op0: Op0, op1: Op1, op2: Op2) -> None: 

96 """ 

97 Create the algorithm with nullary, unary, and binary search operator. 

98 

99 :param op0: the nullary search operator 

100 :param op1: the unary search operator 

101 :param op2: the binary search operator 

102 """ 

103 super().__init__("greedy2plus1EAmod", op0, op1, op2)