退火算法

数学建模课上讲解了它的原理,现在打算实现一遍

蒙特卡罗方法(英语:Monte Carlo method),也称统计模拟方法,是1940年代中期由于科学技术的发展和电子计算机的发明,而提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。

matlab代码实现参考了Reference第一项,计划用c++来实现一遍
下面贴了c++代码,可以解决旅行推销员问题

Reference

matlab练习程序(模拟退火SA)

#include<iostream>
#include<random>
#include<time.h>

using namespace std;

const int MAP_WIDTH = 100;
const int MAP_HEIGHT = 100;

const int CITY_SUM = 20;
float temperature = 100 * CITY_SUM;
int iter = 100;		//随机循环迭代次数

struct city
{
	int x, y;
};
void CityCopy(city* ca, city* cb, int n)
{
	for (int i = 0; i < n; i++)
	{
		ca[i].x = cb[i].x;
		ca[i].y = cb[i].y;
	}
}

city City[CITY_SUM];

int IterationTimes = 0;

float Len[1000000];

float CalTourLen(city *City,int n)
{
	float tempLen = 0;
	for (int i = 0; i < n-1; i++)
	{
		tempLen += sqrt(pow(City[i + 1].x - City[i].x, 2) + pow(City[i + 1].y - City[i].y, 2));
	}
	tempLen+= sqrt(pow(City[n-1].x - City[0].x, 2) + pow(City[n-1].y - City[0].y, 2));
	return tempLen;
}


float random()
{
	float a = rand() % 1000;
	return a / 1000.0;
}

void initCity(city *City,int n)
{
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		City[i].x = rand() % MAP_WIDTH;
		City[i].y = rand() % MAP_HEIGHT;
	}
}


city* RerandomCity(city* City, int n)
{
	city* TempCity = new city[n];

	for (int i = 0; i < n; i++)
	{
		TempCity[i].x = City[i].x;
		TempCity[i].y = City[i].y;
	}

	int city1 = rand() % n;
	int city2 = rand() % n;

	while (city1 == city2)
	{
		city1 = rand() % n;
		city2 = rand() % n;
	}
	city tmp = TempCity[city1];
	TempCity[city1] = TempCity[city2];
	TempCity[city2] = tmp;
	return TempCity;
}


int main()
{
	initCity(City,CITY_SUM);
	Len[0]=CalTourLen(City, CITY_SUM);
	cout << Len[0] << endl;

	while (temperature > 0.001)
	{
		for (int i = 0; i < iter; i++)
		{
			float len1 = CalTourLen(City, CITY_SUM);
			city* Tmp_City = RerandomCity(City, CITY_SUM);
			float len2 = CalTourLen(Tmp_City, CITY_SUM);

			float delta_e = len2 - len1;
			if (delta_e < 0)
			{
				CityCopy(City, Tmp_City, CITY_SUM);
			}
			else
			{
				if (exp(-delta_e / temperature) > random())
				{
					CityCopy(City, Tmp_City, CITY_SUM);
				}
			}
			delete[]Tmp_City;

		}
		IterationTimes++;
		Len[IterationTimes] = CalTourLen(City, CITY_SUM);
		temperature *= 0.99;
	}
	
	cout << Len[IterationTimes] << endl;
	


	return 0;
}

Show Comments