Adding Simulated Annealing Tuner ...
[satune.git] / src / Tuner / satuner.cc
1 #include "satuner.h"
2 #include <float.h>
3 #include <math.h>
4 #include "searchtuner.h"
5 #include <iostream>
6 #include <fstream>
7 #include "solver_interface.h"
8 #include <stdlib.h>
9
10 SATuner::SATuner(uint _budget, uint _timeout) :
11         BasicTuner(_budget, _timeout)
12 {
13 }
14
15 SATuner::~SATuner(){
16
17 }
18
19 void SATuner::rankTunerForProblem(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric){
20         uint k = 0;
21         for (; k < places->getSize(); k++) {
22                 if (metric < places->get(k)->getTime(problem))
23                         break;
24         }
25         model_print("Problem<%s>:place[%u]=Tuner<%p,%d>\n", problem->getProblem(), k, tuner, tuner->getTunerNumber());
26         places->insertAt(k, tuner);             
27 }
28
29 void SATuner::removeTunerIndex(Vector<TunerRecord *> *tunerV, int index,  Vector<Vector<TunerRecord *> *> &allplaces){
30         TunerRecord *tuner = tunerV->get(index);
31         model_print("Removing Tuner %d\n", tuner->getTunerNumber());
32         tunerV->set(index, NULL);
33         for(uint i=0; i < allplaces.getSize(); i++){
34                 Vector<TunerRecord *> *places = allplaces.get(i);
35                 for(uint j=0; j < places->getSize(); j++){
36                         if(tuner == places->get(j)){
37                                 places->removeAt(j);
38                                 break;
39                         }
40                 }
41         }
42
43 }
44
45 void SATuner::removeNullsFromTunerVector( Vector<TunerRecord *> *tunerV){
46         for (int i= tunerV->getSize() -1; i >= 0; i--){
47                 if(tunerV->get(i) == NULL){
48                         tunerV->removeAt(i);
49                 }
50         }
51         model_print("TunerV size after removing nulls = %u\n", tunerV->getSize());
52 }
53
54 void SATuner::initialize(Vector<TunerRecord *> *tunerV, Vector<Vector<TunerRecord *> *> &allplaces){
55         for(uint ii=0; ii< problems.getSize(); ii++){
56                 allplaces.push(new Vector<TunerRecord *>());
57         }
58         for (uint j = 0; j< tunerV->getSize(); j++){
59                 TunerRecord *tuner = tunerV->get(j);
60                 for (uint i=0; i < problems.getSize(); i++){
61                         Problem *problem = problems.get(i);
62                         long long metric = evaluate(problem, tuner);
63                         ASSERT(tuner->getTime(problem) == -1);
64                         tuner->addProblem(problem);
65                         if(metric != -1){
66                                 tuner->setTime(problem , metric);
67                         }else{
68                                 tuner->setTime(problem , -2);
69                         }
70                         if(metric >=0){
71                                 Vector<TunerRecord *> *places = allplaces.get(i);
72                                 rankTunerForProblem(places, tuner, problem, metric);
73                         }
74                 }
75         }
76
77 }
78
79 void SATuner::tune() {
80         Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);     
81         Vector<Vector<TunerRecord *> *> allplaces;
82         uint tunerNumber = tuners.getSize();
83         //Initialization
84         initialize(tunerV, allplaces);
85         //Starting the body of algorithm
86         for (uint t = budget; t >0; t--) {
87                 model_print("Current Temperature = %u\n", t);
88                 Hashtable<TunerRecord *, int, uint64_t> scores;
89                 for (uint i = 0; i < tunerNumber; i++) {
90                         SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), budget-t);
91                         int tunerIndex = subTunerIndex(tmpTuner);
92                         TunerRecord *tmp = NULL;
93                         if(tunerIndex == -1){
94                                 tmp = new TunerRecord(tmpTuner);
95                                 tmp->setTunerNumber(allTuners.getSize());
96                                 model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
97                                 allTuners.push(tmp);    
98                         }else{
99                                 //Previous tuners might get explored with new combination of tuners.
100                                 tmp = explored.get(tunerIndex); 
101                                 model_print("Using exploread tuner <%u>\n", tmp->getTunerNumber());
102                         }
103                         tunerV->push(tmp);
104                 }
105                 ASSERT(tunerNumber * 2 == tunerV->getSize());
106                 for (uint j = tunerNumber; j < tunerV->getSize(); j++) {
107                         TunerRecord *tuner = tunerV->get(j);
108                         for (uint i = 0; i < problems.getSize(); i++) {
109                                 Problem *problem = problems.get(i);
110                                 long long metric = tuner->getTime(problem);
111                                 if (metric == -1) {
112                                         metric = evaluate(problem, tuner);
113                                         if (tuner->getTime(problem) == -1) {
114                                                 tuner->addProblem(problem);
115                                         }
116                                         model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric);
117                                         model_print("*****************************\n");
118                                         if (metric != -1)
119                                                 tuner->setTime(problem, metric);
120                                         else
121                                                 tuner->setTime(problem, -2);
122
123                                 }
124                                 if (metric >= 0) {
125                                         ASSERT(i < allplaces.getSize());
126                                         Vector<TunerRecord *> *places = allplaces.get(i);
127                                         model_print("Problem<%s>:place[size=%u]=Tuner<%p,%d>\n", problem->getProblem(), places->getSize(), tuner, tuner->getTunerNumber());
128                                         rankTunerForProblem(places, tuner, problem, metric);
129                                 }
130                         }
131                 }
132                 for(uint ii=0; ii < problems.getSize(); ii++){
133                         Problem *problem = problems.get(ii);
134                         ASSERT(ii < allplaces.getSize());
135                         Vector<TunerRecord *> *places = allplaces.get(ii);
136                         int points = pow(tunerNumber*1.0, 2*tunerNumber - 1);
137                         for (uint k = 0; k < places->getSize() && points; k++) {
138                                 TunerRecord *tuner = places->get(k);
139                                 int currScore = 0;
140                                 if (scores.contains(tuner))
141                                         currScore = scores.get(tuner);
142                                 currScore += points;
143                                 model_print("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->getProblem(), tuner, tuner->getTunerNumber(),  currScore);
144                                 model_print("**************************\n");
145                                 scores.put(tuner, currScore);
146                                 points = points / tunerNumber;
147                         }
148                 }
149
150                 for(uint i= 0; i < tunerNumber; i++){
151                         ASSERT(i < tunerV->getSize());
152                         TunerRecord *tuner1 = tunerV->get(i);
153                         TunerRecord *tuner2 = tunerV->get(tunerNumber + i);
154                         ASSERT( tunerNumber + i < tunerV->getSize());
155                         model_print("Tuner1 = %d \tTuner2 = %d\n", tuner1->getTunerNumber(), tuner2->getTunerNumber());
156                         ASSERT(scores.contains(tuner1));
157                         ASSERT(scores.contains(tuner2));
158                         int score1 = scores.get(tuner1);
159                         int score2 = scores.get(tuner2);
160                         if( score2 > score1 ){
161                                 removeTunerIndex(tunerV, i, allplaces);
162                         } else if( score2 < score1){
163                                 model_print("score1=%d\tscore2=%d\tt=%u\texp=%f\n", score1, score2, t, exp((score1-score2)*1.0/t));
164                                 double prob = 1/(exp((score1-score2)*1.0/t) );
165                                 double random = ((double) rand() / (RAND_MAX));
166                                 model_print("prob=%f\trandom=%f\n", prob, random);
167                                 if(prob > random){
168                                         removeTunerIndex(tunerV, i, allplaces);
169                                 }else{
170                                         removeTunerIndex(tunerV, tunerNumber + i, allplaces);
171                                 }
172                         } else{
173                                 double random = ((double) rand() / (RAND_MAX));
174                                 int index = random > 0.5? i : tunerNumber + i;
175                                 removeTunerIndex(tunerV, index, allplaces);
176                         }
177                 }
178                 removeNullsFromTunerVector(tunerV);
179                 
180         }
181         for(uint ii=0; ii< allplaces.getSize(); ii++){
182                 delete allplaces.get(ii);
183         }
184         printData();
185 }