-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcrossover_methods.py
135 lines (96 loc) · 4.54 KB
/
crossover_methods.py
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
from Route import Route
from RouteManager import RouteManager
import random
# TODO: Elitism? Where strongest chromosomes are kept through generations
def get_ordered_crossover():
def ordered_crossover(mating_pool : list, offspring_len=1000) -> list: # aka (OX)
offspring = []
for i in range(0, offspring_len, 2):
parent_1 = random.choice(mating_pool)
parent_2 = random.choice(mating_pool)
#print("\nParents:")
#print([s.id for s in parent_1.route_stops])
#print([s.id for s in parent_2.route_stops])
route_len = len(parent_1.route_stops)
offspring_1 = Route(RouteManager.INSTANCE)
offspring_2 = Route(RouteManager.INSTANCE)
offspring_1.route_stops = [ None for s in parent_1.route_stops ]
offspring_2.route_stops = [ None for s in parent_1.route_stops ]
cutoff_1 = random.randrange(route_len + 1)
cutoff_2 = random.randrange(route_len + 1)
cut_start = min(cutoff_1, cutoff_2)
cut_end = max(cutoff_1, cutoff_2)
#print("Cuts:")
#print(cut_start, cut_end)
# Exchange the cutodd point
for i in range(cut_start, cut_end):
offspring_1.route_stops[i] = parent_1.route_stops[i]
offspring_2.route_stops[i] = parent_2.route_stops[i]
j_1 = cut_end % route_len
j_2 = cut_end % route_len
for i in range(route_len):
i_conv = (cut_end + i) % route_len
route_stop_1 = parent_1.route_stops[i_conv]
route_stop_2 = parent_2.route_stops[i_conv]
if not offspring_2.has_station(route_stop_1):
offspring_2.route_stops[j_2] = route_stop_1
j_2 = (j_2 + 1) % route_len
if not offspring_1.has_station(route_stop_2):
offspring_1.route_stops[j_1] = route_stop_2
j_1 = (j_1 + 1) % route_len
offspring_1.build_spf()
offspring_2.build_spf()
#print("Offspring:")
#print([s.id for s in offspring_1.route_stops])
#print([s.id for s in offspring_2.route_stops])
offspring.append(offspring_1)
offspring.append(offspring_2)
return offspring
return ordered_crossover
def get_cycle_crossover():
def cycle_crossover(mating_pool : list, offspring_len=1000) -> list: # aka (CX)
offspring = []
for i in range(0, offspring_len, 2):
parent_1 = random.choice(mating_pool)
parent_2 = random.choice(mating_pool)
#print("\nParents:")
#print([s.id for s in parent_1.route_stops])
#print([s.id for s in parent_2.route_stops])
offspring_1 = Route(RouteManager.INSTANCE)
offspring_2 = Route(RouteManager.INSTANCE)
offspring_1.route_stops = [ None for s in parent_1.route_stops ]
offspring_2.route_stops = [ None for s in parent_1.route_stops ]
i_1 = 0
while True:
offspring_1.route_stops[i_1] = parent_1.route_stops[i_1]
lookup = parent_2.route_stops[i_1]
for i in range(len(parent_1.route_stops)):
if parent_1.route_stops[i].id == lookup.id:
i_1 = i
break
if i_1 == 0:
break
i_2 = 0
while True:
offspring_2.route_stops[i_2] = parent_2.route_stops[i_2]
lookup = parent_1.route_stops[i_2]
for i in range(len(parent_2.route_stops)):
if parent_2.route_stops[i].id == lookup.id:
i_2 = i
break
if i_2 == 0:
break
for i in range(len(parent_1.route_stops)):
if offspring_1.route_stops[i] == None:
offspring_1.route_stops[i] = parent_2.route_stops[i]
if offspring_2.route_stops[i] == None:
offspring_2.route_stops[i] = parent_1.route_stops[i]
offspring_1.build_spf()
offspring_2.build_spf()
#print("Offspring:")
#print([s.id if s != None else None for s in offspring_1.route_stops])
#print([s.id if s != None else None for s in offspring_2.route_stops])
offspring.append(offspring_1)
offspring.append(offspring_2)
return offspring
return cycle_crossover