sccomp/source/solver/DifferentialEvolution.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  */
  10
  11 #pragma once
  12
  13 #include <vector>
  14 #include <random>
  15 #include <limits>
  16
  17 struct Individual
  18 {
  19     std::vector<double> mVariables;
  20 };
  21
  22 template <typename DataProvider> class DifferentialEvolutionAlgorithm
  23 {
  24     static constexpr double mnDifferentialWeight = 0.5; // [0, 2]
  25     static constexpr double mnCrossoverProbability = 0.9; // [0, 1]
  26
  27     static constexpr double constAcceptedPrecision = 0.000000001;
  28
  29     DataProvider& mrDataProvider;
  30
  31     size_t mnPopulationSize;
  32     std::vector<Individual> maPopulation;
  33
  34     std::random_device maRandomDevice;
  35     std::mt19937 maGenerator;
  36     size_t mnDimensionality;
  37
  38     std::uniform_int_distribution<> maRandomPopulation;
  39     std::uniform_int_distribution<> maRandomDimensionality;
  40     std::uniform_real_distribution<> maRandom01;
  41
  42     Individual maBestCandidate;
  43     double mfBestFitness;
  44     int mnGeneration;
  45     int mnLastChange;
  46
  47 public:
  48     DifferentialEvolutionAlgorithm(DataProvider& rDataProvider, size_t nPopulationSize)
  49         : mrDataProvider(rDataProvider)
  50         , mnPopulationSize(nPopulationSize)
  51         , maGenerator(maRandomDevice())
  52         , mnDimensionality(mrDataProvider.getDimensionality())
  53         , maRandomPopulation(0, mnPopulationSize - 1)
  54         , maRandomDimensionality(0, mnDimensionality - 1)
  55         , maRandom01(0.0, 1.0)
  56         , mfBestFitness(std::numeric_limits<double>::lowest())
  57         , mnGeneration(0)
  58         , mnLastChange(0)
  59     {
  60     }
  61
  62     std::vector<double> const& getResult() { return maBestCandidate.mVariables; }
  63
  64     int getGeneration() { return mnGeneration; }
  65
  66     int getLastChange() { return mnLastChange; }
  67
  68     void initialize()
  69     {
  70         mnGeneration = 0;
  71         mnLastChange = 0;
  72         maPopulation.clear();
  73         maBestCandidate.mVariables.clear();
  74
  75         // Initialize population with individuals that have been initialized with uniform random
  76         // noise
  77         // uniform noise means random value inside your search space
  78         maPopulation.reserve(mnPopulationSize);
  79         for (size_t i = 0; i < mnPopulationSize; ++i)
  80         {
  81             maPopulation.emplace_back();
  82             Individual& rIndividual = maPopulation.back();
  83             mrDataProvider.initializeVariables(rIndividual.mVariables, maGenerator);
  84         }
  85     }
  86
  87     // Calculate one generation
  88     bool next()
  89     {
  90         bool bBestChanged = false;
  91
  92         for (size_t agentIndex = 0; agentIndex < mnPopulationSize; ++agentIndex)
  93         {
  94             // calculate new candidate solution
  95
  96             // pick random point from population
  97             size_t x = agentIndex; // randomPopulation(generator);
  98             size_t a, b, c;
  99
 100             // create a copy of chosen random agent in population
 101             Individual& rOriginal = maPopulation[x];
 102             Individual aCandidate(rOriginal);
 103
 104             // pick three different random points from population
 105             do
 106             {
 107                 a = maRandomPopulation(maGenerator);
 108             } while (a == x);
 109
 110             do
 111             {
 112                 b = maRandomPopulation(maGenerator);
 113             } while (b == x || b == a);
 114
 115             do
 116             {
 117                 c = maRandomPopulation(maGenerator);
 118
 119             } while (c == x || c == a || c == b);
 120
 121             size_t randomIndex = maRandomDimensionality(maGenerator);
 122
 123             for (size_t index = 0; index < mnDimensionality; ++index)
 124             {
 125                 double randomCrossoverProbability = maRandom01(maGenerator);
 126                 if (index == randomIndex || randomCrossoverProbability < mnCrossoverProbability)
 127                 {
 128                     double fVarA = maPopulation[a].mVariables[index];
 129                     double fVarB = maPopulation[b].mVariables[index];
 130                     double fVarC = maPopulation[c].mVariables[index];
 131
 132                     double fNewValue = fVarA + mnDifferentialWeight * (fVarB - fVarC);
 133                     fNewValue = mrDataProvider.boundVariable(index, fNewValue);
 134                     aCandidate.mVariables[index] = fNewValue;
 135                 }
 136             }
 137
 138             double fCandidateFitness = mrDataProvider.calculateFitness(aCandidate.mVariables);
 139
 140             // see if is better than original, if so replace
 141             if (fCandidateFitness > mrDataProvider.calculateFitness(rOriginal.mVariables))
 142             {
 143                 maPopulation[x] = std::move(aCandidate);
 144
 145                 if (fCandidateFitness > mfBestFitness)
 146                 {
 147                     if (std::abs(fCandidateFitness - mfBestFitness) > constAcceptedPrecision)
 148                     {
 149                         bBestChanged = true;
 150                         mnLastChange = mnGeneration;
 151                     }
 152                     mfBestFitness = fCandidateFitness;
 153                     maBestCandidate = maPopulation[x];
 154                 }
 155             }
 156         }
 157         mnGeneration++;
 158         return bBestChanged;
 159     }
 160 };
 161
 162 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */