src/Tuner/kmeanstuner.cc

   1 /*
   2  * To change this license header, choose License Headers in Project Properties.
   3  * To change this template file, choose Tools | Templates
   4  * and open the template in the editor.
   5  */
   6
   7 /*
   8  * File:   kmeanstuner.cc
   9  * Author: hamed
  10  *
  11  * Created on December 19, 2018, 4:16 PM
  12  */
  13
  14 #include "kmeanstuner.h"
  15 #include "float.h"
  16 #include "searchtuner.h"
  17 #include "math.h"
  18
  19 KMeansTuner::KMeansTuner(uint budget, uint _rounds, uint timeout) :
  20         BasicTuner(budget, timeout),
  21         rounds(_rounds) {
  22 }
  23
  24 KMeansTuner::~KMeansTuner() {
  25 }
  26
  27 void clearVector(Vector<TunerRecord *> *tunerV) {
  28         for (uint j = 0; j < tunerV->getSize(); j++) {
  29                 TunerRecord *tuner = tunerV->get(j);
  30                 tuner->problems.clear();
  31         }
  32 }
  33
  34 void KMeansTuner::tune() {
  35         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
  36         for (uint i = 0; i < rounds; i++) {
  37                 clearVector(tunerV);
  38                 mapProblemsToTuners(tunerV);
  39                 improveTuners(tunerV);
  40         }
  41         model_print("Best tuners\n");
  42         for (uint j = 0; j < tunerV->getSize(); j++) {
  43                 TunerRecord *tuner = tunerV->get(j);
  44                 char buffer[256];
  45                 sprintf(buffer, "tuner%u.conf", j);
  46                 tuner->getTuner()->serialize(buffer);
  47                 tuner->getTuner()->print();
  48         }
  49         delete tunerV;
  50 }
  51
  52 void KMeansTuner::improveTuners(Vector<TunerRecord *> *tunerV) {
  53         for (uint j = 0; j < tunerV->getSize(); j++) {
  54                 TunerRecord *tuner = tunerV->get(j);
  55                 TunerRecord *newtuner = tune(tuner);
  56                 tunerV->set(j, newtuner);
  57         }
  58 }
  59
  60 double KMeansTuner::evaluateAll(TunerRecord *tuner) {
  61         double product = 1;
  62         for (uint i = 0; i < tuner->problemsSize(); i++) {
  63                 Problem *problem = tuner->getProblem(i);
  64                 long long metric = tuner->getTime(problem);
  65                 if (metric == -1) {
  66                         metric = evaluate(problem, tuner);
  67                         if (metric != -1)
  68                                 tuner->setTime(problem, metric);
  69                         else
  70                                 tuner->setTime(problem, -2);
  71                 }
  72
  73                 double score = metric;
  74                 if (metric < 0)
  75                         score = timeout;
  76                 product *= score;
  77         }
  78         return pow(product, 1 / ((double)tuner->problemsSize()));
  79 }
  80
  81 TunerRecord *KMeansTuner::tune(TunerRecord *tuner) {
  82         TunerRecord *bestTuner = NULL;
  83         double bestScore = DBL_MAX;
  84
  85         TunerRecord *oldTuner = tuner;
  86         double base_temperature = evaluateAll(oldTuner);
  87         double oldScore = base_temperature;
  88
  89         for (uint i = 0; i < budget; i++) {
  90                 SearchTuner *tmpTuner = mutateTuner(oldTuner->getTuner(), i);
  91                 TunerRecord *newTuner = oldTuner->changeTuner(tmpTuner);
  92                 newTuner->setTunerNumber( allTuners.getSize() );
  93                 allTuners.push(newTuner);
  94                 double newScore = evaluateAll(newTuner);
  95                 newTuner->getTuner()->printUsed();
  96                 model_print("Received score %f\n", newScore);
  97                 double scoreDiff = newScore - oldScore; //smaller is better
  98                 if (newScore < bestScore) {
  99                         bestScore = newScore;
 100                         bestTuner = newTuner;
 101                 }
 102
 103                 double acceptanceP;
 104                 if (scoreDiff < 0) {
 105                         acceptanceP = 1;
 106                 } else {
 107                         double currTemp = base_temperature * (((double)budget - i) / budget);
 108                         acceptanceP = exp(-scoreDiff / currTemp);
 109                 }
 110                 double ran = ((double)random()) / RAND_MAX;
 111                 if (ran <= acceptanceP) {
 112                         oldScore = newScore;
 113                         oldTuner = newTuner;
 114                 }
 115         }
 116
 117         return bestTuner;
 118 }
 119
 120 void KMeansTuner::mapProblemsToTuners(Vector<TunerRecord *> *tunerV) {
 121         for (uint i = 0; i < problems.getSize(); i++) {
 122                 Problem *problem = problems.get(i);
 123                 TunerRecord *bestTuner = NULL;
 124                 long long bestscore = 0;
 125                 for (uint j = 0; j < tunerV->getSize(); j++) {
 126                         TunerRecord *tuner = tunerV->get(j);
 127                         long long metric = tuner->getTime(problem);
 128                         if (metric == -1) {
 129                                 metric = evaluate(problem, tuner);
 130                                 if (metric != -1)
 131                                         tuner->setTime(problem, metric);
 132                                 else
 133                                         tuner->setTime(problem, -2);
 134                         }
 135                         if ((bestTuner == NULL && metric >= 0) ||
 136                                         (metric < bestscore && metric >= 0)) {
 137                                 bestTuner = tuner;
 138                                 bestscore = metric;
 139                         }
 140                 }
 141                 if (bestTuner != NULL)
 142                         bestTuner->addProblem(problem);
 143         }
 144 }