Genetic Algorithm in Python
Genetic algorithms (GAs) are designed to address finite and unconstrained optimization problems by modeling natural selection. These algorithms can solve NP-hard optimization problems that are beyond the scope of traditional approaches, saving time and money. The foundation of GAs is a comparison between biological evolution and human chromosomal behavior.This article offers a sample of code that shows how to establish a generic GA and offload a computation to a GPU using numba-dpex for Intel Distribution for Python.
Genetically-Based Algorithms
GA-specific activities
Three essential biology-inspired processes—selection, crossover, and mutation—can be used to produce high-quality GA outputs. Before using GAs to address a specific problem, it is important to define the chromosomal representation and the GA processes.Choosing
This is the process of selecting a mate and reuniting them to have offspring. Parent selection is essential to the convergence rate of GA because good parents inspire their kids to come up with better and more suitable replies.An example of the selection process, which reduces the number of chromosomes in the next generation by half, is shown in Figure 1.
Selection typically requires additional algorithms to determine which chromosomes will become parents.
Transition
This process is known as biological crossover. In this instance, more than one parent is selected, and one or more offspring are created using the genetic material of the parents.
Figure 2: An example of a crossover operation.
Figure 2 illustrates how the crossover process creates child genomes from certain parent chromosomes. The single child genome that has been created may be a one-point crossover. The child receives half of its DNA from each of its parents.
Change
A little, random alteration on the chromosome might provide a unique response. It is used to conserve and increase genetic variety in the population and is often administered with minimal likelihood.- A mutation process with a single chromosomal value alteration is shown in Figure 3.
- A chromosome may be altered by the mutation process, as figure 3 illustrates.
- Improve Python Genetic Algorithms with Intel Distribution
Developers may utilize Intel Distribution for Python to get near-native code performance with libraries like Intel oneAPI Math Kernel Library (oneMKL) and Intel oneAPI Data Analytics Library (oneDAL). Researchers and developers may extend compute-intensive Python programs from laptops to powerful servers with enhanced NumPy, SciPy, and Numba.
Utilizing the Intel Distribution for Python, optimize the evolutionary algorithm using the Data Parallel Extension for Numba (numba-dpex) range kernel. This kernel's work items each represent a logical thread of execution, which is the most fundamental kind of data parallelism and parallelism among a set of work items.
Let us see an example of the implementation of the kernel for a vector-add operation:
import DPNPA
bring in numba_dpex
@numba_dpex.kernel
def vector_add(a, b, c, item: numba_dpex.kernel_api.Item):
I equals item.get_id(0)
a[i] + b[i] = c[i]
To run this code, create the three vectors, a, b, and c. The result of the operation is saved in c, and data is entered into a and b. Next, the kernel has to be run as follows once the vectors are transmitted to a specific device, such a GPU:
1024 is N.
Ones(N, device="gpu") = dpnp.a
B is equal to dpnp.ones_like(a, device="gpu")
c is equal to dpnp.zeros_like(a, device="gpu")
vector_add, numba_dpex.kernel_api.Range(N), a, b, c) and numba_dpex.call_kernel
In the previous code, vector c contained the result of the vector-add operation, which was executed on a GPU. Likewise, for all other functions and methods, the implementation is the same.
Code Performance
To learn how to create the generic GA and optimize the procedure to run on GPUs using numba-dpex for Intel Distribution for Python, see the code example. Additionally, it explains how to use the different GA operationscrossover, mutation, and selection as well as how to adapt these methods to address different optimization problems.In order to initialize the population, set the following values:
- There are five thousand residents.
- A chromosome's size is 10
- Generations: 5
On each chromosome, there are 10 random floats ranging from 0 to 1.
- Putting the GA into action requires creating an evaluation plan. Numba-dpex uses this function as a reference and point of comparison. Any combination of algebraic chromosomal operations is used to calculate an individual's fitness.
- Execute the crossover procedure: First and second parents to two different chromosomes are the inputs. The function returns one more chromosome as its output.
- Execute the mutation operation: In this code example, there is a one percent chance that each float in the chromosome will be swapped out for a random value.
- Apply the selection procedure, which serves as the basis for creating a new generation. Within this function, a new population is created after crossover and mutation processes.
- Start the CPU functions that have been prepared, starting with a baseline. The following procedures are used in every generation to create the initial population:
- We assess the present population using the eval_genomes_plain function.
- Make the next generation by using a next_generation function.
- Since a new generation has already been created, wipe fitness norms.
- The calculating time for such processes is measured and printed. The first chromosome is also shown to show that the computations performed on the CPU and GPU were identical.
- Run on a GPU: Start with a new population initialization and then write an evaluation function for the GPU (just as in step 2). The only difference between CPU and GPU implementation is that the former uses a flattened data structure to represent chromosomes. Use numba-dpex kernels and a global index as well to prevent looping across all chromosomes.
- Just as with the CPU, the time spent on assessment, generation production, and fitness wipe is tracked when a GPU is in use. Deliver every chromosome to the designated gadget along with the fitness container. Following that, a kernel inside a certain range may be used.
In summary
Apply the same techniques to further optimization problems. Explain the processes involved in chromosomal crossing, mutation, evaluation, and selection. The whole algorithm is run in the same manner.Run the code example above to see how well this approach works when running in parallel on a GPU and sequentially on a CPU. The code result demonstrates that performance speed is increased while using a GPU-based numba-dpex parallel implementation.
0 Comments