00001 #include "../ECF_base.h"
00002 #include "Permutation.h"
00003 #include <map>
00004
00005
00006 namespace Permutation
00007 {
00008
00009 void PermutationCrsUPMX::registerParameters(StateP state)
00010 {
00011 myGenotype_->registerParameter(state, "crx.UPMX", (voidP) new double(0), ECF::DOUBLE);
00012 }
00013
00014
00015 bool PermutationCrsUPMX::initialize(StateP state)
00016 {
00017 voidP sptr = myGenotype_->getParameterValue(state, "crx.UPMX");
00018 probability_ = *((double*)sptr.get());
00019 return true;
00020 }
00021
00022
00023 class IndexBackedPermutation {
00024 private:
00025 int * inverseIndexes;
00026 int * array;
00027 int n;
00028
00029 public:
00030
00031 IndexBackedPermutation(int * arr, int n_) {
00032 array = arr;
00033 n = n_;
00034 inverseIndexes = new int[n];
00035 if(array!=NULL) {
00036 for(int i = 0; i < n; i++) {
00037 inverseIndexes[array[i]] = i;
00038 }
00039 }
00040 }
00041
00042
00043 ~IndexBackedPermutation() {
00044 delete [] inverseIndexes;
00045 }
00046
00047
00048 void setIndexForValue(int value, int index) {
00049 inverseIndexes[value] = index;
00050 }
00051
00052
00053 int getIndexForValue(int value) {
00054 return inverseIndexes[value];
00055 }
00056
00057
00058
00059
00060 void remove(int* size, int pos) {
00061 *size = *size - 1;
00062
00063
00064 int t = array[*size];
00065 array[*size] = array[pos];
00066 array[pos] = t;
00067
00068
00069 t = inverseIndexes[array[pos]];
00070 inverseIndexes[array[pos]] = inverseIndexes[array[*size]];
00071 inverseIndexes[array[*size]] = t;
00072 }
00073
00074
00075
00076 void swap(Permutation *p, int pos1, int pos2) {
00077
00078 int t = p->variables[pos1];
00079 p->variables[pos1] = p->variables[pos2];
00080 p->variables[pos2] = t;
00081
00082
00083 t = inverseIndexes[p->variables[pos1]];
00084 inverseIndexes[p->variables[pos1]] = inverseIndexes[p->variables[pos2]];
00085 inverseIndexes[p->variables[pos2]] = t;
00086 }
00087 };
00088
00089
00090 bool PermutationCrsUPMX::mate(GenotypeP gen1, GenotypeP gen2, GenotypeP child)
00091 {
00092 Permutation* p1 = (Permutation*) (gen1.get());
00093 Permutation* p2 = (Permutation*) (gen2.get());
00094 Permutation* ch = (Permutation*) (child.get());
00095
00096 int capacity = p1->getSize();
00097
00098
00099
00100
00101 int * legalPositions = new int[capacity];
00102 for(int i = 0; i < capacity; i++) {
00103 legalPositions[i] = i;
00104 }
00105
00106
00107
00108 IndexBackedPermutation idxCh(NULL, capacity);
00109 IndexBackedPermutation idxP2(NULL, capacity);
00110 IndexBackedPermutation idxLegal(legalPositions, capacity);
00111
00112
00113
00114 for(int i = 0; i < capacity; i++) {
00115 ch->variables[i] = p1->variables[i];
00116 idxCh.setIndexForValue(p1->variables[i], i);
00117 idxP2.setIndexForValue(p2->variables[i], i);
00118 }
00119
00120
00121 int attempts = capacity / 3;
00122
00123
00124 int legalsCount = capacity;
00125
00126
00127 for(int attempt = 0; attempt < attempts; attempt++) {
00128
00129 int rand = state_->getRandomizer()->getRandomInteger(legalsCount);
00130 int pos1 = legalPositions[rand];
00131 idxLegal.remove(&legalsCount, rand);
00132
00133
00134 int value1 = ch->variables[pos1];
00135 int pos2 = idxP2.getIndexForValue(value1);
00136
00137
00138 idxCh.swap(ch, pos1, pos2);
00139
00140
00141 if(idxLegal.getIndexForValue(pos2) < legalsCount) {
00142 idxLegal.remove(&legalsCount, idxLegal.getIndexForValue(pos2));
00143 }
00144 }
00145
00146 delete [] legalPositions;
00147
00148 return true;
00149 }
00150
00151 }