moptipy.operators.bitstrings package

In this package we provide operators for bit strings.

  • Module op0_random offers a nullary search operator that samples bit strings of a fixed length in a uniform random fashion.

  • Module op1_flip1 offers a unary operator that flips exactly one bit.

  • Module op1_flip_m offers a unary operator with step size (see Op1WithStepSize). A step size of 0.0 means that it will flip one bit, a step size of 1.0 means that it flips all bits.

  • Module op1_m_over_n_flip flips each bit with probability m/n but ensures that at least one bit is flipped. This results in a number of bits being flipped being drawn from a Binomial distribution (and re-drawn if 0 was drawn).

  • Module op2_uniform offers the binary uniform crossover operation which copies each bit with probability 0.5 from the first and with the same probability from the second parent.

Submodules

moptipy.operators.bitstrings.op0_random module

A nullary operator filling a bit string with random values.

class moptipy.operators.bitstrings.op0_random.Op0Random[source]

Bases: Op0

Fill a bit string with random values.

op0(random, dest)[source]

Fill the string dest with random values.

Parameters:

  • random (Generator) – the random number generator

  • dest (ndarray) – the bit string to fill. Afterwards, its contents will be random.

Return type:

None

moptipy.operators.bitstrings.op1_flip1 module

A unary operator flipping exactly one bit.

class moptipy.operators.bitstrings.op1_flip1.Op1Flip1[source]

Bases: Op1

A unary search operation that flips exactly one bit.

op1(random, dest, x)[source]

Copy x into dest and flip exactly one bit.

Parameters:

  • self – the self pointer

  • random (Generator) – the random number generator

  • dest (ndarray) – the destination array to receive the new point

  • x (ndarray) – the existing point in the search space

Return type:

None

moptipy.operators.bitstrings.op1_flip_m module

A unary operator flipping a pre-defined number of bits.

This is a unary operator with step size, i.e., an instance of Op1WithStepSize. As such, it also receives a parameter step_size when it is applied, which is from the closed range [0.0, 1.0]. If step_size=0, then exactly 1 bit will be flipped. If step_size=1, then all bits will be flipped. For all values of 0<step_size<1, we use the function exponential_step_size() to extrapolate the number of bits to flip.

Unary operators like this are often used in (1+1)-EAs or even in state-of-the-art EAs such as the Self-Adjusting (1+(lambda,lambda)) GA.

  1. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient. IEEE Transactions on Evolutionary Computation (TEVC). 2022. doi: https://doi.org/10.1109/TEVC.2022.3191698, https://arxiv.org/pdf/2112.00229.pdf.

  2. Eduardo Carvalho Pinto and Carola Doerr. Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms, 2018, arXiv:1812.00493v1 [cs.NE] 3 Dec 2018. https://arxiv.org/abs/1812.00493.

class moptipy.operators.bitstrings.op1_flip_m.Op1FlipM[source]

Bases: Op1WithStepSize

A unary search operation that flips a specified number of m bits.

op1(random, dest, x, step_size=0.0)[source]

Copy x into dest and flip exactly m bits.

step_size=0.0 will flip exactly 1 bit, step_size=1.0 will flip all n bits. All other values are extrapolated by function exponential_step_size(). In between the two extremes, an exponential scaling (exponential_step_size()) is performed, meaning that for n=10 bits, a step-size of 0.2 means flipping two bits, 0.4 means flipping three bits, 0.6 means flipping four bits, 0.7 means flipping five bits, 0.9 means flipping eight bits, 0.95 means flipping nine bits, and 1.0 means flipping all bits. In other words, a larger portion of the step_size range corresponds to making small changes while the large changes are all condensed at the higher end of the scale.

Parameters:

  • self – the self pointer

  • random (Generator) – the random number generator

  • dest (ndarray) – the destination array to receive the new point

  • x (ndarray) – the existing point in the search space

  • step_size (float, default: 0.0) – the number of bits to flip

Return type:

None

>>> op1 = Op1FlipM()
>>> from numpy.random import default_rng as drg
>>> rand = drg()
>>> import numpy as npx
>>> src = npx.zeros(10, bool)
>>> dst = npx.zeros(10, bool)
>>> for ss in [0.0, 0.2, 0.4, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95, 1.0]:
...   op1.op1(rand, dst, src, ss)
...   print(sum(dst != src))
1
2
3
4
5
6
7
8
9
10

moptipy.operators.bitstrings.op1_m_over_n_flip module

A unary operator flipping each bit with probability m/n.

class moptipy.operators.bitstrings.op1_m_over_n_flip.Op1MoverNflip(n, m=1, at_least_1=True)[source]

Bases: Op1

A unary search operation that flips each bit with probability of m/n.

For bit strings of length n, draw the number z of bits to flip from a binomial distribution with p=m/n. If at_least_1 is set to True, then we repeat drawing z until z>0.

initialize()[source]

Initialize this operator.

Return type:

None

op1(random, dest, x)[source]

Copy x into dest and flip each bit with probability m/n.

This method will first copy x to dest. Then it will flip each bit in dest with probability m/n, where n is the length of dest. Regardless of the probability, at least one bit will always be flipped if self.at_least_1 is True.

Parameters:

  • self – the self pointer

  • random (Generator) – the random number generator

  • dest (ndarray) – the destination array to receive the new point

  • x (ndarray) – the existing point in the search space

Return type:

None

moptipy.operators.bitstrings.op2_uniform module

A binary operator copying each bit from either source string.

Uniform crossover copies the value of every bit with the same probability from either of the two parent strings. This means that all bits where both parent strings have the same value remain unchanged and are copied directly to the offspring. The bits where the parent strings have different values are effectively randomized. This is easy to see from the fact that, if both parents have different values for one bit, then one of them must have the bit set to 1 and the other one set to 0. This means that the value in the offspring is set to 0 with probability 0.5 and set to 1 with probability 0.5. This corresponds to drawing it uniformly at random, i.e., randomizing it.

  1. Gilbert Syswerda. Uniform Crossover in Genetic Algorithms. In J. David Schaffer, editor, Proceedings of the 3rd International Conference on Genetic Algorithms (ICGA’89), June 4-7, 1989, Fairfax, VA, USA, pages 2-9. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. ISBN: 1-55860-066-3. https://www.researchgate.net/publication/201976488.

  2. Hans-Georg Beyer and Hans-Paul Schwefel. Evolution Strategies - A Comprehensive Introduction. Natural Computing: An International Journal 1(1):3-52, March 2002, http://doi.org/10.1023/A:1015059928466. https://www.researchgate.net/publication/220132816.

  3. Hans-Georg Beyer. An Alternative Explanation for the Manner in which Genetic Algorithms Operate. Biosystems 41(1):1-15, January 1997, https://doi.org/10.1016/S0303-2647(96)01657-7.

  4. William M. Spears and Kenneth Alan De Jong. On the Virtues of Parameterized Uniform Crossover. In Richard K. Belew and Lashon Bernard Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA’91), July 13-16, 1991, San Diego, CA, USA, pages 230-236. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. ISBN: 1-55860-208-9. https://www.mli.gmu.edu/papers/91-95/91-18.pdf.

class moptipy.operators.bitstrings.op2_uniform.Op2Uniform[source]

Bases: Op2

A binary search operation that copies each bit from either source.

For each index i in the destination array dest, uniform crossover copies the value from the first source string x0`with probability 0.5 and otherwise the value from the second source string `x1. All bits that have the same value in x0 and x1 will retain this value in dest, all bits where x0 and x1 differ will effectively be randomized (be 0 with probability 0.5 and 1 with probability 0.5).

moptipy.operators.bitstrings.op2_uniform.uniform(random, dest, x0, x1)[source]

Perform the actual work of the uniform crossover.

Parameters:

  • random (Generator) – the random number generator

  • dest (ndarray) – the destination array

  • x0 (ndarray) – the first source array

  • x1 (ndarray) – the second source array

Return type:

None

>>> a = np.full(10, True)
>>> b = np.full(len(a), False)
>>> r = np.random.default_rng(10)
>>> out = np.empty(len(a), bool)
>>> uniform(r, out, a, b)
>>> print(out)
[ True  True False False  True  True  True False  True  True]
>>> uniform(r, out, a, b)
>>> print(out)
[False False False  True False  True False False  True  True]
>>> uniform(r, out, a, b)
>>> print(out)
[False  True False False  True  True  True  True  True  True]
>>> uniform(r, out, a, b)
>>> print(out)
[False  True  True False  True  True False False False  True]