Coverage for moptipy / operators / permutations / op2_ox2.py: 43%
56 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2The Order-based Crossover operator.
4Larrañaga et al. describe this operator as follows:
6The order-based crossover operator by Syswerda (1991) selects at random
7several positions in a parent tour, and the order of the cities in the
8selected positions of this parent is imposed on the other parent. For
9example, consider the parents `12345678` and `24687531`. Suppose that in the
10second parent the second, third, and sixth positions are selected. The values
11in these positions are `4`, `6`, and `5` respectively. In the first parent
12these cities are present at the fourth, fifth and sixth positions.
13Now the offspring is equal to parent 1 except in the fourth, fifth and sixth
14positions: `123xxx78`. We add the missing cities to the offspring in the same
15order in which they appear in the second parent tour. This results in
16`12346578`. Exchanging the role of the first parent and the second parent
17gives, using the same selected positions, `24387561`.
19We implement this operator such that each position has the same chance to be
20chosen by either parents, i.e., the total number of positions copied from
21the parents is binomially distributed with `p=0.5`, but we ensure that at
22least two positions are copied from either parents (as the result would
23otherwise necessarily equal one of the parents). We also switch the role of
24the two parents in our implementation.
26As mnemonic for the operator, we use `ox2`, similar to Larrañaga et al., who
27used `OX2`.
291. G. Syswerda. Schedule Optimization Using Genetic Algorithms. In Lawrence
30 Davis, L. (ed.), *Handbook of Genetic Algorithms,* pages 332-349.
31 New York, NY, USA: Van Nostrand Reinhold.
322. Pedro Larrañaga, Cindy M. H. Kuijpers, Roberto H. Murga, Iñaki Inza, and
33 S. Dizdarevic. Genetic Algorithms for the Travelling Salesman Problem: A
34 Review of Representations and Operators. *Artificial Intelligence Review,*
35 13(2):129-170, April 1999. Kluwer Academic Publishers, The Netherlands.
36 https://doi.org/10.1023/A:1006529012972
37"""
38from typing import Final
40import numba # type: ignore
41import numpy as np
42from numpy.random import Generator
43from pycommons.types import type_error
45from moptipy.api.operators import Op2
46from moptipy.spaces.permutations import Permutations
47from moptipy.utils.nputils import (
48 DEFAULT_BOOL,
49 DEFAULT_INT,
50 fill_in_canonical_permutation,
51)
54@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
55def _op2_ox2(indices: np.ndarray,
56 x1_done: np.ndarray,
57 random: Generator, dest: np.ndarray,
58 x0: np.ndarray, x1: np.ndarray) -> None:
59 """
60 Apply the order-based crossover from `x0` and `x1` to `dest`.
62 :param indices: the indices
63 :param x1_done: the elements of x1 that are done
64 :param random: the random number generator
65 :param dest: the array to receive the result
66 :param x0: the first existing point in the search space
67 :param x1: the second existing point in the search space
68 """
69 x1_done.fill(False) # all values in x1 are available
70 length: Final[int] = len(indices) # get length of string
72 # start book
73 while True: # sample the number of values to copy from x0
74 copy_from_x0 = random.binomial(length, 0.5) # p=0.5 for each value
75 if 1 < copy_from_x0 < (length - 1): # ensure difference by
76 break # copying at least two values from each parent
77 copy_from_x0 = length - copy_from_x0 # compute end index-index
79 i: int = length # the index into indices we iterate over
80 mode: bool = True # mode: True = copy from x0, False = from x1
81 x1i: int = 0 # the index of the next unused value from x1
82 while True: # loop until we are finished
83 index_i = random.integers(0, i) # pick a random index-index
84 index = indices[index_i] # load the actual index
85 i -= 1 # reduce the number of values
86 indices[i], indices[index_i] = index, indices[i] # swap
88 if mode: # copy from x0 to dest
89 dest[index] = value = x0[index] # get and store value
90 for x1j in range(x1i, length): # mark as used
91 if (x1[x1j] == value) and (not x1_done[x1j]):
92 x1_done[x1j] = True # mark value as used
93 break # exit inner loop
94 if copy_from_x0 == i: # are we done with copying?
95 mode = False # set mode to load from x1
96 x1i = 0 # reset x1 index
97 else: # go to next iteration
98 dest[index] = x1[x1i] # and store it in dest
99 if i == 0: # check if we are done
100 return # ok, we are finished
101 x1i += 1 # and move on to the next value
102 while x1_done[x1i]: # step x1i to next unused value
103 x1i += 1 # increment
106class Op2OrderBased(Op2):
107 """The order-based crossover operator."""
109 def op2(self, random: Generator, dest: np.ndarray,
110 x0: np.ndarray, x1: np.ndarray) -> None:
111 """
112 Apply the order-based crossover from `x0` and `x1` to `dest`.
114 :param random: the random number generator
115 :param dest: the array to receive the result
116 :param x0: the first existing point in the search space
117 :param x1: the second existing point in the search space
118 """
119 _op2_ox2(self.__indices, self.__x1_done, random, dest, x0, x1)
121 def __init__(self, space: Permutations) -> None:
122 """
123 Initialize the sequence crossover operator.
125 :param space: the permutation space
126 """
127 super().__init__()
128 if not isinstance(space, Permutations):
129 raise type_error(space, "space", Permutations)
130 if space.dimension < 4:
131 raise ValueError(
132 f"dimension must be > 3, but got {space.dimension}.")
133 #: the valid indices
134 self.__indices: Final[np.ndarray] = np.empty(
135 space.dimension, DEFAULT_INT)
136 #: the elements that are done in `x1`
137 self.__x1_done: Final[np.ndarray] = np.ndarray(
138 (space.dimension, ), DEFAULT_BOOL)
140 def initialize(self) -> None:
141 """Initialize this operator."""
142 super().initialize()
143 fill_in_canonical_permutation(self.__indices)
145 def __str__(self) -> str:
146 """
147 Get the name of this binary operator.
149 :returns: "ox2", for "order-based crossover", the name of this
150 operator
151 :retval "ox2": always
152 """
153 return "ox2"