You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/num_methods/simulated_annealing.md
+17-19Lines changed: 17 additions & 19 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -9,11 +9,11 @@ tags:
9
9
10
10
## The Problem
11
11
12
-
We are given a function $E(s)$, which calculates the potential of the state $ s $. We are tasked with finding the state $s_{best}$ at which $E(s)$ is minimized. SA is suited for problems where the states are discrete and $E(s)$ has multiple local minima. We'll take the example of the [Travelling Salesman Problem (TSP)](https://en.wikipedia.org/wiki/Travelling_salesman_problem).
12
+
We are given a function $E(s)$, which calculates the potential of the state $s$. We are tasked with finding the state $s_{best}$ at which $E(s)$ is minimized. SA is suited for problems where the states are discrete and $E(s)$ has multiple local minima. We'll take the example of the [Travelling Salesman Problem (TSP)](https://en.wikipedia.org/wiki/Travelling_salesman_problem).
13
13
14
14
### Travelling Salesman Problem (TSP)
15
15
16
-
You are given a set of nodes in 2 dimensional space. Each node is characterised by its $ x $ and $ y $ coordinates. Your task is to find the an ordering of the nodes, which will minimise the distance to be travelled when visiting these nodes in that order.
16
+
You are given a set of nodes in 2 dimensional space. Each node is characterised by its $x$ and $y$ coordinates. Your task is to find the an ordering of the nodes, which will minimise the distance to be travelled when visiting these nodes in that order.
17
17
18
18
### State
19
19
@@ -26,12 +26,12 @@ It is a State in the State space which is close to the previous State. This usua
26
26
27
27
### E(s)
28
28
29
-
$E(s)$ is the function which needs to be minimised (or maximised). It maps every state to a real number. In the case of TSP, $E(s)$ returns the distance of travelling one full circle in the order of nodes in the state.
29
+
$E(s)$ is the function which needs to be minimised (or maximised). It maps every state to a real number. In the case of TSP, $E(s)$ returns the distance of travelling one full circle in the order of nodes in the state.
30
30
31
31
## Approach
32
32
33
-
We start of with a random state $ s $. In every step, we choose a neighbouring state $s_{next}$ of the current state $ s $. If $E(s_{next}) < E(s)$, then we update $s = s_{next}$. Otherwise, we use a probability acceptance function $P(E(s),E(s_{next}),T)$ which decides whether we should move to $s_{next}$ or stay at s. T here is the temperature, which is initially set to a high value and decays slowly with every step. The higher the temperature, the more likely it is to move to s_next.
34
-
At the same time we also keep a track of the best state $s_{best}$ across all iterations. Proceed till convergence or time runs out.
33
+
We start of with a random state $s$. In every step, we choose a neighbouring state $s_{next}$ of the current state $s$. If $E(s_{next}) < E(s)$, then we update $s = s_{next}$. Otherwise, we use a probability acceptance function $P(E(s),E(s_{next}),T)$ which decides whether we should move to $s_{next}$ or stay at s. T here is the temperature, which is initially set to a high value and decays slowly with every step. The higher the temperature, the more likely it is to move to s_next.
34
+
At the same time we also keep a track of the best state $s_{best}$ across all iterations. Proceed till convergence or time runs out.
This function takes in the current state, the next state and the Temperature , returning a boolean value, which tells our search whether it should move to $s_{next}$ or stay at s. Note that for $E_{next} < E$ , this function will always return True.
45
+
This function takes in the current state, the next state and the Temperature , returning a boolean value, which tells our search whether it should move to $s_{next}$ or stay at s. Note that for $E_{next} < E$ , this function will always return True.
47
46
48
47
```cpp
49
48
boolP(double E,double E_next,double T){
@@ -72,13 +71,12 @@ class state{
72
71
};
73
72
};
74
73
75
-
int main(){
76
-
double T = 1000; // Initial temperature
77
-
double u = 0.99; // decay rate
74
+
pair<int,state> simAnneal(){
78
75
state s = state();
79
76
state best = s;
80
-
double E = s.E();
81
-
double E_next;
77
+
double T = 1000; // Initial temperature
78
+
double u = 0.99; // decay rate
79
+
double E = s.E(),E_next;
82
80
double E_best = E;
83
81
while (T > 1){
84
82
state next = s.next();
@@ -93,12 +91,12 @@ int main(){
93
91
E = E_next;
94
92
T *= u;
95
93
}
96
-
cout << E_best << "\n";
97
-
return 0;
94
+
return {E_best,best};
98
95
}
96
+
99
97
```
100
98
## How to use:
101
-
Fill in the state class functions as appropriate. If you are trying to find a global maxima and not a minima, ensure that the $E()$ function returns negative of the function you are maximising and finally print out $-E_{best}$. Set the below parameters as per your need.
99
+
Fill in the state class functions as appropriate. If you are trying to find a global maxima and not a minima, ensure that the $E()$ function returns negative of the function you are maximising and finally print out $-E_{best}$. Set the below parameters as per your need.
102
100
103
101
### Parameters
104
102
- T : Temperature. Set it to a higher value if you want the search to run for a longer time
@@ -149,11 +147,11 @@ class state{
149
147
## Extra Modifications to the Algorithm:
150
148
151
149
- Add a time based exit condition to the while loop to prevent TLE
152
-
- You can replace the e value in the Probability Acceptance function to any real number > 1. For a given $E_{next} - E > 0$, a higher e value reduces the chance of accepting that state and a smaller e value, increases it.
150
+
- You can replace the e value in the Probability Acceptance function to any real number > 1. For a given $E_{next} - E > 0$, a higher e value reduces the chance of accepting that state and a smaller e value, increases it.
0 commit comments