SimulatedAnnealing.cpp

#include "SimulatedAnnealing.h"
#include "FileHandler.h"
#include "GreedySolve.h"
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <map>
#include <vector>
#include <random>
#include <cmath>

using namespace std;



int SimulatedAnnealing::calculate_cost(Graph* graph, vector<int> path) {
	int cost = 0;
	for (auto i = 0; i < path.size() - 1; i++)
		cost += graph->edge_weight(path[i], path[i + 1]);

	cost += graph->edge_weight(path[path.size()-1], path[0]);
	return cost;
	
}

vector<int> SimulatedAnnealing::calculate_neighbor(vector<int> path) {
	int index1 = rand() % path.size();
	int index2 = rand() % path.size();

	while (index1 == index2) index2 = rand() % path.size();

	if (rand() % 2 == 0) {
		if (index1 > index2) swap(index1, index2);
		reverse(path.begin() + index1, path.begin() + index2 + 1);
	}
	else {
		swap(path[index1], path[index2]);
	}
	return path;
}

void SimulatedAnnealing::print_solution(vector<int> path, int cost) {

	
	cout << endl << "path is: " << endl;
	for (int i = 0; i < path.size(); i++) {
		if(i < path.size() - 1)
			cout << path[i] << "->";
		else
			cout << path[i];
	}
	cout << endl << "Best cost found is: " << cost << endl;
}


float SimulatedAnnealing::calculate_starting_temperature(Graph* graph) {
	int max_cost = 0, min_cost = INT_MAX;
	for (int i = 0; i < graph->no_vertices; i++) {
		for (int j = 0; j < graph->no_vertices; j++) {
			if (i != j) {
				int cost = graph->edge_weight(i, j);
				max_cost = max(max_cost, cost);
				min_cost = min(min_cost, cost);
			}
		}
	}
	return (max_cost - min_cost) * 10; 
}

int SimulatedAnnealing::calculate_epochs(Graph* graph) {
	return graph->no_vertices * graph->no_vertices;
}


float SimulatedAnnealing::calculate_sigma(int prev_cost, int current_cost, float temperature) {
	return 1 / (1 + exp((prev_cost - current_cost) / temperature));
}


void SimulatedAnnealing::solve(Graph* graph, float cooling_rate, double max_time_seconds, bool is_silent) {
	int no_vertices = graph->no_vertices;
	int current_cost = INT_MAX;
	double time_of_finding_best = 0;
	vector<int> current_path;

	int best_cost = INT_MAX;
	vector<int> best_path;

	float temperature = SimulatedAnnealing::calculate_starting_temperature(graph);
	int epochs_number = SimulatedAnnealing::calculate_epochs(graph);

	


	for (auto i = 0; i < no_vertices; i++)
		best_path.push_back(i);

	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
	std::default_random_engine rng(seed);

	// generowanie pocz¹tkowego rozwi¹zania
	Solution* greedy_solution = GreedySolve::solve(graph);
	best_path = greedy_solution->path;
	best_cost = greedy_solution->cost;

	auto start = chrono::high_resolution_clock::now();
	auto next_report_time = 0.01 * max_time_seconds;

	while (true) {
		

		// warunek czasowy zatrzymania algorytmu
		auto now = chrono::high_resolution_clock::now();
		double solve_time = chrono::duration_cast<chrono::duration<double>>(now - start).count();

		if (solve_time >= max_time_seconds) {
			if (!is_silent) {
				cout << endl << "Time run out";
				print_solution(best_path, best_cost);
				cout << endl << "Temperature: " << temperature;
				cout << endl << "Exp(-1/Temperature): " << exp(-1 / temperature) << endl << endl;

				string file_path;
				cout << "Do you wish to save the solution? If so type the path to a file: ";
				cin >> file_path;

				if (file_path != "n") {
					FileHandler::save_solution(best_path, file_path);
				}
			}

			else {
				cout << "found best at " << time_of_finding_best << "s";
				print_solution(best_path, best_cost);
			}
			break;
		}

		for (int i = 0; i < epochs_number; i++) {
			current_path = calculate_neighbor(best_path);
			current_cost = calculate_cost(graph, current_path);

			if (current_cost < best_cost) {
				best_cost = current_cost;
				best_path = current_path;
				time_of_finding_best = chrono::duration_cast<chrono::duration<double>>(now - start).count();
			}
			else if (static_cast<float>(rand()) / RAND_MAX > calculate_sigma(best_cost, current_cost, temperature)) {
				best_cost = current_cost;
				best_path = current_path;
			}
		}

	
		temperature = cooling_rate * temperature;
	}



}