PyGeneticAlgorithms/pygenalgo/operators/crossover/multi_point_crossover.py at master · vrettasm/PyGeneticAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
from pygenalgo.genome.chromosome import Chromosome
from pygenalgo.operators.crossover.crossover_operator import CrossoverOperator


class MultiPointCrossover(CrossoverOperator):
    """
    Description:

        Multipoint crossover creates two children chromosomes (offsprings),
        by taking two parent chromosomes and cutting them at randomly chosen,
        sites (loci).

        It produces faster mixing, compared with single-point crossover.
    """

    def __init__(self, crossover_probability: float = 0.9, n_points: int = 2) -> None:
        """
        Construct a 'MultiPointCrossover' object with a given probability value.

        :param crossover_probability: (float).

        :param n_points: (int) the number of points to cut the genome.
        """
        # Call the super constructor with the provided
        # probability value.
        super().__init__(crossover_probability)

        # Make sure number of points are at least 2.
        self._items = max(int(n_points), 2)
    # _end_def_

    def crossover(self, parent1: Chromosome, parent2: Chromosome) -> tuple[Chromosome, Chromosome]:
        """
        Perform the crossover operation on the two input parent
        chromosomes, using multiple cutting points (num_loci).

        NOTE: the number of loci is held in the '_items' variable.

        :param parent1: (Chromosome).

        :param parent2: (Chromosome).

        :return: child1 and child2 (as Chromosomes).
        """
        # Get the lengths of the chromosomes.
        length_1: int = len(parent1)
        length_2: int = len(parent2)

        # Find the minimum length.
        min_length: int = min(length_1, length_2)

        # Extract the number of cut points.
        num_points: int = self._items

        # Ensure the number of requested cutting points
        # do not exceed the length of the chromosomes.
        if num_points >= min_length:
            raise ValueError(f"{self.__class__.__name__}:"
                             " Number of requested crossover points"
                             " exceeds the length of the chromosome.")
        # _end_def_

        # If the crossover probability is higher than a uniformly
        # random value and the parents aren't identical apply the
        # changes.
        if (parent1 != parent2) and self.is_operator_applicable():

            # Select randomly the crossover points and sort them.
            loci = sorted(self.rng.choice(min_length, size=num_points,
                                          replace=False, shuffle=False))

            # Create the 1st offspring genome list.
            genome_1 = [gene.clone() for gene in parent1.genome]

            # Create the 2nd offspring genome list.
            genome_2 = [gene.clone() for gene in parent2.genome]

            # Initialize a set of hyperparameters.
            reset_flag, upper_lim, j = True, loci[0], 0

            # Scan the genomes up to min_length.
            for i in range(min_length):

                # Once we surpass the upper limit (in loci)
                # we reset the  flag value to allow changes
                # to take place within that range.
                if i >= upper_lim:

                    # Swap the reset flag.
                    reset_flag = not reset_flag

                    # Increase the index of the loci.
                    j += 1

                    # We make sure the upper limit value does not exceed
                    # the number of genes. Also, this avoids the out of
                    # bound IndexError.
                    upper_lim = loci[j] if j < num_points else min_length
                # _end_if_

                # Check the flag value.
                if not reset_flag:
                    genome_1[i], genome_2[i] = genome_2[i], genome_1[i]
                # _end_if_

            # _end_for_

            # Create two NEW offsprings.
            child1 = Chromosome(genome_1)
            child2 = Chromosome(genome_2)

            # Increase the crossover counter.
            self.inc_counter()
        else:
            # Each child points to a clone of a single parent.
            child1 = parent1.clone()
            child2 = parent2.clone()
        # _end_if_

        # Return the two offsprings.
        return child1, child2
    # _end_def_

# _end_class_