1 | import argparse |
---|
2 | import json |
---|
3 | import os |
---|
4 | import pickle |
---|
5 | import time |
---|
6 | import math |
---|
7 | import random |
---|
8 | from abc import ABC, abstractmethod |
---|
9 | |
---|
10 | from ..base.random_sequence_index import RandomIndexSequence |
---|
11 | from ..constants import BAD_FITNESS |
---|
12 | from ..json_encoders import Encoder |
---|
13 | from ..structures.hall_of_fame import HallOfFame |
---|
14 | from ..structures.individual import Individual |
---|
15 | from ..structures.population import PopulationStructures |
---|
16 | |
---|
17 | |
---|
18 | class ExperimentABC(ABC): |
---|
19 | |
---|
20 | def __init__(self, popsize, hof_size, save_only_best) -> None: |
---|
21 | self.population_structures = None |
---|
22 | self.stats = [] |
---|
23 | self.current_generation = 0 |
---|
24 | self.time_elapsed = 0 |
---|
25 | |
---|
26 | self.hof = HallOfFame(hof_size) |
---|
27 | self.popsize = popsize |
---|
28 | self.save_only_best = save_only_best |
---|
29 | |
---|
30 | def select(self, individuals, tournament_size, random_index_sequence): |
---|
31 | """Tournament selection, returns the index of the best individual from those taking part in the tournament""" |
---|
32 | best_index = None |
---|
33 | for i in range(tournament_size): |
---|
34 | rnd_index = random_index_sequence.getNext() |
---|
35 | if best_index is None or individuals[rnd_index].fitness > best_index.fitness: |
---|
36 | best_index = individuals[rnd_index] |
---|
37 | return best_index |
---|
38 | |
---|
39 | def addGenotypeIfValid(self, ind_list, genotype): |
---|
40 | new_individual = Individual() |
---|
41 | new_individual.set_and_evaluate(genotype, self.evaluate) |
---|
42 | if new_individual.fitness is not BAD_FITNESS: |
---|
43 | ind_list.append(new_individual) |
---|
44 | |
---|
45 | @staticmethod |
---|
46 | def stochastic_round(value): # https://en.wikipedia.org/wiki/Rounding#Stochastic_rounding |
---|
47 | # For example, value==2.1 should turn in most cases to int 2, rarely to int 3 |
---|
48 | lower = math.floor(value) # returns int |
---|
49 | return lower + (random.random() < (value - lower)) |
---|
50 | |
---|
51 | def make_new_population(self, individuals, prob_mut, prob_xov, tournament_size): |
---|
52 | """'individuals' is the input population (a list of individuals). |
---|
53 | Assumptions: all genotypes in 'individuals' are valid and evaluated (have fitness set). |
---|
54 | Returns: a new population of size 'self.popsize' with prob_mut mutants, prob_xov offspring, and the remainder of clones.""" |
---|
55 | |
---|
56 | # if (self.popsize * probability) below is not integer (e.g. popsize=50, prob_xov=0.333, expected number of crossovers = 50*0.333=16.65), stochastic_round() will ensure that you will get on average the expected number of crossovers per generation (e.g. 16.65: less often 16, more often 17). |
---|
57 | expected_mut = self.stochastic_round(self.popsize * prob_mut) # or int(...) if you accept less mutants in some cases, see the comment above |
---|
58 | expected_xov = self.stochastic_round(self.popsize * prob_xov) # or int(...) if you accept less crossovers in some cases, see the comment above |
---|
59 | assert expected_mut + expected_xov <= self.popsize, "If probabilities of mutation (%g) and crossover (%g) added together exceed 1.0, then the population would grow every generation..." % (prob_mut, prob_xov) # can be triggered due to stochastic_round() if prob_mut+prob_xov is close to 1 and the expected number of mutants or crossovers is not integer; if this happens, adjust popsize, prob_mut and prob_xov accordingly. |
---|
60 | |
---|
61 | newpop = [] |
---|
62 | ris = RandomIndexSequence(len(individuals)) |
---|
63 | |
---|
64 | # adding valid mutants of selected individuals... |
---|
65 | while len(newpop) < expected_mut: |
---|
66 | ind = self.select(individuals, tournament_size=tournament_size, random_index_sequence=ris) |
---|
67 | self.addGenotypeIfValid(newpop, self.mutate(ind.genotype)) |
---|
68 | |
---|
69 | # adding valid crossovers of selected individuals... |
---|
70 | while len(newpop) < expected_mut + expected_xov: |
---|
71 | ind1 = self.select(individuals, tournament_size=tournament_size, random_index_sequence=ris) |
---|
72 | ind2 = self.select(individuals, tournament_size=tournament_size, random_index_sequence=ris) |
---|
73 | self.addGenotypeIfValid(newpop, self.cross_over(ind1.genotype, ind2.genotype)) |
---|
74 | |
---|
75 | # select clones to fill up the new population until we reach the same size as the input population |
---|
76 | while len(newpop) < self.popsize: |
---|
77 | ind = self.select(individuals, tournament_size=tournament_size, random_index_sequence=ris) |
---|
78 | newpop.append(Individual().copyFrom(ind)) |
---|
79 | |
---|
80 | return newpop |
---|
81 | |
---|
82 | def save_state(self, state_filename): |
---|
83 | state = self.get_state() |
---|
84 | if state_filename is None: |
---|
85 | return |
---|
86 | state_filename_tmp = state_filename + ".tmp" |
---|
87 | try: |
---|
88 | with open(state_filename_tmp, "wb") as f: |
---|
89 | pickle.dump(state, f) |
---|
90 | # ensures the new file was first saved OK (e.g. enough free space on device), then replace |
---|
91 | os.replace(state_filename_tmp, state_filename) |
---|
92 | except Exception as ex: |
---|
93 | raise RuntimeError("Failed to save evolution state '%s' (because: %s). This does not prevent the experiment from continuing, but let's stop here to fix the problem with saving state files." % ( |
---|
94 | state_filename_tmp, ex)) |
---|
95 | |
---|
96 | def load_state(self, state_filename): |
---|
97 | if state_filename is None: |
---|
98 | # print("Loading evolution state: file name not provided") |
---|
99 | return None |
---|
100 | try: |
---|
101 | with open(state_filename, 'rb') as f: |
---|
102 | state = pickle.load(f) |
---|
103 | self.set_state(state) |
---|
104 | except FileNotFoundError: |
---|
105 | return None |
---|
106 | print("...Loaded evolution state from '%s'" % state_filename) |
---|
107 | return True |
---|
108 | |
---|
109 | def get_state_filename(self, save_file_name): |
---|
110 | return None if save_file_name is None else save_file_name + '_state.pkl' |
---|
111 | |
---|
112 | def get_state(self): |
---|
113 | return [self.time_elapsed, self.current_generation, self.population_structures, self.hof, self.stats] |
---|
114 | |
---|
115 | def set_state(self, state): |
---|
116 | self.time_elapsed, self.current_generation, self.population_structures, hof_, self.stats = state |
---|
117 | # sorting: ensure that we add from worst to best so all individuals are added to HOF |
---|
118 | for h in sorted(hof_, key=lambda x: x.rawfitness): |
---|
119 | self.hof.add(h) |
---|
120 | |
---|
121 | def update_stats(self, generation, all_individuals): |
---|
122 | worst = min(all_individuals, key=lambda item: item.rawfitness) |
---|
123 | best = max(all_individuals, key=lambda item: item.rawfitness) |
---|
124 | # instead of single best, could add all individuals in population here, but then the outcome would depend on the order of adding |
---|
125 | self.hof.add(best) |
---|
126 | self.stats.append(best.rawfitness if self.save_only_best else best) |
---|
127 | print("%d\t%d\t%g\t%g" % (generation, len(all_individuals), worst.rawfitness, best.rawfitness)) |
---|
128 | |
---|
129 | def initialize_evolution(self, initialgenotype): |
---|
130 | self.current_generation = 0 |
---|
131 | self.time_elapsed = 0 |
---|
132 | self.stats = [] # stores the best individuals, one from each generation |
---|
133 | initial_individual = Individual() |
---|
134 | initial_individual.set_and_evaluate(initialgenotype, self.evaluate) |
---|
135 | self.hof.add(initial_individual) |
---|
136 | self.stats.append( |
---|
137 | initial_individual.rawfitness if self.save_only_best else initial_individual) |
---|
138 | self.population_structures = PopulationStructures( |
---|
139 | initial_individual=initial_individual, archive_size=0, popsize=self.popsize) |
---|
140 | |
---|
141 | def evolve(self, hof_savefile, generations, initialgenotype, pmut, pxov, tournament_size): |
---|
142 | file_name = self.get_state_filename(hof_savefile) |
---|
143 | state = self.load_state(file_name) |
---|
144 | if state is not None: # loaded state from file |
---|
145 | # saved generation has been completed, start with the next one |
---|
146 | self.current_generation += 1 |
---|
147 | print("...Resuming from saved state: population size = %d, hof size = %d, stats size = %d, archive size = %d, generation = %d/%d" % (len(self.population_structures.population), len(self.hof), len(self.stats), (len(self.population_structures.archive)), self.current_generation, generations)) # self.current_generation (and g) are 0-based, parsed_args.generations is 1-based |
---|
148 | else: |
---|
149 | self.initialize_evolution(initialgenotype) |
---|
150 | time0 = time.process_time() |
---|
151 | for g in range(self.current_generation, generations): |
---|
152 | self.population_structures.population = self.make_new_population( |
---|
153 | self.population_structures.population, pmut, pxov, tournament_size) |
---|
154 | self.update_stats(g, self.population_structures.population) |
---|
155 | if hof_savefile is not None: |
---|
156 | self.current_generation = g |
---|
157 | self.time_elapsed += time.process_time() - time0 |
---|
158 | self.save_state(file_name) |
---|
159 | if hof_savefile is not None: |
---|
160 | self.save_genotypes(hof_savefile) |
---|
161 | return self.population_structures.population, self.stats |
---|
162 | |
---|
163 | @abstractmethod |
---|
164 | def mutate(self, gen1): |
---|
165 | pass |
---|
166 | |
---|
167 | @abstractmethod |
---|
168 | def cross_over(self, gen1, gen2): |
---|
169 | pass |
---|
170 | |
---|
171 | @abstractmethod |
---|
172 | def evaluate(self, genotype): |
---|
173 | pass |
---|
174 | |
---|
175 | def save_genotypes(self, filename): |
---|
176 | """Implement if you want to save finall genotypes,in default implementation this function is run once at the end of evolution""" |
---|
177 | state_to_save = { |
---|
178 | "number_of_generations": self.current_generation, |
---|
179 | "hof": [{"genotype": individual.genotype, |
---|
180 | "fitness": individual.rawfitness} for individual in self.hof.hof]} |
---|
181 | with open(f"{filename}.json", 'w') as f: |
---|
182 | json.dump(state_to_save, f, cls=Encoder) |
---|
183 | |
---|
184 | |
---|
185 | @staticmethod |
---|
186 | def get_args_for_parser(): |
---|
187 | parser = argparse.ArgumentParser() |
---|
188 | parser.add_argument('-popsize', type=int, default=50, |
---|
189 | help="Population size, default: 50.") |
---|
190 | parser.add_argument('-generations', type=int, default=5, |
---|
191 | help="Number of generations, default: 5.") |
---|
192 | parser.add_argument('-tournament', type=int, default=5, |
---|
193 | help="Tournament size, default: 5.") |
---|
194 | parser.add_argument('-pmut', type=float, default=0.7, |
---|
195 | help="Probability of mutation, default: 0.7") |
---|
196 | parser.add_argument('-pxov', type=float, default=0.2, |
---|
197 | help="Probability of crossover, default: 0.2") |
---|
198 | parser.add_argument('-hof_size', type=int, default=10, |
---|
199 | help="Number of genotypes in Hall of Fame. Default: 10.") |
---|
200 | parser.add_argument('-hof_savefile', type=str, required=False, |
---|
201 | help= 'If set, Hall of Fame will be saved in Framsticks file format (recommended extension *.gen. This also activates saving state (checpoint} file and auto-resuming from the saved state, if this file exists.') |
---|
202 | parser.add_argument('-save_only_best', type=bool, default=True, required=False, |
---|
203 | help="") |
---|
204 | parser.add_argument('-fitness_set_negative_to_zero', action='store_true', |
---|
205 | help="This flag forces fitness to become max(0,fitness), so it is always made non-negative. Using niching or novelty techniques without this flag (thus allowing negative fitness values) requires verifying/improving fitness diversification formulas to work as intended for both positive and negative fitness values.") |
---|
206 | |
---|
207 | return parser |
---|