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