The genetic algorithm is inspired by the biological evolution of chromosomes and this is majorly used in optimal feature selection for various kinds of problems. The genetic algorithm basically follows the heuristic algorithms approach to find the best possible solution close to the optimal solution. This algorithm has a variety of applications across the fields, most in optimization problems. It can also be used for image reconstruction to obtain the images in their original form. This article is focused on applying the genetic algorithm for this interesting application of image reconstruction.

Table of Contents

1. An introduction to genetic algorithms
2. What is image reconstruction?
3. Image reconstruction using genetic algorithms
4. Summary

An introduction to genetic algorithms

Genetic algorithms are basically used in optimization tasks where these algorithms follow the metaheuristic approach to obtain the best optimal solution among all the candidate solutions. Genetic algorithms operate on the hierarchy of biological chromosomes and the algorithm tries to obtain the best fittest solution to be passed on to the next generation.

Are you looking for a complete repository of Python libraries used in data science, check out here.

Genetic algorithms initially operate on a cluster of the best possible solutions called the initial population where the cluster contains the best possible solution to the problem. Each of the solutions in the cluster is categorized by certain parameters and they are termed Genes in genetic algorithms the genes in the genetic algorithm will be ranked according to the parameters set. The genes which have all the abilities set will be passed on to a fitness function to determine the fitness of the best possible solutions selected from the cluster of candidate solutions to the problem. If the best possible solution has the ability to inherit all the functionality of the fitness function that solution will be passed on to the next set of generations. The overall operation of genetic algorithms happens at three levels they are Selection, Mutation, and Crossover. Let us try to understand these standard terminologies of genetic algorithms.

Selection

Selection in genetic algorithms is a standard terminology used for selecting the best possible solution among the candidate solutions. Selection plays an important role in genetic algorithms as it would be responsible for selecting the best possible solutions, which would be passed on to the next generations for further process. So the selection phase in genetic algorithms is a very important phase in genetic algorithms.

Crossover

The crossover phase of the genetic algorithm is basically responsible for setting a certain threshold at random places in Genes and the crossover will be responsible for exchanging genes between the two random solutions obtained in the Selection phase. So the information has to be passed over the individual solutions until the crossover for the genes is reached.

Mutation

The mutation phase in genetic algorithms ensures crossover occurs with higher random probability within the genes. So the mutation will be responsible for setting higher random threshold values in the genes so that information passed over between the solutions is considerable and the Mutation phase is also required to maintain diversity between the best possible solutions selected for the problem.

What is image reconstruction?

Image reconstruction is an iterative process of evolving through the various pixels of images and an attempt to obtain the original image through evolution. Image reconstruction finds its major applications in medical imaging, reverse imaging, and original image restoration tasks. 

In a similar way, genetic algorithms can be used for image reconstruction wherein the algorithm tries to reconstruct the image close to the original image. Genetic algorithms basically follow a metaheuristic-based approach and the algorithm iterates over the best possible ways to reconstruct the image close to the original image. Pygad is one such library of genetic algorithms which is structured and designed to reconstruct images close to the original image.

Image reconstruction using Genetic Algorithm

Image reconstruction in genetic algorithms can be taken up using the Pygad library which is specially designed for image reconstruction using the genetic algorithm principles.

So let us see how to carry out image reconstruction using Pygad.

Let us first install the library and import the library into the working environment.

!pip install pygad
import pygad

As the library is imported into the working environment let us visualize the original image using the matplotlib library.

import matplotlib.pyplot as plt
img=plt.imread('/content/drive/MyDrive/Colab notebooks/GA_Img_reconstruction/tiger.jpeg')
plt.imshow(img)
plt.show()

The image has to be scaled down to standard scale values for passing the original image to the genetic algorithm. So let us scale the image using the numpy library.

img = np.asarray(img/255, dtype=np.float)

Once the image is scaled we will have to use a library named GARI [Genetic Algorithm for Reproducing Image] which is a library designed for decomposing the original image into chromosomes and also reshaping the original image accordingly it can be passed onto the genetic algorithms. So GARI can be said to be one of the submodules of Pygad and it has to be made available in the working environment by cloning into the respective Github repository.

!git clone 'https://github.com/ahmedfgad/GARI'
%cd /content/drive/MyDrive/Colab notebooks/GA_Img_reconstruction/GARI
import gari

So once the gari library is imported into the working environment the library has to be used to decompose the image into chromosomes which will be in the cluster of the initial population of the best possible image to be reconstructed close to the original image. So let us look at how to decompose the original image into a set of possible reconstruction images.

target_chromosome = gari.img2chromosome(img)

So here “img2chromosome” function has to be used to decompose the original image into the best possible reconstruction images. So once the original image is reconstructed we will have to create a fitness function to produce only the fittest solutions that can be passed onto the Pygad instance for reconstructing the image. So let us create a fitness function that considers the maximum difference between the original image and the reconstructed image so that the image reconstructed would be close to the original image. 

def fitness_fun(solution, solution_idx):
 fitness = np.sum(np.abs(target_chromosome-solution))
 fitness = np.sum(target_chromosome) - fitness
 return fitness

So here a user-defined function is used to create a fitness function that will be responsible for producing a fitness score which is used to cross-validate the fitness score among the candidate solutions in the population and the solutions that pass the fitness score will be considered for the mutation to reconstruct the image.

Let us now create a genetic algorithm instance using Pygad with certain parameters being declared for efficient optimization and to reconstruct the image close to the original image.

ga_instance = pygad.GA(num_generations=15000,
                      num_parents_mating=4,
                      fitness_func=fitness_fun,
                      sol_per_pop=10,
                      num_genes=img.size,
                      init_range_low=0.0,
                      init_range_high=1.0,
                      mutation_percent_genes=0.01,
                      mutation_type="random",
                      mutation_by_replacement=True,
                      random_mutation_min_val=0.0,
                      random_mutation_max_val=1.0)

Here a genetic algorithm instance is being created using the Pygad library where in certain parameters like the number of generations that the algorithm has to evolve through using the candidate solutions present in the population, the number of parents mating represents the set of solutions which will be responsible for sharing of information(mutation) until the crossover point is reached and all the solutions that will be mutated should pass the parameters enforced in the fitness function and many more. So with a Genetic algorithm instance being created the instance has to be iterated using the underlying principle of heuristic algorithms and in the iteration process, the instance tries to find the best possible solution which implies that the image is reconstructed closer to the original image.

ga_instance.run()

The fitness score increases with an increase in the number of generations and the same can be visualized using the “plot_result” inbuilt function.

ga_instance.plot_result()
plt.show()

The fitness score increases with the increase in the number of generations because the candidate solutions will try to evolve with respect to various factors, declared in the fitness function and try to reproduce the best optimal solution that can be passed on for mutation.

The best solution that is produced near the optimal solution can be visualized using the Pygad instance. Here the image that is being reconstructed can be visualized using the “chromosome2img” inbuilt function of the GARI library as shown below.

solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))
print("Index of the best solution : {solution_idx}".format(solution_idx=solution_idx))
 
if ga_instance.best_solution_generation != -1:
   print("Best fitness value reached after {best_solution_generation} generations.".format(best_solution_generation=ga_instance.best_solution_generation))
 
result = gari.chromosome2img(solution, img.shape)
plt.imshow(result)
plt.title("PyGAD & GARI for Reproducing Images")
plt.show()

Here we can see that after iterating through the 15000 candidate solutions the Pygad instance has tried to reconstruct the image close to the original image as shown above.

Comparing the reconstructed image and the original image

Here we can clearly see how the Genetic algorithm tries to reconstruct the image closer to the original image. The image reconstructed will be better with the increase in the number of generations and with an increase in the number of mutations. This is because the algorithm iterates through all the candidate solutions in the cluster and the fittest solutions that will be passed for the mutation will be more. This makes the algorithm reconstruct the image closer to the original image.

Summary

Genetic algorithms are mainly used for the optimization of various problems and in this article, we have seen how images can be reconstructed using genetic algorithms. More the number of generations and more the number of mutations optimal is the solution provided by the algorithm. The optimization process of genetic algorithms is time-consuming and that is why it finds its major usage in evolutionary algorithms, where the optimal solution is the major requirement for evolutionary algorithms.

References

• Pygad official documentation
• GARI Github repository