00001 /****************************************************************************
00002 
00003 $Id: EGTElitistSel.h,v 1.2 2002/12/02 08:01:12 motegi Exp $
00004 Copyright (C) 2002 Higuchi Lab. All rights reserved.
00005 
00006 *****************************************************************************/
00007 #ifndef INCLUDE__ELITISTSEL_H__FILE
00008 #define INCLUDE__ELITISTSEL_H__FILE
00009 
00010 #include "defs.h"
00011 #include "EGException.h"
00012 #include "EGTSelection.h"
00013 #include "EGTVector.h"
00014 
00021 template<class TP>
00022 class EGTElitistSel : public EGTSelection<TP> {
00023 public:
00024   typedef TP                      Pop;
00025   typedef typename Pop::Graph     Graph;
00026   typedef EGTVector<const Graph*> Graphs;
00027   typedef typename Graphs::Iterator GraphsIterator;
00028   typedef typename Graphs::ConstIterator GraphsConstIterator;
00029 
00031   virtual ~EGTElitistSel() { }
00033   virtual void Selection(const Pop& src, Graphs& dest, UInt uCount) { }
00034   virtual void Selection(const Pop& src, Pop& dest, UInt uCount);
00035 
00036 private:
00037   void Sort(Graphs&);
00038   void Unique(Graphs&);
00039 };
00040 
00041 //============================================================================
00048 template<class TP>
00049 void EGTElitistSel<TP>::Selection(const Pop& src, Pop& dest, UInt uCount)
00050 {
00051   // Checks the size of "src".
00052   if (src.GetNumGraphs() < 1) {
00053     throw EGException("EGTElitistSel::Selection(), "
00054                       "Can't fill the population: no individuals.", 
00055                       __FILE__, __LINE__);
00056   }
00057   Graphs temp = src.GetGraphs();
00058   Sort(temp);
00059   Unique(temp);
00060 
00061   const Graph* graph;
00062   Graph* pg;
00063   GraphsConstIterator it = temp.Begin();
00064   GraphsConstIterator itEnd = temp.End();
00065   for (UInt i=0; i<uCount; ++i) {
00066     if (it == itEnd) {
00067       it = temp.Begin();
00068     }
00069     graph = *(it++);
00070     pg = new Graph(*graph);
00071     pg->SetOperator(OP_SELECTION);
00072     pg->SetMother(graph->GetGraphID());
00073     pg->SetOrigin(ORI_SELECTION);
00074     dest.AddGraph(pg);
00075   }
00076 }
00077 
00078 //============================================================================
00083 template<class TP>
00084 void EGTElitistSel<TP>::Sort(Graphs& graphs)
00085 {
00086   // Bubble sort
00087   UInt uMax = graphs.Size();
00088   const Graph* pg;
00089   for (UInt i=0; i<uMax-1; ++i) {
00090     for (UInt j=uMax-1; j>i; --j) {
00091       if (graphs[j-1]->GetFitness() < graphs[j]->GetFitness()) {
00092         pg = graphs[j];
00093         graphs[j] = graphs[j-1];
00094         graphs[j-1] = pg;
00095       }
00096     }
00097   }
00098 }
00099 
00100 //============================================================================
00114 template<class TP>
00115 void EGTElitistSel<TP>::Unique(Graphs& graphs)
00116 {
00117   Graphs newGraphs;
00118   GraphsIterator it2    = graphs.Begin();
00119   GraphsIterator it2End = graphs.End();
00120   GraphsIterator it1    = it2++;
00121   
00122   newGraphs.PushBack(*it1);
00123   for (; it2 != it2End; ++it1, ++it2) {
00124     UInt uFit1 = (UInt)((*it1)->GetFitness() * 1000.0);
00125     UInt uFit2 = (UInt)((*it2)->GetFitness() * 1000.0);
00126     if (uFit1 != uFit2) {
00127       newGraphs.PushBack(*it2);
00128     }
00129   }
00130   graphs = newGraphs;
00131 }
00132 
00133 #endif  //INCLUDE__ROULETTESEL_H__FILE
00134