Genetic-Algorithms-Project/Variation.py at main · DagMalstaf/Genetic-Algorithms-Project · 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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import numpy as np
from typing import Callable, List, Set
from Individual import Individual
from Debug import DEBUG
from itertools import zip_longest


class Variation():
    _offspring_size: int = 0
    _mutation_rate: float = 0.0

    def __init__(self, offspring_size: int, mutation_rate: float) -> None:
        if DEBUG:
            assert 0 <= mutation_rate <= 1

        self._offspring_size = offspring_size
        self._mutation_rate = mutation_rate

    def produce_offspring(self, parent1: Individual, parent2: Individual, distanceMatrix: np.ndarray) -> List[Individual]:
        offspring_list = list()
        if parent1 == parent2:
            return list()
        for _ in range(self._offspring_size):
            child = self._recombination(parent1, parent2, distanceMatrix)
            mutated_child = self._mutation(child)
            offspring_list.append(mutated_child)
        return offspring_list

    def _find_first_non_zero(self,array: np.ndarray, comparison_operator: Callable[[int], bool]) -> int:

        for index, value in np.ndenumerate(array):
            if comparison_operator(value): return index[0]
        return -1

    def _recombination(self, parent1: Individual, parent2: Individual, distanceMatrix: np.ndarray,
                        p_inherent_common_path: float = 1,
                        p_inherent_common_city_in_common_location: float = 0.6,
                        p_inherent_difference_city_in_common_location: float = 0.6
                        ) -> Individual:
        parent1_cyclic_representation = parent1.get_cyclic_representation()
        parent2_cyclic_representation = parent2.get_cyclic_representation()
        number_of_cities = parent1.get_number_of_cities()

        base_case_no_city = np.full(number_of_cities,-1)
        child_cyclic_representation = np.where(parent1_cyclic_representation == parent2_cyclic_representation, parent1_cyclic_representation, base_case_no_city)
        child = Individual(number_of_cities)
        child.use_cyclic_notation(child_cyclic_representation)
        #start from 1 as the the beginning city should only be allocated last (additional constrain on beginning city)
        all_cities = np.arange(number_of_cities)
        cities_left_to_allocate = np.where(~np.isin(all_cities,child_cyclic_representation), all_cities, base_case_no_city )

        #check for -1 when parents are identical match
        start_city = self._find_first_non_zero(cities_left_to_allocate, lambda x: x != -1)
        if start_city == -1:
            debug = True
            if parent1 == parent2:
                debug2 = True
        cities_left_to_allocate[start_city] = -1

        self._build_hamiltonian_cycle_exposed(start_city, child, parent1, parent2, cities_left_to_allocate,
                                                p_inherent_common_path,
                                                p_inherent_common_city_in_common_location,
                                                p_inherent_difference_city_in_common_location)
        if DEBUG:
            assert((cities_left_to_allocate == -1).all())
        return child

    def _mutation(self, individual: Individual) -> Individual:
        if np.random.random_sample() > self._mutation_rate:
            individual.mutate()
        return individual


    def _get_city(self, start_city: int, child: Individual, city_parent1: int, city_parent2: int, cities_left_to_allocate: np.ndarray,
                  p_inherent_common_city_in_common_location: float,
                  p_inherent_difference_city_in_common_location: float
                  ):
        # last city goes back to the start
        if (cities_left_to_allocate == -1).all():
            # if (np.count_nonzero(child.get_cyclic_representation() == -1) != 1):
            #     debug = True
            return start_city

        p_choice = np.random.random_sample()
        #same city on same place in both parents
        if p_choice <= p_inherent_common_city_in_common_location \
            and city_parent1 == city_parent2:
            can_allocate_city_parent = city_parent1 in cities_left_to_allocate
            if can_allocate_city_parent :
                return self._select_choosen_city(city_parent1, cities_left_to_allocate)
            else:
                return self._get_random_city(cities_left_to_allocate)
        #different city in both parents, but still select from parents
        elif p_choice <= p_inherent_difference_city_in_common_location \
            and city_parent1 != city_parent2:
            can_allocate_city_parent1 = city_parent1 in cities_left_to_allocate
            can_allocate_city_parent2 = city_parent2 in cities_left_to_allocate
            if can_allocate_city_parent1 and can_allocate_city_parent2:
                p_choice_between_parents = np.random.random_sample()
                if p_choice_between_parents <= 0.5:
                    return self._select_choosen_city(city_parent1, cities_left_to_allocate)
                else:
                    return self._select_choosen_city(city_parent2, cities_left_to_allocate)
            elif can_allocate_city_parent1:
                return self._select_choosen_city(city_parent1, cities_left_to_allocate)
            elif can_allocate_city_parent2:
                return self._select_choosen_city(city_parent2, cities_left_to_allocate)
            else:
                return self._get_random_city(cities_left_to_allocate)
        #just random sample
        else:
            return self._get_random_city(cities_left_to_allocate)

    def _get_random_city(self, cities_left_to_allocate: np.ndarray) -> int:
        debug = cities_left_to_allocate[cities_left_to_allocate != -1]
        city = np.random.choice(cities_left_to_allocate[cities_left_to_allocate != -1])
        return self._select_choosen_city(city,cities_left_to_allocate)

    def _select_choosen_city(self, city: int, cities_left_to_allocate: np.ndarray) -> int:
        cities_left_to_allocate[city] = -1
        if city == 0:
            debug = True
        return city

    def _build_hamiltonian_cycle_exposed(self,start_city: int, child: Individual, parent1: Individual, parent2: Individual, cities_left_to_allocate: np.ndarray,
                                         p_inherent_common_path: float,
                                         p_inherent_common_city_in_common_location: float,
                                         p_inherent_difference_city_in_common_location: float
                                         ) -> None:

        p_choice = np.random.random_sample()

        for city_parent1, city_parent2, city_child in zip_longest(parent1(start_city), parent2(start_city), child(start_city)):
            if city_child != -1:
                if p_choice > p_inherent_common_path:
                    cities_left_to_allocate[city_child] = city_child
                    child.iterator_set(self._get_city(start_city, child, city_parent1, city_parent2, cities_left_to_allocate,
                                 p_inherent_common_city_in_common_location,
                                 p_inherent_difference_city_in_common_location))
                else:
                    continue
            p_choice = np.random.random_sample()
            child.iterator_set(self._get_city(start_city, child, city_parent1, city_parent2, cities_left_to_allocate,
                                 p_inherent_common_city_in_common_location,
                                 p_inherent_difference_city_in_common_location))