ARB
MP_Generation.cxx
Go to the documentation of this file.
1 // ============================================================= //
2 // //
3 // File : MP_Generation.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 "MP_externs.hxx"
13 #include "MultiProbe.hxx"
14 #include <arb_progress.h>
15 
17  bool result = true;
18 
19  if (!dup_tree)
20  return NULp;
21 
22  dup_tree->insert(field, result); // dup_tree muss fuer jede Generation neu erstellt werden !!!!
23  // dieser Aufruf wird nur zur Vermeidung von doppelten
24  // Sondenkombis benoetigt
25  if (result) // wenn result, dann in generation einmalig
26  return field;
27 
28  return NULp; // field ist ein Duplikat
29 }
30 
32  for (int i=0; i<probe_combi_array_length; i++)
33  probe_combi_stat_array[i]->print();
34 }
35 
37  for (int i=0; i<probe_combi_array_length; i++) {
38  if (probe_combi_stat_array[i]) {
39  mp_main->get_p_eval()->insert_in_result_list(probe_combi_stat_array[i]);
40  }
41  }
42 }
43 
44 bool Generation::calcFitness(bool use_genetic_algo, double old_avg_fit) {
45  // returns true if aborted
46  //
47  // (roulette_wheel wird am Ende neu initialisiert)
48 
49  arb_progress progress(static_cast<long>(probe_combi_array_length));
50  double fitness = 0;
51 
52  for (int i=0; i<probe_combi_array_length; i++) {
53  double dummy = probe_combi_stat_array[i]->calc_fitness(mp_gl_awars.no_of_probes);
54  fitness += dummy;
55 
56  if (i==0)
57  min_fit = max_fit = dummy;
58 
59  if (dummy < min_fit)
60  min_fit = dummy;
61  else if (dummy > max_fit)
62  max_fit = dummy;
63 
64  if (MP_aborted(generation_counter, old_avg_fit, min_fit, max_fit, progress)) {
65  probe_combi_array_length = i-1;
66  return true;
67  }
68  progress.inc();
69  }
70 
71  if (use_genetic_algo) {
72  average_fitness = fitness / (double)probe_combi_array_length;
73 
74  deviation = 0;
75 
76 
77 #ifdef USE_LINEARSCALING
78  double dev = 0;
79  double a = 0,
80  b = 0;
81 #ifdef USE_SIGMATRUNCATION
82  for (i=0; i<probe_combi_array_length; i++) { // Berechnung der Abweichung nach Goldberg S.124
83  dev = probe_combi_stat_array[i]->get_fitness() - average_fitness;
84  dev = dev * dev;
85  deviation += dev;
86  }
87  deviation = (1.0 / (double)((double)i - 1.0)) * deviation;
88  deviation = sqrt(deviation);
89 
90  for (i=0; i<probe_combi_array_length; i++) // sigma_truncation nur auf schlechte Kombis anwenden ???
91  probe_combi_stat_array[i]->sigma_truncation(average_fitness, deviation);
92 #endif
93  // lineare Skalierung auf fitness anwenden !!!
94  // Skalierung erfolgt nach der Formel fitness'= a*fitness + b
95 
96  prescale(&a, &b); // Koeffizienten a und b berechnen
97 #endif
98 
99  for (int i=0; i<probe_combi_array_length; i++) {
100 #ifdef USE_LINEARSCALING
101  probe_combi_stat_array[i]->scale(a, b);
102 #endif
103  probe_combi_stat_array[i]->calc_expected_children(average_fitness);
104  }
105 
107  }
108  return false;
109 }
110 
111 void Generation::prescale(double *a, double *b) { // berechnet Koeffizienten fuer lineare Skalierung
112  double delta = 0;
113 
114  if ((min_fit > C_MULT * average_fitness - max_fit) / (C_MULT - 1.0)) { // nach Goldberg S.79
115  delta = max_fit - average_fitness; // Normale Skalierung
116  *a = (C_MULT - 1.0) * average_fitness / delta;
117  *b = average_fitness * (max_fit - C_MULT * average_fitness) / delta;
118  }
119  else { // Skalieren soweit moeglich
120  delta = average_fitness - min_fit;
121  *a = average_fitness / delta;
122  *b = -min_fit * average_fitness / delta;
123  }
124 }
125 
127  int i=0;
128 
129  len_roulette_wheel = 0;
130  while (i<probe_combi_array_length)
131  len_roulette_wheel += (int)(MULTROULETTEFACTOR * (probe_combi_stat_array[i++]->get_expected_children())); // um aus z.B. 4,2 42 zu machen
132 }
133 
134 probe_combi_statistic *Generation::choose_combi_for_next_generation() {
135  int random_help = get_random(0, len_roulette_wheel-1),
136  i;
137 
138  for (i=0; i<probe_combi_array_length; i++) { // in einer Schleife bis zu den betreffenden Elementen vordringen (Rouletterad !!!)
139  random_help -= (int) (MULTROULETTEFACTOR * probe_combi_stat_array[i]->get_expected_children());
140 
141  if (random_help <= 0) {
142  if (probe_combi_stat_array[i]->ok_for_next_gen(len_roulette_wheel)) {
143  return probe_combi_stat_array[i];
144  }
145  else {
146  random_help = get_random(0, len_roulette_wheel-1);
147  i = -1;
148  }
149  }
150  }
151 
152  return NULp;
153 }
154 
156  Generation *child_generation = new Generation(MAXPOPULATION, generation_counter+1);
157  probe_combi_statistic *first_child_pcs = NULp,
158  *second_child_pcs = NULp,
159  *orig1 = NULp,
160  *orig2 = NULp;
161  int cnt = 0;
162 #ifdef USE_DUP_TREE
163  bool res;
164 #endif
165 
166  while (len_roulette_wheel > 1) { // kann kleiner sein, wenn Population kleiner als MAXPOPULATION
167  cnt++;
168  orig1 = choose_combi_for_next_generation();
169  orig2 = choose_combi_for_next_generation();
170 
171  if (! orig1 && ! orig2) break;
172  else if (!orig1 && orig2) {
173  orig1 = orig2;
174  orig2 = NULp;
175  }
176 
177  delete first_child_pcs;
178  delete second_child_pcs;
179  first_child_pcs = second_child_pcs = NULp;
180 
181  first_child_pcs = orig1->duplicate();
182  if (orig2)
183  second_child_pcs = orig2->duplicate();
184 
185  if (orig2 && get_random(1, 100) <= CROSSOVER_WS) { // Crossover durchfueheren
186  first_child_pcs->crossover_Probes(second_child_pcs);
187  first_child_pcs->init_life_counter(); // wenn Crossover durchgefuehrt wird, dann Lebensdauer wieder initialisieren, da
188  second_child_pcs->init_life_counter(); // sich die Gene veraendert haben
189  len_roulette_wheel -= orig1->sub_expected_children(0.5); // Verfahren nach Goldberg S.115
190  len_roulette_wheel -= orig2->sub_expected_children(0.5);
191  }
192  else {
193  first_child_pcs->sub_life_counter(); // Gene gleich geblieben => Lebensdauer verkuerzen
194  len_roulette_wheel -= orig1->sub_expected_children(1.0); // nur tatsaechlich subtrahierte Zahl abziehen !!!
195 
196  if (orig2) {
197  second_child_pcs->sub_life_counter();
198  len_roulette_wheel -= orig2->sub_expected_children(1.0);
199  }
200  }
201 
202  first_child_pcs->mutate_Probe(); // fuer jede Position wird mit 1/MUTATION_WS eine Mutation durchgefuehrt.
203  if (orig2) // Mutationen durchfuehren
204  second_child_pcs->mutate_Probe();
205 
206 #ifdef USE_DUP_TREE
207 
208  res = true;
209  if (child_generation->get_dup_tree()->insert(first_child_pcs, res, 0)) {
210  if (!child_generation->insert(first_child_pcs)) // Population schon auf MAXPOPULATION
211  break;
212  }
213 
214  res = true;
215  if (child_generation->get_dup_tree()->insert(second_child_pcs, res, 0)) {
216  if (orig2 && !child_generation->insert(second_child_pcs)) break;
217  }
218 
219 #else
220  if (!child_generation->insert(first_child_pcs)) // Population schon auf MAXPOPULATION
221  break;
222 
223  if (orig2)
224  if (!child_generation->insert(second_child_pcs))
225  break;
226 
227 #endif
228  }
229 
230  delete first_child_pcs;
231  delete second_child_pcs;
232 
233  if (len_roulette_wheel <= 1)
234  child_generation->set_length(); // probe_combi_array_length muss andere laenge bekommen
235 
236  return child_generation;
237 }
238 
239 void Generation::gen_determ_combis(int beg, int len, int &pos_counter, probe_combi_statistic *p) {
240  int i, j;
241  probe_combi_statistic *bastel_probe_combi;
242 
243  if (len == 0) {
244  probe_combi_stat_array[pos_counter++] = p;
245  return;
246  }
247 
248  for (i=beg; i <= mp_main->get_p_eval()->get_pool_length() - len; i++) {
249  bastel_probe_combi = new probe_combi_statistic;
250 
251  for (j=0; j < mp_gl_awars.no_of_probes - len; j++) // LOOP_VECTORIZED[!<6.0]
252  bastel_probe_combi->set_probe_combi(j, p->get_probe_combi(j));
253 
254  if (len == mp_gl_awars.no_of_probes ||
255  (mp_main->get_p_eval()->get_probe_pool())[i]->probe_index
256  !=
257  bastel_probe_combi->get_probe_combi(mp_gl_awars.no_of_probes - len - 1)->probe_index)
258  {
259  bastel_probe_combi->set_probe_combi(mp_gl_awars.no_of_probes - len, (mp_main->get_p_eval()->get_probe_pool())[i]);
260  gen_determ_combis(i+1, len-1, pos_counter, bastel_probe_combi);
261  }
262 
263  if (len != 1)
264  delete bastel_probe_combi;
265  }
266 }
267 
269  if (last_elem == MAXPOPULATION)
270  return false;
271 
272  probe_combi_stat_array[last_elem++] = pcs->duplicate();
273  probe_combi_array_length = last_elem;
274 
275  return true;
276 }
277 
279  int i, counter = 0;
280  probe *random_probe;
281  int zw_erg;
282  int pos = 0;
283 
285 
286  if (probe_combi_array_length < MAXINITPOPULATION) {
287  gen_determ_combis(0, mp_gl_awars.no_of_probes, pos, NULp); // probe_combi_stat_array ist danach gefuellt !!!
288 
289  probe_combi_array_length = pos;
290 
291  return; // aufruf der funktion fuer die letzte Generation
292  }
293 
294  counter = 0;
295  pcs = new probe_combi_statistic;
296 
297  while (counter < probe_combi_array_length) { // Hier erfolgt die Generierung des probe_combi_stat_array
298  for (i=0; i<mp_gl_awars.no_of_probes; i++) {
299  zw_erg = get_random(0, mp_main->get_p_eval()->get_pool_length()-1);
300  random_probe = (mp_main->get_p_eval()->get_probe_pool())[zw_erg];
301  pcs->set_probe_combi(i, random_probe);
302  }
303 
304  if (pcs->check_duplicates(dup_tree)) { // 2 gleiche Sonden in der Kombination => nicht verwendbar
305  probe_combi_stat_array[counter++] = pcs;
306  if (counter < probe_combi_array_length)
307  pcs = new probe_combi_statistic;
308  }
309  }
310 }
311 
312 Generation::Generation(int len, int gen_nr) {
313  memset((char *)this, 0, sizeof(Generation));
314 
315  probe_combi_array_length = len;
316  probe_combi_stat_array = new probe_combi_statistic*[probe_combi_array_length]; // probe_combi_array_length entspricht
317  // der Groesse der Ausgangspopulation
318  memset(probe_combi_stat_array, 0, probe_combi_array_length * sizeof(probe_combi_statistic*)); // Struktur mit 0 initialisieren.
319  generation_counter = gen_nr;
320 
321 #ifdef USE_DUP_TREE
322  dup_tree = new GenerationDuplicates(mp_main->get_p_eval()->get_size_sondenarray()); // nur wenn sondenkombis nur einmal
323  // in der Generation vorkommen duerfen
324 #endif
325 
326 }
327 
329  int i;
330 
331  for (i=0; i<probe_combi_array_length; i++)
332  delete probe_combi_stat_array[i];
333 
334  delete [] probe_combi_stat_array;
335  delete dup_tree;
336 }
string result
GenerationDuplicates * get_dup_tree()
Definition: MP_probe.hxx:126
void gen_determ_combis(int beg, int len, int &pos_counter, probe_combi_statistic *p)
int get_pool_length()
Definition: MP_probe.hxx:173
#define MAXINITPOPULATION
Definition: MultiProbe.hxx:71
int probe_index
Definition: MP_probe.hxx:16
bool insert(probe_combi_statistic *pcs)
void init_roulette_wheel()
int get_size_sondenarray()
Definition: MP_probe.hxx:175
void scale(double a, double b)
Definition: MP_probe.hxx:70
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
probe_combi_statistic * single_in_generation(probe_combi_statistic *field)
void init_valuation()
void set_length()
Definition: MP_probe.hxx:127
bool MP_aborted(int gen_cnt, double avg_fit, double min_fit, double max_fit, arb_progress &progress)
Definition: MP_noclass.cxx:279
void check_for_results()
void set_probe_combi(int j, probe *f)
Definition: MP_probe.hxx:63
Generation * create_next_generation()
void insert_in_result_list(probe_combi_statistic *pcs)
Definition: MP_probe.cxx:69
double calc_expected_children(double average_fitness)
bool insert(probe_combi_statistic *sondenkombi, bool &result, int depth=0)
#define CROSSOVER_WS
Definition: MultiProbe.hxx:73
probe * get_probe_combi(int j)
Definition: MP_probe.hxx:64
bool calcFitness(bool use_genetic_algo, double old_avg_fit)
probe_combi_statistic * check_duplicates(GenerationDuplicates *dup_tree=NULp)
void crossover_Probes(probe_combi_statistic *pcombi2)
#define C_MULT
Definition: MultiProbe.hxx:76
#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
awar_vars mp_gl_awars
Definition: MP_main.cxx:23
#define MAXPOPULATION
Definition: MultiProbe.hxx:72
Generation(int len, int gen_nr)