source: branches/lib/MULTI_PROBE/MP_Generation.cxx

Last change on this file was 17262, checked in by westram, 7 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.5 KB
Line 
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
16probe_combi_statistic *Generation::single_in_generation(probe_combi_statistic *field) {
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
31void Generation::print() {
32    for (int i=0; i<probe_combi_array_length; i++)
33        probe_combi_stat_array[i]->print();
34}
35
36void Generation::check_for_results() {
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
44bool 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
106        init_roulette_wheel();
107    }
108    return false;
109}
110
111void 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
126void Generation::init_roulette_wheel() {
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
134probe_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
155Generation *Generation::create_next_generation() {
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
239void 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
268bool Generation::insert(probe_combi_statistic *pcs) {
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
278void Generation::init_valuation() {
279    int    i, counter = 0;
280    probe *random_probe;
281    int    zw_erg;
282    int    pos        = 0;
283
284    probe_combi_statistic *pcs;
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
312Generation::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
328Generation::~Generation() {
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}
Note: See TracBrowser for help on using the repository browser.