Coverage for moptipy / algorithms / so / marls.py: 96%
85 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2A (mu+lambda) Memetic Algorithm using Randomized Local Search (RLS).
4A memetic algorithm (:class:`~moptipy.algorithms.so.ma.MA`) works similar to a
5(mu+lambda) :class:`~moptipy.algorithms.so.ea.EA`, but it refines all results
6of the search operators with a local search, in this case,
7:class:`~moptipy.algorithms.so.rls.RLS`, which is executed for
8:attr:`~moptipy.algorithms.so.ma.MA.ls_fes` objective function evaluations.
9It also only employs the nullary search operator (to create the initial random
10solutions) and the binary search operator (to combine two selected parental
11solutions), leaving the application of the unary search operator to the RLS.
13A general implementation of a Memetic Algorithm into which arbitrary
14algorithms can be plugged is given in :mod:`~moptipy.algorithms.so.ma`.
15Here, the RLS part and the EA part of the MA are directly merged in a
16hard-coded fashion. If the general :class:`~moptipy.algorithms.so.ma.MA` is
17configured equivalently to the :class:`~moptipy.algorithms.so.marls.MARLS`
18here, i.e., uses the same search operators, same `mu`, `lambda_`, and
19`ls_fes`, then both algorithms will do exactly the same search steps.
211. Pablo Moscato. *On Evolution, Search, Optimization, Genetic Algorithms and
22 Martial Arts: Towards Memetic Algorithms.* Caltech Concurrent Computation
23 Program Report C3P 826. 1989. Pasadena, CA, USA: California Institute of
24 Technology (Caltech), Caltech Concurrent Computation Program (C3P).
25 https://www.researchgate.net/publication/2354457
262. Carlos Cotta, Luke Mathieson, and Pablo Moscato. Memetic Algorithms. In
27 Rafael Martí, Panos M. Pardalos, and Mauricio G. C. Resende, editors,
28 *Handbook of Heuristics.* Part~III: Metaheuristics, pages 607-638. 2018.
29 Cham, Switzerland: Springer. ISBN: 978-3-319-07123-7.
30 doi: https://doi.org/10.1007/978-3-319-07153-4_29-1
31 https://www.researchgate.net/publication/315660932
323. William Eugene Hart, James E. Smith, and Natalio Krasnogor, editors.
33 *Recent Advances in Memetic Algorithms.* Studies in Fuzziness and Soft
34 Computing (STUDFUZZ), volume 166. 2005. Berlin/Heidelberg, Germany:
35 Springer. ISBN: 978-3-540-22904-9.
36 doi: https://doi.org/10.1007/3-540-32363-5
374. Ferrante Neri, Carlos Cotta, and Pablo Moscato. *Handbook of Memetic
38 Algorithms.* Volume 379 of Studies in Computational Intelligence (SCI).
39 2012. Berlin/Heidelberg, Germany: Springer. ISBN: 978-3-642-23246-6
40 doi https://doi.org/10.1007/978-3-642-23247-3.
415. L. Darrell Whitley, V. Scott Gordon, and Keith E. Mathias. Lamarckian
42 Evolution, The Baldwin Effect and Function Optimization. In Yuval Davidor,
43 Hans-Paul Schwefel, and Reinhard Männer, editors, *Proceedings of the Third
44 Conference on Parallel Problem Solving from Nature; International
45 Conference on Evolutionary Computation (PPSN III),* October 9-14, 1994,
46 Jerusalem, Israel, pages 5-15. Volume 866/1994 of Lecture Notes in Computer
47 Science, Berlin, Germany: Springer-Verlag GmbH. ISBN 0387584846.
48 doi: https://doi.org/10.1007/3-540-58484-6_245.
49 https://www.researchgate.net/publication/2521727
50"""
51from typing import Any, 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
64# start book
65class MARLS(Algorithm2):
66 """
67 A Memetic Algorithm as Evolutionary Algorithm + Randomized Local Search.
69 This class implements a Memetic Algorithm (MA) basically as an
70 Evolutionary Algorithm (EA), which only uses the nullary and binary search
71 operators, and that refines each newly generated solution by applying a
72 Randomized Local Search (RLS), which employs the unary search operator.
73 """
75 def solve(self, process: Process) -> None:
76 """
77 Apply the MA=EA+RLS to an optimization problem.
79 :param process: the black-box process object
80 """
81 mu: Final[int] = self.mu # mu: number of best solutions kept
82 mu_plus_lambda: Final[int] = mu + self.lambda_ # size
83 # initialization of some variables omitted in book for brevity
84 # end book
85 random: Final[Generator] = process.get_random() # random gen
86 create: Final[Callable] = process.create # create x container
87 evaluate: Final[Callable] = process.evaluate # the objective
88 op0: Final[Callable] = self.op0.op0 # the nullary operator
89 op1: Final[Callable] = self.op1.op1 # the unary operator
90 op2: Final[Callable] = self.op2.op2 # the binary operator
91 ls_fes: Final[int] = self.ls_fes # the rate at which to use op2
92 should_terminate: Final[Callable] = process.should_terminate
93 r0i: Final[Callable[[int], int]] = cast( # random integers
94 "Callable[[int], int]", random.integers)
95 copy: Final[Callable[[Any, Any], None]] = process.copy
97 # create list of mu random+ls records and lambda empty records
98 # start book
99 lst: Final[list] = [None] * mu_plus_lambda # pre-allocate list
100 f: int | float = 0 # variable to hold objective values # -book
101 tmp = create() # the temporary record
102 for i in range(mu_plus_lambda): # fill list of size mu+lambda
103 x = create() # by creating point in search space
104 if i < mu: # only the first mu records are initialized by
105 op0(random, x) # applying nullary operator = randomize
106 if should_terminate(): # should we quit?
107 return # computational budget exhausted -> quit
108 f = evaluate(x) # continue? ok, evaluate new solution
109 for _ in range(ls_fes): # perform ls_fes of RLS
110 op1(random, tmp, x) # unary operator
111 if should_terminate(): # should we quit?
112 return # computational budget exhausted
113 ftmp: int | float = evaluate(tmp) # evaluate new solution
114 if ftmp <= f: # if it is better or equally good...
115 x, tmp = tmp, x # accept it via swapping
116 f = ftmp # and remember quality
117 lst[i] = Record(x, f) # create and store record
119 it: int = 0 # set iteration counter=0 (but immediately increment)
120 while True: # lst: keep 0..mu-1, overwrite mu..mu+lambda-1
121 it += 1 # step iteration counter
122 for oi in range(mu, mu_plus_lambda): # for all offspring
123 if should_terminate(): # only continue if we still...
124 return # have sufficient budget ... otherwise quit
125 dest: Record = lst[oi] # pick destination record
126 x = dest.x # the destination "x" value
127 dest.it = it # remember iteration of solution creation
128 sx2 = sx = lst[r0i(mu)].x # pick a random source "x"
129 while sx2 is sx: # until different from sx...
130 sx2 = lst[r0i(mu)].x # ..get random second "x"
131 op2(random, x, sx, sx2) # apply binary operator
132 f = evaluate(x) # evaluate new point
133 for _ in range(ls_fes): # perform ls_fes of RLS
134 op1(random, tmp, x) # unary operator
135 if should_terminate(): # should we quit?
136 return # computational budget exhausted
137 ftmp = evaluate(tmp) # evaluate new solution
138 if ftmp <= f: # if it is better or equally good...
139 x, tmp = tmp, x # accept it via swapping {HHH}
140 f = ftmp # and remember quality
141 if x is not dest.x: # if we had swapped x away at {HHH}
142 copy(dest.x, x) # store back solution
143 tmp = x # and put x back into tmp variable
144 dest.f = f # store objective value of refined solution
146 lst.sort() # best records come first, ties broken by age
147 # end book
149 def __init__(self, op0: Op0,
150 op1: Op1,
151 op2: Op2,
152 mu: int = 1, lambda_: int = 1,
153 ls_fes: int = 1000,
154 name: str = "marls") -> None:
155 """
156 Create the Memetic Algorithm using hard-coded RLS as local search.
158 :param op0: the nullary search operator
159 :param op1: the unary search operator
160 :param op2: the binary search operator
161 :param mu: the number of best solutions to survive in each generation
162 :param lambda_: the number of offspring in each generation
163 :param ls_fes: the number of FEs (steps) per local search run
164 :param name: the base name of the algorithm
165 """
166 if not isinstance(op0, Op0):
167 raise type_error(op0, "op0", Op0)
168 if not isinstance(op1, Op1):
169 raise type_error(op1, "op1", Op1)
170 if not isinstance(op2, Op2):
171 raise type_error(op2, "op2", Op2)
173 super().__init__(f"{name}{PART_SEPARATOR}{mu}{PART_SEPARATOR}"
174 f"{lambda_}{PART_SEPARATOR}{ls_fes}", op0, op1, op2)
175 #: the number of records to survive in each generation
176 self.mu: Final[int] = check_int_range(mu, "mu", 1, 1_000_000)
177 #: the number of offsprings per generation
178 self.lambda_: Final[int] = check_int_range(
179 lambda_, "lambda", 1, 1_000_000)
180 #: the number of FEs per local search run
181 self.ls_fes: Final[int] = check_int_range(
182 ls_fes, "ls_fes", 1, 100_000_000)
184 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
185 """
186 Log the parameters of the algorithm to a logger.
188 :param logger: the logger for the parameters
189 """
190 super().log_parameters_to(logger)
191 logger.key_value("mu", self.mu)
192 logger.key_value("lambda", self.lambda_)
193 logger.key_value("lsFEs", self.ls_fes)