moptipy.algorithms.modules package

A set of reuseable algorithm modules.

Subpackages

Submodules

moptipy.algorithms.modules.selection module

Selection algorithms are common modules that choose n out of N objects.

Selection algorithms are modules of the fully-configurable Evolutionary Algorithm GeneralEA. They can utilize fitness values computed by the fitness assignment processes (Fitness). Of course, they can also be applied in different contexts and are not bound to single-objective optimization.

Selection is especially important in Evolutionary Algorithms (~moptipy.algorithms.so.general_ea.GeneralEA), where it is used in two places: As survival selection, it chooses which points will be allowed to remain in the population and, hence, survive into the mating pool for the next generation. As mating selection methods, they choose the inputs of the search operations from the mating pool.

Selection algorithms must only use the fitness of a solution record (and random numbers) to make their decisions. These fitness values are subject to minimization. They can equal to the objective values in optimization or stem from a Fitness Assignment Process.

The following selection algorithms have currently been implemented:

  • Best selection selects the best n solutions without replacement. This is a common strategy for survival selection, especially in (mu+lambda) EAs (compatible to EA).

  • RandomWithoutReplacement selects random solutions without replacement. It is a common strategy for mating selection.

  • FitnessProportionateSUS performs fitness proportionate selection for minimization using stochastic uniform sampling and, optionally, a minimum selection probability threshold. It is the classic survival selection algorithm in Genetic Algorithm.

  • TournamentWithReplacement performs tournament selection with a specified tournament size with replacement.

  • TournamentWithoutReplacement performs tournament selection with a specified tournament size without replacement.

class moptipy.algorithms.modules.selection.FitnessRecord(*args, **kwargs)[source]

Bases: Protocol

A fitness record stores data together with a fitness.

fitness: float

the fitness value, which can either be an integer or a float and is the only criterion to be used by a selection algorithm (besides random numbers)

class moptipy.algorithms.modules.selection.Selection[source]

Bases: Component

The base class for selections algorithms.

select(source, dest, n, random)[source]

Select n records from source and pass them to dest.

When choosing the n records from source to be passed to dest, only the fitness attribute of the records and the random numbers from random must be used as decision criteria.

Parameters:

  • source (list[FitnessRecord]) – the list with the records to select from

  • dest (Callable[[FitnessRecord], Any]) – the destination collector Callable to invoke for each selected record, can be list.`append`.

  • n (int) – the number of records to select

  • random (Generator) – the random number generator

Return type:

None

moptipy.algorithms.modules.selection.check_selection(selection)[source]

Check whether an object is a valid instance of Selection.

Parameters:

selection (Selection) – the Selection object

Return type:

Selection

Returns:

the object

Raises:

TypeError – if selections is not an instance of Selection or if it is an instance of the abstract base class

moptipy.algorithms.modules.temperature_schedule module

A temperature schedule as needed by Simulated Annealing.

The Simulated Annealing algorithm implemented in simulated_annealing performs a local search that always accepts a non-worsening move, i.e., a solution which is not worse than the currently maintained one. However, it will also sometimes accept one that is worse. The probability of doing so depends on how much worse that solution is and on the current temperature of the algorithm. The higher the temperature, the higher the acceptance probability. The temperature changes over time according to the TemperatureSchedule.

The temperature schedule receives an iteration index tau as input and returns the current temperature via temperature(). Notice that tau is zero-based for simplicity reason, meanings that the first objective function evaluation is at index 0.

class moptipy.algorithms.modules.temperature_schedule.ExponentialSchedule(t0, epsilon)[source]

Bases: TemperatureSchedule

The exponential temperature schedule.

The current temperature is computed as t0 * (1 - epsilon) ** tau.

>>> ex = ExponentialSchedule(10.0, 0.05)
>>> print(f"{ex.t0} - {ex.epsilon}")
10.0 - 0.05
>>> ex.temperature(0)
10.0
>>> ex.temperature(1)
9.5
>>> ex.temperature(2)
9.025
>>> ex.temperature(1_000_000_000_000_000_000)
0.0
epsilon: Final[float]

the epsilon parameter of the exponential schedule

log_parameters_to(logger)[source]

Log all parameters of the exponential temperature schedule.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
...     with l.key_values("C") as kv:
...         ExponentialSchedule(0.2, 0.6).log_parameters_to(kv)
...     text = l.get_log()
>>> text[1]
'name: exp0d2_0d6'
>>> text[3]
'T0: 0.2'
>>> text[5]
'e: 0.6'
>>> len(text)
8
temperature(tau)[source]

Compute the temperature at iteration tau.

Parameters:

tau (int) – the iteration index, starting with 0 at the first comparison of two solutions, at which point the starting temperature t0 should be returned

Return type:

float

Returns:

the temperature

>>> s = ExponentialSchedule(100.0, 0.5)
>>> s.temperature(0)
100.0
>>> s.temperature(1)
50.0
>>> s.temperature(10)
0.09765625
class moptipy.algorithms.modules.temperature_schedule.ExponentialScheduleBasedOnBounds(f, lb_sum_weight=-1, ub_sum_weight=1, start_factor=0.001, end_factor=1e-07, n_steps=1000000, min_bound_sum=1e-20, max_bound_sum=1e+20)[source]

Bases: ExponentialSchedule

An exponential schedule configured based on the objective’s range.

This exponential schedule takes an objective function as parameter. It uses the lower and the upper bound of this function, LB and UB, to select a start and end temperature based on the provided fractions. Here, we set W = lb_sum_weight * LB + ub_sum_weight * UB. If we set lb_sum_weight = -1 and ub_sum_weight = 1, then W will be the range of the objective function. If we set lb_sum_weight = 1 and ub_sum_weight = 0, then we base the temperature setup entirely on the lower bound. If we set lb_sum_weight = 0 and ub_sum_weight = 1, then we base the temperature setup entirely on the upper bound. Roughly, the start temperature will be W * start_range_frac and the end temperature, to be reached after n_steps FEs, will be W * end_range_frac. Since sometimes the upper and lower bound may be excessivly large, we can provide limits for W in form of min_bound_sum and max_bound_sum. This will then override any other computation. Notice that it is expected that tau == 0 when the temperature function is first called. It is expected that tau == n_range - 1 when it is called for the last time.

>>> from moptipy.examples.bitstrings.onemax import OneMax
>>> es = ExponentialScheduleBasedOnBounds(
...     OneMax(10), -1, 1, 0.01, 0.0001, 10**8)
>>> es.temperature(0)
0.1
>>> es.temperature(1)
0.09999999539482989
>>> es.temperature(10**8 - 1)
0.0010000000029841878
>>> es.temperature(10**8)
0.0009999999569324865

>>> es = ExponentialScheduleBasedOnBounds(
...         OneMax(10), -1, 1, 0.01, 0.0001, 10**8, max_bound_sum=5)
>>> es.temperature(0)
0.05
>>> es.temperature(1)
0.04999999769741494
>>> es.temperature(10**8 - 1)
0.0005000000014920939
>>> es.temperature(10**8)
0.0004999999784662432

>>> try:
...     ExponentialScheduleBasedOnBounds(1, 0.01, 0.0001, 10**8)
... except TypeError as te:
...     print(te)
objective function should be an instance of moptipy.api.objective.Objective but is int, namely 1.

>>> try:
...     ExponentialScheduleBasedOnBounds(
...         OneMax(10), -1, 1, -1.0, 0.0001, 10**8)
... except ValueError as ve:
...     print(ve)
Invalid bound sum factors [-1.0, 0.0001].

>>> try:
...     ExponentialScheduleBasedOnBounds(
...         OneMax(10), -1, 1, 0.9, 0.0001, 1)
... except ValueError as ve:
...     print(ve)
n_steps=1 is invalid, must be in 2..1000000000000000.
log_parameters_to(logger)[source]

Log all parameters of the configured exponential temperature schedule.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

>>> from moptipy.utils.logger import InMemoryLogger
>>> from moptipy.examples.bitstrings.onemax import OneMax
>>> with InMemoryLogger() as l:
...     with l.key_values("C") as kv:
...         ExponentialScheduleBasedOnBounds(
...             OneMax(10), -1, 1, 0.01, 0.0001).log_parameters_to(kv)
...     text = l.get_log()
>>> text[1]
'name: expRm1_1_0d01_0d0001_1em20_1e20'
>>> text[3]
'T0: 0.1'
>>> text[5]
'e: 4.6051641873212645e-6'
>>> text[7]
'nSteps: 1000000'
>>> text[8]
'lbSumWeight: -1'
>>> text[9]
'ubSumWeight: 1'
>>> len(text)
25
class moptipy.algorithms.modules.temperature_schedule.LogarithmicSchedule(t0, epsilon)[source]

Bases: TemperatureSchedule

The logarithmic temperature schedule.

The temperature is computed as t0 / log(e + (tau * epsilon)).

>>> lg = LogarithmicSchedule(10.0, 0.1)
>>> print(f"{lg.t0} - {lg.epsilon}")
10.0 - 0.1
>>> lg.temperature(0)
10.0
>>> lg.temperature(1)
9.651322627630812
>>> lg.temperature(1_000_000_000_000_000_000_000_000_000_000_000_000_000)
0.11428802155348732
epsilon: Final[float]

the epsilon parameter of the logarithmic schedule

log_parameters_to(logger)[source]

Log all parameters of the logarithmic temperature schedule.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
...     with l.key_values("C") as kv:
...         LogarithmicSchedule(0.2, 0.6).log_parameters_to(kv)
...     text = l.get_log()
>>> text[1]
'name: ln0d2_0d6'
>>> text[3]
'T0: 0.2'
>>> text[5]
'e: 0.6'
>>> len(text)
8
temperature(tau)[source]

Compute the temperature at iteration tau.

Parameters:

tau (int) – the iteration index, starting with 0 at the first comparison of two solutions, at which point the starting temperature t0 should be returned

Return type:

float

Returns:

the temperature

>>> s = LogarithmicSchedule(100.0, 0.5)
>>> s.temperature(0)
100.0
>>> s.temperature(1)
85.55435113150568
>>> s.temperature(10)
48.93345190925178
class moptipy.algorithms.modules.temperature_schedule.TemperatureSchedule(t0)[source]

Bases: Component

The base class for temperature schedules.

log_parameters_to(logger)[source]

Log all parameters of this temperature schedule as key-value pairs.

Parameters:

logger (KeyValueLogSection) – the logger for the parameters

Return type:

None

>>> from moptipy.utils.logger import InMemoryLogger
>>> with InMemoryLogger() as l:
...     with l.key_values("C") as kv:
...         TemperatureSchedule(0.1).log_parameters_to(kv)
...     text = l.get_log()
>>> text[1]
'name: TemperatureSchedule'
>>> text[3]
'T0: 0.1'
>>> len(text)
6
t0: Final[float]

the starting temperature

temperature(tau)[source]

Compute the temperature at iteration tau.

Parameters:

tau (int) – the iteration index, starting with 0 at the first comparison of two solutions, at which point the starting temperature t0 should be returned

Return type:

float

Returns:

the temperature