Genetic algorithm without crossover to solve travelling salesman problem

genetic_algorithm.cpp

// https://www.youtube.com/watch?v=XP8R0yzAbdo 
// CROSSOVER IS OVERRATED, I USED ONLY 1 MUTATION PER CHILDREN TO GET BEST RESULT ON CIRCLE GRAPH

#define _USE_MATH_DEFINES

#include <vector>
#include <random>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

static std::mt19937 generator(0);
static std::uniform_real_distribution<double> distribution(0, 1);
double random(void) {
	return distribution(generator);
}

const int mut_count = 1;
const int population_size = 50;
const double survival_percent = 0.1;
const int generations_count = 50;

typedef vector<int> creature_t;

creature_t generate_random_creature(int size) {
	creature_t c;
	for (int i = 0; i < size; ++i)
		c.push_back(i);
	shuffle(c.begin(), c.end(), generator);
	return c;
}

void mutate(creature_t& c) {
	for (int i = 0; i < mut_count; ++i) {
		int a = min<double>(random() * c.size(), c.size()-1);
		int b = min<double>(random() * c.size(), c.size()-1);

		swap(c[a], c[b]);
	}
}

typedef vector<vector<double>> distance_t;

double calc_fitness(const distance_t& d, const creature_t& c) {
	double sum = 0;
	for (int i = 0; i < c.size()-1; ++i)
		sum += d[c[i]][c[i+1]];
	sum += d[c.back()][c.front()];
	return sum;
}

typedef pair<double, double> point_t;

double calc_distance(const point_t& a, const point_t& b) {
	#define sqr(a) ((a)*(a))
	return sqrt(sqr(a.first-b.first) + sqr(a.second-b.second));
	#undef sqr
}

void calc_distance(const vector<point_t>& points, distance_t& d) {
	d.clear();
	d.resize(points.size(), vector<double>(points.size()));
	for (int i = 0; i < points.size(); ++i) {
		for (int j = 0; j < points.size(); ++j) {
			d[i][j] = calc_distance(points[i], points[j]);
		}
	}
}

int main() {
	vector<point_t> points;
	int point_count = 16;
	double len = 0;
	for (int i = 0; i < point_count; ++i) {
		double angle = 2.0*M_PI * i / point_count;
		points.push_back({sin(angle), cos(angle)});

		angle = 2.0*M_PI * (i+1) / point_count;
		len += calc_distance(points.back(), {sin(angle), cos(angle)});
	}

	distance_t d;
	calc_distance(points, d);

	vector<creature_t> population;
	for (int i = 0; i < population_size; ++i)
		population.push_back(generate_random_creature(point_count));

	for (int generation = 0; generation < generations_count; ++generation) {
		// Calc fitness function for all creatures
		vector<pair<double, creature_t*>> fitness;
		for (auto& i : population)
			fitness.push_back({calc_fitness(d, i), &i});

		// Sort this, find the best
		sort(fitness.begin(), fitness.end(), [] (auto& a, auto& b) -> bool {
			return a.first < b.first;
		});

		// Keep % of the best creatures
		int survival_count = fitness.size() * survival_percent;
		vector<creature_t> new_population;
		for (int i = 0; i < survival_count; ++i)
			new_population.push_back(*fitness[i].second);

		// Make childrens out of the best creatures
		int children_count = fitness.size() - survival_count;
		for (int i = 0; i < children_count; ++i) {
			new_population.push_back(*fitness[random() * survival_count].second);
			mutate(new_population.back());
		}

		swap(population, new_population);

		cout << generation << "\t" << fitness.front().first << "\t" << fitness.front().first / len << endl;
	}

	system("pause");
}