eckity.algorithms.algorithm
This module implements the Algorithm class.
1""" 2This module implements the Algorithm class. 3""" 4 5import logging 6import sys 7from abc import ABC, abstractmethod 8from concurrent.futures.process import ProcessPoolExecutor 9from concurrent.futures.thread import ThreadPoolExecutor 10from time import time 11from typing import Any, Callable, Dict, List, Union 12 13from overrides import overrides 14 15from eckity.population import Population 16from eckity.subpopulation import Subpopulation 17from eckity.breeders import Breeder 18from eckity.evaluators import PopulationEvaluator 19from eckity.event_based_operator import Operator 20from eckity.individual import Individual 21from eckity.random import RNG 22from eckity.statistics.statistics import Statistics 23from eckity.termination_checkers import TerminationChecker 24 25logger = logging.getLogger(__name__) 26logging.basicConfig(level=logging.INFO, stream=sys.stdout) 27 28 29class Algorithm(Operator, ABC): 30 """ 31 Evolutionary algorithm to be executed. 32 33 Abstract Algorithm that can be extended to concrete algorithms, 34 such as SimpleEvolution, Coevolution etc. 35 36 Parameters 37 ---------- 38 population: Population 39 The population to be evolved. 40 Consists of several sub-populations. 41 ref: https://api.eckity.org/eckity/population.html 42 43 statistics: Statistics or list of Statistics, default=None 44 Provide statistics on the population during the evolution. 45 ref: https://api.eckity.org/eckity/statistics.html 46 47 breeder: Breeder, default=SimpleBreeder() 48 Responsible for applying selection and operator sequence on individuals 49 in each generation. Applies on one sub-population in simple case. 50 ref: https://api.eckity.org/eckity/breeders.html 51 52 population_evaluator: PopulationEvaluator, 53 default=SimplePopulationEvaluator() 54 Evaluates individual fitness scores concurrently and returns the best 55 individual of each subpopulation (one individual in simple case). 56 ref: https://api.eckity.org/eckity/evaluators.html 57 58 max_generation: int, default=100 59 Maximal number of generations to run the evolutionary process. 60 Note the evolution could end before reaching max_generation, 61 depends on the termination checker. 62 Note there are up to `max_generation + 1` fitness calculations, 63 but only up to `max_generation` selections 64 65 events: dict(str, dict(object, function)), default=None 66 dict of events, each event holds a dict (subscriber, callback). 67 68 event_names: list of strings, default=None 69 Names of events to publish during the evolution. 70 71 termination_checker: TerminationChecker or a list of TerminationCheckers, 72 default=None 73 Checks if the algorithm should terminate early. 74 ref: https://api.eckity.org/eckity/termination_checkers.html 75 76 max_workers: int, default=None 77 Maximal number of worker nodes for the Executor object 78 that evaluates the fitness of the individuals. 79 ref: https://docs.python.org/3/library/concurrent.futures.html 80 81 random_generator: RNG, default=RNG() 82 Random Number Generator. 83 84 random_seed: int, default=current system time 85 Random seed for deterministic experiment. 86 87 generation_seed: int, default=None 88 Current generation seed. 89 Useful for resuming a previously paused experiment. 90 91 generation_num: int, default=0 92 Current generation number 93 94 Attributes 95 ---------- 96 final_generation_: int 97 The generation in which the evolution ended. 98 """ 99 100 def __init__( 101 self, 102 population: Union[Population, Subpopulation, List[Subpopulation]], 103 statistics: Union[Statistics, List[Statistics]] = None, 104 breeder: Breeder = None, 105 population_evaluator: PopulationEvaluator = None, 106 termination_checker: Union[ 107 TerminationChecker, List[TerminationChecker] 108 ] = None, 109 max_generation: int = 100, 110 events: Dict[str, Dict[object, Callable]] = None, 111 event_names: List[str] = None, 112 random_generator: RNG = RNG(), 113 random_seed: int = None, 114 generation_seed: int = None, 115 executor: str = "process", 116 max_workers: int = None, 117 generation_num: int = 0, 118 ): 119 120 ext_event_names = event_names.copy() if event_names is not None else [] 121 122 ext_event_names.extend( 123 ["init", "evolution_finished", "after_generation"] 124 ) 125 super().__init__(events=events, event_names=ext_event_names) 126 127 self._validate_population_type(population) 128 self._validate_statistics_type(statistics) 129 130 self.breeder = breeder 131 self.population_evaluator = population_evaluator 132 self.termination_checker = termination_checker 133 self.max_generation = max_generation 134 135 # set random seed to current time if not provided 136 if random_seed is None: 137 t = time() 138 # convert seed to int for np.random compatibility 139 pre_dec_pnt, post_dec_pnt = str(t).split(".") 140 int_seed = int(pre_dec_pnt + post_dec_pnt) 141 random_seed = int_seed % (2**32) 142 143 self.random_generator = random_generator 144 self.random_seed = random_seed 145 self.generation_seed = ( 146 generation_seed if generation_seed is not None else random_seed 147 ) 148 149 self.best_of_run_ = None 150 self.worst_of_gen = None 151 self.generation_num = generation_num 152 153 self.max_workers = max_workers 154 155 if executor == "thread": 156 self.executor = ThreadPoolExecutor(max_workers=max_workers) 157 elif executor == "process": 158 self.executor = ProcessPoolExecutor(max_workers=max_workers) 159 else: 160 raise ValueError('Executor must be either "thread" or "process"') 161 self._executor_type = executor 162 163 self.final_generation_ = 0 164 165 @overrides 166 def apply_operator(self, payload): 167 """ 168 begin the evolutionary run 169 """ 170 self.evolve() 171 172 def evolve(self) -> None: 173 """ 174 Performs the evolutionary run by initializing the random seed, 175 creating the population, performing the evolutionary loop 176 and finally finishing the evolution process 177 """ 178 self.initialize() 179 180 if self.should_terminate( 181 self.population, self.best_of_run_, self.generation_num 182 ): 183 self.final_generation_ = 0 184 self.publish("after_generation") 185 else: 186 self.evolve_main_loop() 187 188 self.publish("evolution_finished") 189 self.finish() 190 191 @abstractmethod 192 def execute(self, **kwargs) -> object: 193 """ 194 Execute the algorithm result after evolution ended. 195 196 Parameters 197 ---------- 198 kwargs : keyword arguments (relevant in GP representation) 199 Input to program, including every variable 200 in the terminal set as a keyword argument. 201 For example, if `terminal_set=['x', 'y', 'z', 0, 1, -1]` 202 then call `execute(x=..., y=..., z=...)`. 203 204 Returns 205 ------- 206 object 207 Result of algorithm execution (for example: the best 208 individual in GA, or the best individual execution in GP) 209 """ 210 raise ValueError("execute is an abstract method in class Algorithm") 211 212 def initialize(self) -> None: 213 """ 214 Initialize seed, Executor and relevant operators 215 """ 216 self.set_random_seed(self.random_seed) 217 logger.info("random seed = %d", self.random_seed) 218 self.population_evaluator.set_executor(self.executor) 219 220 for field in self.__dict__.values(): 221 if isinstance(field, Operator): 222 field.initialize() 223 224 self.create_population() 225 self.best_of_run_ = self.population_evaluator.act(self.population) 226 self.publish("init") 227 228 def _validate_population_type(self, population: Any) -> None: 229 # Assert valid population input 230 if population is None: 231 raise ValueError("Population cannot be None") 232 233 if isinstance(population, Population): 234 self.population = population 235 elif isinstance(population, Subpopulation): 236 self.population = Population([population]) 237 elif isinstance(population, list): 238 if len(population) == 0: 239 raise ValueError("Population cannot be empty") 240 for sub_pop in population: 241 if not isinstance(sub_pop, Subpopulation): 242 raise ValueError( 243 "Detected a non-Subpopulation " 244 "instance as an element in Population" 245 ) 246 self.population = Population(population) 247 else: 248 raise ValueError( 249 "Parameter population must be either a Population, " 250 "a Subpopulation or a list of Subpopulations. " 251 "Received population with unexpected type of", 252 type(population), 253 ) 254 255 def _validate_statistics_type(self, statistics: Any) -> None: 256 # Assert valid statistics input 257 if isinstance(statistics, Statistics): 258 self.statistics = [statistics] 259 elif isinstance(statistics, list): 260 for stat in statistics: 261 if not isinstance(stat, Statistics): 262 raise ValueError( 263 "Expected a Statistics instance as an element" 264 " in Statistics list, but received", 265 type(stat), 266 ) 267 self.statistics = statistics 268 else: 269 raise ValueError( 270 "Parameter statistics must be either a subclass of Statistics" 271 " or a list of subclasses of Statistics.\n" 272 "received statistics with unexpected type of", 273 type(statistics), 274 ) 275 276 def evolve_main_loop(self) -> None: 277 """ 278 Performs the evolutionary main loop 279 """ 280 # there was already "preprocessing" generation created - gen #0 281 # now create another self.max_generation generations, starting gen #1 282 for gen in range(1, self.max_generation + 1): 283 self.generation_num = gen 284 self.update_gen(gen) 285 286 self.set_generation_seed(self.next_seed()) 287 self.generation_iteration(gen) 288 if self.should_terminate(self.population, self.best_of_run_, gen): 289 self.final_generation_ = gen 290 self.publish("after_generation") 291 break 292 self.publish("after_generation") 293 294 def update_gen(self, gen: int) -> None: 295 """ 296 Update `gen` field for all individuals 297 298 Parameters 299 ---------- 300 gen : int 301 Current generation number 302 """ 303 for subpopulation in self.population.sub_populations: 304 for ind in subpopulation.individuals: 305 ind.gen = gen 306 307 @abstractmethod 308 def generation_iteration(self, gen: int) -> bool: 309 """ 310 Performs an iteration of the evolutionary main loop 311 312 Parameters 313 ---------- 314 gen: int 315 current generation number 316 317 Returns 318 ------- 319 bool 320 True if the main loop should terminate, False otherwise 321 """ 322 raise ValueError( 323 "generation_iteration is an abstract method in class Algorithm" 324 ) 325 326 def finish(self) -> None: 327 """ 328 Finish the evolutionary run 329 """ 330 self.executor.shutdown() 331 332 def create_population(self) -> None: 333 """ 334 Create the population for the evolutionary run 335 """ 336 self.population.create_population_individuals() 337 338 def event_name_to_data(self, event_name) -> Dict[str, object]: 339 """ 340 Convert event name to relevant data of the Algorithm for the event 341 342 Parameters 343 ---------- 344 event_name: string 345 name of the event that is happening 346 347 Returns 348 ---------- 349 Dict[str, object] 350 Algorithm data regarding the given event 351 """ 352 if event_name == "init": 353 return { 354 "population": self.population, 355 "statistics": self.statistics, 356 "breeder": self.breeder, 357 "termination_checker": self.termination_checker, 358 "max_generation": self.max_generation, 359 "events": self.events, 360 "max_workers": self.max_workers, 361 } 362 return {} 363 364 def set_random_seed(self, seed: int = None) -> None: 365 """ 366 Set the initial seed for the random generator 367 This method is called once at the beginning of the run. 368 369 Parameters 370 ---------- 371 seed: int 372 random seed number 373 """ 374 self.random_generator.set_seed(seed) 375 self.random_seed = seed 376 377 def set_generation_seed(self, seed: int) -> None: 378 """ 379 Set the seed for current generation. 380 This method is called once every generation. 381 382 Parameters 383 ---------- 384 seed: int 385 current generation seed 386 """ 387 self.random_generator.set_seed(seed) 388 self.generation_seed = seed 389 390 def next_seed(self) -> int: 391 """ 392 Increase the random seed for the next generation. 393 394 Returns 395 ---------- 396 int 397 random seed number 398 """ 399 return (self.generation_seed + 1) % (2**32) 400 401 def should_terminate( 402 self, 403 population: Population, 404 best_of_run_: Individual, 405 generation_num: int, 406 ) -> bool: 407 if self.termination_checker is None: 408 return False 409 elif isinstance(self.termination_checker, list): 410 return any( 411 [ 412 t.should_terminate( 413 population, best_of_run_, generation_num 414 ) 415 for t in self.termination_checker 416 ] 417 ) 418 else: 419 return self.termination_checker.should_terminate( 420 population, best_of_run_, generation_num 421 ) 422 423 def __getstate__(self) -> Dict[str, object]: 424 """ 425 Return a dictionary of the Algorithm's fields and values. 426 It is mainly used for serialization. 427 We remove executor field since it cannot be pickled. 428 429 Returns 430 ------- 431 Dict[str, object] 432 Dictionary of {field name: field value} for the Algorithm object. 433 """ 434 state = self.__dict__.copy() 435 del state["executor"] 436 return state 437 438 def __setstate__(self, state: Dict[str, object]) -> None: 439 """ 440 Set the __dict__ of the algorithm upon deserialization. 441 We update executor field according to the _executor_type field, 442 since the executor was removed in the serialization process. 443 444 Parameters 445 ---------- 446 state : Dict[str, object] 447 Dictionary of {field name: field value} for the Algorithm object. 448 """ 449 self.__dict__.update(state) 450 if self._executor_type == "thread": 451 self.executor = ThreadPoolExecutor(max_workers=self.max_workers) 452 else: 453 self.executor = ProcessPoolExecutor(max_workers=self.max_workers)
30class Algorithm(Operator, ABC): 31 """ 32 Evolutionary algorithm to be executed. 33 34 Abstract Algorithm that can be extended to concrete algorithms, 35 such as SimpleEvolution, Coevolution etc. 36 37 Parameters 38 ---------- 39 population: Population 40 The population to be evolved. 41 Consists of several sub-populations. 42 ref: https://api.eckity.org/eckity/population.html 43 44 statistics: Statistics or list of Statistics, default=None 45 Provide statistics on the population during the evolution. 46 ref: https://api.eckity.org/eckity/statistics.html 47 48 breeder: Breeder, default=SimpleBreeder() 49 Responsible for applying selection and operator sequence on individuals 50 in each generation. Applies on one sub-population in simple case. 51 ref: https://api.eckity.org/eckity/breeders.html 52 53 population_evaluator: PopulationEvaluator, 54 default=SimplePopulationEvaluator() 55 Evaluates individual fitness scores concurrently and returns the best 56 individual of each subpopulation (one individual in simple case). 57 ref: https://api.eckity.org/eckity/evaluators.html 58 59 max_generation: int, default=100 60 Maximal number of generations to run the evolutionary process. 61 Note the evolution could end before reaching max_generation, 62 depends on the termination checker. 63 Note there are up to `max_generation + 1` fitness calculations, 64 but only up to `max_generation` selections 65 66 events: dict(str, dict(object, function)), default=None 67 dict of events, each event holds a dict (subscriber, callback). 68 69 event_names: list of strings, default=None 70 Names of events to publish during the evolution. 71 72 termination_checker: TerminationChecker or a list of TerminationCheckers, 73 default=None 74 Checks if the algorithm should terminate early. 75 ref: https://api.eckity.org/eckity/termination_checkers.html 76 77 max_workers: int, default=None 78 Maximal number of worker nodes for the Executor object 79 that evaluates the fitness of the individuals. 80 ref: https://docs.python.org/3/library/concurrent.futures.html 81 82 random_generator: RNG, default=RNG() 83 Random Number Generator. 84 85 random_seed: int, default=current system time 86 Random seed for deterministic experiment. 87 88 generation_seed: int, default=None 89 Current generation seed. 90 Useful for resuming a previously paused experiment. 91 92 generation_num: int, default=0 93 Current generation number 94 95 Attributes 96 ---------- 97 final_generation_: int 98 The generation in which the evolution ended. 99 """ 100 101 def __init__( 102 self, 103 population: Union[Population, Subpopulation, List[Subpopulation]], 104 statistics: Union[Statistics, List[Statistics]] = None, 105 breeder: Breeder = None, 106 population_evaluator: PopulationEvaluator = None, 107 termination_checker: Union[ 108 TerminationChecker, List[TerminationChecker] 109 ] = None, 110 max_generation: int = 100, 111 events: Dict[str, Dict[object, Callable]] = None, 112 event_names: List[str] = None, 113 random_generator: RNG = RNG(), 114 random_seed: int = None, 115 generation_seed: int = None, 116 executor: str = "process", 117 max_workers: int = None, 118 generation_num: int = 0, 119 ): 120 121 ext_event_names = event_names.copy() if event_names is not None else [] 122 123 ext_event_names.extend( 124 ["init", "evolution_finished", "after_generation"] 125 ) 126 super().__init__(events=events, event_names=ext_event_names) 127 128 self._validate_population_type(population) 129 self._validate_statistics_type(statistics) 130 131 self.breeder = breeder 132 self.population_evaluator = population_evaluator 133 self.termination_checker = termination_checker 134 self.max_generation = max_generation 135 136 # set random seed to current time if not provided 137 if random_seed is None: 138 t = time() 139 # convert seed to int for np.random compatibility 140 pre_dec_pnt, post_dec_pnt = str(t).split(".") 141 int_seed = int(pre_dec_pnt + post_dec_pnt) 142 random_seed = int_seed % (2**32) 143 144 self.random_generator = random_generator 145 self.random_seed = random_seed 146 self.generation_seed = ( 147 generation_seed if generation_seed is not None else random_seed 148 ) 149 150 self.best_of_run_ = None 151 self.worst_of_gen = None 152 self.generation_num = generation_num 153 154 self.max_workers = max_workers 155 156 if executor == "thread": 157 self.executor = ThreadPoolExecutor(max_workers=max_workers) 158 elif executor == "process": 159 self.executor = ProcessPoolExecutor(max_workers=max_workers) 160 else: 161 raise ValueError('Executor must be either "thread" or "process"') 162 self._executor_type = executor 163 164 self.final_generation_ = 0 165 166 @overrides 167 def apply_operator(self, payload): 168 """ 169 begin the evolutionary run 170 """ 171 self.evolve() 172 173 def evolve(self) -> None: 174 """ 175 Performs the evolutionary run by initializing the random seed, 176 creating the population, performing the evolutionary loop 177 and finally finishing the evolution process 178 """ 179 self.initialize() 180 181 if self.should_terminate( 182 self.population, self.best_of_run_, self.generation_num 183 ): 184 self.final_generation_ = 0 185 self.publish("after_generation") 186 else: 187 self.evolve_main_loop() 188 189 self.publish("evolution_finished") 190 self.finish() 191 192 @abstractmethod 193 def execute(self, **kwargs) -> object: 194 """ 195 Execute the algorithm result after evolution ended. 196 197 Parameters 198 ---------- 199 kwargs : keyword arguments (relevant in GP representation) 200 Input to program, including every variable 201 in the terminal set as a keyword argument. 202 For example, if `terminal_set=['x', 'y', 'z', 0, 1, -1]` 203 then call `execute(x=..., y=..., z=...)`. 204 205 Returns 206 ------- 207 object 208 Result of algorithm execution (for example: the best 209 individual in GA, or the best individual execution in GP) 210 """ 211 raise ValueError("execute is an abstract method in class Algorithm") 212 213 def initialize(self) -> None: 214 """ 215 Initialize seed, Executor and relevant operators 216 """ 217 self.set_random_seed(self.random_seed) 218 logger.info("random seed = %d", self.random_seed) 219 self.population_evaluator.set_executor(self.executor) 220 221 for field in self.__dict__.values(): 222 if isinstance(field, Operator): 223 field.initialize() 224 225 self.create_population() 226 self.best_of_run_ = self.population_evaluator.act(self.population) 227 self.publish("init") 228 229 def _validate_population_type(self, population: Any) -> None: 230 # Assert valid population input 231 if population is None: 232 raise ValueError("Population cannot be None") 233 234 if isinstance(population, Population): 235 self.population = population 236 elif isinstance(population, Subpopulation): 237 self.population = Population([population]) 238 elif isinstance(population, list): 239 if len(population) == 0: 240 raise ValueError("Population cannot be empty") 241 for sub_pop in population: 242 if not isinstance(sub_pop, Subpopulation): 243 raise ValueError( 244 "Detected a non-Subpopulation " 245 "instance as an element in Population" 246 ) 247 self.population = Population(population) 248 else: 249 raise ValueError( 250 "Parameter population must be either a Population, " 251 "a Subpopulation or a list of Subpopulations. " 252 "Received population with unexpected type of", 253 type(population), 254 ) 255 256 def _validate_statistics_type(self, statistics: Any) -> None: 257 # Assert valid statistics input 258 if isinstance(statistics, Statistics): 259 self.statistics = [statistics] 260 elif isinstance(statistics, list): 261 for stat in statistics: 262 if not isinstance(stat, Statistics): 263 raise ValueError( 264 "Expected a Statistics instance as an element" 265 " in Statistics list, but received", 266 type(stat), 267 ) 268 self.statistics = statistics 269 else: 270 raise ValueError( 271 "Parameter statistics must be either a subclass of Statistics" 272 " or a list of subclasses of Statistics.\n" 273 "received statistics with unexpected type of", 274 type(statistics), 275 ) 276 277 def evolve_main_loop(self) -> None: 278 """ 279 Performs the evolutionary main loop 280 """ 281 # there was already "preprocessing" generation created - gen #0 282 # now create another self.max_generation generations, starting gen #1 283 for gen in range(1, self.max_generation + 1): 284 self.generation_num = gen 285 self.update_gen(gen) 286 287 self.set_generation_seed(self.next_seed()) 288 self.generation_iteration(gen) 289 if self.should_terminate(self.population, self.best_of_run_, gen): 290 self.final_generation_ = gen 291 self.publish("after_generation") 292 break 293 self.publish("after_generation") 294 295 def update_gen(self, gen: int) -> None: 296 """ 297 Update `gen` field for all individuals 298 299 Parameters 300 ---------- 301 gen : int 302 Current generation number 303 """ 304 for subpopulation in self.population.sub_populations: 305 for ind in subpopulation.individuals: 306 ind.gen = gen 307 308 @abstractmethod 309 def generation_iteration(self, gen: int) -> bool: 310 """ 311 Performs an iteration of the evolutionary main loop 312 313 Parameters 314 ---------- 315 gen: int 316 current generation number 317 318 Returns 319 ------- 320 bool 321 True if the main loop should terminate, False otherwise 322 """ 323 raise ValueError( 324 "generation_iteration is an abstract method in class Algorithm" 325 ) 326 327 def finish(self) -> None: 328 """ 329 Finish the evolutionary run 330 """ 331 self.executor.shutdown() 332 333 def create_population(self) -> None: 334 """ 335 Create the population for the evolutionary run 336 """ 337 self.population.create_population_individuals() 338 339 def event_name_to_data(self, event_name) -> Dict[str, object]: 340 """ 341 Convert event name to relevant data of the Algorithm for the event 342 343 Parameters 344 ---------- 345 event_name: string 346 name of the event that is happening 347 348 Returns 349 ---------- 350 Dict[str, object] 351 Algorithm data regarding the given event 352 """ 353 if event_name == "init": 354 return { 355 "population": self.population, 356 "statistics": self.statistics, 357 "breeder": self.breeder, 358 "termination_checker": self.termination_checker, 359 "max_generation": self.max_generation, 360 "events": self.events, 361 "max_workers": self.max_workers, 362 } 363 return {} 364 365 def set_random_seed(self, seed: int = None) -> None: 366 """ 367 Set the initial seed for the random generator 368 This method is called once at the beginning of the run. 369 370 Parameters 371 ---------- 372 seed: int 373 random seed number 374 """ 375 self.random_generator.set_seed(seed) 376 self.random_seed = seed 377 378 def set_generation_seed(self, seed: int) -> None: 379 """ 380 Set the seed for current generation. 381 This method is called once every generation. 382 383 Parameters 384 ---------- 385 seed: int 386 current generation seed 387 """ 388 self.random_generator.set_seed(seed) 389 self.generation_seed = seed 390 391 def next_seed(self) -> int: 392 """ 393 Increase the random seed for the next generation. 394 395 Returns 396 ---------- 397 int 398 random seed number 399 """ 400 return (self.generation_seed + 1) % (2**32) 401 402 def should_terminate( 403 self, 404 population: Population, 405 best_of_run_: Individual, 406 generation_num: int, 407 ) -> bool: 408 if self.termination_checker is None: 409 return False 410 elif isinstance(self.termination_checker, list): 411 return any( 412 [ 413 t.should_terminate( 414 population, best_of_run_, generation_num 415 ) 416 for t in self.termination_checker 417 ] 418 ) 419 else: 420 return self.termination_checker.should_terminate( 421 population, best_of_run_, generation_num 422 ) 423 424 def __getstate__(self) -> Dict[str, object]: 425 """ 426 Return a dictionary of the Algorithm's fields and values. 427 It is mainly used for serialization. 428 We remove executor field since it cannot be pickled. 429 430 Returns 431 ------- 432 Dict[str, object] 433 Dictionary of {field name: field value} for the Algorithm object. 434 """ 435 state = self.__dict__.copy() 436 del state["executor"] 437 return state 438 439 def __setstate__(self, state: Dict[str, object]) -> None: 440 """ 441 Set the __dict__ of the algorithm upon deserialization. 442 We update executor field according to the _executor_type field, 443 since the executor was removed in the serialization process. 444 445 Parameters 446 ---------- 447 state : Dict[str, object] 448 Dictionary of {field name: field value} for the Algorithm object. 449 """ 450 self.__dict__.update(state) 451 if self._executor_type == "thread": 452 self.executor = ThreadPoolExecutor(max_workers=self.max_workers) 453 else: 454 self.executor = ProcessPoolExecutor(max_workers=self.max_workers)
Evolutionary algorithm to be executed.
Abstract Algorithm that can be extended to concrete algorithms, such as SimpleEvolution, Coevolution etc.
Parameters
- population (Population): The population to be evolved. Consists of several sub-populations. ref: https://api.eckity.org/eckity/population.html
- statistics (Statistics or list of Statistics, default=None): Provide statistics on the population during the evolution. ref: https://api.eckity.org/eckity/statistics.html
- breeder (Breeder, default=SimpleBreeder()): Responsible for applying selection and operator sequence on individuals in each generation. Applies on one sub-population in simple case. ref: https://api.eckity.org/eckity/breeders.html
- population_evaluator (PopulationEvaluator,): default=SimplePopulationEvaluator() Evaluates individual fitness scores concurrently and returns the best individual of each subpopulation (one individual in simple case). ref: https://api.eckity.org/eckity/evaluators.html
- max_generation (int, default=100):
Maximal number of generations to run the evolutionary process.
Note the evolution could end before reaching max_generation,
depends on the termination checker.
Note there are up to
max_generation + 1fitness calculations, but only up tomax_generationselections - events (dict(str, dict(object, function)), default=None): dict of events, each event holds a dict (subscriber, callback).
- event_names (list of strings, default=None): Names of events to publish during the evolution.
- termination_checker (TerminationChecker or a list of TerminationCheckers,): default=None Checks if the algorithm should terminate early. ref: https://api.eckity.org/eckity/termination_checkers.html
- max_workers (int, default=None): Maximal number of worker nodes for the Executor object that evaluates the fitness of the individuals. ref: https://docs.python.org/3/library/concurrent.futures.html
- random_generator (RNG, default=RNG()): Random Number Generator.
- random_seed (int, default=current system time): Random seed for deterministic experiment.
- generation_seed (int, default=None): Current generation seed. Useful for resuming a previously paused experiment.
- generation_num (int, default=0): Current generation number
Attributes
- final_generation_ (int): The generation in which the evolution ended.
166 @overrides 167 def apply_operator(self, payload): 168 """ 169 begin the evolutionary run 170 """ 171 self.evolve()
begin the evolutionary run
173 def evolve(self) -> None: 174 """ 175 Performs the evolutionary run by initializing the random seed, 176 creating the population, performing the evolutionary loop 177 and finally finishing the evolution process 178 """ 179 self.initialize() 180 181 if self.should_terminate( 182 self.population, self.best_of_run_, self.generation_num 183 ): 184 self.final_generation_ = 0 185 self.publish("after_generation") 186 else: 187 self.evolve_main_loop() 188 189 self.publish("evolution_finished") 190 self.finish()
Performs the evolutionary run by initializing the random seed, creating the population, performing the evolutionary loop and finally finishing the evolution process
192 @abstractmethod 193 def execute(self, **kwargs) -> object: 194 """ 195 Execute the algorithm result after evolution ended. 196 197 Parameters 198 ---------- 199 kwargs : keyword arguments (relevant in GP representation) 200 Input to program, including every variable 201 in the terminal set as a keyword argument. 202 For example, if `terminal_set=['x', 'y', 'z', 0, 1, -1]` 203 then call `execute(x=..., y=..., z=...)`. 204 205 Returns 206 ------- 207 object 208 Result of algorithm execution (for example: the best 209 individual in GA, or the best individual execution in GP) 210 """ 211 raise ValueError("execute is an abstract method in class Algorithm")
Execute the algorithm result after evolution ended.
Parameters
- kwargs (keyword arguments (relevant in GP representation)):
Input to program, including every variable
in the terminal set as a keyword argument.
For example, if
terminal_set=['x', 'y', 'z', 0, 1, -1]then callexecute(x=..., y=..., z=...).
Returns
- object: Result of algorithm execution (for example: the best individual in GA, or the best individual execution in GP)
213 def initialize(self) -> None: 214 """ 215 Initialize seed, Executor and relevant operators 216 """ 217 self.set_random_seed(self.random_seed) 218 logger.info("random seed = %d", self.random_seed) 219 self.population_evaluator.set_executor(self.executor) 220 221 for field in self.__dict__.values(): 222 if isinstance(field, Operator): 223 field.initialize() 224 225 self.create_population() 226 self.best_of_run_ = self.population_evaluator.act(self.population) 227 self.publish("init")
Initialize seed, Executor and relevant operators
277 def evolve_main_loop(self) -> None: 278 """ 279 Performs the evolutionary main loop 280 """ 281 # there was already "preprocessing" generation created - gen #0 282 # now create another self.max_generation generations, starting gen #1 283 for gen in range(1, self.max_generation + 1): 284 self.generation_num = gen 285 self.update_gen(gen) 286 287 self.set_generation_seed(self.next_seed()) 288 self.generation_iteration(gen) 289 if self.should_terminate(self.population, self.best_of_run_, gen): 290 self.final_generation_ = gen 291 self.publish("after_generation") 292 break 293 self.publish("after_generation")
Performs the evolutionary main loop
295 def update_gen(self, gen: int) -> None: 296 """ 297 Update `gen` field for all individuals 298 299 Parameters 300 ---------- 301 gen : int 302 Current generation number 303 """ 304 for subpopulation in self.population.sub_populations: 305 for ind in subpopulation.individuals: 306 ind.gen = gen
Update gen field for all individuals
Parameters
- gen (int): Current generation number
308 @abstractmethod 309 def generation_iteration(self, gen: int) -> bool: 310 """ 311 Performs an iteration of the evolutionary main loop 312 313 Parameters 314 ---------- 315 gen: int 316 current generation number 317 318 Returns 319 ------- 320 bool 321 True if the main loop should terminate, False otherwise 322 """ 323 raise ValueError( 324 "generation_iteration is an abstract method in class Algorithm" 325 )
Performs an iteration of the evolutionary main loop
Parameters
- gen (int): current generation number
Returns
- bool: True if the main loop should terminate, False otherwise
327 def finish(self) -> None: 328 """ 329 Finish the evolutionary run 330 """ 331 self.executor.shutdown()
Finish the evolutionary run
333 def create_population(self) -> None: 334 """ 335 Create the population for the evolutionary run 336 """ 337 self.population.create_population_individuals()
Create the population for the evolutionary run
339 def event_name_to_data(self, event_name) -> Dict[str, object]: 340 """ 341 Convert event name to relevant data of the Algorithm for the event 342 343 Parameters 344 ---------- 345 event_name: string 346 name of the event that is happening 347 348 Returns 349 ---------- 350 Dict[str, object] 351 Algorithm data regarding the given event 352 """ 353 if event_name == "init": 354 return { 355 "population": self.population, 356 "statistics": self.statistics, 357 "breeder": self.breeder, 358 "termination_checker": self.termination_checker, 359 "max_generation": self.max_generation, 360 "events": self.events, 361 "max_workers": self.max_workers, 362 } 363 return {}
Convert event name to relevant data of the Algorithm for the event
Parameters
- event_name (string): name of the event that is happening
Returns
- Dict[str, object]: Algorithm data regarding the given event
365 def set_random_seed(self, seed: int = None) -> None: 366 """ 367 Set the initial seed for the random generator 368 This method is called once at the beginning of the run. 369 370 Parameters 371 ---------- 372 seed: int 373 random seed number 374 """ 375 self.random_generator.set_seed(seed) 376 self.random_seed = seed
Set the initial seed for the random generator This method is called once at the beginning of the run.
Parameters
- seed (int): random seed number
378 def set_generation_seed(self, seed: int) -> None: 379 """ 380 Set the seed for current generation. 381 This method is called once every generation. 382 383 Parameters 384 ---------- 385 seed: int 386 current generation seed 387 """ 388 self.random_generator.set_seed(seed) 389 self.generation_seed = seed
Set the seed for current generation. This method is called once every generation.
Parameters
- seed (int): current generation seed
391 def next_seed(self) -> int: 392 """ 393 Increase the random seed for the next generation. 394 395 Returns 396 ---------- 397 int 398 random seed number 399 """ 400 return (self.generation_seed + 1) % (2**32)
Increase the random seed for the next generation.
Returns
- int
- random seed number
402 def should_terminate( 403 self, 404 population: Population, 405 best_of_run_: Individual, 406 generation_num: int, 407 ) -> bool: 408 if self.termination_checker is None: 409 return False 410 elif isinstance(self.termination_checker, list): 411 return any( 412 [ 413 t.should_terminate( 414 population, best_of_run_, generation_num 415 ) 416 for t in self.termination_checker 417 ] 418 ) 419 else: 420 return self.termination_checker.should_terminate( 421 population, best_of_run_, generation_num 422 )