Coverage for moptipy / algorithms / so / ea.py: 88%
108 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2A simple implementation of a (mu+lambda) Evolutionary Algorithm.
4This is the basic `mu+lambda`-EA, which works as follows:
61. Start with a list `lst` of `mu` random records and `lambda` blank records.
72. In each iteration:
9 2.1. Use the `mu` first records as input to the search operators to
10 generate `lambda` new points in the search space.
11 For each new point to be created, the binary operator is applied
12 with probability `0<=br<=1` and the unary operator is used otherwise.
14 2.2. Sort the list `lst` according to the objective value of the record.
15 Ties are broken by preferring younger solutions over old ones. Soring
16 uses the `__lt__` dunder method of class
17 :class:`~moptipy.algorithms.so.record.Record`. This moves the best
18 solutions to the front of the list. The tie breaking method both
19 encourages drift and ensures compatibility with `RLS`.
21If `mu=1`, `lambda=1`, and `br=0`, then this algorithm is exactly equivalent
22to the :class:`~moptipy.algorithms.so.rls.RLS` if the same unary and nullary
23operator are used. It is only a bit slower due to the additional overhead of
24maintaining a list of records. This compatibility is achieved by the tie
25breaking strategy of `step 2.2` above: RLS will prefer the newer solution over
26the current one if the new solution is either better or as same as good. Now
27the latter case cannot be achieved by just sorting the list without
28considering the iteration at which a solution was created, since sorting in
29Python is *stable* (equal elements remain in the order in which they are
30encountered in the original list) and because our new solutions would be in
31the `lambda` last entries of the list. This can easily be fixed by the tie
32breaking, which is implemented in the `__lt__` dunder method of class
33:class:`~moptipy.algorithms.so.record.Record`.
351. Thomas Bäck, David B. Fogel, and Zbigniew Michalewicz, eds., *Handbook of
36 Evolutionary Computation.* 1997. Computational Intelligence Library.
37 New York, NY, USA: Oxford University Press, Inc. ISBN: 0-7503-0392-1
382. James C. Spall. *Introduction to Stochastic Search and Optimization.*
39 Estimation, Simulation, and Control - Wiley-Interscience Series in Discrete
40 Mathematics and Optimization, volume 6. 2003. Chichester, West Sussex, UK:
41 Wiley Interscience. ISBN: 0-471-33052-3. http://www.jhuapl.edu/ISSO/.
423. Frank Hoffmeister and Thomas Bäck. Genetic Algorithms and Evolution
43 Strategies: Similarities and Differences. In Hans-Paul Schwefel and
44 Reinhard Männer, *Proceedings of the International Conference on Parallel
45 Problem Solving from Nature (PPSN I),* October 1-3, 1990, Dortmund,
46 Germany, volume 496 of Lecture Notes in Computer Science, pages 455-469,
47 Berlin/Heidelberg, Germany: Springer. ISBN: 978-3-540-54148-6.
48 https://doi.org/10.1007/BFb0029787.
49"""
50from math import isfinite
51from typing import Callable, Final, cast
53from numpy.random import Generator
54from pycommons.types import check_int_range, type_error
56from moptipy.algorithms.so.record import Record
57from moptipy.api.algorithm import Algorithm2
58from moptipy.api.operators import Op0, Op1, Op2
59from moptipy.api.process import Process
60from moptipy.utils.logger import KeyValueLogSection
61from moptipy.utils.strings import PART_SEPARATOR, num_to_str_for_name
64def _int_0(_: int) -> int:
65 """
66 Return an integer with value `0`.
68 :retval 0: always
69 """
70 return 0
73def _float_0() -> float:
74 """
75 Return a float with value `0.0`.
77 :retval 0.0: always
78 """
79 return 0.0
82# start nobinary
83class EA(Algorithm2):
84 """
85 The EA is a population-based algorithm using unary and binary operators.
87 It starts with a list of :attr:`mu` randomly initialized solutions. In
88 each step, it retains the `mu` best solutions and generates
89 :attr:`lambda_` new solutions from them using the unary operator
90 (:attr:`~moptipy.api.algorithm.Algorithm1.op1`) with probability
91 1-:attr:`br` and the binary search operator
92 ((:attr:`~moptipy.api.algorithm.Algorithm2.op2`) at rate :attr:`br`. From
93 the joint set of `mu+lambda_` solutions, it again selects the best `mu`
94 ones for the next iteration. And so on.
96 If `mu=1`, `lambda_=1`, and `br=0`, then this algorithm is exactly
97 equivalent to the :class:`~moptipy.algorithms.so.rls.RLS` if the same
98 unary and nullary operator are used.
99 """
101 def solve(self, process: Process) -> None:
102 """
103 Apply the EA to an optimization problem.
105 :param process: the black-box process object
106 """
107 mu: Final[int] = self.mu # mu: number of best solutions kept
108 mu_plus_lambda: Final[int] = mu + self.lambda_ # size
109 # initialization of some variables omitted in book for brevity
110 # end nobinary
111 random: Final[Generator] = process.get_random() # random gen
112 create: Final[Callable] = process.create # create x container
113 evaluate: Final[Callable] = process.evaluate # the objective
114 op0: Final[Callable] = self.op0.op0 # the nullary operator
115 op1: Final[Callable] = self.op1.op1 # the unary operator
116 op2: Final[Callable] = self.op2.op2 # the binary operator
117 br: Final[float] = self.br # the rate at which to use op2
118 should_terminate: Final[Callable] = process.should_terminate
119 r0i: Final[Callable[[int], int]] = cast( # only if m > 1, we
120 "Callable[[int], int]", random.integers # need random
121 if mu > 1 else _int_0) # indices
122 r01: Final[Callable[[], float]] = cast( # only if 0<br<1, we
123 "Callable[[], float]", # need random floats
124 random.random if 0 < br < 1 else _float_0)
125 # start nobinary
126 # create list of mu random records and lambda empty records
127 lst: Final[list] = [None] * mu_plus_lambda # pre-allocate list
128 f: int | float = 0 # variable to hold objective values
129 for i in range(mu_plus_lambda): # fill list of size mu+lambda
130 x = create() # by creating point in search space
131 if i < mu: # only the first mu records are initialized by
132 op0(random, x) # applying nullary operator = randomize
133 if should_terminate(): # should we quit?
134 return # computational budget exhausted -> quit
135 f = evaluate(x) # continue? ok, evaluate new solution
136 lst[i] = Record(x, f) # create and store record
138 it: int = 0 # set iteration counter=0 (but immediately increment)
139 while True: # lst: keep 0..mu-1, overwrite mu..mu+lambda-1
140 it += 1 # step iteration counter
141 for oi in range(mu, mu_plus_lambda): # for all offspring
142 if should_terminate(): # only continue if we still...
143 return # have sufficient budget ... otherwise quit
144 dest: Record = lst[oi] # pick destination record
145 x = dest.x # the destination "x" value
146 dest.it = it # remember iteration of solution creation
148 sx = lst[r0i(mu)].x # pick a random source "x"
149 # end nobinary
150 # start binary
151 if r01() < br: # apply binary operator at rate br
152 sx2 = sx # second source "x" initially=first sx
153 while sx2 is sx: # until different from sx...
154 sx2 = lst[r0i(mu)].x # ..get random second "x"
155 op2(random, x, sx, sx2) # apply binary operator
156 dest.f = evaluate(x) # evaluate new point
157 continue # below is "else" part with unary operat.
158 # end binary
159 # start nobinary
160 op1(random, x, sx) # apply unary operator
161 dest.f = evaluate(x) # evaluate new point
163 lst.sort() # best records come first, ties broken by age
164# end nobinary
166 def __init__(self, op0: Op0,
167 op1: Op1 | None = None,
168 op2: Op2 | None = None,
169 mu: int = 1, lambda_: int = 1,
170 br: float | None = None,
171 name: str = "ea") -> None:
172 """
173 Create the Evolutionary Algorithm (EA).
175 :param op0: the nullary search operator
176 :param op1: the unary search operator
177 :param op2: the binary search operator
178 :param mu: the number of best solutions to survive in each generation
179 :param lambda_: the number of offspring in each generation
180 :param br: the rate at which the binary operator is applied
181 :param name: the base name of the algorithm
182 """
183 if op1 is None:
184 op1 = Op1()
185 if br is None:
186 br = 1.0
187 elif br != 1.0:
188 raise ValueError(
189 f"if op1==None, br must be None or 1.0, but is {br}.")
190 elif op1.__class__ is Op1:
191 if br is None:
192 br = 1.0
193 elif br != 1.0:
194 raise ValueError(
195 f"if op1 is Op1, br must be None or 1.0, but is {br}.")
196 elif (br is not None) and (br == 1.0):
197 op1 = Op1()
199 if op2 is None:
200 op2 = Op2()
201 if br is None:
202 br = 0.0
203 elif br != 0.0:
204 raise ValueError(
205 f"if op2==None, br must be None or 0.0, but is {br}.")
206 elif op2.__class__ is Op2:
207 if br is None:
208 br = 0.0
209 elif br != 0.0:
210 raise ValueError(
211 f"if op2 is Op2, br must be None or 0.0, but is {br}.")
212 elif (br is not None) and (br == 0.0):
213 op2 = Op2()
214 elif (mu == 1) and (br is None):
215 br = 0.0
216 op2 = Op2()
218 if br is None:
219 br = 0.2
221 name = f"{name}{PART_SEPARATOR}{mu}{PART_SEPARATOR}{lambda_}"
222 if 0 < br < 1:
223 name = f"{name}{PART_SEPARATOR}{num_to_str_for_name(br)}"
224 super().__init__(name, op0, op1, op2)
226 #: the number of records to survive in each generation
227 self.mu: Final[int] = check_int_range(mu, "mu", 1, 1_000_000)
228 #: the number of offsprings per generation
229 self.lambda_: Final[int] = check_int_range(
230 lambda_, "lambda", 1, 1_000_000)
232 if not isinstance(br, float):
233 raise type_error(br, "br", float)
234 if not (isfinite(br) and (0.0 <= br <= 1.0)):
235 raise ValueError(f"invalid br={br}, must be in [0, 1].")
236 if (br > 0.0) and (mu <= 1):
237 raise ValueError(
238 f"if br (={br}) > 0, then mu (={mu}) must be > 1.")
239 #: the rate at which the binary operator is applied
240 self.br: Final[float] = br
242 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
243 """
244 Log the parameters of the algorithm to a logger.
246 :param logger: the logger for the parameters
247 """
248 super().log_parameters_to(logger)
249 logger.key_value("mu", self.mu)
250 logger.key_value("lambda", self.lambda_)
251 logger.key_value("br", self.br)