00001 #ifndef Algorithm_h
00002 #define Algorithm_h
00003
00004 #include "State.h"
00005 #include "SelectionOperator.h"
00006 #include "Crossover.h"
00007 #include "Mutation.h"
00008 #include "EvaluateOp.h"
00009 #include<vector>
00010
00019 class Algorithm
00020 {
00021 protected:
00022 DemeP activeDeme_;
00023 std::string name_;
00024 bool bImplicitParallel_;
00025 std::vector<SelectionOperatorP> selectionOp;
00026
00035 bool registerParameter(StateP state, std::string name, voidP value, enum ECF::type T, std::string description = "")
00036 {
00037 return state->getRegistry()->registerEntry(name_ + "." + name, value, T, description);
00038 }
00039
00046 voidP getParameterValue(StateP state, std::string name)
00047 {
00048 return state->getRegistry()->getEntry(name_ + "." + name);
00049 }
00050
00051 #ifdef _MPI
00052 std::vector<IndividualP> requests_, stored_;
00053 std::vector<uint> requestIds_;
00054 std::vector<IndividualP> demeCopy_;
00055 std::vector<IndividualP> myJob_;
00056 CommunicatorP comm_;
00057 uint jobSize_;
00058 uint totalEvaluations_, wastedEvaluations_;
00059 bool bImplicitEvaluation_;
00060 bool bImplicitMutation_;
00061 bool bSynchronized_;
00062 SelectionOperatorP selBestOp;
00063 std::vector<IndividualP> requestsMut_, receivedMut_;
00064 std::vector<uint> requestMutIds_;
00065 IndividualP currentBest_;
00066
00067 std::vector<IndividualP> storedInds_;
00068 std::vector< std::vector<IndividualP> > sentInds_;
00069 std::vector<bool> isConsistent_;
00070
00071 void storeIndividual(IndividualP);
00072 void storeGenotypes(std::vector<IndividualP>&);
00073 void setConsistency(IndividualP);
00074 void restoreIndividuals(std::vector<uint>);
00075 void restorePopulation();
00076 #endif
00077
00078
00079 public:
00080 CrossoverP crossover_;
00081 MutationP mutation_;
00082 EvaluateOpP evalOp_;
00083 StateP state_;
00084
00085 Algorithm()
00086 { bImplicitParallel_ = false; }
00087
00088 virtual ~Algorithm()
00089 { }
00090
00092 std::string getName()
00093 { return name_; }
00094
00096 virtual bool isParallel()
00097 { return false; }
00098
00100 bool isImplicitParallel()
00101 { return bImplicitParallel_; }
00102
00108 virtual bool advanceGeneration(StateP, DemeP) = 0;
00109
00115 virtual bool initialize(StateP)
00116 { return true; }
00117
00123 virtual void registerParameters(StateP) {}
00124
00128 virtual bool initializePopulation(StateP);
00129
00130 virtual void read() {}
00131
00132 #ifndef _MPI
00133
00139 virtual bool advanceGeneration(StateP state)
00140 {
00141 ECF_LOG(state, 4, name_ + ": starting generation");
00142
00143 bool bResult = true;
00144 for(uint iDeme = 0; iDeme < state->getPopulation()->size(); iDeme++) {
00145 activeDeme_ = state->getPopulation()->at(iDeme);
00146 bResult |= advanceGeneration(state, state->getPopulation()->at(iDeme));
00147 }
00148
00149 ECF_LOG(state, 4, name_ + ": ending generation");
00150
00151 return bResult;
00152 }
00153
00157 void evaluate(IndividualP ind)
00158 {
00159 state_->getContext()->evaluatedIndividual = ind;
00160 ECF_LOG(state_, 5, "Evaluating individual: " + ind->toString());
00161 ind->fitness = evalOp_->evaluate(ind);
00162 ECF_LOG(state_, 5, "New fitness: " + ind->fitness->toString());
00163 state_->increaseEvaluations();
00164 }
00165
00169 uint mutate(const std::vector<IndividualP>& pool)
00170 { return mutation_->mutation(pool); }
00171
00175 uint mutate(const IndividualP victim)
00176 {
00177 std::vector<IndividualP> pool;
00178 pool.push_back(victim);
00179 return mutation_->mutation(pool);
00180 }
00181
00187 void replaceWith(IndividualP oldInd, IndividualP newInd)
00188 { activeDeme_->replace(oldInd->index, newInd); }
00189
00191 void registerParallelParameters(StateP state)
00192 { }
00193
00195 bool initializeParallel(StateP state)
00196 { return true; }
00197
00198 #else // implicit parallel version
00199
00201 virtual bool advanceGeneration(StateP state);
00202
00204 virtual void bcastTermination(StateP state);
00205
00207 void registerParallelParameters(StateP state);
00208
00210 bool initializeParallel(StateP state);
00211
00213 void initializeImplicit(StateP state);
00214
00216 bool implicitParallelOperate(StateP state);
00217
00219 void evaluate(IndividualP ind)
00220 {
00221
00222 if(bImplicitEvaluation_)
00223 implicitEvaluate(ind);
00224
00225 else if(bImplicitMutation_ && ind->fitness->isValid())
00226 return;
00227
00228 state_->getContext()->evaluatedIndividual = ind;
00229 ECF_LOG(state_, 5, "Evaluating individual: " + ind->toString());
00230 ind->fitness = evalOp_->evaluate(ind);
00231 ECF_LOG(state_, 5, "New fitness: " + ind->fitness->toString());
00232 state_->increaseEvaluations();
00233 }
00234
00236 void implicitEvaluate(IndividualP ind);
00237
00239 uint mutate(const IndividualP victim)
00240 {
00241 std::vector<IndividualP> pool;
00242 pool.push_back(victim);
00243 return mutate(pool);
00244 }
00245
00247 uint mutate(const std::vector<IndividualP>& pool)
00248 {
00249 if(bImplicitMutation_) {
00250 uint nMutations = 0;
00251 for(uint i = 0; i < pool.size(); i++) {
00252 nMutations += implicitMutate(pool[i]);
00253 }
00254 return nMutations;
00255 }
00256 else
00257 return mutation_->mutation(pool);
00258 }
00259
00261 uint implicitMutate(IndividualP ind);
00262
00264 void replaceWith(IndividualP oldInd, IndividualP newInd);
00265
00266 #endif
00267
00268
00269
00273 bool mate(IndividualP p1, IndividualP p2, IndividualP child)
00274 { return crossover_->mate(p1, p2, child); }
00275
00279 IndividualP copy(IndividualP source)
00280 { return (IndividualP) source->copy(); }
00281
00285 bool removeFrom(IndividualP victim, std::vector<IndividualP> &pool)
00286 {
00287 uint iWorst = 0;
00288 while(iWorst < pool.size() && pool[iWorst] != victim)
00289 iWorst++;
00290 if(iWorst == pool.size())
00291 return false;
00292 pool.erase(pool.begin() + iWorst);
00293 return true;
00294 }
00295
00299 bool isMember(IndividualP single, std::vector<IndividualP> &pool)
00300 {
00301 uint index = 0;
00302 while(index < pool.size() && pool[index] != single)
00303 index++;
00304 if(index == pool.size())
00305 return false;
00306 return true;
00307 }
00308 };
00309 typedef boost::shared_ptr<Algorithm> AlgorithmP;
00310
00311 #endif // Algorithm_h
00312