00001
00002
00003
00004
00005
00006 #ifndef eoOrderXover_h
00007 #define eoOrderXover_h
00008
00009
00010
00011 #include <algorithm>
00012 #include <utils/eoRNG.h>
00013 #include <eoInit.h>
00014
00024 template<class Chrom> class eoOrderXover: public eoQuadOp<Chrom>
00025 {
00026 public:
00028 virtual std::string className() const { return "eoOrderXover"; }
00029
00035 bool operator()(Chrom& _chrom1, Chrom& _chrom2){
00036
00037 char direction=eo::rng.flip()? 1 : -1;
00038 unsigned cut2= 1 + eo::rng.random(_chrom1.size());
00039 unsigned cut1= eo::rng.random(cut2);
00040 Chrom tmp1= _chrom1;
00041 Chrom tmp2= _chrom2;
00042
00043 cross(tmp1, tmp2, _chrom1, direction, cut1, cut2);
00044 cross(tmp2, tmp1, _chrom2, direction, cut1, cut2);
00045
00046 _chrom1.invalidate();
00047 _chrom2.invalidate();
00048
00049 return true;
00050 }
00051
00052 private:
00053
00060 void cross(Chrom& _chrom1, Chrom& _chrom2, Chrom& _child, char _direction, unsigned _cut1, unsigned _cut2){
00061
00062 unsigned size, id=0, from=0;
00063 size= _chrom1.size();
00064
00065 std::vector<bool> verif(size, false);
00066
00067 for(unsigned i= _cut1; i<_cut2; i++){
00068 _child[id++]= _chrom1[i];
00069 verif[_chrom1[i] % size] = true;
00070 }
00071
00072 while(_chrom2[from] != _child[_cut2 - 1])
00073 from++;
00074
00075 for(unsigned i=0; i<size; i++){
00076 unsigned j= (_direction*i + from + size) % size;
00077 if(!verif[_chrom2[j] % size]){
00078 _child[id++]=_chrom2[j];
00079 verif[_chrom2[j]%size]=true;
00080 }
00081 }
00082 }
00083
00084 };
00085
00086 #endif