metaheuristic/tabu-search.py

#/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)