In [319]:
import numpy as np
from scipy import spatial
In [356]:
def evaluate_tour_len(x,d):
'''
x: solution
d: DxD matrix of Euclidean distance
'''
L = 0
for i in range(len(x)-1):
# print(x[i],x[i+1])
L += d[x[i],x[i+1]]
# print(d[x[i],x[i+1]],L)
L += d[len(x)-1,0]
# print(d[x[len(x)-1],x[0]],L)
return L
In [321]:
x = np.array([2,3,1,0])
y = np.matrix([[5,5,6,6],
[7,7,7,7],
[1,2,3,4],
[8,8,8,8]])
evaluate_tour_len(x,y)
Out[321]:
In [322]:
def order_crossover(xa,xb):
xa = np.copy(xa)
xb = np.copy(xb)
D = len(xa)
r = np.arange(D)
np.random.shuffle(r)
if r[0]<r[1]:
c1 = r[0]
c2 = r[1]
else:
c1 = r[1]
c2 = r[0]
u = xa
#print(c1,c2)
for j in range(c1,c2+1):
h = np.where(u==xb[j])[0][0]
l = h + 1
while h!=c2:
# print(h,l)
if h == D :
h = 0
if l == D :
l = 0
u[h] = u [l]
h += 1
l += 1
# print(u)
for j in range(c1,c2+1):
u[j] = xb[j]
return u
D = 10 a = np.arange(D) np.random.shuffle(a) b = np.arange(D) np.random.shuffle(b) u = order_crossover(a,b) print(a,b,u)
In [323]:
def inversion_mutation(vector,probability):
'''
a kind of mutation machanism for permutation problem
flip
'''
if np.random.rand() > probability:
D = len(vector)
r = np.arange(D)
np.random.shuffle(r)
[m1,m2] = sorted([r[0],r[1]])
# print(m1,m2)
vector[m1:(m2+1)] = np.flip(vector[m1:(m2+1)],0)
return vector
In [324]:
def random_init(mu,P,D, evaluate_func,d):
'''
initialize and evaluate the population
mu: number of the individuals
P: the list for the population and value
D: dimension
'''
x = np.arange(D)
for i in range(mu):
np.random.shuffle(x)
vector = np.copy(x)
#print(evaluate_func(vector,d))
P.append((vector,evaluate_func(vector,d)))
return P
In [325]:
def get_distance_matrix(TSP_data):
'''
get the distance matrix
'''
x = scipy.spatial.distance.pdist(TSP_data,'euclidean')
d = scipy.spatial.distance.squareform(x)
return d
In [364]:
def genetic_algorithm(TSP_data):
'''
converge condition: bsf not change for 20 generations
'''
D = len(TSP_data)
pm = 1/D
n = 0
mu = D
t = 0
lambda_ = 2*mu
d = get_distance_matrix(TSP_data)
P = list()
random_init(mu,P,D,evaluate_tour_len,d)
x_bsf = sorted(P,key=lambda x:x[1])[0]
count_no_change = 0
while count_no_change<200:
Q = list()
updated = False
for i in range(lambda_):
# Step1 Mating Selection
r = np.arange(len(P))
np.random.shuffle(r)
selected = r[:2]
# Step2: Variation operator : Order Crossover
u = order_crossover(P[selected[0]][0],P[selected[1]][0])
# Step3: Variation operator2: inversion_mutation
u = inversion_mutation(u,pm)
# Step4: Evaluate
new_value = evaluate_tour_len(u,d)
n += 1
Q.append((u,new_value))
# Step5: Update bsf solution
if new_value <x_bsf[1]:
updated = True
x_bsf=(u,new_value)
print(x_bsf)
# Step6: Environment Selection
R = P + Q
sort_result = sorted(R,key=lambda x:x[1])
P = sort_result[:int(len(R)/2)]
t += 1
if updated == True:
count_no_change = 0
else:
count_no_change += 1
return (t,n,x_bsf)
In [368]:
def main():
data = list()
# dj38.tsp
with open("wi29.tsp") as tspdata:
for line in tspdata:
linedata = line.split(' ')
if linedata[0].isdigit():
data.append((float(linedata[1]),float(linedata[2])))
#print(data[-1])
#print(d)
x = genetic_algorithm(data)
print(x)
return
In [370]:
main()
wi29
t = 883, n = 51214
[ 0, 1, 5, 4, 3, 2, 6, 8, 7, 9, 10, 11, 12, 13, 16, 17, 14, 18, 21, 22, 20, 28, 27, 25, 19, 15, 24, 26, 23]
31525.83488130699dj38
t = 1552, n = 117952
[28, 29, 31, 34, 36, 37, 32, 33, 35, 30, 26, 27, 23, 21, 24, 25, 22, 19, 14, 12, 15, 16, 17, 18, 10, 11, 8, 7, 6, 5, 4, 2, 3, 1, 0, 9, 13, 20]
8021.0298369392722)
In [ ]: