Coverage for moptipy / algorithms / so / ma.py: 98%
84 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) Memetic Algorithm.
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
7:attr:`~moptipy.algorithms.so.ma.MA.ls` 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).
13This is the general form of the Memetic Algorithm of the type
14"EA+something else." A specialized version combining an
15:mod:`~moptipy.algorithms.so.ea` with
16:mod:`~moptipy.algorithms.so.rls` can be found in
17:mod:`~moptipy.algorithms.so.marls`.
19This Memetic Algorithm implementation begins by sampling
20:attr:`~moptipy.algorithms.so.ma.MA.mu`
21solutions using the nullary search operation
22:attr:`~moptipy.api.algorithm.Algorithm0.op0`. Each of these initial solutions
23is used as a starting point of a local search
24:attr:`~moptipy.algorithms.so.ma.MA.ls`, which is executed for
25:attr:`~moptipy.algorithms.so.ma.MA.ls_fes` objective function evaluations.
26In each iteration, it then uses the
27:attr:`~moptipy.algorithms.so.ma.MA.mu` existing solutions as input for
28the binary search operator :attr:`~moptipy.algorithms.so.ma.MA.op2` to create
29:attr:`~moptipy.algorithms.so.ma.MA.lambda_` new solutions, each of which is
30again used as a starting point of a local search
31:attr:`~moptipy.algorithms.so.ma.MA.ls` executed for
32:attr:`~moptipy.algorithms.so.ma.MA.ls_fes` objective function evaluations.
33The results of the local searches enter the population and in the next
34iteration, the :attr:`~moptipy.algorithms.so.ma.MA.mu` best solutions of the
35:attr:`~moptipy.algorithms.so.ma.MA.mu` +
36:attr:`~moptipy.algorithms.so.ma.MA.lambda_` ones in the population are
37retained.
39Due to the :class:`~moptipy.api.process.Process` and
40:mod:`~moptipy.api.subprocesses` API of `moptipy`, you can use almost arbitrary
41algorithms as local search :attr:`~moptipy.algorithms.so.ma.MA.ls`. The only
42requirement is that is a subclass of
43:class:`~moptipy.api.algorithm.Algorithm0` and uses
44it uses an instance of
45:class:`moptipy.operators.op0_forward.Op0Forward` as nullary search operator
46(:attr:`~moptipy.api.algorithm.Algorithm0.op0`).
47This allows the MA to set a solution as starting point for the inner algorithm
48:attr:`~moptipy.algorithms.so.ma.MA.ls`.
50It should be noted that it is by no means required that the inner algorithm
51:attr:`~moptipy.algorithms.so.ma.MA.ls` needs to be a local search. Any
52algorithm that fulfills the above requirements could be used. For example, if
53we were conducting numerical optimization, it would be totally OK to plug an
54instance of the Sequential Least Squares Programming
55(:class:`~moptipy.algorithms.so.vector.scipy.SLSQP`) algorithm into the
56memetic algorithm…
58Further reading on how to realize using one algorithm as a sub-algorithm
59of another one can be found in the documentation of
60:func:`~moptipy.api.subprocesses.from_starting_point`,
61:func:`~moptipy.api.subprocesses.for_fes`, and
62:class:`moptipy.operators.op0_forward.Op0Forward`.
641. Pablo Moscato. *On Evolution, Search, Optimization, Genetic Algorithms and
65 Martial Arts: Towards Memetic Algorithms.* Caltech Concurrent Computation
66 Program Report C3P 826. 1989. Pasadena, CA, USA: California Institute of
67 Technology (Caltech), Caltech Concurrent Computation Program (C3P).
68 https://www.researchgate.net/publication/2354457
692. Carlos Cotta, Luke Mathieson, and Pablo Moscato. Memetic Algorithms. In
70 Rafael Martí, Panos M. Pardalos, and Mauricio G. C. Resende, editors,
71 *Handbook of Heuristics.* Part~III: Metaheuristics, pages 607-638. 2018.
72 Cham, Switzerland: Springer. ISBN: 978-3-319-07123-7.
73 doi: https://doi.org/10.1007/978-3-319-07153-4_29-1
74 https://www.researchgate.net/publication/315660932
753. William Eugene Hart, James E. Smith, and Natalio Krasnogor, editors.
76 *Recent Advances in Memetic Algorithms.* Studies in Fuzziness and Soft
77 Computing (STUDFUZZ), volume 166. 2005. Berlin/Heidelberg, Germany:
78 Springer. ISBN: 978-3-540-22904-9.
79 doi: https://doi.org/10.1007/3-540-32363-5
804. Ferrante Neri, Carlos Cotta, and Pablo Moscato. *Handbook of Memetic
81 Algorithms.* Volume 379 of Studies in Computational Intelligence (SCI).
82 2012. Berlin/Heidelberg, Germany: Springer. ISBN: 978-3-642-23246-6
83 doi https://doi.org/10.1007/978-3-642-23247-3.
845. L. Darrell Whitley, V. Scott Gordon, and Keith E. Mathias. Lamarckian
85 Evolution, The Baldwin Effect and Function Optimization. In Yuval Davidor,
86 Hans-Paul Schwefel, and Reinhard Männer, editors, *Proceedings of the Third
87 Conference on Parallel Problem Solving from Nature; International
88 Conference on Evolutionary Computation (PPSN III),* October 9-14, 1994,
89 Jerusalem, Israel, pages 5-15. Volume 866/1994 of Lecture Notes in Computer
90 Science, Berlin, Germany: Springer-Verlag GmbH. ISBN 0387584846.
91 doi: https://doi.org/10.1007/3-540-58484-6_245.
92 https://www.researchgate.net/publication/2521727
93"""
94from typing import Callable, Final, cast
96from numpy.random import Generator
97from pycommons.types import check_int_range, type_error
99from moptipy.algorithms.so.record import Record
100from moptipy.api.algorithm import Algorithm0
101from moptipy.api.logging import SCOPE_OP2
102from moptipy.api.operators import Op0, Op2, check_op2
103from moptipy.api.process import Process
104from moptipy.api.subprocesses import for_fes, from_starting_point
105from moptipy.operators.op0_forward import Op0Forward
106from moptipy.utils.logger import KeyValueLogSection
107from moptipy.utils.strings import PART_SEPARATOR
110# start book
111class MA(Algorithm0):
112 """An MA is a population-based algorithm using binary operators."""
114 def solve(self, process: Process) -> None:
115 """
116 Apply the MA to an optimization problem.
118 :param process: the black-box process object
119 """
120 # initialization of some variables omitted in book for brevity
121 # end book
122 mu: Final[int] = self.mu # mu: number of best solutions kept
123 mu_plus_lambda: Final[int] = mu + self.lambda_ # size
124 random: Final[Generator] = process.get_random() # random gen
125 create: Final[Callable] = process.create # create x container
126 evaluate: Final[Callable] = process.evaluate # the objective
127 op0: Final[Callable] = self.op0.op0 # the nullary operator
128 op2: Final[Callable] = self.op2.op2 # the binary operator
129 ls_fes: Final[int] = self.ls_fes # the number of FEs per ls run
130 ls_solve: Final[Callable[[Process], None]] = self.ls.solve # +book
131 forward_ls_op0_to: Final[Callable] = cast( # forward starting
132 "Op0Forward", self.ls.op0).forward_to # point of ls to...
133 should_terminate: Final[Callable] = process.should_terminate
134 r0i: Final[Callable[[int], int]] = cast( # random integers
135 "Callable[[int], int]", random.integers)
136 # start book
137 # create list of mu random+ls records and lambda empty records
138 lst: Final[list] = [None] * mu_plus_lambda # pre-allocate list
139 f: int | float = 0 # variable to hold objective values
140 for i in range(mu_plus_lambda): # fill list of size mu+lambda
141 x = create() # by creating point in search space
142 if i < mu: # only the first mu records are initialized by
143 op0(random, x) # applying nullary operator = randomize
144 if should_terminate(): # should we stop now?
145 cast("Op0Forward", self.ls.op0).stop_forwarding() # -book
146 return # computational budget exhausted -> quit
147 with for_fes(process, ls_fes) as s1, \
148 from_starting_point(s1, x, evaluate(x)) as s2:
149 forward_ls_op0_to(s2.get_copy_of_best_x)
150 ls_solve(s2) # apply local search modifying x
151 f = s2.get_best_f() # get quality of x
152 lst[i] = Record(x, f) # create and store record
154 it: int = 0 # set iteration counter=0 (but immediately increment)
155 while True: # lst: keep 0..mu-1, overwrite mu..mu+lambda-1
156 it += 1 # step iteration counter
157 for oi in range(mu, mu_plus_lambda): # for all offspring
158 if should_terminate(): # should we stop now?
159 cast("Op0Forward", self.ls.op0).stop_forwarding() # -book
160 return # computational budget exhausted -> quit
161 dest: Record = lst[oi] # pick destination record
162 x = dest.x # the destination "x" value
163 dest.it = it # remember iteration of solution creation
165 sx = lst[r0i(mu)].x # pick random first source "x"
166 sx2 = sx # second source "x" initially=first sx
167 while sx2 is sx: # until different from sx...
168 sx2 = lst[r0i(mu)].x # ..get random second "x"
169 op2(random, x, sx, sx2) # apply binary operator
170 with for_fes(process, ls_fes) as s1, \
171 from_starting_point(s1, x, evaluate(x)) as s2:
172 forward_ls_op0_to(s2.get_copy_of_best_x)
173 ls_solve(s2) # apply local search modifying x
174 dest.f = s2.get_best_f() # get quality of x
175 lst.sort() # best records come first, ties broken by age
176 # end book
178 def __init__(self, op0: Op0,
179 op2: Op2, ls: Algorithm0,
180 mu: int = 2, lambda_: int = 1,
181 ls_fes: int = 1000,
182 name: str = "ma") -> None:
183 """
184 Create the Memetic Algorithm (MA).
186 :param op0: the nullary search operator
187 :param op2: the binary search operator
188 :param ls: the local search to apply to each new solution
189 :param mu: the number of best solutions to survive in each generation
190 :param lambda_: the number of offspring in each generation
191 :param ls_fes: the number of FEs (steps) per local search run
192 :param name: the base name of the algorithm
193 """
194 super().__init__(f"{name}{PART_SEPARATOR}{mu}{PART_SEPARATOR}"
195 f"{lambda_}{PART_SEPARATOR}{ls_fes}{PART_SEPARATOR}"
196 f"{op2}{PART_SEPARATOR}{ls}", op0)
197 if not isinstance(ls, Algorithm0):
198 raise type_error(ls, "ls", Algorithm0)
199 if not isinstance(ls.op0, Op0Forward):
200 raise type_error(ls.op0, "ls.op0", Op0Forward)
201 #: the number of records to survive in each generation
202 self.mu: Final[int] = check_int_range(mu, "mu", 1, 1_000_000)
203 #: the number of offsprings per generation
204 self.lambda_: Final[int] = check_int_range(
205 lambda_, "lambda", 1, 1_000_000)
206 #: the number of FEs per local search run
207 self.ls_fes: Final[int] = check_int_range(
208 ls_fes, "ls_fes", 1, 100_000_000)
209 #: The binary search operator.
210 self.op2: Final[Op2] = check_op2(op2)
211 #: the local search algorithm
212 self.ls: Final[Algorithm0] = ls
214 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
215 """
216 Log the parameters of the algorithm to a logger.
218 :param logger: the logger for the parameters
219 """
220 super().log_parameters_to(logger)
221 logger.key_value("mu", self.mu)
222 logger.key_value("lambda", self.lambda_)
223 logger.key_value("lsFEs", self.ls_fes)
224 with logger.scope(SCOPE_OP2) as o:
225 self.op2.log_parameters_to(o)
226 with logger.scope("ls") as ls:
227 self.ls.log_parameters_to(ls)
229 def initialize(self) -> None:
230 """Initialize the memetic algorithm."""
231 super().initialize()
232 self.ls.initialize()
233 self.op2.initialize()