pygad.torchga Module

This section of the PyGAD’s library documentation discusses thepygad.utils module.

PyGAD supports different types of operators for selecting the parents,applying the crossover, and mutation. More features will be added in thefuture. To ask for a new feature, please check theAsk forFeaturesection.

The submodules in thepygad.utils module are:

  1. crossover: Has theCrossover class that implements thecrossover operators.

  2. mutation: Has theMutation class that implements the mutationoperators.

  3. parent_selection: Has theParentSelection class thatimplements the parent selection operators.

  4. nsga2: Has theNSGA2 class that implements the Non-DominatedSorting Genetic Algorithm II (NSGA-II).

Note that thepygad.GA class extends all of these classes. So, theuser can access any of the methods in such classes directly by theinstance/object of thepygad.GA class.

The next sections discuss each submodule.

pygad.utils.crossover Submodule

Thepygad.utils.crossover module has a class namedCrossoverwith the supported crossover operations which are:

  1. Single point: Implemented using thesingle_point_crossover()method.

  2. Two points: Implemented using thetwo_points_crossover() method.

  3. Uniform: Implemented using theuniform_crossover() method.

  4. Scattered: Implemented using thescattered_crossover() method.

All crossover methods accept this parameter:

  1. parents: The parents to mate for producing the offspring.

  2. offspring_size: The size of the offspring to produce.

pygad.utils.mutation Submodule

Thepygad.utils.mutation module has a class namedMutation withthe supported mutation operations which are:

  1. Random: Implemented using therandom_mutation() method.

  2. Swap: Implemented using theswap_mutation() method.

  3. Inversion: Implemented using theinversion_mutation() method.

  4. Scramble: Implemented using thescramble_mutation() method.

  5. Adaptive: Implemented using theadaptive_mutation() method.

All mutation methods accept this parameter:

  1. offspring: The offspring to mutate.

Thepygad.utils.mutation module has some helper methods to assistapplying the mutation operation:

  1. mutation_by_space(): Applies the mutation using thegene_space parameter.

  2. mutation_probs_by_space(): Uses the mutation probabilities inthemutation_probabilities instance attribute to apply themutation using thegene_space parameter. For each gene, if itsprobability is <= that the mutation probability, then it will bemutated based on the mutation space.

  3. mutation_process_gene_value(): Generate/select values for thegene that satisfy the constraint. The values could be generatedrandomly or from the gene space.

  4. mutation_randomly(): Applies the random mutation.

  5. mutation_probs_randomly(): Uses the mutation probabilities inthemutation_probabilities instance attribute to apply therandom mutation. For each gene, if its probability is <= that themutation probability, then it will be mutated randomly.

  6. adaptive_mutation_population_fitness(): A helper method tocalculate the average fitness of the solutions before applying theadaptive mutation.

  7. adaptive_mutation_by_space(): Applies the adaptive mutationbased on thegene_space parameter. A number of genes areselected randomly for mutation. This number depends on the fitnessof the solution. The random values are selected from thegene_space parameter.

  8. adaptive_mutation_probs_by_space(): Uses the mutationprobabilities to decide which genes to apply the adaptive mutationby space.

  9. adaptive_mutation_randomly(): Applies the adaptive mutationbased on randomly. A number of genes are selected randomly formutation. This number depends on the fitness of the solution. Therandom values are selected based on the 2 parametersandom_mutation_min_val andrandom_mutation_max_val.

  10. adaptive_mutation_probs_randomly(): Uses the mutationprobabilities to decide which genes to apply the adaptive mutationrandomly.

Adaptive Mutation

In the regular genetic algorithm, the mutation works by selecting asingle fixed mutation rate for all solutions regardless of their fitnessvalues. So, regardless on whether this solution has high or low quality,the same number of genes are mutated all the time.

The pitfalls of using a constant mutation rate for all solutions aresummarized in this paperLibelli, S. Marsili, and P. Alba. “Adaptivemutation in genetic algorithms.” Soft computing 4.2 (2000):76-80as follows:

The weak point of “classical” GAs is the total randomness ofmutation, which is applied equally to all chromosomes, irrespectiveof their fitness. Thus a very good chromosome is equally likely to bedisrupted by mutation as a bad one.

On the other hand, bad chromosomes are less likely to produce goodones through crossover, because of their lack of building blocks,until they remain unchanged. They would benefit the most frommutation and could be used to spread throughout the parameter spaceto increase the search thoroughness. So there are two conflictingneeds in determining the best probability of mutation.

Usually, a reasonable compromise in the case of a constant mutationis to keep the probability low to avoid disruption of goodchromosomes, but this would prevent a high mutation rate oflow-fitness chromosomes. Thus a constant probability of mutationwould probably miss both goals and result in a slow improvement ofthe population.

According toLibelli, S. Marsili, and P.Alba.work, the adaptive mutation solves the problems of constant mutation.

Adaptive mutation works as follows:

  1. Calculate the average fitness value of the population (f_avg).

  2. For each chromosome, calculate its fitness value (f).

  3. Iff<f_avg, then this solution is regarded as a low-qualitysolution and thus the mutation rate should be kept high because thiswould increase the quality of this solution.

  4. Iff>f_avg, then this solution is regarded as a high-qualitysolution and thus the mutation rate should be kept low to avoiddisrupting this high quality solution.

In PyGAD, iff=f_avg, then the solution is regarded of high quality.

The next figure summarizes the previous steps.

image1

This strategy is applied in PyGAD.

Use Adaptive Mutation in PyGAD

InPyGAD2.10.0,adaptive mutation is supported. To use it, just follow the following 2simple steps:

  1. In the constructor of thepygad.GA class, setmutation_type="adaptive" to specify that the type of mutation isadaptive.

  2. Specify the mutation rates for the low and high quality solutionsusing one of these 3 parameters according to your preference:mutation_probability,mutation_num_genes, andmutation_percent_genes. Please check thedocumentation of eachof theseparametersfor more information.

When adaptive mutation is used, then the value assigned to any of the 3parameters can be of any of these data types:

  1. list

  2. tuple

  3. numpy.ndarray

Whatever the data type used, the length of thelist,tuple, orthenumpy.ndarray must be exactly 2. That is there are just 2values:

  1. The first value is the mutation rate for the low-quality solutions.

  2. The second value is the mutation rate for the high-quality solutions.

PyGAD expects that the first value is higher than the second value andthus a warning is printed in case the first value is lower than thesecond one.

Here are some examples to feed the mutation rates:

# mutation_probabilitymutation_probability=[0.25,0.1]mutation_probability=(0.35,0.17)mutation_probability=numpy.array([0.15,0.05])# mutation_num_genesmutation_num_genes=[4,2]mutation_num_genes=(3,1)mutation_num_genes=numpy.array([7,2])# mutation_percent_genesmutation_percent_genes=[25,12]mutation_percent_genes=(15,8)mutation_percent_genes=numpy.array([21,13])

Assume that the average fitness is 12 and the fitness values of 2solutions are 15 and 7. If the mutation probabilities are specified asfollows:

mutation_probability=[0.25,0.1]

Then the mutation probability of the first solution is 0.1 because itsfitness is 15 which is higher than the average fitness 12. The mutationprobability of the second solution is 0.25 because its fitness is 7which is lower than the average fitness 12.

Here is an example that uses adaptive mutation.

importpygadimportnumpyfunction_inputs=[4,-2,3.5,5,-11,-4.7]# Function inputs.desired_output=44# Function output.deffitness_func(ga_instance,solution,solution_idx):# The fitness function calulates the sum of products between each input and its corresponding weight.output=numpy.sum(solution*function_inputs)# The value 0.000001 is used to avoid the Inf value when the denominator numpy.abs(output - desired_output) is 0.0.fitness=1.0/(numpy.abs(output-desired_output)+0.000001)returnfitness# Creating an instance of the GA class inside the ga module. Some parameters are initialized within the constructor.ga_instance=pygad.GA(num_generations=200,fitness_func=fitness_func,num_parents_mating=10,sol_per_pop=20,num_genes=len(function_inputs),mutation_type="adaptive",mutation_num_genes=(3,1))# Running the GA to optimize the parameters of the function.ga_instance.run()ga_instance.plot_fitness(title="PyGAD with Adaptive Mutation",linewidth=5)

pygad.utils.parent_selection Submodule

Thepygad.utils.parent_selection module has a class namedParentSelection with the supported parent selection operations whichare:

  1. Steady-state: Implemented using thesteady_state_selection()method.

  2. Roulette wheel: Implemented using theroulette_wheel_selection()method.

  3. Stochastic universal: Implemented using thestochastic_universal_selection()method.

  4. Rank: Implemented using therank_selection() method.

  5. Random: Implemented using therandom_selection() method.

  6. Tournament: Implemented using thetournament_selection() method.

  7. NSGA-II: Implemented using thensga2_selection() method.

  8. NSGA-II Tournament: Implemented using thetournament_selection_nsga2() method.

All parent selection methods accept these parameters:

  1. fitness: The fitness of the entire population.

  2. num_parents: The number of parents to select.

It has the following helper methods:

  1. wheel_cumulative_probs(): A helper function to calculate thewheel probabilities for these 2 methods: 1)roulette_wheel_selection() 2)rank_selection()

pygad.utils.nsga2 Submodule

Thepygad.utils.nsga2 module has a class namedNSGA2 thatimplements NSGA-II. The methods inside this class are:

  1. non_dominated_sorting(): Returns all the pareto fronts byapplying non-dominated sorting over the solutions.

  2. get_non_dominated_set(): Returns the set of non-dominatedsolutions from the passed solutions.

  3. crowding_distance(): Calculates the crowding distance for allsolutions in the current pareto front.

  4. sort_solutions_nsga2(): Sort the solutions. If the problem issingle-objective, then the solutions are sorted by sorting thefitness values of the population. If it is multi-objective, thennon-dominated sorting and crowding distance are applied to sort thesolutions.

User-Defined Crossover, Mutation, and Parent Selection Operators

Previously, the user can select the the type of the crossover, mutation,and parent selection operators by assigning the name of the operator tothe following parameters of thepygad.GA class’s constructor:

  1. crossover_type

  2. mutation_type

  3. parent_selection_type

This way, the user can only use the built-in functions for each of theseoperators.

Starting fromPyGAD2.16.0,the user can create a custom crossover, mutation, and parent selectionoperators and assign these functions to the above parameters. Thus, anew operator can be plugged easily into thePyGADLifecycle.

This is a sample code that does not use any custom function.

importpygadimportnumpyequation_inputs=[4,-2,3.5]desired_output=44deffitness_func(ga_instance,solution,solution_idx):output=numpy.sum(solution*equation_inputs)fitness=1.0/(numpy.abs(output-desired_output)+0.000001)returnfitnessga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=fitness_func)ga_instance.run()ga_instance.plot_fitness()

This section describes the expected input parameters and outputs. Forsimplicity, all of these custom functions all accept the instance of thepygad.GA class as the last parameter.

User-Defined Crossover Operator

The user-defined crossover function is a Python function that accepts 3parameters:

  1. The selected parents.

  2. The size of the offspring as a tuple of 2 numbers: (the offspringsize, number of genes).

  3. The instance from thepygad.GA class. This instance helps toretrieve any property likepopulation,gene_type,gene_space, etc.

This function should return a NumPy array of shape equal to the valuepassed to the second parameter.

The next code creates a template for the user-defined crossoveroperator. You can use any names for the parameters. Note how a NumPyarray is returned.

defcrossover_func(parents,offspring_size,ga_instance):offspring=......returnnumpy.array(offspring)

As an example, the next code creates a single-point crossover function.By randomly generating a random point (i.e. index of a gene), thefunction simply uses 2 parents to produce an offspring by copying thegenes before the point from the first parent and the remaining from thesecond parent.

defcrossover_func(parents,offspring_size,ga_instance):offspring=[]idx=0whilelen(offspring)!=offspring_size[0]:parent1=parents[idx%parents.shape[0],:].copy()parent2=parents[(idx+1)%parents.shape[0],:].copy()random_split_point=numpy.random.choice(range(offspring_size[1]))parent1[random_split_point:]=parent2[random_split_point:]offspring.append(parent1)idx+=1returnnumpy.array(offspring)

To use this user-defined function, simply assign its name to thecrossover_type parameter in the constructor of thepygad.GAclass. The next code gives an example. In this case, the custom functionwill be called in each generation rather than calling the built-incrossover functions defined in PyGAD.

ga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=fitness_func,crossover_type=crossover_func)

User-Defined Mutation Operator

A user-defined mutation function/operator can be created the same way acustom crossover operator/function is created. Simply, it is a Pythonfunction that accepts 2 parameters:

  1. The offspring to be mutated.

  2. The instance from thepygad.GA class. This instance helps toretrieve any property likepopulation,gene_type,gene_space, etc.

The template for the user-defined mutation function is given in the nextcode. According to the user preference, the function should make somerandom changes to the genes.

defmutation_func(offspring,ga_instance):...returnoffspring

The next code builds the random mutation where a single gene from eachchromosome is mutated by adding a random number between 0 and 1 to thegene’s value.

defmutation_func(offspring,ga_instance):forchromosome_idxinrange(offspring.shape[0]):random_gene_idx=numpy.random.choice(range(offspring.shape[1]))offspring[chromosome_idx,random_gene_idx]+=numpy.random.random()returnoffspring

Here is how this function is assigned to themutation_typeparameter.

ga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=fitness_func,crossover_type=crossover_func,mutation_type=mutation_func)

Note that there are other things to take into consideration like:

  • Making sure that each gene conforms to the data type(s) listed in thegene_type parameter.

  • If thegene_space parameter is used, then the new value for thegene should conform to the values/ranges listed.

  • Mutating a number of genes that conforms to the parametersmutation_percent_genes,mutation_probability, andmutation_num_genes.

  • Whether mutation happens with or without replacement based on themutation_by_replacement parameter.

  • The minimum and maximum values from which a random value is generatedbased on therandom_mutation_min_val andrandom_mutation_max_val parameters.

  • Whether duplicates are allowed or not in the chromosome based on theallow_duplicate_genes parameter.

and more.

It all depends on your objective from building the mutation function.You may neglect or consider some of the considerations according to yourobjective.

User-Defined Parent Selection Operator

No much to mention about building a user-defined parent selectionfunction as things are similar to building a crossover or mutationfunction. Just create a Python function that accepts 3 parameters:

  1. The fitness values of the current population.

  2. The number of parents needed.

  3. The instance from thepygad.GA class. This instance helps toretrieve any property likepopulation,gene_type,gene_space, etc.

The function should return 2 outputs:

  1. The selected parents as a NumPy array. Its shape is equal to (thenumber of selected parents,num_genes). Note that the number ofselected parents is equal to the value assigned to the second inputparameter.

  2. The indices of the selected parents inside the population. It is a 1Dlist with length equal to the number of selected parents.

The outputs must be of typenumpy.ndarray.

Here is a template for building a custom parent selection function.

defparent_selection_func(fitness,num_parents,ga_instance):...returnparents,fitness_sorted[:num_parents]

The next code builds the steady-state parent selection where the bestparents are selected. The number of parents is equal to the value in thenum_parents parameter.

defparent_selection_func(fitness,num_parents,ga_instance):fitness_sorted=sorted(range(len(fitness)),key=lambdak:fitness[k])fitness_sorted.reverse()parents=numpy.empty((num_parents,ga_instance.population.shape[1]))forparent_numinrange(num_parents):parents[parent_num,:]=ga_instance.population[fitness_sorted[parent_num],:].copy()returnparents,numpy.array(fitness_sorted[:num_parents])

Finally, the defined function is assigned to theparent_selection_type parameter as in the next code.

ga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=fitness_func,crossover_type=crossover_func,mutation_type=mutation_func,parent_selection_type=parent_selection_func)

Example

By discussing how to customize the 3 operators, the next code uses theprevious 3 user-defined functions instead of the built-in functions.

importpygadimportnumpyequation_inputs=[4,-2,3.5]desired_output=44deffitness_func(ga_instance,solution,solution_idx):output=numpy.sum(solution*equation_inputs)fitness=1.0/(numpy.abs(output-desired_output)+0.000001)returnfitnessdefparent_selection_func(fitness,num_parents,ga_instance):fitness_sorted=sorted(range(len(fitness)),key=lambdak:fitness[k])fitness_sorted.reverse()parents=numpy.empty((num_parents,ga_instance.population.shape[1]))forparent_numinrange(num_parents):parents[parent_num,:]=ga_instance.population[fitness_sorted[parent_num],:].copy()returnparents,numpy.array(fitness_sorted[:num_parents])defcrossover_func(parents,offspring_size,ga_instance):offspring=[]idx=0whilelen(offspring)!=offspring_size[0]:parent1=parents[idx%parents.shape[0],:].copy()parent2=parents[(idx+1)%parents.shape[0],:].copy()random_split_point=numpy.random.choice(range(offspring_size[1]))parent1[random_split_point:]=parent2[random_split_point:]offspring.append(parent1)idx+=1returnnumpy.array(offspring)defmutation_func(offspring,ga_instance):forchromosome_idxinrange(offspring.shape[0]):random_gene_idx=numpy.random.choice(range(offspring.shape[0]))offspring[chromosome_idx,random_gene_idx]+=numpy.random.random()returnoffspringga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=fitness_func,crossover_type=crossover_func,mutation_type=mutation_func,parent_selection_type=parent_selection_func)ga_instance.run()ga_instance.plot_fitness()

This is the same example but using methods instead of functions.

importpygadimportnumpyequation_inputs=[4,-2,3.5]desired_output=44classTest:deffitness_func(self,ga_instance,solution,solution_idx):output=numpy.sum(solution*equation_inputs)fitness=1.0/(numpy.abs(output-desired_output)+0.000001)returnfitnessdefparent_selection_func(self,fitness,num_parents,ga_instance):fitness_sorted=sorted(range(len(fitness)),key=lambdak:fitness[k])fitness_sorted.reverse()parents=numpy.empty((num_parents,ga_instance.population.shape[1]))forparent_numinrange(num_parents):parents[parent_num,:]=ga_instance.population[fitness_sorted[parent_num],:].copy()returnparents,numpy.array(fitness_sorted[:num_parents])defcrossover_func(self,parents,offspring_size,ga_instance):offspring=[]idx=0whilelen(offspring)!=offspring_size[0]:parent1=parents[idx%parents.shape[0],:].copy()parent2=parents[(idx+1)%parents.shape[0],:].copy()random_split_point=numpy.random.choice(range(offspring_size[0]))parent1[random_split_point:]=parent2[random_split_point:]offspring.append(parent1)idx+=1returnnumpy.array(offspring)defmutation_func(self,offspring,ga_instance):forchromosome_idxinrange(offspring.shape[0]):random_gene_idx=numpy.random.choice(range(offspring.shape[1]))offspring[chromosome_idx,random_gene_idx]+=numpy.random.random()returnoffspringga_instance=pygad.GA(num_generations=10,sol_per_pop=5,num_parents_mating=2,num_genes=len(equation_inputs),fitness_func=Test().fitness_func,parent_selection_type=Test().parent_selection_func,crossover_type=Test().crossover_func,mutation_type=Test().mutation_func)ga_instance.run()ga_instance.plot_fitness()