TSP 的遗传算法

省流：不如模拟退火

打 OI 的时候一直对乱搞很感兴趣，只是没时间学，现在算是弥补一下吧

旅行商问题（Traveling Salesman Problem, TSP）：求无向图边权和最小的哈密顿回路

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;

mt19937 mt(20050827);
int rnd(int l, int r)
{
	return uniform_int_distribution<>(l, r)(mt);
}

double haversin(double x)
{
	return (1 - cos(x)) / 2;
}

const int N = 35, m = 128;
int n;
double total, dis[N][N];
string name[N];

void input()
{
	freopen("in.txt", "r", stdin);
	const double R = 6371;
	static double x[N], y[N];
	n = 34;
	for (int i = 1; i <= n; ++i)
	{
		string tmp;
		cin >> name[i] >> x[i] >> tmp >> y[i] >> tmp;
		// cerr << name[i] << " " << x[i] << " " << y[i] << '\n';
		x[i] = x[i] * M_PI / 180;
		y[i] = y[i] * M_PI / 180;
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			double h = haversin(x[j] - x[i]) + cos(x[i]) * cos(x[j]) * haversin(y[j] - y[i]);
			dis[i][j] = 2 * R * asin(sqrt(h));
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j < i; ++j)
		{
			total += dis[i][j];
		}
	}
}

struct Individual
{
	vector<int> p;
	double distance, fitness;
	bool operator<(const Individual &rhs) { return fitness < rhs.fitness; }
	void evaluate()
	{
		distance = dis[p.front()][p.back()];
		for (int i = 1; i < p.size(); ++i)
		{
			distance += dis[p[i - 1]][p[i]];
		}
		fitness = total / distance;
	}
	void mutate()
	{
		while (rnd(1, 100) <= 1)
		{
			int l = rnd(0, n - 1), r = rnd(0, n - 1);
			// swap(p[l],p[r]);
			if (l > r)
			{
				swap(l, r);
			}
			reverse(p.begin() + l, p.begin() + r + 1);
			evaluate();
		}
	}
};
Individual cross(const Individual &x, const Individual &y)
{
	static bool vis[N];
	memset(vis, 0, sizeof vis);
	Individual z;
	z.p.resize(n);
	int l = rnd(0, n - 1), r = rnd(0, n - 1);
	if (l > r)
	{
		swap(l, r);
	}
	for (int i = l; i <= r; ++i)
	{
		z.p[i] = x.p[i];
		vis[z.p[i]] = 1;
	}
	for (int i = 0, j = 0; i < n; ++i)
	{
		if (l <= i && i <= r)
		{
			continue;
		}
		while (vis[y.p[j]])
		{
			++j;
		}
		z.p[i] = y.p[j];
		vis[z.p[i]] = 1;
	}
	z.evaluate();
	return z;
}

vector<Individual> population(m);

struct
{
	double sumf;
	void init()
	{
		sumf = 0;
		for (auto &i : population)
		{
			sumf += i.fitness;
		}
	}
	Individual select()
	{
		double rate = uniform_real_distribution<>(0, sumf)(mt);
		for (auto &i : population)
		{
			rate -= i.fitness;
			if (rate < eps)
			{
				return i;
			}
		}
		assert(0);
	}
} roulette;

void GA()
{
	roulette.init();
	vector<Individual> children;
	children.emplace_back(*max_element(population.begin(), population.end()));
	for (int i = 1; i < m; ++i)
	{
		Individual son = rnd(1, 100) <= 60 ?
			cross(roulette.select(), roulette.select()) : roulette.select();
		son.mutate();
		children.emplace_back(son);
	}
	population = children;
}

void output()
{
	Individual best = *max_element(population.begin(), population.end());
	cout << best.distance << "km\n";
	for (int i = 0; i < n; ++i)
	{
		cout << name[best.p[i]] << " ";
	}
	cout << '\n';
	cerr << (double)clock() / CLOCKS_PER_SEC << "s\n";
}

signed main()
{
	input();
	for (auto &i : population)
	{
		i.p.resize(n);
		iota(i.p.begin(), i.p.end(), 1);
		shuffle(i.p.begin(), i.p.end(), mt);
		i.evaluate();
	}
	for (int generation = 1; generation <= 1 << 16; ++generation)
	{
		GA();
	}
	output();
	return 0;
}

上海市 31.2304°N 121.4737°E
云南省昆明市 24.8801°N 102.8329°E
内蒙古自治区呼和浩特市 40.48°N 111.41°E
北京市 39.9042°N 116.4074°E
台湾省台北市 25.0639°N 121.5217°E
吉林省长春市 43.8171°N 125.3235°E
四川省成都市 30.5728°N 104.0668°E
天津市 39.3434°N 117.3616°E
宁夏回族自治区银川市 38.4680°N 106.2730°E
安徽省合肥市 31.8206°N 117.2272°E
山东省济南市 36.6512°N 117.1206°E
山西省太原市 37.8706°N 112.5489°E
广东省广州市 23.1291°N 113.2644°E
广西壮族自治区南宁市 22.8240°N 108.3200°E
新疆维吾尔自治区乌鲁木齐市 43.8256°N 87.6168°E
江苏省南京市 32.0603°N 118.7969°E
江西省南昌市 28.6820°N 115.8579°E
河北省石家庄市 38.0428°N 114.5149°E
河南省郑州市 34.7466°N 113.6253°E
浙江省杭州市 30.2741°N 120.1551°E
海南省海口市 20.0442°N 110.1999°E
湖北省武汉市 30.5928°N 114.3055°E
湖南省长沙市 28.2282°N 112.9388°E
澳门特别行政区 22.18°N 115.12°E
甘肃省兰州市 36.0611°N 103.8343°E
福建省福州市 26.0745°N 119.2965°E
西藏自治区拉萨市 29.6500°N 91.1000°E
贵州省贵阳市 26.6466°N 106.6302°E
辽宁省沈阳市 41.7968°N 123.4294°E
重庆市 29.4316°N 106.9123°E
陕西省西安市 34.3416°N 108.9398°E
青海省西宁市 36.6171°N 101.7782°E
香港特别行政区 22.25°N 114.25°E
黑龙江省哈尔滨市 45.8038°N 126.5350°E