TabuSearch.cpp

#include "TabuSearch.h"
#include "FileHandler.h"
#include "Graph.h"
#include "GreedySolve.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <map>
#include <vector>
#include <random>
#include <cmath>
#include <queue>
using namespace std;


struct MoveComparator {
	bool operator()(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
		return a.second < b.second;
	}
};


struct TabuComparator {
	bool operator()(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
		return a.second > b.second;
	}
};

int TabuSearch::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> TabuSearch::calculate_neighbor(vector<int> path, int neighboor_function_choice, int index1, int index2) {

	// wybieramy dwa miasta i odwracamy kolejnoœæ œcie¿ki miêdzy nimi
	if (neighboor_function_choice == 1) {
		
		if (index1 > index2) 
			swap(index1, index2);

		reverse(path.begin() + index1, path.begin() + index2 + 1);
	}
	// zamieniamy dwa losowe miasta
	else if (neighboor_function_choice == 2) {
		swap(path[index1], path[index2]);
	}

	// przesuwamy segment na koniec trasy
	else if (neighboor_function_choice == 3) {
		vector<int> segment(path.begin() + index1, path.begin() + index2 + 1);
		path.erase(path.begin() + index1, path.begin() + index2 + 1);
		path.insert(path.end(), segment.begin(), segment.end());
	}
	return path;
}



void TabuSearch::solve(Graph* graph, int neighboor_function_choice, double max_time_seconds, bool is_silent) {

	int no_vertices = graph->no_vertices;

	int current_cost = INT_MAX;
	vector<int> current_path;

	int proposal_cost = INT_MAX;
	vector<int> proposal_path;

	int global_best_cost = INT_MAX;
	vector<int> global_best_path;

	int local_best_cost = INT_MAX;
	vector<int> local_best_path;


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

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

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

	copy(global_best_path.begin(), global_best_path.end(), back_inserter(local_best_path));
	

	double time_of_finding_best = 0;

	vector<pair<pair<int, int>, int>> tabu;
	
	// czas ¿ycia rekordu w liœcie tabu == maksymalna wielkoœæ tablicu tabu
	int tabu_tenure = no_vertices / 2;

	// liczba iteracji przed zastosowaniem mechanizmu dywersyfikacji
	int diversification_threshold = no_vertices * 2;

	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, MoveComparator> move_heap;
	int max_move_choices = no_vertices * (no_vertices - 1) / 2;

	int iteration_without_bettering = 0;
	int index1, index2;
	auto start = chrono::high_resolution_clock::now();
	auto next_report_time = 0.005 * max_time_seconds;
	while (true) {
		

		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(global_best_path, global_best_cost);
				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(global_best_path, file_path);
				}
			}
			else {
				cout << "found best at " << time_of_finding_best << "s";
				print_solution(global_best_path, global_best_cost);
			}
			break;
		}

		current_path = local_best_path;
		current_cost = local_best_cost;

		// metoda dywersifikacji przeszukiwania przestrzeni rozwi¹zañ
		// losowo wybieramy ca³kiem inny obszar poszukiwañ
		if (iteration_without_bettering >= diversification_threshold) {
			shuffle(current_path.begin(), current_path.end(), rng);
		}

		for (int i = 0; i < max_move_choices; i++) {
			// obliczanie dwóch indeksów
			index1 = rand() % current_path.size();
			index2 = rand() % current_path.size();

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

			if (index2 < index1)
				swap(index1, index2);

			// generowanie nowego wyniku
			proposal_path = calculate_neighbor(current_path, neighboor_function_choice, index1, index2);
			proposal_cost = calculate_cost(graph, proposal_path);
			int improvement = current_cost - proposal_cost;
			move_heap.push({ {index1, index2}, improvement });
		}

		do {
			pair<pair<int, int>, int> best_move = move_heap.top();
			int improvement = best_move.second;
			pair<int, int> move = best_move.first;
			move_heap.pop();

			bool in_tabu = false;
			vector<pair<pair<int, int>, int>>::iterator tabu_iter = tabu.end();
			
			for (auto record = tabu.begin(); record != tabu.end(); ++record) {
				if (record->first.first == index1 && record->first.second == index2) {
					in_tabu = true;
					tabu_iter = record; 
					break;
				}
			}

			// ignorujemy tabu jeœli jest tam lepsze rozwi¹zanie ni¿ obecne
			// lub generujemy ruch o najmniejszej stracie lub najwiêkszym przyroœcie nie w tabu
			if (improvement + current_cost > global_best_cost) {
				global_best_path = calculate_neighbor(current_path, neighboor_function_choice, move.first, move.second);
				global_best_cost = calculate_cost(graph, global_best_path);

				local_best_cost = global_best_cost;
				local_best_path = global_best_path;
				move_heap = priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, MoveComparator>();
				time_of_finding_best = chrono::duration_cast<chrono::duration<double>>(now - start).count();
				iteration_without_bettering = 0;
				if (!in_tabu)
					tabu.push_back({ {move.first, move.second}, tabu_tenure });
				else
					tabu_iter->second = tabu_tenure;
				break;
			}
			else if (!in_tabu) {
				move_heap = priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, MoveComparator>();
				local_best_path = calculate_neighbor(current_path, neighboor_function_choice, move.first, move.second);
				local_best_cost = calculate_cost(graph, global_best_path);

				if(improvement > 0)
					iteration_without_bettering = 0;

				tabu.push_back({ {move.first, move.second}, tabu_tenure });
				break;
			}
			

			
		} while (!move_heap.empty());

		iteration_without_bettering++;
		

		// aktualizowanie ¿ycia zabronionych par indeksów 
		for (auto record = tabu.begin(); record != tabu.end();) {
			if (record->second > 0) {
				record->second -= 1;
				++record;
			}
			else {
				record = tabu.erase(record);
			}
		}
	}

}

void TabuSearch::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;
}