75 lines
2.6 KiB
Python
75 lines
2.6 KiB
Python
#/bin/python
|
|
|
|
# edges = [[None, 6, 9, 18, None],
|
|
# [6, None, 2, None, 8],
|
|
# [9, 2, None, 0, None],
|
|
# [18, None, 0, None, 12],
|
|
# [None, 8, None, 12, None]]
|
|
|
|
costs = {"x1":6, "x2":9, "x3":18, "x4":2, "x5":0, "x6":8, "x7":12}
|
|
solution = {"x1":1, "x2":0, "x3":0, "x4":1, "x5":1, "x6":1, "x7":0}
|
|
|
|
def check_constraint(solution):
|
|
penalty = 0
|
|
if solution["x1"] and not solution["x3"]:
|
|
penalty += 50
|
|
if solution["x1"] + solution["x2"] + solution["x6"] > 1:
|
|
penalty +=50
|
|
return penalty
|
|
|
|
def check_validity(solution):
|
|
return (sum(solution.values()) == 4) and not ((solution["x1"] and solution["x2"] and solution["x4"]) or (solution["x2"] and solution["x3"] and solution["x5"]) or (solution["x4"] and solution["x5"] and solution["x7"] and solution["x6"]) or (solution["x1"] and solution["x3"] and solution["x6"] and solution["x7"]) or (solution["x1"] and solution["x3"] and solution["x4"] and solution["x5"]))
|
|
|
|
def neighbors(solution):
|
|
neighbors = list()
|
|
dict_0 = {k: v for k, v in solution.items() if v == 0}
|
|
dict_1 = {k: v for k, v in solution.items() if v == 1}
|
|
for i in dict_0.keys():
|
|
for j in dict_1.keys():
|
|
copy = solution.copy()
|
|
copy[i]=1
|
|
copy[j]=0
|
|
neighbors.append(copy)
|
|
return neighbors
|
|
|
|
def calculate_cost(solution):
|
|
return check_constraint(solution) + sum(costs[key] for key in solution if solution[key] == 1)
|
|
|
|
def tabu_search(initial_solution, n_max):
|
|
solution = initial_solution
|
|
best = initial_solution
|
|
cost = calculate_cost(initial_solution)
|
|
cost_best = cost
|
|
tabu = [solution,]
|
|
n = 0
|
|
while n < n_max:
|
|
neighbors_list = []
|
|
for s in neighbors(solution):
|
|
if check_validity(s) and s not in tabu:
|
|
neighbors_list.append((s, calculate_cost(s)))
|
|
new = min(neighbors_list, key=lambda x: x[1])
|
|
if cost - new[1] >= 0:
|
|
n = 0
|
|
solution = new[0]
|
|
cost = new[1]
|
|
if cost_best - new[1] >= 0:
|
|
best = new[0]
|
|
cost_best = new[1]
|
|
else:
|
|
solution = new[0]
|
|
cost = new[1]
|
|
n += 1
|
|
tabu.append(solution)
|
|
|
|
print("tabu list:")
|
|
for e in tabu:
|
|
print(e, calculate_cost(e))
|
|
print("solution found:")
|
|
print(best, cost_best)
|
|
return (best, cost_best)
|
|
|
|
print("tabu search accepting 1 degradation: (find a local optimum)")
|
|
tabu_search(solution, 1)
|
|
print("tabu search accepting 2 degradations:")
|
|
tabu_search(solution, 2)
|