-
Notifications
You must be signed in to change notification settings - Fork 0
/
hill_climbing_multistart.py
84 lines (74 loc) · 3.69 KB
/
hill_climbing_multistart.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
# Libraries
from random import shuffle, choice
import pandas as pd
import numpy as np
# Import Excel file into Python
file_name, sheet = "TSP.xlsx", "Arkusz1"
data = pd.read_excel(file_name, sheet_name = sheet, engine = 'openpyxl')
m = np.delete(data.to_numpy(), 0, 1) # The first arrays column removal, because it contains indexes
multistarts = 40 # Parameter 1
iterations1 = 1000 # Parameter 2
iterations2 = 750 # Parameter 3
neighbourhood_type = ""
solution = list(range(1, len(data) + 1)) # List for future job indexes from the file
def count_score(z): # Function responsible for counting distance
time_travel, copied_solution = 0, z.copy()
time_travel = np.double(time_travel)
for n in range(0, len(solution) - 1):
first_city, second_city = copied_solution[n], copied_solution[n + 1]
time_travel += m[first_city - 1, second_city - 1]
time_travel += m[copied_solution[0] - 1, copied_solution[-1] - 1]
return time_travel
def pick_two_towns(): # Function responsible for picking two random jobs
while True:
t1, t2 = choice(solution), choice(solution) # Picking two random jobs
if t1 != t2: # Checking if these jobs are not same
break
return t1, t2
def swap_method(x, y): # One of the neighbourhood types
copied_solution = new_solution.copy() # Copied solution which is used for experiments
copied_solution[x], copied_solution[y] = copied_solution[y], copied_solution[x] # Swapping positions of these jobs in list
neighbourhood_type = "swap"
return copied_solution, neighbourhood_type
def insertion_method(t1, y): # Second type of neighbourhood
copied_solution = new_solution.copy() # Copied solution which is used for experiments
copied_solution.remove(t1)
copied_solution.insert(y, t1) # Inserting experimental solution with job 1 on the place of job 2
neighbourhood_type = "insertion"
return copied_solution, neighbourhood_type
score2 = 1000000000
solution2 = []
i = 0
while i != multistarts: # Multistart mechanism
shuffle(solution) # Creating new solution (changing point) by shuffling jobs
j = 0
score = count_score(solution)
while j != iterations1:
min_solution = solution.copy() # Unchanged solution
min_score, k = count_score(min_solution), 0
while k != iterations2: # Testing neighbourhood
new_solution = solution.copy()
t1, t2 = pick_two_towns()
x, y = solution.index(t1), solution.index(t2) # Obtaining index of each job
new_solution, neighbourhood_type = insertion_method(t1, y) # There can be also used swap method
new_score = count_score(new_solution) # Calculating score of experimental solution
if new_score < min_score:
min_solution, min_score = new_solution.copy(), new_score # Prescribing new already changed solution
k += 1
if min_score < score: # Checking if the local solution is better than min_solution
solution = min_solution # Applying changes to the solution
score = min_score
elif solution == min_solution: # Moment when local maximum is achieved
break
j += 1
if score < score2: # Checking if proposed solution is better than previous one
score2 = score
solution2 = solution.copy()
i += 1
print(f"The results of Hill Climbing algorithm with multistart mechanism for {file_name} file")
print(f"Solution: {solution2}")
print(f"Score: {round(score2,3)}")
print(f"Neighbourhood type: {neighbourhood_type}")
print(f"Multistarts: {multistarts}")
print(f"Iterations 1: {iterations1}")
print(f"Iterations 2: {iterations2}")