+++ /dev/null
-#include "csolver.h"
-#include "comptuner.h"
-#include "searchtuner.h"
-
-int main(int argc, char **argv) {
- if (argc < 7) {
- printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]);
- exit(-1);
- }
- uint budget;
- uint rounds;
- uint timeout;
- sscanf(argv[1], "%u", &budget);
- sscanf(argv[2], "%u", &rounds);
- sscanf(argv[3], "%u", &timeout);
-
- CompTuner *multituner = new CompTuner(budget, timeout);
- bool tunerfiles = false;
- for (int i = 4; i < argc; i++) {
- if (!tunerfiles) {
- if (argv[i][0] == '-' && argv[i][1] == 0)
- tunerfiles = true;
- else
- multituner->addProblem(argv[i]);
- } else
- multituner->addTuner(new SearchTuner(argv[i], true )); //add settings to usedsettigs
- }
-
- if (!tunerfiles) {
- printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]);
- exit(-1);
- }
-
- multituner->tune();
- delete multituner;
- return 0;
-}
#include "csolver.h"
#include "searchtuner.h"
#include "kmeanstuner.h"
+#include "satuner.h"
+#include "comptuner.h"
+#include "randomtuner.h"
+
+void printKnownTunerTypes(){
+ printf("Known Tuner Types:\nRandom Tuner=1\nComp Tuner=2\nKmeans Tuner=3\nSimulated Annealing Tuner=4\n");
+}
+
+BasicTuner *createTuner(uint tunertype, uint budget, uint rounds, uint timeout){
+ switch(tunertype){
+ case 1: return new RandomTuner(budget, timeout);
+ case 2: return new CompTuner(budget, timeout);
+ case 3: return new KMeansTuner(budget, rounds, timeout);
+ case 4: return new SATuner(budget, timeout);
+ default:
+ printf("Tuner type %u is unknown\n", tunertype);
+ printKnownTunerTypes();
+ exit(-1);
+ }
+
+}
int main(int argc, char **argv) {
- if (argc < 7) {
- printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]);
+ if (argc < 8) {
+ printf("You should specify: %s TunerType budget rounds timeout problemfilenames - tunerfilenames\n", argv[0]);
+ printKnownTunerTypes();
exit(-1);
}
+ uint tunertype;
uint budget;
uint rounds;
uint timeout;
- sscanf(argv[1], "%u", &budget);
- sscanf(argv[2], "%u", &rounds);
- sscanf(argv[3], "%u", &timeout);
+ sscanf(argv[1], "%u", &tunertype);
+ sscanf(argv[2], "%u", &budget);
+ sscanf(argv[3], "%u", &rounds);
+ sscanf(argv[4], "%u", &timeout);
- KMeansTuner *multituner = new KMeansTuner(budget, rounds, timeout);
+ BasicTuner *multituner = createTuner(tunertype, budget, rounds, timeout);
bool tunerfiles = false;
- for (int i = 4; i < argc; i++) {
+ for (int i = 5; i < argc; i++) {
if (!tunerfiles) {
if (argv[i][0] == '-' && argv[i][1] == 0)
tunerfiles = true;
else
multituner->addProblem(argv[i]);
} else
- multituner->addTuner(new SearchTuner(argv[i]));
+ multituner->addTuner(new SearchTuner(argv[i], true )); //add settings to usedsettigs
}
if (!tunerfiles) {
+++ /dev/null
-#include "csolver.h"
-#include "randomtuner.h"
-#include "searchtuner.h"
-
-int main(int argc, char **argv) {
- if (argc < 6) {
- printf("You should specify %s rounds timeout problemfilenames - tunerfilenames", argv[0]);
- exit(-1);
- }
- uint rounds;
- uint timeout;
- sscanf(argv[1], "%u", &rounds);
- sscanf(argv[2], "%u", &timeout);
-
- RandomTuner *randomTuner = new RandomTuner(rounds, timeout);
- bool tunerfiles = false;
- for (int i = 3; i < argc; i++) {
- if (!tunerfiles) {
- if (argv[i][0] == '-' && argv[i][1] == 0)
- tunerfiles = true;
- else
- randomTuner->addProblem(argv[i]);
- } else
- randomTuner->addTuner(new SearchTuner(argv[i]));
- }
-
- if (!tunerfiles) {
- printf("You should specify %s budget rounds timeout problemfilenames - tunerfilenames", argv[0]);
- exit(-1);
- }
-
- randomTuner->tune();
- delete randomTuner;
- return 0;
-}
}
}
-bool BasicTuner::tunerExists(SearchTuner *tuner){
+bool BasicTuner::tunerExists(TunerRecord *tunerec){
+ SearchTuner *tuner = tunerec->getTuner();
for(uint i=0; i< explored.getSize(); i++){
- if(explored.get(i)->getTuner()->equalUsed(tuner))
+ if(explored.get(i)->getTuner()->equalUsed(tuner)){
+ model_print("************Tuner <%d> is replicate of Tuner <%d>\n", tunerec->getTunerNumber(), explored.get(i)->getTunerNumber());
return true;
+ }
}
return false;
}
return newTuner;
}
-bool BasicTuner::subTunerExist(SearchTuner *newTuner){
+int BasicTuner::subTunerIndex(SearchTuner *newTuner){
for (uint i=0; i< explored.getSize(); i++){
SearchTuner *tuner = explored.get(i)->getTuner();
if(tuner->isSubTunerof(newTuner)){
- return true;
+ return i;
}
}
- return false;
+ return -1;
}
if (metric < problem->getBestTime()) {
problem->setBestTime( metric );
}
-}
\ No newline at end of file
+}
class TunerRecord {
public:
- TunerRecord(SearchTuner *_tuner) : tuner(_tuner), tunernumber(-1) {}
- TunerRecord(SearchTuner *_tuner, int _tunernumber) : tuner(_tuner), tunernumber(_tunernumber) {}
+ TunerRecord(SearchTuner *_tuner) : tuner(_tuner), tunernumber(-1), isduplicate(false) {}
+ TunerRecord(SearchTuner *_tuner, int _tunernumber) : tuner(_tuner), tunernumber(_tunernumber), isduplicate(false) {}
SearchTuner *getTuner() {return tuner;}
void inline addProblem(Problem * problem){problems.push(problem);}
TunerRecord *changeTuner(SearchTuner *_newtuner);
inline void setTunerNumber(int numb){tunernumber = numb;}
inline int getTunerNumber(){return tunernumber;}
inline uint problemsSize() {return problems.getSize();}
+ inline void setDuplicate(bool _duplicate) { isduplicate = _duplicate;}
+ inline bool isDuplicate() {return isduplicate;}
inline Problem *getProblem(uint index){return problems.get(index);}
void print();
void printProblemsInfo();
Hashtable<Problem *, long long, uint64_t> timetaken;
int tunernumber;
friend void clearVector(Vector<TunerRecord *> *tunerV);
+ bool isduplicate;
};
class BasicTuner {
* @param newTuner
* @return
*/
- bool subTunerExist(SearchTuner *newTuner);
- bool tunerExists(SearchTuner *tunerRec);
+ int subTunerIndex(SearchTuner *newTuner);
+ bool tunerExists(TunerRecord *tunerRec);
SearchTuner *mutateTuner(SearchTuner *oldTuner, uint k);
void updateTimeout(Problem *problem, long long metric);
Vector<TunerRecord *> allTuners;
Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
for (uint b = 0; b < budget; b++) {
model_print("Round %u of %u\n", b, budget);
- uint tSize = tunerV->getSize();
- for (uint i = 0; i < tSize; i++) {
- SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b);
- TunerRecord *tmp = new TunerRecord(tmpTuner);
- tmp->setTunerNumber(allTuners.getSize());
- model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
- allTuners.push(tmp);
- tunerV->push(tmp);
- }
-
Hashtable<TunerRecord *, int, uint64_t> scores;
- for (uint i = 0; i < problems.getSize(); i++) {
- Problem *problem = problems.get(i);
- Vector<TunerRecord *> places;
- for (uint j = 0; j < tunerV->getSize(); j++) {
- TunerRecord *tuner = tunerV->get(j);
+ Vector<Vector<TunerRecord *> *> allplaces;
+ for(uint ii=0; ii< problems.getSize(); ii++){
+ allplaces.push(new Vector<TunerRecord *>());
+ }
+ for (uint j = 0; j < tunerV->getSize(); j++) {
+ TunerRecord *tuner = tunerV->get(j);
+
+ for (uint i = 0; i < problems.getSize(); i++) {
+ Vector<TunerRecord *> *places = allplaces.get(i);
+ Problem *problem = problems.get(i);
long long metric = tuner->getTime(problem);
if (metric == -1) {
metric = evaluate(problem, tuner);
tuner->setTime(problem, metric);
else
tuner->setTime(problem, -2);
+
+ if(tunerExists(tuner)){
+ //Solving the problem and noticing the tuner
+ //already exists
+ tuner->setDuplicate(true);
+ break;
+ }
}
if (metric >= 0) {
uint k = 0;
- for (; k < places.getSize(); k++) {
- if (metric < places.get(k)->getTime(problem))
+ for (; k < places->getSize(); k++) {
+ if (metric < places->get(k)->getTime(problem))
break;
}
model_print("place[%u]=Tuner<%p,%d>\n", k, tuner, tuner->getTunerNumber());
- places.insertAt(k, tuner);
+ places->insertAt(k, tuner);
}
}
+ }
+ for(uint ii=0; ii < problems.getSize(); ii++){
+ Problem *problem = problems.get(ii);
+ Vector<TunerRecord *> *places = allplaces.get(ii);
int points = 9;
- for (uint k = 0; k < places.getSize() && points; k++) {
- TunerRecord *tuner = places.get(k);
+ for (uint k = 0; k < places->getSize() && points; k++) {
+ TunerRecord *tuner = places->get(k);
+ if(tuner->isDuplicate()){
+ continue;
+ }
int currScore = 0;
if (scores.contains(tuner))
currScore = scores.get(tuner);
points = points / 3;
}
}
+ for(uint ii=0; ii< problems.getSize(); ii++){
+ delete allplaces.get(ii);
+ }
Vector<TunerRecord *> ranking;
for (uint i = 0; i < tunerV->getSize(); i++) {
TunerRecord *tuner = tunerV->get(i);
tunerV->removeAt(j);
}
}
+ uint tSize = tunerV->getSize();
+ for (uint i = 0; i < tSize; i++) {
+ SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b);
+ while(subTunerIndex(tmpTuner) != -1){
+ model_print("******** New Tuner already explored...\n");
+ delete tmpTuner;
+ tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), b);
+ }
+ TunerRecord *tmp = new TunerRecord(tmpTuner);
+ tmp->setTunerNumber(allTuners.getSize());
+ model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
+ allTuners.push(tmp);
+ tunerV->push(tmp);
+ }
}
printData();
}
tuner->setTime(problem, metric);
else
tuner->setTime(problem, -2);
- if(tunerExists(tuner->getTuner())){
+ if(tunerExists(tuner)){
//Solving the problem and noticing the tuner
//already exists
isNew = false;
uint tSize = tuners.getSize();
for (uint i = 0; i < tSize; i++) {
SearchTuner *tmpTuner = mutateTuner(tuners.get(i)->getTuner(), budget);
- while(subTunerExist(tmpTuner)){
+ while(subTunerIndex(tmpTuner) != -1){
tmpTuner->randomMutate();
}
TunerRecord *tmp = new TunerRecord(tmpTuner);
--- /dev/null
+#include "satuner.h"
+#include <float.h>
+#include <math.h>
+#include "searchtuner.h"
+#include <iostream>
+#include <fstream>
+#include "solver_interface.h"
+#include <stdlib.h>
+
+SATuner::SATuner(uint _budget, uint _timeout) :
+ BasicTuner(_budget, _timeout)
+{
+}
+
+SATuner::~SATuner(){
+
+}
+
+void SATuner::rankTunerForProblem(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric){
+ uint k = 0;
+ for (; k < places->getSize(); k++) {
+ if (metric < places->get(k)->getTime(problem))
+ break;
+ }
+ model_print("Problem<%s>:place[%u]=Tuner<%p,%d>\n", problem->getProblem(), k, tuner, tuner->getTunerNumber());
+ places->insertAt(k, tuner);
+}
+
+void SATuner::removeTunerIndex(Vector<TunerRecord *> *tunerV, int index, Vector<Vector<TunerRecord *> *> &allplaces){
+ TunerRecord *tuner = tunerV->get(index);
+ model_print("Removing Tuner %d\n", tuner->getTunerNumber());
+ tunerV->set(index, NULL);
+ for(uint i=0; i < allplaces.getSize(); i++){
+ Vector<TunerRecord *> *places = allplaces.get(i);
+ for(uint j=0; j < places->getSize(); j++){
+ if(tuner == places->get(j)){
+ places->removeAt(j);
+ break;
+ }
+ }
+ }
+
+}
+
+void SATuner::removeNullsFromTunerVector( Vector<TunerRecord *> *tunerV){
+ for (int i= tunerV->getSize() -1; i >= 0; i--){
+ if(tunerV->get(i) == NULL){
+ tunerV->removeAt(i);
+ }
+ }
+ model_print("TunerV size after removing nulls = %u\n", tunerV->getSize());
+}
+
+void SATuner::initialize(Vector<TunerRecord *> *tunerV, Vector<Vector<TunerRecord *> *> &allplaces){
+ for(uint ii=0; ii< problems.getSize(); ii++){
+ allplaces.push(new Vector<TunerRecord *>());
+ }
+ for (uint j = 0; j< tunerV->getSize(); j++){
+ TunerRecord *tuner = tunerV->get(j);
+ for (uint i=0; i < problems.getSize(); i++){
+ Problem *problem = problems.get(i);
+ long long metric = evaluate(problem, tuner);
+ ASSERT(tuner->getTime(problem) == -1);
+ tuner->addProblem(problem);
+ if(metric != -1){
+ tuner->setTime(problem , metric);
+ }else{
+ tuner->setTime(problem , -2);
+ }
+ if(metric >=0){
+ Vector<TunerRecord *> *places = allplaces.get(i);
+ rankTunerForProblem(places, tuner, problem, metric);
+ }
+ }
+ }
+
+}
+
+void SATuner::tune() {
+ Vector<TunerRecord *> *tunerV = new Vector<TunerRecord *>(&tuners);
+ Vector<Vector<TunerRecord *> *> allplaces;
+ uint tunerNumber = tuners.getSize();
+ //Initialization
+ initialize(tunerV, allplaces);
+ //Starting the body of algorithm
+ for (uint t = budget; t >0; t--) {
+ model_print("Current Temperature = %u\n", t);
+ Hashtable<TunerRecord *, int, uint64_t> scores;
+ for (uint i = 0; i < tunerNumber; i++) {
+ SearchTuner *tmpTuner = mutateTuner(tunerV->get(i)->getTuner(), budget-t);
+ int tunerIndex = subTunerIndex(tmpTuner);
+ TunerRecord *tmp = NULL;
+ if(tunerIndex == -1){
+ tmp = new TunerRecord(tmpTuner);
+ tmp->setTunerNumber(allTuners.getSize());
+ model_print("Mutated tuner %u to generate tuner %u\n", tunerV->get(i)->getTunerNumber(), tmp->getTunerNumber());
+ allTuners.push(tmp);
+ }else{
+ //Previous tuners might get explored with new combination of tuners.
+ tmp = explored.get(tunerIndex);
+ model_print("Using exploread tuner <%u>\n", tmp->getTunerNumber());
+ }
+ tunerV->push(tmp);
+ }
+ ASSERT(tunerNumber * 2 == tunerV->getSize());
+ for (uint j = tunerNumber; j < tunerV->getSize(); j++) {
+ TunerRecord *tuner = tunerV->get(j);
+ for (uint i = 0; i < problems.getSize(); i++) {
+ Problem *problem = problems.get(i);
+ long long metric = tuner->getTime(problem);
+ if (metric == -1) {
+ metric = evaluate(problem, tuner);
+ if (tuner->getTime(problem) == -1) {
+ tuner->addProblem(problem);
+ }
+ model_print("%u.Problem<%s>\tTuner<%p, %d>\tMetric<%lld>\n", i, problem->getProblem(),tuner, tuner->getTunerNumber(), metric);
+ model_print("*****************************\n");
+ if (metric != -1)
+ tuner->setTime(problem, metric);
+ else
+ tuner->setTime(problem, -2);
+
+ }
+ if (metric >= 0) {
+ ASSERT(i < allplaces.getSize());
+ Vector<TunerRecord *> *places = allplaces.get(i);
+ model_print("Problem<%s>:place[size=%u]=Tuner<%p,%d>\n", problem->getProblem(), places->getSize(), tuner, tuner->getTunerNumber());
+ rankTunerForProblem(places, tuner, problem, metric);
+ }
+ }
+ }
+ for(uint ii=0; ii < problems.getSize(); ii++){
+ Problem *problem = problems.get(ii);
+ ASSERT(ii < allplaces.getSize());
+ Vector<TunerRecord *> *places = allplaces.get(ii);
+ int points = pow(tunerNumber*1.0, 2*tunerNumber - 1);
+ for (uint k = 0; k < places->getSize() && points; k++) {
+ TunerRecord *tuner = places->get(k);
+ int currScore = 0;
+ if (scores.contains(tuner))
+ currScore = scores.get(tuner);
+ currScore += points;
+ model_print("Problem<%s>\tTuner<%p,%d>\tmetric<%d>\n", problem->getProblem(), tuner, tuner->getTunerNumber(), currScore);
+ model_print("**************************\n");
+ scores.put(tuner, currScore);
+ points = points / tunerNumber;
+ }
+ }
+
+ for(uint i= 0; i < tunerNumber; i++){
+ ASSERT(i < tunerV->getSize());
+ TunerRecord *tuner1 = tunerV->get(i);
+ TunerRecord *tuner2 = tunerV->get(tunerNumber + i);
+ ASSERT( tunerNumber + i < tunerV->getSize());
+ model_print("Tuner1 = %d \tTuner2 = %d\n", tuner1->getTunerNumber(), tuner2->getTunerNumber());
+ ASSERT(scores.contains(tuner1));
+ ASSERT(scores.contains(tuner2));
+ int score1 = scores.get(tuner1);
+ int score2 = scores.get(tuner2);
+ if( score2 > score1 ){
+ removeTunerIndex(tunerV, i, allplaces);
+ } else if( score2 < score1){
+ model_print("score1=%d\tscore2=%d\tt=%u\texp=%f\n", score1, score2, t, exp((score1-score2)*1.0/t));
+ double prob = 1/(exp((score1-score2)*1.0/t) );
+ double random = ((double) rand() / (RAND_MAX));
+ model_print("prob=%f\trandom=%f\n", prob, random);
+ if(prob > random){
+ removeTunerIndex(tunerV, i, allplaces);
+ }else{
+ removeTunerIndex(tunerV, tunerNumber + i, allplaces);
+ }
+ } else{
+ double random = ((double) rand() / (RAND_MAX));
+ int index = random > 0.5? i : tunerNumber + i;
+ removeTunerIndex(tunerV, index, allplaces);
+ }
+ }
+ removeNullsFromTunerVector(tunerV);
+
+ }
+ for(uint ii=0; ii< allplaces.getSize(); ii++){
+ delete allplaces.get(ii);
+ }
+ printData();
+}
--- /dev/null
+#ifndef SATUNER_H
+#define SATUNER_H
+#include "classlist.h"
+#include "structs.h"
+#include "basictuner.h"
+
+/**
+*This tuner has the simulated annealing in its core
+*
+*/
+class SATuner : public BasicTuner {
+public:
+ SATuner(uint budget, uint timeout);
+ virtual ~SATuner();
+ void tune();
+protected:
+ void insertInPlace(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric);
+ void initialize(Vector<TunerRecord *> *tunerV, Vector<Vector<TunerRecord *> *> &allplaces);
+ void rankTunerForProblem(Vector<TunerRecord *> *places, TunerRecord *tuner, Problem *problem, long long metric);
+ void removeTunerIndex(Vector<TunerRecord *> *tunerV, int index, Vector<Vector<TunerRecord *> *> &allplaces);
+ void removeNullsFromTunerVector( Vector<TunerRecord *> *tunerV);
+};
+
+
+#endif
projects / satune.git / commitdiff