- Main Page
- Classes
- Files

- File List

# OptFrame/Heuristic/TabuSearch.hpp

    00001 #ifndef OPTFRAME_TABUSEARCH_HPP_
    00002 #define OPTFRAME_TABUSEARCH_HPP_
    00003
    00004 #include "../Heuristic.hpp"
    00005 #include "../NSEnum.hpp"
    00006 #include "../Evaluator.hpp"
    00007
    00008 template<class R, class M = OPTFRAME_DEFAULT_MEMORY>
    00009 class TabuSearch: public Heuristic<R, M>
    00010 {
    00011 private:
    00012         NSSeq<R, M>& nsSeq;
    00013         Evaluator<R, M>& evaluator;
    00014         int tlSize;
    00015         int tsMax;
    00016
    00017 public:
    00018
    00019         using Heuristic<R, M>::exec; // prevents name hiding
    00020
    00021         TabuSearch(Evaluator<R, M>& _ev, NSSeq<R, M>& _nsSeq, int _tlSize, int _tsMax) :
    00022                 evaluator(_ev), nsSeq(_nsSeq), tlSize(_tlSize), tsMax(_tsMax)
    00023         {
    00024         }
    00025
    00026         virtual void exec(Solution<R>& s, double timelimit, double target_f)
    00027         {
    00028                 Evaluation<M>& e = evaluator.evaluate(s.getR());
    00029                 exec(s, e, timelimit, target_f);
    00030                 delete &e;
    00031         }
    00032
    00033         virtual void exec(Solution<R>& s, Evaluation<M>& e, double timelimit, double target_f)
    00034         {
    00035                 //cout << "TabuSearch exec(" << target_f << "," << timelimit << ")" << endl;
    00036
    00037                 long tini = time(NULL);
    00038
    00039                 Solution<R>* sStar = &s.clone();
    00040                 Evaluation<M>* evalSStar = &evaluator.evaluate(*sStar);
    00041
    00042                 //evalSStar->print();
    00043
    00044                 int Iter = 0;
    00045
    00046                 int BestIter = 0;
    00047
    00048                 const vector<Move<R, M>*> emptyList;
    00049                 vector<Move<R, M>*> tabuList;
    00050
    00051                 long tnow = time(NULL);
    00052
    00053                 int estimative_BTmax = 0;
    00054
    00055                 while (Iter - BestIter <= tsMax && ((tnow - tini) < timelimit))
    00056                 {
    00057                         Iter = Iter + 1;
    00058
    00059                         if ((Iter - BestIter) > estimative_BTmax)
    00060                                 estimative_BTmax = (Iter - BestIter);
    00061
    00062                         //cout << "Iter " << Iter << " (" << (Iter - BestIter - 1) << " without improvement)" << endl;
    00063
    00064                         // ==================
    00065                         // First: aspiration
    00066                         // ==================
    00067
    00068                         Move<R, M>* bestMove = tabuBestMove(s, e, emptyList);
    00069
    00070                         Solution<R>* s1 = &s.clone();
    00071
    00072                         Move<R, M>* newTabu = &bestMove->apply(*s1);
    00073                         Evaluation<M>* evalS1 = &evaluator.evaluate(*s1);
    00074
    00075                         if (evaluator.betterThan(*evalS1, *evalSStar))
    00076                         {
    00077                                 // Better than global!
    00078
    00079                                 for (unsigned int i = 0; i < tabuList.size(); i++)
    00080                                         if ((*tabuList[i]) == (*bestMove))
    00081                                         {
    00082                                                 delete tabuList[i];
    00083                                                 tabuList.erase(tabuList.begin() + i);
    00084                                                 break;
    00085                                         }
    00086                         }
    00087                         else
    00088                         {
    00089                                 delete s1;
    00090                                 delete evalS1;
    00091                                 delete newTabu;
    00092                                 delete bestMove;
    00093
    00094                                 bestMove = tabuBestMove(s, e, tabuList);
    00095                                 s1 = &s.clone();
    00096                                 newTabu = &bestMove->apply(*s1);
    00097                                 evalS1 = &evaluator.evaluate(*s1);
    00098
    00099                                 delete bestMove;
    00100                         }
    00101
    00102                         // =====================================================
    00103                         //    |T| <= tsSize
    00104                         // =====================================================
    00105
    00106                         tabuList.push_back(newTabu);
    00107
    00108                         if (tabuList.size() > tlSize)
    00109                         {
    00110                                 delete tabuList[0];
    00111                                 tabuList.erase(tabuList.begin());
    00112                         }
    00113
    00114                         //-----------------------------------------------------------
    00115                         if (tabuList.size() > tlSize)
    00116                                 throw string("ERROR on Tabu Search! more elements than expected...");
    00117                         //-----------------------------------------------------------
    00118
    00119
    00120                         // =====================================================
    00121                         //        's' <- 's1';
    00122                         // =====================================================
    00123                         s = *s1;
    00124                         e = *evalS1;
    00125
    00126                         delete s1;
    00127                         delete evalS1;
    00128
    00129                         // =====================================================
    00130                         //        's' better than 's*' (?)
    00131                         // =====================================================
    00132
    00133                         if (evaluator.betterThan(e, *evalSStar))
    00134                         {
    00135                                 delete sStar;
    00136                                 delete evalSStar;
    00137
    00138                                 sStar = &s.clone();
    00139                                 evalSStar = &evaluator.evaluate(*sStar);
    00140
    00141                                 BestIter = Iter;
    00142
    00143                                 //cout << "Improvement on " << BestIter << ": fo=" << evalSStar->evaluation() << endl;
    00144                         }
    00145
    00146                         tnow = time(NULL);
    00147                 }
    00148
    00149                 while (tabuList.size() > 0)
    00150                 {
    00151                         delete tabuList[0];
    00152                         tabuList.erase(tabuList.begin());
    00153                 }
    00154
    00155                 // ===========
    00156                 // 's' <- 's*'
    00157                 // ===========
    00158
    00159                 s = *sStar;
    00160                 e = *evalSStar;
    00161
    00162                 delete sStar;
    00163                 delete evalSStar;
    00164
    00165                 FILE* ftabu = fopen("tabu.txt", "a");
    00166                 if (!ftabu)
    00167                 {
    00168                         cout << "Error creating file 'tabu.txt'" << endl;
    00169                         return;
    00170                 }
    00171
    00172                 fprintf(ftabu, "%d\n", estimative_BTmax);
    00173                 fclose(ftabu);
    00174         }
    00175
    00176         Move<R, M>* tabuBestMove(Solution<R>& s, Evaluation<M>& e, const vector<Move<R, M>*>& tabuList)
    00177         {
    00178                 NSIterator<R, M>& it = nsSeq.getIterator(e.getM(), s.getR());
    00179
    00180                 it.first();
    00181
    00182                 if (it.isDone())
    00183                 {
    00184                         delete &it;
    00185                         return NULL;
    00186                 }
    00187
    00188                 Move<R, M>* bestMove = &it.current();
    00189
    00190                 while (!bestMove->canBeApplied(s) || inList(bestMove, tabuList))
    00191                 {
    00192                         delete bestMove;
    00193                         it.next();
    00194
    00195                         if (!it.isDone())
    00196                         {
    00197                                 bestMove = &it.current();
    00198                         }
    00199                         else
    00200                         {
    00201                                 delete &it;
    00202                                 return NULL;
    00203                         }
    00204                 }
    00205
    00206                 double bestCost = evaluator.moveCost(e, *bestMove, s);
    00207                 it.next();
    00208                 while (!it.isDone())
    00209                 {
    00210                         Move<R, M>* move = &it.current();
    00211                         if (move->canBeApplied(s) && !inList(bestMove, tabuList))
    00212                         {
    00213                                 double cost = evaluator.moveCost(e, *move, s);
    00214
    00215                                 if (evaluator.betterThan(cost, bestCost))
    00216                                 {
    00217                                         delete bestMove;
    00218                                         bestMove = move;
    00219                                         bestCost = cost;
    00220                                 }
    00221                                 else
    00222                                         delete move;
    00223                         }
    00224                         else
    00225                                 delete move;
    00226                         it.next();
    00227                 }
    00228
    00229                 delete &it;
    00230
    00231                 return bestMove;
    00232         }
    00233
    00234         bool inList(Move<R, M>* m, const vector<Move<R, M>*>& v)
    00235         {
    00236                 for (unsigned int i = 0; i < v.size(); i++)
    00237                         if ((*m) == (*v[i]))
    00238                                 return true;
    00239                 return false;
    00240         }
    00241
    00242 };
    00243
    00244 #endif /*OPTFRAME_TABUSEARCH_HPP_*/

All Classes Functions