Optimization-Algorithms-and-Problems/Simulated Annealing Quadratic Assignment Problem.py at main · SeyedMuhammadHosseinMousavi/Optimization-Algorithms-and-Problems · GitHub

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
import numpy as np
import matplotlib.pyplot as plt
import random
import pandas as pd

# Function to generate a random QAP problem
def generate_qap_problem(size):
    flow_matrix = np.random.randint(1, 100, size=(size, size))
    distance_matrix = np.random.randint(1, 100, size=(size, size))
    return flow_matrix, distance_matrix

# Objective function for QAP
def calculate_cost(permutation, flow_matrix, distance_matrix):
    size = len(permutation)
    cost = 0
    for i in range(size):
        for j in range(size):
            cost += flow_matrix[i][j] * distance_matrix[permutation[i]][permutation[j]]
    return cost

# Simulated Annealing for QAP
def simulated_annealing_qap(flow_matrix, distance_matrix, initial_temp=1000, cooling_rate=0.95, max_iterations=1000):
    size = len(flow_matrix)
    current_permutation = list(range(size))
    random.shuffle(current_permutation)
    current_cost = calculate_cost(current_permutation, flow_matrix, distance_matrix)

    best_permutation = current_permutation.copy()
    best_cost = current_cost

    costs_over_iterations = [current_cost]

    temperature = initial_temp

    for iteration in range(max_iterations):
        i, j = random.sample(range(size), 2)
        new_permutation = current_permutation.copy()
        new_permutation[i], new_permutation[j] = new_permutation[j], new_permutation[i]

        new_cost = calculate_cost(new_permutation, flow_matrix, distance_matrix)

        delta = new_cost - current_cost
        if delta < 0 or random.uniform(0, 1) < np.exp(-delta / temperature):
            current_permutation = new_permutation
            current_cost = new_cost

            if current_cost < best_cost:
                best_permutation = current_permutation
                best_cost = current_cost

        costs_over_iterations.append(current_cost)
        temperature *= cooling_rate

    return best_permutation, best_cost, costs_over_iterations

# Main execution for a single run
size = 10  # Problem size
flow_matrix, distance_matrix = generate_qap_problem(size)
best_perm, best_cost, costs = simulated_annealing_qap(flow_matrix, distance_matrix)

# Plotting iteration cost progress
plt.figure(figsize=(10, 6))
plt.plot(costs, marker="o", linestyle="--")
plt.title("Cost over Iterations - Simulated Annealing")
plt.xlabel("Iteration")
plt.ylabel("Cost")
plt.grid()
plt.show()

# Displaying the QAP flow matrix
plt.figure(figsize=(8, 6))
plt.imshow(flow_matrix, cmap="Blues", interpolation="nearest")
plt.colorbar()
plt.title("Flow Matrix")
plt.show()

# Displaying results
results = pd.DataFrame({
    "Best Permutation": [best_perm],
    "Best Cost": [best_cost],
    "Iterations": [len(costs)],
})
print("Simulated Annealing QAP Results:")
print(results)

# Save results to a CSV file
results.to_csv("Simulated_Annealing_QAP_Results.csv", index=False)
print("Results saved to 'Simulated_Annealing_QAP_Results.csv'")