In practical daily life, people often encounter the following problems: in a given domainInside, find the functionCorresponding optimal value. Here, the minimum value problem is taken as an example (the maximum value problem can be equivalent to the minimum value problem), which is formalized as:

IfIf it is a discrete finite value, the optimal solution of the problem can be obtained by the finite value method; IfContinuous, butIf it is convex, the optimal solution can be obtained by gradient descent and other methods; IfContinuous andNon convex, although the solution of the problem can be found according to the existing approximate solution method, whether the solution is optimal remains to be considered. In many cases, if the initial value is not selected well, it is very easy to fall into the local optimal value.

With the complexity of daily business scenarios, the third problem is often encountered. How to effectively avoid the problem of local optimization? Simulated annealing algorithm came into being. In fact, simulated annealing is also a kind of heuristic algorithm, which specifically studies the process of metal heating and cooling in metallurgy. Invented by S. Kirkpatrick, C. D. GELAT and M.P.Vecchi in 1983, V Č ern also independently invented this algorithm in 1985.

However, how does simulated annealing algorithm simulate the principle of metal annealing? It mainly applies the theory of thermodynamics to statistics, imagining every point in the search space as molecules in the air; The energy of a molecule is its own kinetic energy; The degree of search for each point in space is the same as that of the molecule. The algorithm starts with an arbitrary point in the search space: each step first selects a "neighbor", and then calculates the probability of reaching the "neighbor" from the existing location. If the probability is greater than the given threshold, jump to "neighbor"; If the probability is small, stay in the original position.

1, Basic idea of simulated annealing algorithm

Simulated annealing is not only A heuristic algorithm, but also A greedy algorithm, but its search process introduces random factors. When iteratively updating the feasible solution, accept A solution worse than the current solution with A certain probability, so it is possible to jump out of the local optimal solution and reach the global optimal solution. Taking the following figure as an example, assuming that the initial solution is blue dot A on the left, the simulated annealing algorithm will quickly search for the local optimal solution B, but after searching for the local optimal solution, it will not end here, but will accept the movement on the left with A certain probability. Perhaps after several such moves that are not locally optimal, we will reach the global best D, so we jump out of the local minimum.

According to the principle of thermodynamics, when the temperature isWhen the energy difference is dE, the probability of cooling is, expressed as:

amongIs the Boltzmann constant with a value of, exp is the natural index, and. therefore, soThe value range of the function is (0, 1). Meet the definition of probability density function. In fact, the more intuitive meaning of this formula is: the higher the temperature, the primary energy difference isThe greater the probability of cooling; The lower the temperature, the smaller the probability of cooling.

In practical problems, the calculation of "certain probability" here refers to the annealing process of metal smelting. It is assumed that the current feasible solution is, the iterative updated solution is, then the corresponding "energy difference" is defined as:

The corresponding "certain probability" is:

Minimum optimization:

Maximum optimization:

Note: in practical problems, it can be set, i.e. parametersAndMerge.

2, Description of simulated annealing algorithm

1. Initialization: initial temperature(large enough), lower temperature limit(sufficiently small), initial solution state(the starting point of algorithm iteration), eachNumber of iterations of value；
2. yes=1, 2, ..., Do steps 3 to 6;
3. Generate new solutions: ；byRandom number between.
4. Profit calculation increment, whereFor optimization objectives;
5. if(if looking for the maximum value,)Then acceptAs a new current solution, otherwise in probabilityacceptAs a new current solution;
6. If the termination conditions are met, the current solution is output as the optimal solution and the program is ended. (the termination condition is usually to terminate the algorithm when several new solutions in succession are not accepted.);
7. T gradually decreases, and, then go to step 2.

At each temperatureNext iterationSecond, by constantly changing x to find the optimal value under the current temperature, and then reducing the temperature to continue to find until the temperature reaches the lowest, that is, the selection probabilityClose to 0.

Note: generate newAfter that, it is necessary to judge whether it is within the definition fieldThe value should be discarded.

3, Advantages and disadvantages of simulated annealing algorithm

Simulated annealing algorithm is widely used and can efficiently solve NP complete problems, such as traveling salesman problem (TSP), Max cut problem, zero one knapsack problem, graph coloring problem, etc., but its parameters are difficult to control and can not guarantee to converge to the optimal value at one time, It usually takes many attempts to obtain (in most cases, it will still fall into the local optimal value). By observing the process of simulated annealing algorithm, it is found that it mainly has the following three parameter problems:

(1) Initial value setting of temperature T

The initial value setting of temperature T is one of the important factors affecting the global search performance of simulated annealing algorithm. If the initial temperature is high, it is more likely to search the global optimal solution, but it takes a lot of calculation time; On the contrary, the calculation time can be saved, but the global search performance may be affected.

(2) Annealing speed problem, that is, the number of iterations of each T value

The global search performance of simulated annealing algorithm is also closely related to the annealing speed. Generally speaking, a "full" search at the same temperature is quite necessary, but it also requires calculation time. The increase of the number of cycles will inevitably lead to the increase of computing overhead.

(3) Temperature management issues

Temperature management is also one of the problems that simulated annealing algorithm is difficult to deal with. In practical application, the following cooling methods are often adopted because the practical feasibility of calculation complexity must be considered:

Note: in order to ensure a large search space, α Generally take values close to 1, such as 0.95 and 0.9, and set to 0.98 in the code.

The algorithm principle is transferred from: https://blog.csdn.net/huahua19891221/article/details/81737053.

4, Case

TSP problem is the traveling salesman problem. The classic TSP can be described as: a commodity salesman wants to sell goods in several cities. The salesman starts from one city and needs to go through all cities before returning to the starting place. How to select the travel route to minimize the total travel. From the perspective of graph theory, the essence of this problem is to find a Hamiltonian circuit with the smallest weight in a weighted completely undirected graph.

Analysis: the solutions obtained from different route configurations constitute the understanding space. The algorithm iterates the extreme value from the solution space with a certain probability, and randomly adjusts the route for each route update.

5, Code

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

#Define t 3000 / / initial temperature
#Define EPS 1e-8 / / termination temperature
#define DELTA 0.98 / / temperature decay rate	

#define LIMIT 1000 / / upper limit of probability selection
#define OLOOP 20 / / number of external loops
#define ILOOP 100 / / number of internal loops
#define cN 6 / / number of cities
using namespace std;

//Define alignment structure
struct Path
{
	int citys[cN];
	double len;
};

//Define city point coordinates
struct Point
{
	double x, y;
};
typedef struct Point pt;
Path bestPath;        //Record the optimal path
       
double w[cN][cN];   //Path length between two cities
int nCase;        //Number of tests

double dist(Point A, Point B)
{
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

void GetDist(std::vector<pt> p, int n)
{
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			w[i][j] = w[j][i] = dist(p[i], p[j]);//The distance from A to B is equal to the distance from A to B.
}



void Init(int n)
{
	nCase = 0;
	bestPath.len = 0;
	for (int i = 0; i < n; i++)
	{
		bestPath.citys[i] = i;//Number the lines
		if (i != n - 1)
		{
			printf("%d--->", i);
			bestPath.len += w[i][i + 1];
		}
		else
			printf("%d\n", i);
	}
	printf("\n  path length is : %.4f\n", bestPath.len);
	
}

void Print(Path t, int n)
{
	printf("current path : ");
	for (int i = 0; i < n; i++)
	{
		if (i != n - 1)
			printf("%d-->", t.citys[i]);
		else
			printf("%d\n", t.citys[i]);
	}
	printf("\nThe path length is : %.3lf\n", t.len);
	printf("-----------------------------------\n\n");
}

/*-----------------------------
Generate new route
------------------------------*/
Path GetcNext(Path p, int n)
{
	Path ans = p;
	int x = (int)(n * (rand() / (RAND_MAX + 1.0)));
	int y = (int)(n * (rand() / (RAND_MAX + 1.0)));
	while (x == y)
	{
		x = (int)(n * (rand() / (RAND_MAX + 1.0)));
		y = (int)(n * (rand() / (RAND_MAX + 1.0)));
	}
	swap(ans.citys[x], ans.citys[y]);
	ans.len = 0;
 	for (int i = 0; i < n - 1; i++)
		ans.len += w[ans.citys[i]][ans.citys[i + 1]];
	cout << "nCase = " << nCase << endl;
	Print(ans, n);
	nCase++;
	return ans;
}

void SA(int n)
{
	double t = T;
	srand((unsigned)(time(NULL)));
	Path curPath = bestPath;
	Path newPath = bestPath;
	int P_L = 0;
	int P_F = 0;
	while (1)       //External circulation, main update parameter t, simulated annealing process
	{
		for (int i = 0; i < ILOOP; i++)    //Internal circulation to find the optimal value at a certain temperature
		{
			newPath = GetcNext(curPath, n);
			double dE = newPath.len - curPath.len;
			if (dE < 0)   //The current value is less than the previous value (the problem of finding the minimum value), and the update accepts the new value.
			{
				curPath = newPath;
				P_L = 0;
				P_F = 0;
			}
			else//Accepting a new value with a certain probability may jump out of the local optimal solution
			{
				double rd = rand() / (RAND_MAX + 1.0);
				
				if (exp(dE / t) > rd && exp(dE / t) < 1)//When the probability is greater than the randomly generated value between 0-1, the new value is accepted.
					curPath = newPath;
				P_L++;
			}
			if (P_L > LIMIT)//Termination conditions
			{
				P_F++;
				break;
			}
		}
		if (curPath.len < bestPath.len)
			bestPath = curPath;
		if (P_F > OLOOP || t < EPS)
			break;
		t *= DELTA;//Update the temperature at a certain rate
	}
}

int main(int argc, const char * argv[]) {

	
	ifstream  f_data("C:/Users/91324/Desktop/Tsp.data");
	std::vector<pt> city_pt;
	city_pt.clear();
	string data = "";

	if (f_data.fail())//File open failed: return 0  
	{
		std::cout << "Open file faild!" << std::endl;
		return 0;
	}

	getline(f_data, data);
	int n = atoi(data.c_str());

	while (getline(f_data, data))
	{
		int pos=data.find(" ");
		pt c_pt;
		string x_str = data.substr(0, pos);
		c_pt.x = atof(x_str.c_str());
		string y_str = data.substr(pos+1, pos);
		c_pt.y = atof(y_str.c_str());
		city_pt.push_back(c_pt);

	}


	GetDist(city_pt, n);
	Init(n);
	SA(n);
	Print(bestPath, n);
	printf("Total test times is : %d\n", nCase);
	system("pause");
	return 0;
}