-
Notifications
You must be signed in to change notification settings - Fork 1
/
crossover.py
151 lines (126 loc) · 3.77 KB
/
crossover.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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
from random import randint
from random import uniform
from random import sample
def template_co(p1, p2):
"""[summary]
Args:
p1 ([type]): [description]
p2 ([type]): [description]
Returns:
[type]: [description]
"""
return offspring1, offspring2
def cycle_co(p1,p2):
"""
Parameters
----------
p1 : TYPE
DESCRIPTION.
p2 : TYPE
DESCRIPTION.
Returns
-------
offspring1 : TYPE
DESCRIPTION.
offspring2 : TYPE
DESCRIPTION.
"""
offspring1=[None]*len(p1)
offspring2=[None]*len(p2)
while None in offspring1:
index = offspring1.index(None)
# alternate parents between cycles beginning on second cycle
if index!=0:
p1,p2=p2,p1
val1=p1[index]
val2=p2[index]
while val1!=val2:
offspring1[index]=p1[index]
offspring2[index]=p2[index]
val2=p2[index]
index=list(p1).index(val2)
offspring1[index]=p1[index]
offspring2[index]=p2[index]
return offspring1, offspring2
def pmx_crossover(p1,p2):
"""
Parameters
----------
p1 : TYPE
DESCRIPTION.
p2 : TYPE
DESCRIPTION.
Returns
-------
TYPE
DESCRIPTION.
"""
# Sample two crossover points
co_points = sample(range(len(p1)), 2)
co_points.sort()
def PMX(x, y):
# Create holders for offspring
o = [None]*len(p1)
# Copy co segement to offspring
o[co_points[0]:co_points[1]] = x[co_points[0]:co_points[1]]
# Find set of values not in offspring from co segment in P2
z = set(y[co_points[0]:co_points[1]]) -set(x[co_points[0]:co_points[1]])
# Map values in set to corresponding position in offspring
for i in z:
temp = i
index = y.index(x[y.index(temp)])
while o[index] != None:
temp = index
index = y.index(x[temp])
o[index] = i
while None in o:
index = o.index(None)
o[index]=y[index]
return o
o1, o2 = (PMX(p1, p2), PMX(p2, p1))
return o1, o2
def order_1_crossover(p1, p2):
"""
Parameters
----------
p1 : TYPE
DESCRIPTION.
p2 : TYPE
DESCRIPTION.
Returns
-------
offspring1 : TYPE
DESCRIPTION.
offspring2 : TYPE
DESCRIPTION.
"""
# Choose random start/end position for crossover
offspring1 = [None]*len(p1)
offspring2 = [None]*len(p1)
co_points = sample(range(len(p1)), 2)
co_points.sort()
# Replicate mum's sequence for alice, dad's sequence for bob
offspring1[co_points[0]:(co_points[1]+1)] = p1[co_points[0]:(co_points[1]+1)]
offspring2[co_points[0]:(co_points[1]+1)] = p2[co_points[0]:(co_points[1]+1)]
#Fill the remaining position with the other parents' entries
current_p2_position, current_p1_position = 0, 0
fixed_pos = list(range(co_points[0], co_points[1] + 1))
i = 0
while i < len(p1):
if i in fixed_pos:
i += 1
continue
if offspring1[i]==None:
p2_trait = p2[current_p2_position]
while p2_trait in offspring1:
current_p2_position += 1
p2_trait = p2[current_p2_position]
offspring1[i] = p2_trait
if offspring2[i]==None: #to be filled
p1_trait = p1[current_p1_position]
while p1_trait in offspring2:
current_p1_position += 1
p1_trait = p1[current_p1_position]
offspring2[i] = p1_trait
i +=1
return offspring1, offspring2