Simulated Annealing Algorithm

Hello everyone, the word optimized is a word that we encounter very often in everyday life. As you know, the word optimization is the case where an event, problem, or situation chooses the best possible possibilities within a situation 📈. The Simulated Annealing method, which helps to find the best result by obtaining the results of the problem at different times in order to find a general minimum point by moving towards the value that is good from these results and testing multiple solutions, is also an optimization problem solution method [1].

🔎About the Simulated Annealing Algorithm

The simulated annealing method is a popular metaheuristic local search method used to address discrete and to a lesser extent continuous optimization problem. The main feature of simulated annealing is that it provides a means of evading the local optimality by allowing hill climbing movements (movements that worsen the purpose function value) with the hope of finding a global optimum [2].

The reason why the algorithm is called annealing is since the blacksmith’s heat treatment to a certain degree while beating the iron is based on the iron’s desired consistency. The problem is addressed with the same logic as in this example, and the heating process is passed with the degree of annealing, and then it is assumed that it reaches the desired point. (Local Objective Function)  

The function that gives the probability of acceptance of motion leading to an elevation up to Δ in the objective function is called the acceptance function [4].

Probability formula

When the temperature is high, there will be a very high probability of acceptance of movements that may cause an increase in goal function, and this probability will decrease as the temperature decreases. For this reason, it is necessary to start the search with a sufficiently high temperature value [4]. I have determined the initial temperature value to be used in the project I’ m working on as T= 100000 🌡️. In the algorithm, the search process is continued by trying a certain number of movements at each temperature value while the temperature is gradually reduced [4].

Flow Chart of The Algorithm 🖋

Working Principle of Algorithm 📲

The most important operation in the running logic of the simulated algorithm is that the temperature must be cooled over time. Because if the initial temperature does not decrease over time, the energy will remain consistently high and the search of  the energy levels are compared in each solution until the cooling process is performed in the algorithm. In the calculation of Energy Exchange, the current configuration difference is utilized from a possible configuration as pos’ [5].

Calculation of Energy Exchange [5]

A calculation probability is then presented for calculating the position to be accepted, as seen in Figure 4. The equation is simplified by ignoring the Boltzmann constant k. In this way, it is possible to calculate the new candidate solution.

Probability calculation of new candidate solution [5]

            In these cases, the temperature of T continues to decrease at a certain interval repeating. The data set used in this project is ‘gr137.tsp’. This data set works with the TSP infrastructure and is based on mobile vendor problems. This data set contains information for 666 city problems in the American infrastructure and provides 137 x and Y coordinates in the content size. We will compare the nodes executed in the simulated annealing method by first replacing them with the swap method and try to get the best result 👩🏻‍🏫.

Preview from file ‘gr137.tsp’  with coordinates

  We will calculate the distances of the nodes to be compared in the objective function as follows. Here we take the distance to be calculated as the Euclidean distance 📏.

We will continue to encode in Python, which is a very common language in optimization algorithms. Let’s write together the objective function based on Euclidean distance 👍.

Purpose function distance calculation

Calculation with Swap Method 🧮

As shown in Figure 8, the value denoted by N represents the size of the coordinates. We will assign swap1 and swap2 variables by generating random values in size N. If the two values to be checked are the same as each other, swap2 will re-create the probability to create a new probability value. In this data set, the value expressed by p is equivalent to the Id column. Values ​​are copied with the copy( ) function to prevent any changes. The reason for calculating energy at each stage is because the temperature value in the Simulated Annealing algorithm logic must be heated to a certain value and then cooled to a certain level by a cooling factor called cooling factor. In the case of simulated annealing, there will be an increase in energy due to the mobility of the particles in the heating process and it is desired to check whether they have high energy by making energy calculations in each process ⚡.

Calculation with Swap method

Since this method is used in the algorithm, it can not go to the method of calculating random values so it is very important in terms of time to go to the correct results with the use of other search operators.

Swap exchange method between values

DatasetOptimumBestWorstMeanStandard Deviation
gr137.tsp69853854.7855305691671868.838856972194863.772459811443.9530597090364

The first solution and best solution values in iteration outputs are shown below respectively. We will achieve the first solution and last solution values throughout 10 iterations by aiming to reach the optimum values.

Table of Objective values
Graphization of Objective values

E.g. 5.the results obtained at different times during the calculation to observe the value changes during iteration are shown below. Thus, the logic of the swap process and the energy changes (ΔE) in this process can be seen.

Showing energy values while swaps are in progress

Result values based on calculation in Link 5 and 102

Result values, depending on the calculation in links 113 and 127

🔎 APPLYING THE ALGORITHM 2-OPT OVER S.A.

2-opt algorithm is probably the most basic and widely used algorithm for solving TSP problems [6]. Basically, it can be defined as the deletion of the two edges in the round and the Connecting of the round divided into two parts in a different way to reduce costs. (Gutin ve Punnen, 2002).

✔️ In the swap method of simulated annealing, the two values are controlled by each other and stored according to the probability value. However, since all operations will be done in sequence, it will not be very efficient in terms of runtime.

✔️With the 2-opt algorithm, it is seen that the index values (initial_p) have passed to the 17th node after the 4th node. The 2 opt algorithm enters the circuit by breaking the link between nodes 4 and 5 and creating the link between nodes d and 17. Thus, runtime produces more efficient results.

Connecting different values in tour connection

In the two_opt_python function, the index values in the cities are controlled with 2 increments and change. If there is a change in the path on the Tour, this change is assigned to the tour variable. as a result of the dist( ) function, the Euclidean distance between two cities ( such as 4-17) is calculated and the coordinates in the tour are returned. This ensures improvement on the best solution ⭐

REFERENCES

[1] Sadi Evren Seker, Computer Concepts, “Simulated Annealing”, Retrieved from http://bilgisayarkavramlari.sadievrenseker.com/2009/11/23/simulated-annealing-benzetilmis-tavlama/.

 [2] Darrall Henderson, Sheldon H Jacobson, Alan W. Johnson, The Theory and Practice of Simulated Annealing, April 2006.          

 [3] Orhan Baylan, “WHAT IS HEAT TREATMENT? WHY HEAT TREATMENT IS DONE TO STEEL?”, Retrieved from https://www.metaluzmani.com/isil-islem-nedir-celige-nicin-isil-islem-yapilir/.

 [4] Annealing Simulation Algorithm (Simulated Annealing), BMU-579 Simulation and modeling , Assistant Prof. Dr. Ilhan AYDIN.

[5] Hefei University, Thomas Weise, Metaheuristic Optimization, 7. Simulated Annealing.

[6] Timur KESKINTURK, Baris KIREMITCI, Serap KIREMITCI, 2-opt Algorithm and Effect Of Initial Solution On Algorithm Results, 2016.

Leave a Reply

Your email address will not be published. Required fields are marked *