• Main Page
  • Modules
  • Classes
  • Files
  • File List

D:/Projekt/ECF_trunk/ECF/AlgArtificialBeeColony.cpp

00001 #include "ECF_base.h"
00002 #include "ECF_derived.h"
00003 #include "ECF_macro.h"
00004 #include "AlgArtificialBeeColony.h"
00005 
00006 
00007 ArtificialBeeColony::ArtificialBeeColony()
00008 {
00009     // define algorithm name
00010     name_ = "ArtificialBeeColony";
00011 
00012     // create selection operators needed
00013     // in this case, selRandomOp and selFitOp
00014     selRandomOp = (SelRandomOpP) (new SelRandomOp);
00015     selBestOp = (SelBestOpP) (new SelBestOp);
00016     selWorstOp = (SelWorstOpP) (new SelWorstOp);
00017     selFitOp = (SelFitnessProportionalOpP) (new SelFitnessProportionalOp);
00018 
00019     isTrialAdded_ = false;
00020     elitism_ = true;
00021 }
00022 
00023 
00024 //register any parameters
00025 void ArtificialBeeColony::registerParameters(StateP state)
00026 {
00027     // limit is a maximum number of cycles for each individual  
00028     registerParameter(state, "limit", (voidP) new uint(300), ECF::INT, 
00029         "Maximum number of cycles for each individual (default: 300)");
00030     // elitism: should the current best individual be preserved
00031     registerParameter(state, "elitism", (voidP) new uint(1), ECF::INT, 
00032         "Elitism: the current best food source is preserved (default: 1)");
00033 }
00034 
00035 
00036 bool ArtificialBeeColony::initialize(StateP state)
00037 {
00038     // initialize all operators
00039     selFitOp->initialize(state);
00040     selFitOp->setSelPressure(2);
00041     selBestOp->initialize(state);
00042     selWorstOp->initialize(state);
00043     selRandomOp->initialize(state);
00044 
00045     voidP sptr = state->getRegistry()->getEntry("population.size");
00046     uint size = *((uint*) sptr.get());
00047     probability_.resize(size);
00048 
00049     // this algorithm accepts a single FloatingPoint Genotype
00050     FloatingPointP flp (new FloatingPoint::FloatingPoint);
00051     if(state->getGenotypes()[0]->getName() != flp->getName()) {
00052         ECF_LOG_ERROR(state, "Error: ABC algorithm accepts only a single FloatingPoint genotype!");
00053         throw ("");
00054     }
00055 
00056     voidP limitp = getParameterValue(state, "limit");
00057     limit_ = *((uint*) limitp.get());
00058 
00059     if( (int)limit_ < 0 ) {
00060         ECF_LOG(state, 1, "Error: ABC algorithm requires parameter 'limit' to be a nonnegative value!");
00061         throw "";
00062     }
00063 
00064     voidP elitismp = getParameterValue(state, "elitism");
00065     elitism_ = *((bool*) elitismp.get());
00066 
00067     voidP lBound = state->getGenotypes()[0]->getParameterValue(state, "lbound");
00068     lbound_ = *((double*) lBound.get());
00069     voidP uBound = state->getGenotypes()[0]->getParameterValue(state, "ubound");
00070     ubound_ = *((double*) uBound.get());
00071 
00072     // batch run check
00073     if(isTrialAdded_)
00074         return true;
00075 
00076     FloatingPointP flpoint[2];
00077     for(uint iGen = 1; iGen < 2; iGen++) {
00078 
00079         flpoint[iGen] = (FloatingPointP) new FloatingPoint::FloatingPoint;
00080         state->setGenotype(flpoint[iGen]);
00081 
00082         flpoint[iGen]->setParameterValue(state, "dimension", (voidP) new uint(1));
00083 
00084         // initial value of trial parameter should be (as close as possible to) 0               
00085         flpoint[iGen]->setParameterValue(state, "lbound", (voidP) new double(0));
00086         flpoint[iGen]->setParameterValue(state, "ubound", (voidP) new double(0.01));
00087     }
00088     ECF_LOG(state, 1, "ABC algorithm: added 1 FloatingPoint genotype (trial)");
00089 
00090     // mark adding of trial genotype
00091     isTrialAdded_ = true;
00092 
00093     return true;
00094 }
00095 
00096 
00097 bool ArtificialBeeColony::advanceGeneration(StateP state, DemeP deme)
00098 {
00099 //          In ABC, a colony of artificial bees search for artificial food sources (good solutions for a given problem):
00100 //          The colony of artificial bees contains three groups of bees: employed bees, onlooker bees, and scout bees 
00101 //          - employed bees are associated with specific food sources
00102 //          - onlooker bees watch the dance of employed bees within the hive to choose a food source
00103 //          - scout bees search for food sources randomly
00104 //
00105 //          Initially, a randomly distributed initial population (food sources) is generated
00106 //          REPEAT 
00107 //          1)  Employed Bees Phase
00108 //              1a) for each food source createNewFoodSource() is called            
00109 //
00110 //          2)  Onlooker Bees Phase
00111 //              2a) each onlooker bee chooses a food source depending on their fitness values (better individuals are more likely to be chosen)
00112 //              2b) for each chosen food source createNewFoodSource() is called 
00113 //  
00114 //          3)  Scout Bees Phase
00115 //              ** as a rule, none or one food source gets abandoned per generation
00116 //              3a) for each food source get trial variable
00117 //              3b) remember the source if its trial exceeded limit 
00118 //              3c) if there is a source that exceeded limit, replace it with a random food source
00119 //
00120 //          UNTIL(requirements are met)
00121 //
00122 //          *createNewFoodSource()
00123 //              a)  for each food source find a neighbour (a random food source in the population) 
00124 //              b)  produce a modification on the food source (discover a new food source)
00125 //              c)  evaluate new food source 
00126 //              d)  if the fitness value of the new one is better than that of the original source,
00127 //                  memorize the new source, forget the old one and set trial to 0
00128 //                  otherwise keep the old one and increment trial
00129 
00130 
00131     employedBeesPhase(state, deme);
00132     onlookerBeesPhase(state, deme); 
00133     scoutBeesPhase(state, deme);
00134 
00135     return true;
00136 }
00137 
00138 
00139 bool ArtificialBeeColony::employedBeesPhase(StateP state, DemeP deme)
00140 {
00141     for( uint i = 0; i < deme->getSize(); i++ ) { // for each food source
00142         IndividualP food = deme->at(i);
00143         createNewFoodSource(food, state, deme);
00144     }
00145     return true;
00146 }
00147 
00148 
00149 bool ArtificialBeeColony::onlookerBeesPhase(StateP state, DemeP deme)
00150 {
00151     // choose a food source depending on its fitness value (better individuals are more likely to be chosen)
00152     // calculate selection probabilities, rotate individuals
00153     calculateProbabilities(state, deme);
00154     int demeSize = deme->getSize();
00155     int i = state->getRandomizer()->getRandomInteger(demeSize);
00156     int n = 0;
00157     while( n < demeSize) {
00158         int fact = i++ % demeSize;
00159         IndividualP food = deme->at(fact);
00160         
00161         if (state->getRandomizer()->getRandomDouble() < probability_[fact]){
00162             n++;
00163             createNewFoodSource(food, state, deme);
00164         }           
00165     }
00166 
00167     return true;
00168 }
00169 
00170 
00171 bool ArtificialBeeColony::calculateProbabilities(StateP state, DemeP deme)
00172 {
00173     IndividualP bestFood = selBestOp->select(*deme);
00174     double bestFitness = bestFood->fitness->getValue();
00175     double worstFitness = selWorstOp->select(*deme)->fitness->getValue();
00176     double offset = 0;
00177 
00178     // scale fitness values
00179     if(bestFitness < worstFitness && bestFitness < 0)
00180         offset = 0.1 - bestFitness; // minimization
00181     else if(worstFitness < 0)
00182         offset = 0.1 - worstFitness;    // maximization
00183 
00184     // for each food source
00185     for( uint i = 0; i < deme->getSize(); i++ ) {
00186         IndividualP food = deme->at(i);
00187         double thisFitness = food->fitness->getValue();
00188 
00189         if (bestFitness == thisFitness)
00190             probability_[i] = 1.0;
00191         else if (thisFitness < bestFitness) // maximization problems
00192             probability_[i] = 0.1 + 0.9 * (thisFitness + offset) / (bestFitness + offset);
00193         else                                // minimization problems
00194             probability_[i] = 0.1 + 0.9 * (bestFitness + offset) / (thisFitness + offset);
00195 
00196         // using selFitPropOp method
00197         //probability_[i] = 0.1 + 0.9 * (thisFitness - worstFitness)/(bestFitness - worstFitness);
00198     }
00199     return true;
00200 }
00201 
00202 
00203 
00204 bool ArtificialBeeColony::scoutBeesPhase(StateP state, DemeP deme)
00205 {
00206     IndividualP unimproved;
00207     IndividualP bestFood = selBestOp->select(*deme);
00208 
00209     double maxTrial = 0;
00210     for( uint i = 0; i < deme->getSize(); i++ ) { // for each food source
00211         IndividualP food = deme->at(i);
00212 
00213         if(food == bestFood)
00214             continue;
00215 
00216         // get food source's trial variable
00217         FloatingPointP flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (food->getGenotype(1));
00218         double &trial = flp->realValue[0];
00219 
00220         // remember the source if its trial exceeded limit 
00221         if (trial > limit_ && trial > maxTrial){
00222             unimproved = food;
00223             maxTrial = trial;
00224         }                   
00225     }
00226 
00227     // if there is a  food source that exceeded the limit, replace it with a random one
00228     if (unimproved != NULL){
00229         FloatingPointP flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (unimproved->getGenotype(1));
00230         double &trial = flp->realValue[0];
00231         trial = 0;
00232         flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (unimproved->getGenotype(0));
00233         flp->initialize(state);
00234         evaluate(unimproved);
00235     }
00236 
00237     return true;
00238 }
00239 
00240 
00241 bool ArtificialBeeColony::createNewFoodSource(IndividualP food, StateP state, DemeP deme)
00242 {
00243     // for each food source find a neighbour 
00244     IndividualP neighbour;
00245     do{
00246         neighbour = selRandomOp->select(*deme);
00247     }while(food->index == neighbour->index);
00248 
00249     // potential new food source
00250     IndividualP newFood = copy(food);
00251 
00252     FloatingPointP flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (food->getGenotype(0));
00253     std::vector< double > &foodVars = flp->realValue;
00254     flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (neighbour->getGenotype(0));
00255     std::vector< double > &neighbourVars = flp->realValue;
00256     flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (newFood->getGenotype(0));
00257     std::vector< double > &newFoodVars = flp->realValue;
00258 
00259 
00260     uint param = state->getRandomizer()->getRandomInteger((int)foodVars.size());
00261     double factor = state->getRandomizer()->getRandomDouble();
00262     double value = foodVars[param] * (1 - 2 * factor) * (foodVars[param] - neighbourVars[param]);
00263     if (value > ubound_)
00264         value = ubound_;
00265     else if (value < lbound_)
00266         value = lbound_;
00267 
00268     // produce a modification on the food source (discover a new food source)
00269     newFoodVars[param] = value;
00270     evaluate(newFood);
00271 
00272     flp = boost::static_pointer_cast<FloatingPoint::FloatingPoint> (food->getGenotype(1));
00273     double &foodTrial = flp->realValue[0];
00274 
00275     //  d)  if the fitness value of the new food source is better than that of the original source,
00276     //      memorize the new source, forget the old one and set trial to 0
00277     //      otherwise keep the old one and increment trial
00278     if(newFood->fitness->isBetterThan(food->fitness) )
00279     {
00280         foodVars[param] = value;
00281         evaluate(food);
00282         foodTrial = 0;
00283     }
00284     else {
00285         foodTrial += 1;
00286     }
00287     return true;
00288 }

Generated on Tue Nov 4 2014 13:04:30 for ECF by  doxygen 1.7.1