sampo.scheduler.genetic.operators#

Overview#

Classes#
`FitnessFunction`	Base class for description of different fitness functions.
`TimeFitness`	Fitness function that relies on finish time.
`TimeAndResourcesFitness`	Fitness function that relies on finish time and the set of resources.
`DeadlineResourcesFitness`	The fitness function is dependent on the set of resources and requires the end time to meet the deadline.
`DeadlineCostFitness`	The fitness function is dependent on the cost of resources and requires the end time to meet the deadline.
`IndividualType`	Class to define a type of individual in genetic algorithm

Function#
`init_toolbox`(wg, contractors, worker_pool, landscape, index2node, work_id2index, worker_name2index, index2contractor_obj, init_chromosomes, mut_order_pb, mut_res_pb, population_size, rand, spec, worker_pool_indices, contractor2index, contractor_borders, node_indices, parents, resources_border, assigned_parent_time, work_estimator)	Object, that include set of functions (tools) for genetic model and other functions related to it.
`copy_chromosome`(chromosome)	-
`generate_population`(n, wg, contractors, spec, work_id2index, worker_name2index, contractor2index, contractor_borders, init_chromosomes, rand, work_estimator, landscape)	Generates population.
`generate_chromosome`(wg, contractors, work_id2index, worker_name2index, contractor2index, contractor_borders, init_chromosomes, spec, rand, work_estimator, landscape)	It is necessary to generate valid scheduling, which are satisfied to current dependencies
`select_new_population`(population, pop_size)	Selection operator for genetic algorithm.
`is_chromosome_correct`(chromosome, node_indices, parents, contractor_borders)	Check correctness of works order and contractors borders.
`is_chromosome_order_correct`(chromosome, parents)	Checks that assigned order of works are topologically correct.
`is_chromosome_contractors_correct`(chromosome, work_indices, contractor_borders)	Checks that assigned contractors can supply assigned workers.
`get_order_part`(order, other_order)	Get a new part in topologic order for chromosome.
`mate_scheduling_order`(ind1, ind2, rand, copy)	Two-Point crossover for order.
`mutate_scheduling_order`(ind, mutpb, rand, parents)	Mutation operator for order.
`mate_resources`(ind1, ind2, optimize_resources, rand, copy)	One-Point crossover for resources.
`mutate_resources`(ind, mutpb, rand, resources_border)	Mutation function for resources.
`mate`(ind1, ind2, optimize_resources, rand)	Combined crossover function of Two-Point crossover for order and One-Point crossover for resources.
`mutate`(ind, resources_border, parents, order_mutpb, res_mutpb, rand)	Combined mutation function of mutation for order and mutation for resources.
`mutate_resource_borders`(ind, mutpb, rand, contractor_borders)	Mutation for contractors’ resource borders.
`mutate_values`(chromosome_part, row_indexes, col_indexes, low_borders, up_borders, masks, mut_part, rand)	Changes numeric values in m x n part of chromosome.
`update_resource_borders_to_peak_values`(ind, schedule, worker_name2index, contractor2index)	Changes the resource borders to the peak values obtained in the schedule.

Attributes#
`Individual`	-

Classes#

class sampo.scheduler.genetic.operators.FitnessFunction(deadline: sampo.schemas.time.Time | None)#

Bases: abc.ABC

Base class for description of different fitness functions.

abstract evaluate(schedules: list[sampo.schemas.schedule.Schedule]) → list[int]#: Calculate the value of fitness function of the all schedules. It is better when value is less.

class sampo.scheduler.genetic.operators.TimeFitness(deadline: sampo.schemas.time.Time | None = None)#

Bases: FitnessFunction

Fitness function that relies on finish time.

evaluate(schedules: list[sampo.schemas.schedule.Schedule]) → list[int]#: Calculate the value of fitness function of the all schedules. It is better when value is less.

class sampo.scheduler.genetic.operators.TimeAndResourcesFitness(deadline: sampo.schemas.time.Time | None = None)#

Bases: FitnessFunction

Fitness function that relies on finish time and the set of resources.

evaluate(schedules: list[sampo.schemas.schedule.Schedule]) → list[int]#: Calculate the value of fitness function of the all schedules. It is better when value is less.

class sampo.scheduler.genetic.operators.DeadlineResourcesFitness(deadline: sampo.schemas.time.Time)#

Bases: FitnessFunction

The fitness function is dependent on the set of resources and requires the end time to meet the deadline.

evaluate(schedules: list[sampo.schemas.schedule.Schedule]) → list[int]#: Calculate the value of fitness function of the all schedules. It is better when value is less.

class sampo.scheduler.genetic.operators.DeadlineCostFitness(deadline: sampo.schemas.time.Time)#

Bases: FitnessFunction

The fitness function is dependent on the cost of resources and requires the end time to meet the deadline.

evaluate(schedules: list[sampo.schemas.schedule.Schedule]) → list[int]#: Calculate the value of fitness function of the all schedules. It is better when value is less.

class sampo.scheduler.genetic.operators.IndividualType#

Bases: enum.Enum

Class to define a type of individual in genetic algorithm

Population = 'population'#

Offspring = 'offspring'#

Functions#

sampo.scheduler.genetic.operators.init_toolbox(wg: sampo.schemas.graph.WorkGraph, contractors: list[sampo.schemas.contractor.Contractor], worker_pool: sampo.schemas.contractor.WorkerContractorPool, landscape: sampo.schemas.landscape.LandscapeConfiguration, index2node: dict[int, sampo.schemas.graph.GraphNode], work_id2index: dict[str, int], worker_name2index: dict[str, int], index2contractor_obj: dict[int, sampo.schemas.contractor.Contractor], init_chromosomes: dict[str, tuple[sampo.scheduler.genetic.converter.ChromosomeType, float, sampo.schemas.schedule_spec.ScheduleSpec]], mut_order_pb: float, mut_res_pb: float, population_size: int, rand: random.Random, spec: sampo.schemas.schedule_spec.ScheduleSpec, worker_pool_indices: dict[int, dict[int, sampo.schemas.resources.Worker]], contractor2index: dict[str, int], contractor_borders: numpy.ndarray, node_indices: list[int], parents: dict[int, set[int]], resources_border: numpy.ndarray, assigned_parent_time: sampo.schemas.time.Time = Time(0), work_estimator: sampo.schemas.time_estimator.WorkTimeEstimator = DefaultWorkEstimator()) → deap.base.Toolbox#

Object, that include set of functions (tools) for genetic model and other functions related to it. list of parameters that received this function is sufficient and complete to manipulate with genetic algorithm

Returns:: Object, included tools for genetic algorithm

sampo.scheduler.genetic.operators.copy_chromosome(chromosome: sampo.scheduler.genetic.converter.ChromosomeType) → sampo.scheduler.genetic.converter.ChromosomeType#

sampo.scheduler.genetic.operators.generate_population(n: int, wg: sampo.schemas.graph.WorkGraph, contractors: list[sampo.schemas.contractor.Contractor], spec: sampo.schemas.schedule_spec.ScheduleSpec, work_id2index: dict[str, int], worker_name2index: dict[str, int], contractor2index: dict[str, int], contractor_borders: numpy.ndarray, init_chromosomes: dict[str, tuple[sampo.scheduler.genetic.converter.ChromosomeType, float, sampo.schemas.schedule_spec.ScheduleSpec]], rand: random.Random, work_estimator: sampo.schemas.time_estimator.WorkTimeEstimator = None, landscape: sampo.schemas.landscape.LandscapeConfiguration = LandscapeConfiguration()) → list[Individual]#: Generates population. Do not use generate_chromosome function.

sampo.scheduler.genetic.operators.generate_chromosome(wg: sampo.schemas.graph.WorkGraph, contractors: list[sampo.schemas.contractor.Contractor], work_id2index: dict[str, int], worker_name2index: dict[str, int], contractor2index: dict[str, int], contractor_borders: numpy.ndarray, init_chromosomes: dict[str, tuple[sampo.scheduler.genetic.converter.ChromosomeType, float, sampo.schemas.schedule_spec.ScheduleSpec]], spec: sampo.schemas.schedule_spec.ScheduleSpec, rand: random.Random, work_estimator: sampo.schemas.time_estimator.WorkTimeEstimator = DefaultWorkEstimator(), landscape: sampo.schemas.landscape.LandscapeConfiguration = LandscapeConfiguration()) → Individual#: It is necessary to generate valid scheduling, which are satisfied to current dependencies That’s why will be used the approved order of works (HEFT order and Topological sorting) Topological sorts are generating always different HEFT is always the same(now not) HEFT we will choose in 30% of attempts Topological in others

sampo.scheduler.genetic.operators.select_new_population(population: list[sampo.scheduler.genetic.converter.ChromosomeType], pop_size: int) → list[sampo.scheduler.genetic.converter.ChromosomeType]#: Selection operator for genetic algorithm. Select top n individuals in population.

sampo.scheduler.genetic.operators.is_chromosome_correct(chromosome: sampo.scheduler.genetic.converter.ChromosomeType, node_indices: list[int], parents: dict[int, set[int]], contractor_borders: numpy.ndarray) → bool#: Check correctness of works order and contractors borders.

sampo.scheduler.genetic.operators.is_chromosome_order_correct(chromosome: sampo.scheduler.genetic.converter.ChromosomeType, parents: dict[int, set[int]]) → bool#: Checks that assigned order of works are topologically correct.

sampo.scheduler.genetic.operators.is_chromosome_contractors_correct(chromosome: sampo.scheduler.genetic.converter.ChromosomeType, work_indices: Iterable[int], contractor_borders: numpy.ndarray) → bool#: Checks that assigned contractors can supply assigned workers.

sampo.scheduler.genetic.operators.get_order_part(order: numpy.ndarray, other_order: numpy.ndarray) → numpy.ndarray#: Get a new part in topologic order for chromosome. This function is needed to make crossover for order.

sampo.scheduler.genetic.operators.mate_scheduling_order(ind1: sampo.scheduler.genetic.converter.ChromosomeType, ind2: sampo.scheduler.genetic.converter.ChromosomeType, rand: random.Random, copy: bool = True) → tuple[sampo.scheduler.genetic.converter.ChromosomeType, sampo.scheduler.genetic.converter.ChromosomeType]#

Two-Point crossover for order.

Parameters:

ind1 – first individual
ind2 – second individual
rand – the rand object used for randomized operations
copy – if True individuals will be copied before mating so as not to change them

Returns:

two mated individuals

sampo.scheduler.genetic.operators.mutate_scheduling_order(ind: sampo.scheduler.genetic.converter.ChromosomeType, mutpb: float, rand: random.Random, parents: dict[int, set[int]]) → sampo.scheduler.genetic.converter.ChromosomeType#

Mutation operator for order. Swap neighbors.

Parameters:

ind – the individual to be mutated
mutpb – probability of gene mutation
rand – the rand object used for randomized operations
parents – mapping object of works and their parent-works to create valid order

Returns:

mutated individual

sampo.scheduler.genetic.operators.mate_resources(ind1: sampo.scheduler.genetic.converter.ChromosomeType, ind2: sampo.scheduler.genetic.converter.ChromosomeType, optimize_resources: bool, rand: random.Random, copy: bool = True) → tuple[sampo.scheduler.genetic.converter.ChromosomeType, sampo.scheduler.genetic.converter.ChromosomeType]#

One-Point crossover for resources.

Parameters:

ind1 – first individual
ind2 – second individual
optimize_resources – if True resource borders should be changed after mating
rand – the rand object used for randomized operations
copy – if True individuals will be copied before mating so as not to change them

Returns:

two mated individuals

sampo.scheduler.genetic.operators.mutate_resources(ind: sampo.scheduler.genetic.converter.ChromosomeType, mutpb: float, rand: random.Random, resources_border: numpy.ndarray) → sampo.scheduler.genetic.converter.ChromosomeType#

Mutation function for resources. It changes selected numbers of workers in random work in a certain interval for this work.

Parameters:

ind – the individual to be mutated
resources_border – low and up borders of resources amounts
mutpb – probability of gene mutation
rand – the rand object used for randomized operations

Returns:

mutated individual

sampo.scheduler.genetic.operators.mate(ind1: sampo.scheduler.genetic.converter.ChromosomeType, ind2: sampo.scheduler.genetic.converter.ChromosomeType, optimize_resources: bool, rand: random.Random) → tuple[sampo.scheduler.genetic.converter.ChromosomeType, sampo.scheduler.genetic.converter.ChromosomeType]#

Combined crossover function of Two-Point crossover for order and One-Point crossover for resources.

Parameters:

ind1 – first individual
ind2 – second individual
optimize_resources – if True resource borders should be changed after mating
rand – the rand object used for randomized operations

Returns:

two mated individuals

sampo.scheduler.genetic.operators.mutate(ind: sampo.scheduler.genetic.converter.ChromosomeType, resources_border: numpy.ndarray, parents: dict[int, set[int]], order_mutpb: float, res_mutpb: float, rand: random.Random) → sampo.scheduler.genetic.converter.ChromosomeType#

Combined mutation function of mutation for order and mutation for resources.

Parameters:

ind – the individual to be mutated
resources_border – low and up borders of resources amounts
parents – mapping object of works and their parent-works to create valid order
order_mutpb – probability of order’s gene mutation
res_mutpb – probability of resources’ gene mutation
rand – the rand object used for randomized operations

Returns:

mutated individual

sampo.scheduler.genetic.operators.mutate_resource_borders(ind: sampo.scheduler.genetic.converter.ChromosomeType, mutpb: float, rand: random.Random, contractor_borders: numpy.ndarray) → sampo.scheduler.genetic.converter.ChromosomeType#

Mutation for contractors’ resource borders.

Parameters:

ind – the individual to be mutated
contractor_borders – up borders of contractors capacity
mutpb – probability of gene mutation
rand – the rand object used for randomized operations

Returns:

mutated individual

sampo.scheduler.genetic.operators.mutate_values(chromosome_part: numpy.ndarray, row_indexes: numpy.ndarray, col_indexes: numpy.ndarray, low_borders: numpy.ndarray, up_borders: numpy.ndarray, masks: numpy.ndarray, mut_part: int, rand: random.Random) → None#: Changes numeric values in m x n part of chromosome. This function is needed to make mutation for resources and resource borders.

sampo.scheduler.genetic.operators.update_resource_borders_to_peak_values(ind: sampo.scheduler.genetic.converter.ChromosomeType, schedule: sampo.schemas.schedule.Schedule, worker_name2index: dict[str, int], contractor2index: dict[str, int])#

Changes the resource borders to the peak values obtained in the schedule.

Parameters:

ind – the individual to be updated
schedule – schedule obtained from the individual
worker_name2index – mapping object of resources and their index in chromosome
contractor2index – mapping object of contractors and their index in chromosome

Returns:

individual with updated resource borders

Attributes#

sampo.scheduler.genetic.operators.Individual#