diff options
Diffstat (limited to 'experimental/bidirectional/src/mkcls/MSBOptimization.cpp')
| -rw-r--r-- | experimental/bidirectional/src/mkcls/MSBOptimization.cpp | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/experimental/bidirectional/src/mkcls/MSBOptimization.cpp b/experimental/bidirectional/src/mkcls/MSBOptimization.cpp new file mode 100644 index 0000000..9478826 --- /dev/null +++ b/experimental/bidirectional/src/mkcls/MSBOptimization.cpp @@ -0,0 +1,229 @@ +/* + +Copyright (C) 1997,1998,1999,2000,2001 Franz Josef Och + +mkcls - a program for making word classes . + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, +USA. + +*/ + + + + +#include "MSBOptimization.h" +#include <stdlib.h> +#include "ProblemTest.h" + +#ifdef __GNUC__ +template class Array<double>; +template class Array<ProbAndOpt>; +#endif + +struct doubleInt { double a; int i; }; +static int doubleintcompare(const void *p,const void *j) +{ + if(((struct doubleInt *)p)->a < ((doubleInt *)j)->a) + return -1; + else if(((struct doubleInt *)p)->a == ((doubleInt *)j)->a) + return 0; + else + return 1; +} + + +MSBOptimization::MSBOptimization(Problem &p,int verf,int anz,Array<double> &pos,Array<double> &por) +: PopOptimization(p,verf,anz), +percentOfSteps(pos),percentOfRun(por),nachMinimierung(0) +{ +} + + +void MSBOptimization::zInitialize() +{ + PopOptimization::zInitialize(); + + int iterationsschritte; + double mean; + StatVar end,laufzeit,start; + zufallSeed(); + + + + + solveProblem(ProblemTestVerboseMode,*originalProblem,2,-1,verfahren,mean, + end,laufzeit,start,0,&iterationsschritte); + expectedSteps=(int)(iterationsschritte); + + if(verboseMode) + cout << "MSB:mean number of steps for one run: " << expectedSteps << endl; +} + + +double MSBOptimization::minimize(int) +{ + if( initialisiert==0 ) + zInitialize(); + + int i; + int anz=size(); + int numproblems=anz; + + if( verboseMode ) + { + double usedSteps=0; + for(i=0;i<percentOfSteps.size();i++) + { + usedSteps+=expectedSteps*(percentOfSteps[i]- + (i==0?0:percentOfSteps[i-1]))*numproblems; + numproblems=(int)(ceil(anz*(1.0-percentOfRun[i]))); + if( numproblems<1 )numproblems=1; + } + usedSteps+=expectedSteps* + (1.0-percentOfSteps[percentOfSteps.size()-1])*numproblems; + cout << "MSB: speed factor: " + << (double)usedSteps/(expectedSteps*size()) << endl; + numproblems=anz=size(); + } + + for(i=0;i<percentOfSteps.size();i++) + { + + int steps=(int)(expectedSteps*(percentOfSteps[i]- + (i==0?0:percentOfSteps[i-1]))); + + + for(int a=0;a<numproblems;a++) + { + + double v; + v= optimization(a)->minimize(steps); + if(verboseMode)cout << "MSB:" << i << " " << a << ":" << v << endl; + } + + sort(); + + if(verboseMode) + cout << "MSB: best:" << problem(0)->value() + << " worst:" << problem(numproblems-1)->value() << endl; + + + numproblems=(int)(anz*(1.0-percentOfRun[i])); + if( numproblems<1 ) + numproblems=1; + if(verboseMode) + cout << "MSB: now i have : " << numproblems << " Problem's." << endl; + if(numproblems==1) + break; + } + assert( numproblems>0 ); + + + for(int a=0;a<numproblems;a++) + optimization(a)->minimize(-1); + sort(); + + double ergebnisWert = problem(0)->value(); + cout << "MSB: value:" << ergebnisWert << " (nicevalue:" + << problem(0)->nicevalue() << ")\n"; + nachMinimierung=1; + return ergebnisWert; +} + + + +void MSBOptimization::optimizeValues(Problem &p,int verfahren) +{ + int i; + struct doubleInt ri[20]; + double mean; + StatVar end,laufzeit,start; + solveProblem(ProblemTestVerboseMode,p,5,-1,verfahren,mean,end,laufzeit,start); + double fivePercentSteps=(int)(laufzeit.getMean()/20.0); + double qualitaet[20][20]; + for(i=0;i<20;i++) + { + Optimization *o=(Optimization *)genIterOptimizer(verfahren,p,-1); + for(int a=0;a<20;a++) + { + qualitaet[i][a]=o->minimize((int)fivePercentSteps); + cout << qualitaet[i][a] << " "; + } + ri[i].a=o->minimize(-1); + ri[i].i=i; + cout << ri[i].a << endl; + delete o; + } + qsort(ri,20,sizeof(struct doubleInt),doubleintcompare); + + cout << "#Beschneidungsmatrix, welche die drei besten Laeufe erhaelt: "; + for(i=0;i<20;i++) + { + int a; + struct doubleInt v[20]; + for(a=0;a<20;a++) + { v[a].i=a;v[a].a=qualitaet[a][i];} + qsort(v,20,sizeof(struct doubleInt),doubleintcompare); + int nr=0; + for(a=0;a<20;a++) + if( v[a].i==ri[0].i || v[a].i==ri[1].i || v[a].i==ri[2].i ) + nr=a; + float percent=(1.0-nr/20.0)*100.0; + if(nr==2) + percent=100.0; + cout << "# " << i << " " << (i/20.0)*100 << "% " << percent << "%\n"; + } + cout << "#Beschneidungsmatrix, welche die zwei besten Laeufe erhaelt: "; + for(i=0;i<20;i++) + { + int a; + struct doubleInt v[20]; + for(a=0;a<20;a++) + { v[a].i=a;v[a].a=qualitaet[a][i];} + qsort(v,20,sizeof(struct doubleInt),doubleintcompare); + int nr=0; + for(a=0;a<20;a++) + if( v[a].i==ri[0].i || v[a].i==ri[1].i ) + nr=a; + float percent=(1.0-nr/20.0)*100.0; + if(nr==1) + percent=100.0; + cout << "# " << i << " " << (i/20.0)*100 << "% " << percent << "%\n"; + } + cout << "#Beschneidungsmatrix, welche den besten Lauf erhaelt: "; + for(i=0;i<20;i++) + {int a; + struct doubleInt v[20]; + for(a=0;a<20;a++) + { v[a].i=a;v[a].a=qualitaet[a][i];} + qsort(v,20,sizeof(struct doubleInt),doubleintcompare); + int nr=0; + for(a=0;a<20;a++) + if( v[a].i==ri[0].i ) + nr=a; + float percent=(1.0-nr/20.0)*100.0; + if(nr==0) + percent=100.0; + cout << "# " << i << " " << (i/20.0)*100 << "% " << percent << "%\n"; + } +} + + +Problem& MSBOptimization::bestProblem() +{ + assert(nachMinimierung==1); + return *(problem(0)); +} |