Line data    Source code

       1             : #include "Opt/GeneticSolver.hpp"
       2             : 
       3             : #include <cmath>
       4             : #include <iostream>
       5             : #include <random>
       6             : 
       7             : #include "Opt/UnivariateSolver.hpp"
       8             : 
       9             : using namespace std;
      10             : using namespace Opt;
      11             : 
      12             : typedef UnivariateSolver::Var Var;
      13             : 
      14           7 : GeneticSolver::GeneticSolver(
      15             :     size_t              populationSize_,
      16             :     size_t              newPopulationSize_,
      17             :     Var                 variabilityCoeff_,
      18             :     size_t              maxNumberGenerations_,
      19             :     int                 parallelism,
      20             :     shared_ptr<mt19937> gen_
      21           7 : ):
      22             :     populationSize(populationSize_),
      23             :     newPopulationSize(newPopulationSize_),
      24             :     variabilityCoeff(variabilityCoeff_),
      25             :     maxNumberGenerations(maxNumberGenerations_),
      26             :     pool(parallelism),
      27           7 :     gen(gen_) {}
      28             : 
      29           7 : void GeneticSolver::clearInitialSolutions() {
      30           7 :     newPopulation.clear();
      31           7 : }
      32             : 
      33        7700 : void GeneticSolver::addInitialSolution(Var v) {
      34        7700 :     newPopulation.push_back(v);
      35        7700 : }
      36             : 
      37           7 : void GeneticSolver::setStopCriteria(Var e) {
      38           7 :     epsilon = e;
      39           7 : }
      40             : 
      41           7 : Var GeneticSolver::solve(Problem p) {
      42           7 :     population.clear();
      43             : 
      44           7 :     problem = &p;
      45             : 
      46           7 :     tournament();
      47             : 
      48          60 :     for(size_t i = 0; i < maxNumberGenerations; ++i) {
      49          60 :         Var a = 1e9, b = -1e9;
      50        6060 :         for(const auto &[z, v]: population) {
      51        6000 :             a = min(a, v);
      52        8948 :             b = max(b, v);
      53             :         }
      54             : 
      55          60 :         Var Delta = b - a;
      56          60 :         if(Delta < epsilon) {
      57             :             break;
      58             :         }
      59             : 
      60          53 :         crossover();
      61          53 :         mutation();
      62          53 :         tournament();
      63             :     }
      64             : 
      65           7 :     return population[0].second;
      66             : }
      67             : 
      68          53 : void GeneticSolver::crossover() {
      69          53 :     uniform_int_distribution<size_t> distribution(0, populationSize - 1);
      70             : 
      71       53549 :     while(newPopulation.size() < newPopulationSize) {
      72       53496 :         size_t a = distribution(*gen);
      73       53496 :         size_t b = distribution(*gen);
      74       53496 :         if(a == b) continue;
      75             : 
      76      106000 :         newPopulation.push_back(crossover(population[a].second, population[b].second));
      77             :     }
      78          53 : }
      79             : 
      80       53000 : Var GeneticSolver::crossover(const Var &a, const Var &b) {
      81       53000 :     uniform_real_distribution<double> distribution(0.0, 1.0);
      82             : 
      83       53000 :     double r = distribution(*gen);
      84             : 
      85       53000 :     return a + (b - a) * r;
      86             : }
      87             : 
      88          53 : void GeneticSolver::mutation() {
      89          53 :     Var variability = getVariability();
      90       53053 :     for(auto &v: newPopulation) {
      91      106000 :         mutation(v, variability);
      92             :     }
      93          53 : }
      94             : 
      95       53000 : Var &GeneticSolver::mutation(Var &v, const Var &variability) {
      96       53000 :     uniform_real_distribution<double> distribution(-1.0, 1.0);
      97             : 
      98       53000 :     double r = distribution(*gen);
      99             : 
     100       53000 :     return v += r * variability;
     101             : }
     102             : 
     103          53 : Var GeneticSolver::getVariability() const {
     104          53 :     Var a = 1e9, b = -1e9;
     105        5353 :     for(const auto &[z, v]: population) {
     106        5300 :         a = min(a, v);
     107        7945 :         b = max(b, v);
     108             :     }
     109          53 :     return (b - a) * variabilityCoeff;
     110             : }
     111             : 
     112          60 : void GeneticSolver::tournament() {
     113          60 :     if(pool.size() <= 0) {
     114           0 :         for(const Var &v: newPopulation)
     115           0 :             population.emplace_back((*problem)(v), v);
     116             :     } else {
     117         120 :         vector<future<Var>> results;
     118       60760 :         for(const Var &v: newPopulation) {
     119      181828 :             results.emplace_back(pool.push([this, v](int) -> Var {
     120       60428 :                 return (*problem)(v);
     121       60700 :             }));
     122             :         }
     123       60760 :         for(size_t i = 0; i < results.size(); ++i) {
     124       60700 :             Var z = results[i].get();
     125       60700 :             population.emplace_back(z, newPopulation[i]);
     126             :         }
     127             :     }
     128             : 
     129          60 :     newPopulation.clear();
     130             : 
     131          60 :     sort(population.begin(), population.end());
     132             : 
     133       60060 :     while(population.size() > populationSize) {
     134       60000 :         population.pop_back();
     135             :     }
     136          60 : }