timor.configuration_search.GA
Classes
This class provides an interface to optimize assemblies with genetic algorithms using a custom fitness function. |
|
Classifies the different methods to count the progress in a GA optimization. |
Functions
|
Returns the progress of a genetic algorithm in [ProgressUnit] units. |
Module Contents
- class timor.configuration_search.GA.GA(db, custom_hp=None, mutation_weights=None, rng=None)
This class provides an interface to optimize assemblies with genetic algorithms using a custom fitness function.
The idea of a genetic algorithm is to mimic the process of natural selection and evolution to solve optimization problems. It involves creating a population of potential solutions (chromosomes), applying genetic operators like crossover and mutation to generate offsprings, evaluating their fitness, and selecting the fittest individuals for the next generation. Here, our target is to select candidate modules from a module base and assemble them in a sequence aiming to minimize a user-specified fitness function.The iterative process ends after a pre-defined number of iterations.
Currently, this class is limited to modules that have exactly two connectors, so it can only be used for the assembly of serial kinematic chains.
Initialize the GA optimizer by performing necessary pre-computations once a DB is provided.
The initialization itself does not perform any optimization and is computationally cheap. To start the actual optimization, call the optimize() method.
- Parameters:
db (Union[str, timor.ModulesDB]) – Either the name of a ModulesDB or a ModulesDB instance that will be used for the GA. The operators for the genetic optimization expect each module to have exactly two connectors – if the DB contains any modules with more or less connectors, this method will raise an error.
custom_hp (Optional[Dict[str, any]]) – A dictionary of custom hyperparameters that will be used instead of the default ones. For more hyperparameters see reference: https://pygad.readthedocs.io/en/latest/pygad.html#pygad-ga-class.
mutation_weights (Optional[Dict[str, float]]) – Maps a module ID or the EMPTY ID to a weight that determines how likely it is to be chosen as a replacement during mutation. If None, all modules have the same weight.
rng (Optional[numpy.random.Generator]) – A numpy random number generator. If None, a new one will be created.
- G: networkx.MultiDiGraph
- __empty_slot = 'EMPTY'
- static _chain_callbacks(original_callback=None, optional_callbacks=())
This is a helper function to create a single callback function from a sequence of callable objects.
The order of the callbacks is preserved, with the original callback being called first. If any of the optional callbacks returns False, the callback chain is terminated and “stop” is returned which will stop the GA.
- Parameters:
original_callback (Optional[Callable[[pygad.GA], any]]) – The original callback function - this function can return any value, but any value other than “stop” will be ignored by pygad.
optional_callbacks (Sequence[Callable[[pygad.GA], any]]) – A sequence of optional callbacks. Each callback should return True to continue the callback chain, or either False or ‘stop’ to stop the callback chain.
- Return type:
Callable[[pygad.GA], Optional[str]]
- _get_candidate_assembly(module_ids)
Perform pre-computation for the fitness function.
It converts the solution from integer encodings to IDs and assembles the modules in a chain.
- Parameters:
module_ids (Tuple[str]) – The solution to be evaluated, encoded as module ids.
- Return type:
timor.ModuleAssembly
- _get_initial_population(population_size, module_weights=None)
Generates the initial population for the genetic algorithm.
It returns a list of chromosomes, where each chromosome represents a potential solution. It extends the shortest paths to a desired length by successively adding detours of length 1. Each chromosome is a list of genes, where each gene represents a module. The first gene is the base, the last gene is the end effector, and the genes in between are links and joints. The length of the chromosome equals to the gene_len.
- Parameters:
population_size (Tuple[int, int]) – The size of the initial population as a tuple of (num_offsprings, num_genes).
module_weights (Optional[Dict[str, float]]) – A dictionary, mapping each module ID in the database to be optimized to a weight that determines how likely it is to be chosen as a replacement during mutation.
- Return type:
- _map_genes_to_id(genome)
Maps a list of gene encodings to the corresponding tuple of module IDs.
- assembly_cache: timor.utilities.dtypes.LimitedSizeMap[Tuple[str], timor.ModuleAssembly]
- check_individual(individual)
Checks whether an integer-encoded individual (i.e. a module sequence) can be assembled.
- Parameters:
individual (numpy.ndarray) – The individual/offspring to be checked. Notice it consists of integers, not IDs.
- Returns:
True of the offspring is valid, False otherwise.
- Return type:
- create_gene_space(run_hp)
Create gene space and type for pygad.
- fitness_cache: timor.utilities.dtypes.LimitedSizeMap[Tuple[str], float]
- make_visualization_callback(viz=None, task=None, save_at=None, file_format='html', every_n_generations=10, checkmark_successful=False)
Creates a callback function that can be passed to the GA optimizer to visualize solution candidates.
The callback function will be called every n generations and will visualize the best solution candidate of that generation. If multiple candidates achieve the best fitness, one will be selected at random.
- Parameters:
viz (Optional[timor.utilities.visualization.MeshcatVisualizer]) – A meshcat visualizer instance. If None, a new visualizer will be created.
task (Optional[timor.Task.Task]) – If given, a candidate assembly will be visualized in the context of the given task.
save_at (Optional[Union[str, pathlib.Path]]) – Per default, the visualization is only shown in the browser. If a path to a directory is given, all visualizations will be saved in there as static HTML or PNG.
file_format (str) – If save_at is given, this parameter determines the format of the saved visualizations. Can be either ‘html’ or ‘png’. While html works “headless” without opening a browser, png enforces opening a viewer and cannot be used on a remote server. However, html files are much larger than png files.
every_n_generations (int) – Every nth generation, a visualization will be created.
checkmark_successful (bool) – If True, a checkmark will be added to every goal that was achieved in the task.
- Return type:
Callable[[pygad.GA], bool]
- mutation(population, ga_instance)
Performs mutation on each chromosome of the offspring by randomly selecting genes and replacing them.
The replacement is based on finding modules with the same connectors as the initial module, and the replacement candidate is chosen randomly. Notice offspring contains integers not IDs.
- Parameters:
population (numpy.ndarray) – The offspring to be mutated.
ga_instance (pygad.GA) – The instance of pygad.GA class.
- Return type:
- optimize(fitness_function, hp=None, progress_bar=True, debug_logging_frequency=10, sane_keyboard_interrupt=True, timeout=None, wandb_run=None, progress_unit=ProgressUnit.GENERATIONS, steps_at_start=0, selection_type='sss', **ga_kwargs)
Perform optimization utilizing a GA by trying to optimize the fitness function over module assemblies.
Users can specify the hyperparameters for the GA. If not specified, the default hyperparameters will be used.
- Ref:
- Parameters:
fitness_function (Callable[[timor.ModuleAssembly, pygad.GA, int], Union[float, timor.utilities.dtypes.Lexicographic]]) – the fitness function for the GA. It should take three arguments: a ModuleAssembly which is to be evaluated as well as the GA instance and the index of the solution in the population. It is up to the user which of these arguments are used in the fitness function.
hp (Optional[dict]) – Optional hyperparameters overriding the user and default hyperparameters.
progress_bar (bool) – If True, a tqdm progress bar over the numbers of generations completed will be shown.
debug_logging_frequency (Optional[int]) – If specified, internal debug metrics will be logged every full n progress units.
sane_keyboard_interrupt (bool) – If True, the GA will be stopped when a keyboard interrupt is received, but the exception will not be raised.
timeout (Optional[float]) – If specified, the GA will be stopped after the specified number of seconds.
wandb_run – You can optionally pass a Weights and Biases run instance to log the results. A run instance can be obtained by calling wandb.init() before calling this function.
progress_unit (ProgressUnit) – The metric to be used for tracking performance metrics, e.g. for logging or wandb.
steps_at_start (int) – The value of the progress unit at the first generation. This is useful if you want to continue a run that was interrupted or if multiple runs should be tracked “as one”.
selection_type (str) – The type of parent selection to be used. The options defined in pyGAD include ‘sss’, ‘rws’, ‘sus’, ‘rank’, ‘tournament’, ‘random’. Notice that use a customized rank-based selection function can be beneficial for diversity in the population and avoiding premature convergence to suboptimal solutions.
ga_kwargs – Additional keyword arguments to be passed to the pygad.GA class that do not qualify as hyperparameters (so anything that should not be logged as a hyperparameter, e.g., callbacks).
- Return type:
pygad.GA
- rank_based_selection(fitness, num_parents, ga_instance)
Selects the parents using a rank-based selection process.
- Source:
https://en.wikipedia.org/wiki/Selection_(genetic_algorithm). The original paper for linear ranking: - Baker, James E. (1985), Grefenstette, John J. (ed.), “Adaptive Selection Methods for Genetic Algorithms”, Conf. Proc. of the 1st Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 101–111, ISBN 0-8058-0426-9 - Baker, James E. (1987), Grefenstette, John J. (ed.), “Reducing Bias and Inefficiency in the Selection Algorithm”, Conf. Proc. of the 2nd Int. Conf. on Genetic Algorithms and Their Applications (ICGA), Hillsdale, New. Jersey: L. Erlbaum Associates, pp. 14–21, ISBN 0-8058-0158-8
- Parameters:
fitness (numpy.ndarray) – A list of fitness values of the current population. Its shape is 1D array with length equal to
num_parents (int)
ga_instance (pygad.GA)
- Return type:
Tuple[numpy.ndarray, numpy.ndarray]
the number of individuals, while each element is a ‘Lexicographic’ object encompassing multiple values. :param num_parents: The number of parents to select. :param ga_instance: An instance of the pygad.GA class. :return: 1. The selected parents as a numpy array. Its shape is (the number of selected parents, num_genes). Note that the number of selected parents is equal to num_parents. 2. The indices of the selected parents inside the population. It is a 1D list with length equal to the number of selected parents.
- rng: numpy.random.Generator = None
- single_valid_crossover(parents, offspring_size, ga_instance)
Performs single-point crossover between parents to create new offspring.
Generally speaking, the genetic section after the split point in ‘parent1’ is replaced with the genetic section after the same split point in ‘parent2’. Notice parents consists of integers not IDs.
- Params parents:
Indicates the whole parental generation of genetic sections.
- Params offspring_size:
Indicates the size of the offspring, which is a tuple of (num_offsprings, num_genes).
- Params ga_instance:
The instance of pygad.GA class.
- Parameters:
parents (numpy.ndarray)
offspring_size (Tuple)
ga_instance (pygad.GA)
- Return type:
- sp
- class timor.configuration_search.GA.ProgressUnit(*args, **kwds)
Classifies the different methods to count the progress in a GA optimization.
- GENERATIONS = 0
- INDIVIDUALS = 1
- SECONDS = 2
- timor.configuration_search.GA.get_ga_progress(unit, ga_inst=None, t0=0, generation_bias=0)
Returns the progress of a genetic algorithm in [ProgressUnit] units.
- Parameters:
unit (ProgressUnit) – The unit to count the progress in.
ga_inst (Optional[pygad.GA]) – The pygad.GA instance to get the progress from. Necessary for GENERATIONS and INDIVIDUALS.
t0 (Optional[float]) – The start time of the optimization. Necessary for SECONDS.
generation_bias (int) – The “generation” to start counting from
- Return type: