metavis/Metaheuristics/GeneticAlgorithm.cpp

#include "GeneticAlgorithm.h"
#include <iostream>

GeneticAlgorithm::GeneticAlgorithm(std::ostream& outstream, int iteration, int population, double mutateProbability, double swapProbability, double tournamentSize):
	iteration(iteration), populationSize(population), mutateProbability(mutateProbability), swapProbability(swapProbability), tournamentSize(tournamentSize), BinaryHeuristic(outstream)
{
}

Solution GeneticAlgorithm::execute(int rounds, int n, std::function<double(const std::vector<bool>&)> objectiveFunction, ObjectiveFunctionGoal goal)
{
	outstream << "round,iteration,populationNumber,objectiveFunction,binary" << std::endl;
	std::function<bool(double, double)> op = getOperatorFromGoal(goal);
	Solution bestFound;
	//init with Worst Value
	bestFound.objectiveFunctionValue = (goal == ObjectiveFunctionGoal::min) ? std::numeric_limits<double>::max() : std::numeric_limits<double>::min();
	for (int r = 0; r < rounds; r++) {
		Solution bestFoundInRun;
		//init with Worst Value
		bestFoundInRun.objectiveFunctionValue = (goal == ObjectiveFunctionGoal::min) ? std::numeric_limits<double>::max() : std::numeric_limits<double>::min();
		//Init populattion
		std::vector<Solution> population(populationSize);
		std::vector<Solution> childList(populationSize);
		for (Solution& sol : population) {
			std::vector<bool> bitstring(n);
			std::generate(bitstring.begin(), bitstring.end(), [this]() {return rand.doubleRandom() < 0.5; });
			sol.bitstring = bitstring;
		}

		for (int i = 0; i < iteration; i++) {
			//Evaluate
			for (Solution& sol : population) {
				sol.objectiveFunctionValue = objectiveFunction(sol.bitstring);
				//UpdateBest
				if (op(sol.objectiveFunctionValue, bestFoundInRun.objectiveFunctionValue)) {
					bestFoundInRun = sol;
				}
			}
			for (int k = 0; k < population.size() - 1; k++) {
				outstream << r << "," << i << "," << k << "," << population[k].objectiveFunctionValue << ","
					<< population[k].bitstringToStdString() << std::endl;
			}
			//GenerateChildren
			for (int k = 0; k < populationSize / 2; k++) {
				childList[2 * k] = selectAParent(population, op);
				childList[2 * k + 1] = selectAParent(population, op);
				crossover(childList[2 * k], childList[2 * k + 1]);
				mutate(childList[2 * k]);
				mutate(childList[2 * k + 1]);
			}
			//Exchange generations
			std::swap(population, childList);
			std::cout << "BestFound:" << bestFoundInRun.bitstringToStdString() << " with value:" << bestFoundInRun.objectiveFunctionValue << std::endl;
		}
		//update best run
		if (op(bestFoundInRun.objectiveFunctionValue, bestFound.objectiveFunctionValue)) {
			bestFound = bestFoundInRun;
		}
	}
	
	return bestFound;
}

Solution& GeneticAlgorithm::selectAParent(std::vector<Solution>& population, std::function<bool(double, double)> op)
{
	Solution* tournamentBest = &population[rand.randomIntegerInRange(0, populationSize)];
	double participants;
	for (participants = tournamentSize; participants >= 2; participants -= 1.0) {
		Solution& next = population[rand.randomIntegerInRange(0, populationSize)];
		if (op(next.objectiveFunctionValue,tournamentBest->objectiveFunctionValue)) tournamentBest = &next;
	}
	//if decimal participant stays in tournament its a chance to play another
	if (participants > 1) {
		if (rand.doubleRandom() < participants - 1.0) {
			Solution& next = population[rand.randomIntegerInRange(0, populationSize)];
			if (op(next.objectiveFunctionValue, tournamentBest->objectiveFunctionValue)) tournamentBest = &next;
		}
	}
	return *tournamentBest;
}

void GeneticAlgorithm::crossover(Solution& parentA, Solution& parentB)
{
	std::vector<bool>::iterator iterA= parentA.bitstring.begin();
	std::vector<bool>::iterator iterB= parentB.bitstring.begin();
	for (int i = 0; i < parentA.bitstring.size(); i++) {
		if (rand.doubleRandom() <= swapProbability) {
			//Swap 
			std::iter_swap(iterA, iterB);
		}
		iterA++;
		iterB++;
	}
}

void GeneticAlgorithm::mutate(Solution& individual)
{
	std::transform(individual.bitstring.begin(), individual.bitstring.end(), individual.bitstring.begin(), [this](bool bit) {
		return (rand.doubleRandom() < mutateProbability) ? !bit : bit;
	});
}