Optimizer.cpp

#include "Optimizer.hpp"
#include <iostream>
#include <limits>
#include <iomanip>

using namespace LcVRPContest;

Optimizer::Optimizer(Evaluator& evaluator) 
	: evaluator_(evaluator), 
	  rng_(random_device{}()), 
	  current_best_fitness_(numeric_limits<double>::max()) {}

void Optimizer::Initialize() {
	current_best_.clear();
	current_best_.resize(evaluator_.GetSolutionSize());
	//InitRandomIndividual(current_best_);
	//current_best_fitness_ = evaluator_.Evaluate(current_best_);

	num_threads_ = 5;
	num_islands_ = 31; // 2^5 - 1

	std::vector<Config> configs;
	configs.reserve(num_islands_);
	islands_.reserve(num_islands_);

	unsigned id = 0;

	//id, pop_size, elite_count, cross_prob, mut_prob, diversity_level, migrants_count

	// central lvl 0
	
	configs.push_back({ id, 1500, 25, 0.95f, 0.001f, 0, 0 });
	++id;

	// commanders lvl 1
	int group_size = 2; // 2

	for (int i = 0; i < group_size; ++i)
	{
		configs.push_back({ id, 600, 10, 0.9f, 0.005f, 1, 10 });
		++id;
	}
	
	// weirdos lvl 2
	group_size *= 2; // 4

	for (int i = 0; i < group_size; ++i)
	{
		configs.push_back({ id, 260, 5, 0.0f, 0.0f, 2, 5 });
		++id;
	}

	// scouts lvl 3
	group_size *= 2; // 8

	for (int i = 0; i < group_size; ++i)
	{
		configs.push_back({ id, 130, 3, 0.85f, 0.02f, 3, 2 });
		++id;
	}

	// kamikaze lvl 4
	group_size *= 2; // 16

	for (int i = 0; i < group_size; ++i)
	{
		configs.push_back({ id, 46, 1, 0.20f, 0.90f, 4, 1 });
		++id;
	}

	// create objects
	islands_.clear();
	for (size_t i = 0; i < num_islands_; ++i)
	{
		islands_.push_back(UniquePtr<GeneticAlgorithm>(new GeneticAlgorithm(evaluator_, configs[i])));
	}

	// init
	for (size_t i = 0; i < num_islands_; ++i)
	{
		islands_[i]->initialize();
	}
	
	// create reverse tree topology
	for (size_t i = 1; i < num_islands_; ++i)
	{
		size_t parent_idx = (i - 1) / 2;
		islands_[i]->addDestination(islands_[parent_idx].get());
	}

	current_best_ = islands_[0]->getBest().getGenotype();
	current_best_fitness_ = islands_[0]->getBestFitness();
}

void Optimizer::RunIteration() 
{
	std::vector<std::thread> threads;
	threads.reserve(num_threads_);

	size_t start_idx = 0;

	auto runBatch = [this](size_t start, size_t end) {
			for (size_t i = start; i < end; ++i)
			{
				islands_[i]->runIteration();
			}
		};

	for (size_t i = 0; i < num_threads_; ++i)
	{
		size_t end_idx = start_idx * 2 + 1;

		threads.emplace_back(runBatch, start_idx, end_idx);

		start_idx = end_idx;
	}

	for (auto &thread : threads)
	{
		if (thread.joinable()) 
		{
			thread.join();
		}
	}

	for (size_t i = 0; i < num_islands_; ++i)
	{
		double best_fitness = islands_[i]->getBestFitness();

		if (best_fitness < current_best_fitness_)
		{
			current_best_ = islands_[i]->getBest().getGenotype();
			current_best_fitness_ = best_fitness;
			//PrintIndivual(current_best_, current_best_fitness_);
		}
	}
}

void Optimizer::InitRandomIndividual(vector<int>& individual) {
	uniform_int_distribution<int> dist(evaluator_.GetLowerBound(), evaluator_.GetUpperBound());
	for (size_t i = 0; i < individual.size(); ++i) {
		individual[i] = dist(rng_);
	}
}

void Optimizer::PrintIndivual(vector<int>& individual, double fitness) const {
	vector<int> group_counts(evaluator_.GetNumGroups(), 0);
	for (int group : individual) {
		group_counts[group]++;
	}

	cout << "current fitness: " << fixed << setprecision(2) << fitness << ", groups: [";
	for (size_t i = 0; i < group_counts.size(); ++i) {
		cout << group_counts[i] << (i < group_counts.size() - 1 ? ", " : "");
	}
	cout << "]" << endl;
}