ARB
MP_probe_combi_statistic.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : MP_probe_combi_statistic.cxx //
4 // Purpose : //
5 // //
6 // Institute of Microbiology (Technical University Munich) //
7 // http://www.arb-home.de/ //
8 // //
9 // ============================================================= //
10 
11 #include "MP_probe.hxx"
12 #include "MultiProbe.hxx"
13 
14 probe_combi_statistic::probe_combi_statistic(probe **pc, probe_tabs *ps, double exp, double fit, int life_cnt) {
15  memset((void*)this, 0, sizeof(probe_combi_statistic)); // @@@ potentially dangerous (overwrites vtable pointer!)
16 
17  if (ps) probe_tab = ps;
18  else probe_tab = NULp; // new probe_tabs
19 
20  probe_combi = new probe*[mp_gl_awars.no_of_probes];
21  if (pc) {
22  for (int i=0; i < mp_gl_awars.no_of_probes; i++) {
23  probe_combi[i] = pc[i];
24  }
25  }
26  else {
27  memset(probe_combi, 0, mp_gl_awars.no_of_probes * sizeof(probe*));
28  }
29 
30  expected_children = exp;
31  fitness = fit;
32  life_counter = life_cnt;
33 }
34 
36  delete [] probe_combi;
37  delete probe_tab;
38 }
39 
40 bool probe_combi_statistic::ok_for_next_gen(int &len_roul_wheel) {
41  double exp_child = get_expected_children();
42 
43  if (exp_child >= 1.0 || get_random(1, 100) <= 100 * exp_child) { // Behandlung nach Goldberg S.115 bzw. S.121
44  if (!is_dead()) {
45  return true;
46  }
47  else {
48  len_roul_wheel -= (int) (MULTROULETTEFACTOR * get_expected_children());
49  expected_children = 0.0;
50  }
51  }
52  return false;
53 }
54 
56  life_counter = MAXLIFEFORCOMBI;
57 }
58 
59 void probe_combi_statistic::sort(long feld_laenge) {
60  if (!feld_laenge)
61  return;
62 
63  quicksort(0, feld_laenge-1);
64 }
65 
66 inline void probe_combi_statistic::swap(probe **a, probe **b) {
67  probe *help;
68 
69  help = *a;
70  *a = *b;
71  *b = help;
72 }
73 
74 void probe_combi_statistic::quicksort(long left, long right) {
75  // Randomized Quicksort!!! wegen effizienz fuer den Fall, dass Feld sortiert
76  long i = left,
77  j = right;
78  int x,
79  help,
80  help2;
81 
82  if (j>i) {
83  help = (left + right) / 2;
84 
85  // Randomisierung des Quicksort Anfang
86  // Falls keine Randomisierung erwuenscht, einfach diesen Teil auskommentieren !!!
87  help2 = get_random(left, right);
88  swap(& probe_combi[help2], & probe_combi[help]);
89  // Randomisierung des Quicksort Ende
90 
91  x = probe_combi[help]->probe_index; // Normale Auswahl des Pivotelements
92 
93  do {
94  while (probe_combi[i]->probe_index < x) i++;
95  while (probe_combi[j]->probe_index > x) j--;
96 
97  if (i<=j) {
98  swap (& probe_combi[i], & probe_combi[j]);
99 
100  i++;
101  j--;
102  }
103  } while (i<=j) ;
104 
105  quicksort(left, j);
106  quicksort(i, right);
107  }
108 }
109 
111  bool result = true;
112 
114 
115  if (get_dupl_pos() == -1)
116  return this;
117 
118  if (dup_tree) // d.h. dass feld this nur einmal in der Generation vorkommen darf
119  if (dup_tree->insert(this, result, mp_gl_awars.no_of_probes))
120  return this;
121 
122  return NULp;
123 }
124 
125 
127  printf("Idx:%d alMis:%d ", p->probe_index, p->allowed_mismatches);
128 }
129 
131  for (int i=0; i<mp_gl_awars.no_of_probes; i++)
132  print(probe_combi[i]);
133 
134  printf("Fit:%f Expchil: %f\n", fitness, expected_children);
135  probe_tab->print();
136 }
137 
139  for (int i=0; i<length; i++)
140  print(arr[i]);
141 }
142 
144  double result;
145 
146  if (expected_children - val > 0)
147  result = (double)MULTROULETTEFACTOR * val;
148  else
149  result = (double)MULTROULETTEFACTOR * expected_children;
150 
151  expected_children -= val;
152 
153  if (expected_children < 0)
154  expected_children = 0;
155 
156  return (int)result;
157 }
158 
160  probe_tabs *new_obje = NULp;
161 
162  if (probe_tab)
163  new_obje = probe_tab->duplicate();
164 
165  return new probe_combi_statistic(probe_combi, new_obje, expected_children, fitness, life_counter);
166 }
167 
169  int rand_pool_pos; // Stelle, an der die Sonde im Pool liegt ( von 0 bis laenge-)
170 
171 
172  for (int i=0; i<mp_gl_awars.no_of_probes; i++) {
173  // Jede Posititon der Sondenkombination wird mit einer Wahrscheinlichkeit von 1/MUTATION_WS mutiert.
174  if (get_random(1, MUTATION_WS) == 1) {
175  init_stats(); // Statistik hat sich geaendert.
176  rand_pool_pos = get_random(0, mp_main->get_p_eval()->get_pool_length() - 1);
177  probe_combi[i] = (mp_main->get_p_eval()->get_probe_pool())[rand_pool_pos];
178  }
179  }
180 
181  while (!check_duplicates()) {
182  // Solange wie in der Sondenkombination noch Duplikate vorhanden sind muessen diese entfernt werden.
183  rand_pool_pos = get_random(0, mp_main->get_p_eval()->get_pool_length() - 1);
184  probe_combi[get_dupl_pos()] = (mp_main->get_p_eval()->get_probe_pool())[rand_pool_pos];
185  }
186 
187 
188 }
189 
190 int probe_combi_statistic::get_dupl_pos() {
192 
193  for (int i=0; i<length-1; i++) // auf duplikate in der Sondenkombi. pruefen
194  if (probe_combi[i]->probe_index == probe_combi[i+1]->probe_index)
195  return i;
196 
197  return -1;
198 }
199 
200 
201 void probe_combi_statistic::sigma_truncation(double average_fit, double deviation) {
202  // vor allem dafuer gedacht, dass wenn wenige schlecht und sehr viele gute
203  // vorhanden sind, dann werden die schlechten 'herausskaliert'
204  fitness = (fitness - average_fit) + ((double)SIGMATRUNCATION_CONST * deviation);
205  if (fitness < 0)
206  fitness = 0;
207 }
208 
210  // An bis zu no_of_probes werden Gene zwischen pcombi1 und pcombi2 ausgetauscht.
211 
212  int rand_cross_pos1, // Position an der der Crossover aufgefuehrt wird.
213  rand_cross_pos2,
214  rand_no_of_cross, // Anzahl der Austauschaktionen. (mind. 1)
215  random_interval = mp_gl_awars.no_of_probes - 1;
216  probe_combi_statistic *f1, *f2;
217 
218  rand_no_of_cross = random_interval ? get_random(1, random_interval) : 0;
219 
220  for (int i = 0; i < rand_no_of_cross; i++) { // eigentliche Crossover Schleife
221  rand_cross_pos1 = get_random(0, random_interval);
222  rand_cross_pos2 = get_random(0, random_interval);
223 
224  swap(& probe_combi[rand_cross_pos1], & pcombi2->probe_combi[rand_cross_pos2]);
225  swap(& probe_combi[rand_cross_pos1], & probe_combi[random_interval]); // um keine Listen zu verwenden
226  swap(& pcombi2->probe_combi[rand_cross_pos2], & pcombi2->probe_combi[random_interval]); // wird im Array getauscht
227 
228  random_interval--;
229  }
230 
231  while (true) { // Crossovernachbehandlung, um duplikate in Kombinationen zu vermeiden
232  int change1, change2;
233 
234  f1 = check_duplicates();
235  f2 = pcombi2->check_duplicates();
236 
237  if (f1 && f2) break;
238 
239  if (f1) change1 = get_random(0, mp_gl_awars.no_of_probes - 1); // in f1 kein Duplikat
240  else change1 = get_dupl_pos();
241 
242  if (f2) change2 = get_random(0, mp_gl_awars.no_of_probes - 1); // in f2 kein Duplikat
243  else change2 = pcombi2->get_dupl_pos();
244 
245  swap(&probe_combi[change1], &pcombi2->probe_combi[change2]); // worst case = die Felder sehen genauso aus, wie vor dem Crossover
246  }
247 
248  init_stats();
249  pcombi2->init_stats();
250 }
251 
253  memset(&probe_tab, 0, sizeof(probe_tabs)); // bisherige Statistiken fuer diese Sondenkombination zuruecksetzten
254  life_counter = MAXLIFEFORCOMBI;
255  fitness = 0;
256  expected_children = 0;
257 }
258 
260  int i, result = 0;
261 
262  for (i=0; i<mp_gl_awars.no_of_probes; i++)
263  result += system3_tab[field[i]][i]; // Ergebnis von : (3^i) * field[i];
264 
265  return result;
266 }
267 
268 
269 inline int probe_combi_statistic::modificated_hamming_dist(int one, int two) { // pseudo hamming distanz einer Sondenkombi
270  return hamming_tab[one][two];
271 }
272 
273 double probe_combi_statistic::calc_fitness(int len_of_field) { // fitness-bewertung einer Sondenkombi
274  int i, j, k, mod_ham_dist;
275  long *hammingarray;
276  double tolerated_non_group_hits, ham_dist;
277 
278 
279  Sondentopf *sondentopf = new Sondentopf(mp_main->get_stc()->Bakterienliste,
281 
282  for (i=0; i<len_of_field; i++)
283  sondentopf->put_Sonde((mp_main->get_p_eval()->get_sondenarray())[probe_combi[i]->probe_index],
284  probe_combi[i]->allowed_mismatches,
285  probe_combi[i]->allowed_mismatches + mp_gl_awars.outside_mismatches_difference);
286 
287  probe_tab = sondentopf->fill_Stat_Arrays();
288  delete sondentopf;
289 
290  fitness = 0.0;
291  hammingarray = new long[mp_gl_awars.no_of_probes+1];
292 
293  for (i=0; i< probe_tab->get_len_group_tabs()-1; i++) {
294  memset(hammingarray, 0, sizeof(long) * (mp_gl_awars.no_of_probes + 1));
295  for (j=0; j<probe_tab->get_len_group_tabs(); j++) {
296  mod_ham_dist = modificated_hamming_dist(i, j);
297  hammingarray[mod_ham_dist] += probe_tab->get_non_group_tab(j);
298  }
299 
300  tolerated_non_group_hits = (double) mp_gl_awars.qualityborder_best;
301 
302  for (k=0; k < mp_gl_awars.no_of_probes + 1 && tolerated_non_group_hits >= 0.0; k++) {
303  for (j=0; j<FITNESSSCALEFACTOR && tolerated_non_group_hits >= 0.0; j++) {
304  tolerated_non_group_hits -= (double) ((double)hammingarray[k] / (double)FITNESSSCALEFACTOR);
305  }
306 
307  }
308 
309  if (tolerated_non_group_hits<0.0) {
310  if (j) ham_dist = (double)k - 1.0 + ((double)(((double)j - 1.0)/(double)FITNESSSCALEFACTOR));
311  else ham_dist = (double)k - 1.0;
312  }
313  else if (tolerated_non_group_hits > 0.0) ham_dist = (double) mp_gl_awars.no_of_probes;
314  else ham_dist = 0.0;
315 
316  fitness += ham_dist * ((double) probe_tab->get_group_tab(i));
317  }
318 
319  delete [] hammingarray;
320  return fitness;
321 }
322 
323 double probe_combi_statistic::calc_expected_children(double average_fitness) {
324  expected_children = fitness / average_fitness;
325  return expected_children;
326 }
327 
328 
string result
void sigma_truncation(double average_fit, double dev)
int get_pool_length()
Definition: MP_probe.hxx:173
unsigned char ** hamming_tab
Definition: MP_noclass.cxx:32
int probe_index
Definition: MP_probe.hxx:16
static void help()
double calc_fitness(int len_of_field)
probe ** get_probe_pool()
Definition: MP_probe.hxx:174
ProbeValuation * get_p_eval()
Definition: MultiProbe.hxx:146
MP_Main * mp_main
Definition: MP_main.cxx:24
int allowed_mismatches
Definition: MP_probe.hxx:17
bool ok_for_next_gen(int &len_roul_wheel)
void swap(probe **a, probe **b)
MO_Liste * Auswahlliste
Definition: MultiProbe.hxx:285
probe_combi_statistic(probe **pc=NULp, probe_tabs *ps=NULp, double exp=0, double fit=0, int lifec=MAXLIFEFORCOMBI)
probe_tabs * fill_Stat_Arrays()
double calc_expected_children(double average_fitness)
bool insert(probe_combi_statistic *sondenkombi, bool &result, int depth=0)
probe_tabs * duplicate()
int get_group_tab(int j)
Definition: MP_probe.hxx:34
char ** get_sondenarray()
Definition: MP_probe.hxx:176
void put_Sonde(char *name, int allowed_mis, double outside_mis)
void sort(long feld_laenge)
probe_combi_statistic * check_duplicates(GenerationDuplicates *dup_tree=NULp)
int get_non_group_tab(int j)
Definition: MP_probe.hxx:33
float outside_mismatches_difference
Definition: MultiProbe.hxx:92
void crossover_Probes(probe_combi_statistic *pcombi2)
#define FITNESSSCALEFACTOR
Definition: MultiProbe.hxx:67
double get_expected_children()
Definition: MP_probe.hxx:67
#define MUTATION_WS
Definition: MultiProbe.hxx:74
#define MAXLIFEFORCOMBI
Definition: MP_probe.hxx:8
int ** system3_tab
Definition: MP_noclass.cxx:29
MO_Liste * Bakterienliste
Definition: MultiProbe.hxx:284
#define MULTROULETTEFACTOR
Definition: MultiProbe.hxx:70
#define NULp
Definition: cxxforward.h:97
long no_of_probes
Definition: MultiProbe.hxx:96
probe_combi_statistic * duplicate()
int get_random(int min, int max)
Definition: MP_noclass.cxx:44
#define SIGMATRUNCATION_CONST
Definition: MultiProbe.hxx:75
awar_vars mp_gl_awars
Definition: MP_main.cxx:23
size_t length
int get_len_group_tabs()
Definition: MP_probe.hxx:35
ST_Container * get_stc()
Definition: MultiProbe.hxx:147
long qualityborder_best
Definition: MultiProbe.hxx:100