123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 |
- #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;
- });
- }
|