Skip to content

sequence

This module contains operators for problems whose solutions contain variable-length sequences (list-like objects).

CutAndSplice (CrossOver)

Cut & Splice operator for variable-length solutions.

This class serves as a cross-over operator to be used on problems with their dtypes set as object, and with their solutions initialized to contain variable-length sequences (list-like objects).

Reference:

David E. Goldberg, Bradley Korb, Kalyanmoy Deb (1989).
Messy Genetic Algorithms: Motivation, Analysis, and First Results.
Complex Systems 3, 493-530.
Source code in evotorch/operators/sequence.py
class CutAndSplice(CrossOver):
    """Cut & Splice operator for variable-length solutions.

    This class serves as a cross-over operator to be used on problems
    with their `dtype`s set as `object`, and with their solutions
    initialized to contain variable-length sequences (list-like objects).

    Reference:

        David E. Goldberg, Bradley Korb, Kalyanmoy Deb (1989).
        Messy Genetic Algorithms: Motivation, Analysis, and First Results.
        Complex Systems 3, 493-530.
    """

    def _cut_and_splice(
        self,
        parents1: ObjectArray,
        parents2: ObjectArray,
        children1: SolutionBatch,
        children2: SolutionBatch,
        row_index: int,
    ):
        parvals1 = parents1[row_index]
        parvals2 = parents2[row_index]

        length1 = len(parvals1)
        length2 = len(parvals2)

        cutpoint1 = int(self.problem.make_randint(tuple(), n=length1))
        cutpoint2 = int(self.problem.make_randint(tuple(), n=length2))

        childvals1 = parvals1[:cutpoint1]
        childvals1.extend(parvals2[cutpoint2:])

        childvals2 = parvals2[:cutpoint2]
        childvals2.extend(parvals1[cutpoint1:])

        children1.access_values(keep_evals=True)[row_index] = childvals1
        children2.access_values(keep_evals=True)[row_index] = childvals2

    def _do_cross_over(self, parents1: ObjectArray, parents2: ObjectArray) -> SolutionBatch:
        n = len(parents1)

        children1 = SolutionBatch(self.problem, popsize=n, empty=True)
        children2 = SolutionBatch(self.problem, popsize=n, empty=True)

        for i in range(n):
            self._cut_and_splice(parents1, parents2, children1, children2, i)

        return children1.concat(children2)