eckity.algorithms.algorithm

  1"""
  2This module implements the Algorithm class.
  3"""
  4
  5from abc import abstractmethod
  6
  7import random
  8from concurrent.futures.thread import ThreadPoolExecutor
  9from concurrent.futures.process import ProcessPoolExecutor
 10from time import time
 11
 12from overrides import overrides
 13
 14from eckity.event_based_operator import Operator
 15from eckity.population import Population
 16from eckity.statistics.statistics import Statistics
 17from eckity.subpopulation import Subpopulation
 18
 19SEED_MIN_VALUE = 0
 20SEED_MAX_VALUE = 1000000
 21
 22
 23class Algorithm(Operator):
 24	"""
 25	Evolutionary algorithm to be executed.
 26
 27	Abstract Algorithm that can be extended to concrete algorithms such as SimpleAlgorithm.
 28
 29	Parameters
 30	----------
 31	population: Population
 32		The population to be evolved. Consists of a list of individuals.
 33
 34	statistics: Statistics or list of Statistics, default=None
 35		Provide multiple statistics on the population during the evolutionary run.
 36
 37    breeder: Breeder, default=SimpleBreeder()
 38        Responsible for applying the selection method and operator sequence on the individuals
 39        in each generation. Applies on one sub-population in simple case.
 40
 41    population_evaluator: PopulationEvaluator, default=SimplePopulationEvaluator()
 42        Responsible for evaluating each individual's fitness concurrently and returns the best
 43         individual of each subpopulation (returns a single individual in simple case).
 44
 45	max_generation: int, default=1000
 46		Maximal number of generations to run the evolutionary process.
 47		Note the evolution could end before reaching max_generation,
 48		depends on the termination checker.
 49		Note that there are max_generation + 1 (at max) fitness calculations,
 50		but only max_generation (at max) of selection
 51
 52	events: dict(str, dict(object, function)), default=None
 53		Dictionary of events, where each event holds a dictionary of (subscriber, callback method).
 54
 55	event_names: list of strings, default=None
 56		Names of events to publish during the evolution.
 57
 58    termination_checker: TerminationChecker or a list of TerminationCheckers, default=ThresholdFromTargetTerminationChecker()
 59        Responsible for checking if the algorithm should finish before reaching max_generation.
 60
 61	max_workers: int, default=None
 62		Maximal number of worker nodes for the Executor object
 63		that evaluates the fitness of the individuals.
 64
 65	random_generator: module, default=random
 66		Random generator module.
 67
 68	random_seed: float or int, default=current system time
 69		Random seed for deterministic experiment.
 70
 71	generation_seed: int, default=None
 72		Current generation seed. Useful for resuming a previously paused experiment.
 73
 74	generation_num: int, default=0
 75		Current generation number
 76
 77	Attributes
 78	----------
 79	final_generation_: int
 80		The generation in which the evolution ended.
 81	"""
 82
 83	def __init__(self,
 84				 population,
 85				 statistics=None,
 86				 breeder=None,
 87				 population_evaluator=None,
 88				 termination_checker=None,
 89				 max_generation=None,
 90				 events=None,
 91				 event_names=None,
 92				 random_generator=None,
 93				 random_seed=time(),
 94				 generation_seed=None,
 95				 executor='thread',
 96				 max_workers=None,
 97				 generation_num=0):
 98
 99		ext_event_names = event_names.copy() if event_names is not None else []
100
101		ext_event_names.extend(["init", "evolution_finished", "after_generation"])
102		super().__init__(events=events, event_names=ext_event_names)
103
104		# Assert valid population input
105		if population is None:
106			raise ValueError('Population cannot be None')
107
108		if isinstance(population, Population):
109			self.population = population
110		elif isinstance(population, Subpopulation):
111			self.population = Population([population])
112		elif isinstance(population, list):
113			if len(population) == 0:
114				raise ValueError('Population cannot be empty')
115			for sub_pop in population:
116				if not isinstance(sub_pop, Subpopulation):
117					raise ValueError('Detected a non-Subpopulation '
118									 'instance as an element in Population')
119			self.population = Population(population)
120		else:
121			raise ValueError(
122				'Parameter population must be either a Population, '
123				'a Subpopulation or a list of Subpopulations\n '
124				'received population with unexpected type of', type(population)
125			)
126
127		# Assert valid statistics input
128		if isinstance(statistics, Statistics):
129			self.statistics = [statistics]
130		elif isinstance(statistics, list):
131			for stat in statistics:
132				if not isinstance(stat, Statistics):
133					raise ValueError('Expected a Statistics instance as an element'
134									 ' in Statistics list, but received', type(stat))
135			self.statistics = statistics
136		else:
137			raise ValueError(
138				'Parameter statistics must be either a subclass of Statistics'
139				' or a list of subclasses of Statistics.\n'
140				'received statistics with unexpected type of', type(statistics)
141			)
142
143		self.breeder = breeder
144		self.population_evaluator = population_evaluator
145		self.termination_checker = termination_checker
146		self.max_generation = max_generation
147
148		if random_generator is None:
149			random_generator = random
150
151		self.random_generator = random_generator
152		self.random_seed = random_seed
153		self.generation_seed = generation_seed
154
155		self.best_of_run_ = None
156		self.worst_of_gen = None
157		self.generation_num = generation_num
158
159		self.max_workers = max_workers
160
161		if executor == 'thread':
162			self.executor = ThreadPoolExecutor(max_workers=max_workers)
163		elif executor == 'process':
164			self.executor = ProcessPoolExecutor(max_workers=max_workers)
165		else:
166			raise ValueError('Executor must be either "thread" or "process"')
167		self._executor_type = executor
168		
169
170		self.final_generation_ = 0
171
172	@overrides
173	def apply_operator(self, payload):
174		"""
175		begin the evolutionary run
176		"""
177		self.evolve()
178
179	def evolve(self):
180		"""
181		Performs the evolutionary run by initializing the random seed, creating the population,
182		performing the evolutionary loop and finally finishing the evolution process
183		"""
184		self.initialize()
185
186		if self.should_terminate(self.population,
187                                 self.best_of_run_,
188                                 self.generation_num):
189			self.final_generation_ = 0
190			self.publish('after_generation')
191		else:
192			self.evolve_main_loop()
193
194		self.finish()
195		self.publish('evolution_finished')
196
197	@abstractmethod
198	def execute(self, **kwargs):
199		"""
200		Execute the algorithm result after evolution ended.
201
202		Parameters
203		----------
204		kwargs : keyword arguments (relevant in GP representation)
205			Input to program, including every variable in the terminal set as a keyword argument.
206			For example, if `terminal_set=['x', 'y', 'z', 0, 1, -1]`
207			then call `execute(x=..., y=..., z=...)`.
208
209		Returns
210		-------
211		object
212			Result of algorithm execution (for example: the best
213			 individual in GA, or the best individual execution in GP)
214		"""
215		raise ValueError("execute is an abstract method in class Algorithm")
216
217	def initialize(self):
218		"""
219		Initialize the algorithm before beginning the evolution process
220
221        Initialize seed, Executor and relevant operators
222        """
223		self.set_random_seed(self.random_seed)
224		print('debug: random seed =', self.random_seed)
225		self.population_evaluator.set_executor(self.executor)
226
227		for field in self.__dict__.values():
228			if isinstance(field, Operator):
229				field.initialize()
230
231		self.create_population()
232		self.best_of_run_ = self.population_evaluator.act(self.population)
233		self.publish('init')
234
235	def evolve_main_loop(self):
236		"""
237		Performs the evolutionary main loop
238		"""
239		# there was already "preprocessing" generation created - gen #0
240		# now create another self.max_generation generations (at maximum), starting for gen #1
241		for gen in range(1, self.max_generation + 1):
242			self.generation_num = gen
243
244			self.set_generation_seed(self.next_seed())
245			self.generation_iteration(gen)
246			if self.should_terminate(self.population,
247                                     self.best_of_run_,
248                                     self.generation_num):
249				self.final_generation_ = gen
250				self.publish('after_generation')
251				break
252			self.publish('after_generation')
253
254		self.executor.shutdown()
255
256	@abstractmethod
257	def generation_iteration(self, gen):
258		"""
259		Performs an iteration of the evolutionary main loop
260
261		Parameters
262		----------
263		gen: int
264			current generation number
265
266		Returns
267		-------
268		bool
269			True if the main loop should terminate, False otherwise
270		"""
271		raise ValueError("generation_iteration is an abstract method in class Algorithm")
272
273	@abstractmethod
274	def finish(self):
275		"""
276		Finish the evolutionary run
277		"""
278		raise ValueError("finish is an abstract method in class Algorithm")
279
280	def set_generation_seed(self, seed):
281		"""
282		Set the seed for current generation
283
284		Parameters
285		----------
286		seed: int
287			current generation seed
288		"""
289		self.random_generator.seed(seed)
290		self.generation_seed = seed
291
292	def create_population(self):
293		"""
294		Create the population for the evolutionary run
295		"""
296		self.population.create_population_individuals()
297
298	def event_name_to_data(self, event_name):
299		"""
300		Convert a given event name to relevant data of the Algorithm for the event
301
302		Parameters
303		----------
304		event_name: string
305			name of the event that is happening
306
307		Returns
308		----------
309		dict
310			Algorithm data regarding the given event
311		"""
312		if event_name == "init":
313			return {"population": self.population,
314					"statistics": self.statistics,
315					"breeder": self.breeder,
316					"termination_checker": self.termination_checker,
317					"max_generation": self.max_generation,
318					"events": self.events,
319					"max_workers": self.max_workers}
320		return {}
321
322	def set_random_generator(self, rng):
323		"""
324		Set random generator object
325
326		Parameters
327		----------
328		rng: object
329			random number generator
330		"""
331		self.random_generator = rng
332
333	def set_random_seed(self, seed=None):
334		"""
335		Set random seed
336
337		Parameters
338		----------
339		seed: int
340			random seed number
341		"""
342		self.random_generator.seed(seed)
343		self.random_seed = seed
344
345	def next_seed(self):
346		"""
347		Generate a random seed
348
349		Returns
350		----------
351		int
352			random seed number
353		"""
354		return self.random_generator.randint(SEED_MIN_VALUE, SEED_MAX_VALUE)
355
356	def should_terminate(self, population, best_of_run_, generation_num):
357		if isinstance(self.termination_checker, list):
358			return any([t.should_terminate(population, best_of_run_, generation_num) for t in self.termination_checker])
359		else:
360			return self.termination_checker.should_terminate(population, best_of_run_, generation_num)
361
362    # Necessary for valid pickling, since SimpleQueue object cannot be pickled
363	def __getstate__(self):
364		state = self.__dict__.copy()
365		del state['executor']
366		del state['random_generator']
367
368		return state
369
370	# Necessary for valid unpickling, since SimpleQueue object cannot be pickled
371	def __setstate__(self, state):
372		self.__dict__.update(state)
373		if self._executor_type == 'thread':
374			self.executor = ThreadPoolExecutor(max_workers=self.max_workers)
375		else:
376			self.executor = ProcessPoolExecutor(max_workers=self.max_workers)
377		self.random_generator = random