Coverage for moptipy / tests / on_bitstrings.py: 85%
232 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""Test stuff on bit strings."""
3from typing import Any, Callable, Final, Iterable, cast
5import numpy as np
6from numpy.random import Generator, default_rng
7from pycommons.types import check_int_range, type_error, type_name_of
9from moptipy.algorithms.so.fitness import Fitness
10from moptipy.api.algorithm import Algorithm, check_algorithm
11from moptipy.api.execution import Execution
12from moptipy.api.mo_algorithm import MOAlgorithm
13from moptipy.api.mo_problem import MOProblem
14from moptipy.api.objective import Objective
15from moptipy.api.operators import Op0, Op1, Op1WithStepSize, Op2
16from moptipy.examples.bitstrings.ising1d import Ising1d
17from moptipy.examples.bitstrings.leadingones import LeadingOnes
18from moptipy.examples.bitstrings.onemax import OneMax
19from moptipy.examples.bitstrings.zeromax import ZeroMax
20from moptipy.mo.problem.weighted_sum import WeightedSum
21from moptipy.operators.bitstrings.op0_random import Op0Random
22from moptipy.spaces.bitstrings import BitStrings
23from moptipy.tests.algorithm import validate_algorithm
24from moptipy.tests.fitness import validate_fitness
25from moptipy.tests.mo_algorithm import validate_mo_algorithm
26from moptipy.tests.op0 import validate_op0
27from moptipy.tests.op1 import validate_op1
28from moptipy.tests.op1_with_step_size import validate_op1_with_step_size
29from moptipy.tests.op2 import validate_op2
30from moptipy.utils.nputils import array_to_str
33def dimensions_for_tests() -> Iterable[int]:
34 """
35 Get a sequence of dimensions for tests.
37 :returns: the sequence of integers
38 """
39 r = default_rng()
40 bs: list[int] = [1, 2, 3, 4, 5, 10, 16, 100,
41 int(r.integers(20, 50)), int(r.integers(200, 300))]
42 r.shuffle(cast("list", bs))
43 return bs
46def bitstrings_for_tests() -> Iterable[BitStrings]:
47 """
48 Get a sequence of bit strings for tests.
50 :returns: the sequence of BitStrings
51 """
52 return [BitStrings(i) for i in dimensions_for_tests()]
55def random_bit_string(random: Generator, x: np.ndarray) -> np.ndarray:
56 """
57 Randomize a bit string.
59 :param random: the random number generator
60 :param x: the bit string
61 :returns: the array
62 """
63 ri = random.integers
64 for i in range(len(x)): # pylint: disable=C0200
65 x[i] = ri(2) <= 0
66 return x
69def validate_op0_on_1_bitstrings(
70 op0: Op0 | Callable[[BitStrings], Op0],
71 search_space: BitStrings,
72 number_of_samples: int | None = None,
73 min_unique_samples:
74 int | Callable[[int, BitStrings], int] | None
75 = None) -> None:
76 """
77 Validate the unary operator on one bit strings instance.
79 :param op0: the operator or operator factory
80 :param search_space: the search space
81 :param number_of_samples: the optional number of samples
82 :param min_unique_samples: the optional unique samples
83 """
84 args: dict[str, Any] = {
85 "op0": op0(search_space) if callable(op0) else op0,
86 "search_space": search_space,
87 "make_search_space_element_valid": random_bit_string,
88 }
89 if number_of_samples is not None:
90 args["number_of_samples"] = number_of_samples
91 if min_unique_samples is not None:
92 args["min_unique_samples"] = min_unique_samples
93 validate_op0(**args)
96def validate_op0_on_bitstrings(
97 op0: Op0 | Callable[[BitStrings], Op0],
98 number_of_samples: int | None = None,
99 min_unique_samples:
100 int | Callable[[int, BitStrings], int] | None
101 = None) -> None:
102 """
103 Validate the unary operator on several BitStrings instances.
105 :param op0: the operator or operator factory
106 :param number_of_samples: the optional number of samples
107 :param min_unique_samples: the optional unique samples
108 """
109 for bst in bitstrings_for_tests():
110 validate_op0_on_1_bitstrings(op0, bst,
111 number_of_samples, min_unique_samples)
114def validate_op1_on_1_bitstrings(
115 op1: Op1 | Callable[[BitStrings], Op1],
116 search_space: BitStrings,
117 number_of_samples: int | None = None,
118 min_unique_samples:
119 int | Callable[[int, BitStrings], int] | None
120 = None) -> None:
121 """
122 Validate the unary operator on one BitStrings instance.
124 :param op1: the operator or operator factory
125 :param search_space: the search space
126 :param number_of_samples: the optional number of samples
127 :param min_unique_samples: the optional unique samples
128 """
129 args: dict[str, Any] = {
130 "op1": op1(search_space) if callable(op1) else op1,
131 "search_space": search_space,
132 "make_search_space_element_valid": random_bit_string,
133 }
134 if number_of_samples is not None:
135 args["number_of_samples"] = number_of_samples
136 if min_unique_samples is not None:
137 args["min_unique_samples"] = min_unique_samples
138 validate_op1(**args)
141def validate_op1_on_bitstrings(
142 op1: Op1 | Callable[[BitStrings], Op1],
143 number_of_samples: int | None = None,
144 min_unique_samples:
145 int | Callable[[int, BitStrings], int] | None
146 = None) -> None:
147 """
148 Validate the unary operator on several BitStrings instances.
150 :param op1: the operator or operator factory
151 :param number_of_samples: the optional number of samples
152 :param min_unique_samples: the optional unique samples
153 """
154 for bst in bitstrings_for_tests():
155 validate_op1_on_1_bitstrings(op1, bst,
156 number_of_samples, min_unique_samples)
159def validate_op1_with_step_size_on_1_bitstrings(
160 op1: Op1WithStepSize | Callable[[BitStrings], Op1WithStepSize],
161 search_space: BitStrings,
162 number_of_samples: int | None = None,
163 min_unique_samples: int | Callable[[
164 int, BitStrings], int] | None = None,
165 step_sizes: Iterable[float] | Callable[
166 [BitStrings], Iterable[float]] = (),
167 get_step_size: Callable[[
168 BitStrings, np.ndarray, np.ndarray,
169 ], float | None] | None = None) -> None:
170 """
171 Validate the step-sized unary operator on one `BitStrings` instance.
173 :param op1: the operator or operator factory
174 :param search_space: the search space
175 :param number_of_samples: the optional number of samples
176 :param min_unique_samples: the optional unique samples
177 :param step_sizes: the step sizes to test
178 :param get_step_size: try to get the step size from two space elements
179 """
180 args: dict[str, Any] = {
181 "op1": op1(search_space) if callable(op1) else op1,
182 "search_space": search_space,
183 "make_search_space_element_valid": random_bit_string,
184 "step_sizes": step_sizes(search_space) if callable(step_sizes)
185 else step_sizes,
186 "get_step_size": get_step_size,
187 }
188 if number_of_samples is not None:
189 args["number_of_samples"] = number_of_samples
190 if min_unique_samples is not None:
191 args["min_unique_samples"] = min_unique_samples
192 validate_op1_with_step_size(**args)
195def validate_op1_with_step_size_on_bitstrings(
196 op1: Op1WithStepSize | Callable[[BitStrings], Op1WithStepSize],
197 number_of_samples: int | None = None,
198 min_unique_samples: int | Callable[[
199 int, BitStrings], int] | None = None,
200 step_sizes: Iterable[float] | Callable[
201 [BitStrings], Iterable[float]] = (),
202 get_step_size: Callable[[
203 BitStrings, np.ndarray, np.ndarray,
204 ], float | None] | None = None) -> None:
205 """
206 Validate the unary operator on several `BitStrings` instances.
208 :param op1: the operator or operator factory
209 :param number_of_samples: the optional number of samples
210 :param min_unique_samples: the optional unique samples
211 :param step_sizes: the step sizes to test
212 :param get_step_size: try to get the step size from two space elements
213 """
214 for bs in bitstrings_for_tests():
215 validate_op1_with_step_size_on_1_bitstrings(
216 op1, bs, number_of_samples, min_unique_samples, step_sizes,
217 get_step_size)
220def validate_op2_on_1_bitstrings(
221 op2: Op2 | Callable[[BitStrings], Op2],
222 search_space: BitStrings,
223 number_of_samples: int | None = None,
224 min_unique_samples:
225 int | Callable[[int, BitStrings], int] | None
226 = None) -> None:
227 """
228 Validate the binary operator on one BitStrings instance.
230 :param op2: the operator or operator factory
231 :param search_space: the search space
232 :param number_of_samples: the optional number of samples
233 :param min_unique_samples: the optional unique samples
234 """
235 args: dict[str, Any] = {
236 "op2": op2(search_space) if callable(op2) else op2,
237 "search_space": search_space,
238 "make_search_space_element_valid": random_bit_string,
239 }
240 if number_of_samples is not None:
241 args["number_of_samples"] = number_of_samples
242 if min_unique_samples is not None:
243 args["min_unique_samples"] = min_unique_samples
244 validate_op2(**args)
247def validate_op2_on_bitstrings(
248 op2: Op2 | Callable[[BitStrings], Op2],
249 number_of_samples: int | None = None,
250 min_unique_samples:
251 int | Callable[[int, BitStrings], int] | None
252 = None) -> None:
253 """
254 Validate the binary operator on several BitStrings instances.
256 :param op2: the operator or operator factory
257 :param number_of_samples: the optional number of samples
258 :param min_unique_samples: the optional unique samples
259 """
260 for bst in bitstrings_for_tests():
261 validate_op2_on_1_bitstrings(op2, bst,
262 number_of_samples, min_unique_samples)
265def validate_algorithm_on_bitstrings(
266 objective: Objective | Callable[[int], Objective],
267 algorithm: Algorithm | Callable[
268 [BitStrings, Objective], Algorithm],
269 dimension: int = 5, max_fes: int = 100,
270 required_result: int | Callable[
271 [int, int], int] | None = None,
272 uses_all_fes_if_goal_not_reached: bool = True,
273 post: Callable[[Algorithm, int], Any] | None = None) -> None:
274 """
275 Check the validity of a black-box algorithm on a bit strings problem.
277 :param algorithm: the algorithm or algorithm factory
278 :param objective: the objective function or function factory
279 :param dimension: the dimension of the problem
280 :param max_fes: the maximum number of FEs
281 :param required_result: the optional required result quality
282 :param uses_all_fes_if_goal_not_reached: will the algorithm use all FEs
283 unless it reaches the goal?
284 :param post: a check to run after each execution of the algorithm,
285 receiving the algorithm and the number of consumed FEs as parameter
286 """
287 if not (isinstance(algorithm, Algorithm) or callable(algorithm)):
288 raise type_error(algorithm, "algorithm", Algorithm, True)
289 if not (isinstance(objective, Objective) or callable(objective)):
290 raise type_error(objective, "objective", Objective, True)
291 check_int_range(dimension, "dimension", 1, 1_000_000)
292 if (post is not None) and (not callable(post)):
293 raise type_error(post, "post", None, call=True)
295 if callable(objective):
296 objective = objective(dimension)
297 if not isinstance(objective, Objective):
298 raise type_error(objective, "result of callable 'objective'",
299 Objective)
300 bs: Final[BitStrings] = BitStrings(dimension)
301 if callable(algorithm):
302 algorithm = algorithm(bs, objective)
303 if not isinstance(algorithm, Algorithm):
304 raise type_error(algorithm, "result of callable 'algorithm'",
305 Algorithm)
307 goal: Final[int | None] = required_result(max_fes, dimension) \
308 if callable(required_result) else required_result
310 validate_algorithm(
311 algorithm=algorithm, solution_space=bs, objective=objective,
312 max_fes=max_fes, required_result=goal,
313 uses_all_fes_if_goal_not_reached=uses_all_fes_if_goal_not_reached,
314 post=post)
317def validate_algorithm_on_onemax(
318 algorithm: Algorithm | Callable[
319 [BitStrings, Objective], Algorithm],
320 post: Callable[[Algorithm, int], Any] | None = None) -> None:
321 """
322 Check the validity of a black-box algorithm on OneMax.
324 :param algorithm: the algorithm or algorithm factory
325 :param post: a check to run after each execution of the algorithm,
326 receiving the algorithm and the number of consumed FEs as parameter
327 """
328 max_fes: Final[int] = 100
329 for i in dimensions_for_tests():
330 rr: int = 1 if i < 3 else (1 + max(1, i // 2, i - int(max_fes ** 0.5)))
331 validate_algorithm_on_bitstrings(
332 objective=OneMax,
333 algorithm=algorithm,
334 dimension=i,
335 max_fes=max_fes,
336 required_result=rr,
337 post=post)
340def validate_algorithm_on_leadingones(
341 algorithm: Algorithm | Callable[
342 [BitStrings, Objective], Algorithm],
343 post: Callable[[Algorithm, int], Any] | None = None) -> None:
344 """
345 Check the validity of a black-box algorithm on LeadingOnes.
347 :param algorithm: the algorithm or algorithm factory
348 :param post: a check to run after each execution of the algorithm,
349 receiving the algorithm and the number of consumed FEs as parameter
350 """
351 max_fes: Final[int] = 100
352 for i in dimensions_for_tests():
353 rr: int
354 if i < 3:
355 rr = 1
356 elif max_fes > (10 * (i ** 1.5)):
357 rr = i - 1
358 else:
359 rr = i
360 validate_algorithm_on_bitstrings(
361 objective=LeadingOnes,
362 algorithm=algorithm,
363 dimension=i,
364 max_fes=int(1.4 * max_fes),
365 required_result=rr,
366 post=post)
369def validate_mo_algorithm_on_bitstrings(
370 problem: MOProblem | Callable[[int], MOProblem],
371 algorithm: MOAlgorithm | Callable[
372 [BitStrings, MOProblem], MOAlgorithm],
373 dimension: int = 5,
374 max_fes: int = 100) -> None:
375 """
376 Check a black-box multi-objective algorithm on a bit strings problem.
378 :param algorithm: the algorithm or algorithm factory
379 :param problem: the multi-objective optimization problem or factory
380 :param dimension: the dimension of the problem
381 :param max_fes: the maximum number of FEs
382 """
383 if not (isinstance(algorithm, MOAlgorithm) or callable(algorithm)):
384 raise type_error(algorithm, "algorithm", MOAlgorithm, True)
385 if not (isinstance(problem, MOProblem) or callable(problem)):
386 raise type_error(problem, "problem", MOProblem, True)
387 check_int_range(dimension, "dimension", 1, 1_000_000)
389 if callable(problem):
390 problem = problem(dimension)
391 if not isinstance(problem, MOProblem):
392 raise type_error(problem, "result of callable 'problem'",
393 MOProblem)
394 bs: Final[BitStrings] = BitStrings(dimension)
395 if callable(algorithm):
396 algorithm = algorithm(bs, problem)
397 if not isinstance(algorithm, MOAlgorithm):
398 raise type_error(algorithm, "result of callable 'algorithm'",
399 MOAlgorithm)
401 validate_mo_algorithm(algorithm=algorithm,
402 solution_space=bs,
403 problem=problem,
404 max_fes=max_fes)
407def validate_mo_algorithm_on_2_bitstring_problems(
408 algorithm: MOAlgorithm | Callable[
409 [BitStrings, MOProblem], MOAlgorithm]) -> None:
410 """
411 Check the validity of a black-box algorithm on OneMax and ZeroMax.
413 :param algorithm: the algorithm or algorithm factory
414 """
415 max_fes: Final[int] = 100
416 random: Final[Generator] = default_rng()
417 for i in dimensions_for_tests():
418 weights: list[int | float] = [float(random.uniform(0.01, 10)),
419 float(random.uniform(0.01, 10))] \
420 if random.integers(2) <= 0 else \
421 [1 + int(random.integers(1 << random.integers(40))),
422 1 + int(random.integers(1 << random.integers(40)))]
423 validate_mo_algorithm_on_bitstrings(
424 problem=WeightedSum([OneMax(i), ZeroMax(i)], weights),
425 algorithm=algorithm,
426 dimension=i,
427 max_fes=max_fes)
430def validate_mo_algorithm_on_3_bitstring_problems(
431 algorithm: MOAlgorithm | Callable[
432 [BitStrings, MOProblem], MOAlgorithm]) -> None:
433 """
434 Check the validity of an algorithm on OneMax, ZeroMax, and Ising1d.
436 :param algorithm: the algorithm or algorithm factory
437 """
438 max_fes: Final[int] = 100
439 random: Final[Generator] = default_rng()
440 for i in dimensions_for_tests():
441 weights: list[int | float] = [float(random.uniform(0.01, 10)),
442 float(random.uniform(0.01, 10)),
443 float(random.uniform(0.01, 10))] \
444 if random.integers(2) <= 0 else \
445 [1 + int(random.integers(1 << random.integers(40))),
446 1 + int(random.integers(1 << random.integers(40))),
447 1 + int(random.integers(1 << random.integers(40)))]
448 validate_mo_algorithm_on_bitstrings(
449 problem=WeightedSum([OneMax(i), ZeroMax(i), Ising1d(i)],
450 weights),
451 algorithm=algorithm,
452 dimension=i,
453 max_fes=max_fes)
456def verify_algorithms_equivalent(
457 algorithms: Iterable[Callable[[BitStrings, Objective], Algorithm]],
458 max_fes: int | None = None) \
459 -> None:
460 """
461 Verify that a set of algorithms performs identical steps.
463 :param algorithms: the sequence of algorithms
464 :param max_fes: the maximum number of FEs
465 """
466 if not isinstance(algorithms, Iterable):
467 raise type_error(algorithms, "algorithms", Iterable)
468 if (max_fes is not None) and (not isinstance(max_fes, int)):
469 raise type_error(max_fes, "max_fes", int)
471 random: Final[Generator] = default_rng()
472 dim: Final[int] = int(random.integers(4, 16))
473 space: Final[BitStrings] = BitStrings(dim)
474 steps: Final[int] = int(random.integers(100, 1000)) \
475 if max_fes is None else max_fes
476 if steps <= 0:
477 raise ValueError(f"invalid maximum FEs={steps} for max_fes={max_fes}")
478 choice: Final[int] = int(random.integers(3))
479 f: Final[Objective] = \
480 LeadingOnes(dim) if choice <= 0 else \
481 OneMax(dim) if choice <= 1 else \
482 Ising1d(dim)
483 evaluate: Final[Callable] = f.evaluate # noqa
484 seed: Final[int] = int(random.integers(1 << 62))
486 result1: Final[list[bool]] = []
487 result2: Final[list[bool]] = []
488 first: bool = True
489 first_name: str = ""
490 do_fes: int = -1
491 do_res: int | float = -1
492 for index, algo in enumerate(algorithms):
493 if not callable(algo):
494 raise type_error(algo, f"algorithms[{index}] for {f}", call=True)
495 algorithm: Algorithm = check_algorithm(algo(space, f))
496 current_name: str = str(algorithm)
497 if first:
498 first_name = current_name
499 result = result1
500 else:
501 result = result2
502 result.clear()
504 def ff(x, rr=(result, )) -> int:
505 rres = evaluate(x)
506 rr[0].extend(x)
507 return rres
509 ex = Execution()
510 ex.set_algorithm(algorithm)
511 ex.set_solution_space(space)
512 f.evaluate = ff # type: ignore
513 ex.set_objective(f)
514 ex.set_rand_seed(seed)
515 ex.set_max_fes(steps)
516 with ex.execute() as p:
517 cf = p.get_consumed_fes()
518 if not (0 < cf <= steps):
519 raise ValueError(f"{current_name} consumed {cf} FS for "
520 f"{steps} max FEs on {f} for seed {seed}.")
521 if first:
522 do_fes = cf
523 elif do_fes != cf:
524 raise ValueError(f"{current_name} consumed {cf} FEs but "
525 f"{first_name} consumed {do_fes} FEs on "
526 f"{f} for seed {seed}.")
527 res = p.get_best_f()
528 if not (0 <= res <= dim):
529 raise ValueError(f"{current_name} got {res} as objective "
530 f"value on {f} for seed {seed}.")
531 if first:
532 do_res = res
533 elif do_res != res:
534 raise ValueError(
535 f"{current_name} got {res} as objective value on {f} but "
536 f"{first_name} got {do_res} for seed {seed}.")
537 if len(result) != (cf * dim):
538 raise ValueError(
539 f"len(result) == {len(result)}, but should be {cf * dim} "
540 f"for {current_name} for seed {seed} on {f}.")
541 if (not first) and (result1 != result2):
542 raise ValueError(
543 f"{current_name} produced different steps than {first_name} "
544 f"on {f} for seed {seed}: is "
545 f"{array_to_str(np.array(result2))}"
546 f" but should be {array_to_str(np.array(result1))}.")
548 first = False
551def validate_fitness_on_bitstrings(
552 fitness: Fitness | Callable[[Objective], Fitness],
553 class_needed: str | type = Fitness,
554 prepare_objective: Callable[[Objective], Objective] = lambda x: x) \
555 -> None:
556 """
557 Validate a fitness assignment process on bit strings.
559 :param fitness: the fitness assignment process, or a callable creating it
560 :param class_needed: the required class
561 :param prepare_objective: prepare the objective function
562 """
563 if (not isinstance(fitness, Fitness)) and (not callable(fitness)):
564 raise type_error(fitness, "fitness", Fitness, call=True)
565 if not isinstance(class_needed, str | type):
566 raise type_error(class_needed, "class_needed", (str, type))
567 if not callable(prepare_objective):
568 raise type_error(prepare_objective, "prepare_objective", call=True)
570 random: Final[Generator] = default_rng()
571 sizes: set[int] = set()
572 while len(sizes) < 4:
573 sizes.add(int(random.integers(2, 10)))
574 op0: Op0Random = Op0Random()
575 for s in sizes:
576 space: BitStrings = BitStrings(s)
577 f: Objective = OneMax(s) if random.integers(2) <= 0 else LeadingOnes(s)
578 f2 = prepare_objective(f)
579 if not isinstance(f2, Objective):
580 raise type_error(f2, f"prepare_objective({f})", Objective)
581 del f
582 if callable(fitness):
583 ff = fitness(f2)
584 if not isinstance(ff, Fitness):
585 raise type_error(ff, f"fitness({f2})", Fitness)
586 if isinstance(class_needed, str):
587 name = type_name_of(ff)
588 if name != class_needed:
589 raise TypeError(f"fitness assignment process should be "
590 f"{class_needed!r}, but is {name!r}.")
591 elif not isinstance(ff, class_needed):
592 raise type_error(ff, f"fitness({f2})", class_needed)
593 else:
594 ff = fitness
595 validate_fitness(ff, f2, space, op0)