moptipy.algorithms package¶
In this package, we provide implementations of metaheuristic algorithms.
We divide them into single-objective algorithms, which are provided in the package moptipy.algorithms.so, and multi-objective algorithms, which can be found in package moptipy.algorithms.mo.
Methods which are based on random sampling and random walks are unaffected by the number of objective functions and therefore can be found in this package directly.
The black-box methods are given directly in these package, more specialized algorithms will be placed in sub-packages corresponding to their requirements for the search- and solution space. Perform restarts of an algorithm based on the Luby sequence. Luby et al. showed that, for Las Vegas algorithms with known run time distribution, there is an optimal stopping time in order to minimize the expected running time. Even if the distribution is unknown, there is a universal sequence of running times given by (1,1,2,1,1,2,4,1,1,2,1,1,2,4, 8,…), which is the optimal restarting strategy up to constant factors. While this only holds for Las Vegas algorithms, this restart length may also be used for optimization, e.g., if we aim to find a globally optimal solution. M. Luby, A. Sinclair, and S. Zuckerman. Optimal Speedup of Las Vegas Algorithms. Information Processing Letters 47(4):173-180. September 1993. https://doi.org/10.1016/0020-0190(93)90029-9 the type variable for single- and multi-objective algorithms. alias of TypeVar(‘T’, ~moptipy.api.algorithm.Algorithm, ~moptipy.api.mo_algorithm.MOAlgorithm) Perform restarts of an algorithm in the Luby fashion. The restart run length in FEs is determined by the Luby sequence (1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, 1, 2, 1, 1, 2, 4, 1, …) multiplied by base_fes. Restarts are performed until a termination criterion is met. algorithm ( base_fes ( log_restarts ( The random sampling algorithm rs. The random sampling algorithm keeps creating random solutions until the computational budget is exhausted or any other termination criterion is met. In a loop that is repeated until the termination criterion applies the nullary search operator, an implementation of evaluates the solution by passing it to This algorithm has a very bad performance. It makes no use of the information that is learned during the search. Every single solution is created completely independent on anything that has happened before in the algorithm. Only if the problem is completely random, has no structure, or is entirely deceptive, this algorithm can be of any use. Basically, this algorithm is an iterated version of the 1rs algorithm implemented in Thomas Weise. Optimization Algorithms. 2021. Hefei, Anhui, China: Institute of Applied Optimization (IAO), School of Artificial Intelligence and Big Data, Hefei University. http://thomasweise.github.io/oa/ Bases: In each step, random sampling creates a new, random solution. A random walk algorithm implementation. A random walk starts with a random point in the search space created with the nullary search operator. In each step, it applies the unary search operator to move a new point. It does not really care whether the new point is better or worse, it will always accept it. Of course, it still needs to call the objective function to make sure to inform the Bases: Perform a random walk through the search space. In each step, a random walk creates a modified copy of the current solution and accepts it as starting point for the next step. Perform restarts of an algorithm that terminates too early. the type variable for single- and multi-objective algorithms. alias of TypeVar(‘T’, ~moptipy.api.algorithm.Algorithm, ~moptipy.api.mo_algorithm.MOAlgorithm) Perform restarts of an algorithm until the termination criterion is met. algorithm ( The 1rs “algorithm” creates one single random solution. The single random sample algorithm applies the nullary search operator, an implementation of This is a very very bad optimization algorithm. We only use it in our book to illustrate one basic concept for solving optimization problems: The generation of random solutions. The single-random sampling algorithm here is actually very wasteful: since it only generates exactly one single solution, it does not use its computational budget well. Even if you grant it 10’000 years, it will still only generate one solution. Even if it could generate and test thousands or millions of solutions, it will not do it. Nevertheless, after applying this “algorithm,” you will have one valid solution remembered in the optimization process (embodied as instance process of This concept of random sampling is then refined in the Thomas Weise. Optimization Algorithms. 2021. Hefei, Anhui, China: Institute of Applied Optimization (IAO), School of Artificial Intelligence and Big Data, Hefei University. http://thomasweise.github.io/oa/ Bases: An algorithm that creates one single random solution.Subpackages¶
Submodules¶
moptipy.algorithms.luby_restarts module¶
TypeVar(T, Algorithm, MOAlgorithm)) – the algorithmint, default: 64) – the basic objective function evaluationsbool, default: False) – should we log the restarts?TypeVar(T, Algorithm, MOAlgorithm)moptipy.algorithms.random_sampling module¶
should_terminate() becomes True, itop0(), to sample exactly one single random solution. It thenevaluate().SingleRandomSample.Algorithm0moptipy.algorithms.random_walk module¶
moptipy.api.process.Process about the new point so that, at the end, we can obtain the best point that was visited. But during the course of its run, it will walk around the search space randomly without direction.Algorithm1moptipy.algorithms.restarts module¶
TypeVar(T, Algorithm, MOAlgorithm)) – the algorithmTypeVar(T, Algorithm, MOAlgorithm)moptipy.algorithms.single_random_sample module¶
op0(), to sample exactly one single random solution. It then evaluates the solution by passing it to evaluate(). It then terminates.Process).RandomSampling as the rs algorithm, which repeats generating random solutions until its allotted runtime is exhausted.Algorithm0