The world’s leading publication for data science, AI, and ML professionals.

A Guide to Genetic ‘Learning’ Algorithms for Optimization

Reconstructing Images using Reinforcement Learning and Genetic Algorithms

In a broader mathematical or computational perspective, an optimization problem is defined as a problem of finding the best solution from all feasible solutions. In terms of Machine Learning and Artificial Intelligence, two significant algorithms that perform these tasks are Reinforcement Learning and Genetic Algorithms. They serve the purpose of finding the ‘best fit’ solutions from a range of possible solutions for a given problem statement. In the article that follows below, we will be working closely on these algorithms and will see their implementation in action on an Image Processing problem.

Repeated Gene Mutations and Recursions form the basis of Genetic Algorithm | Image by The Digital Artist on Pixabay
Repeated Gene Mutations and Recursions form the basis of Genetic Algorithm | Image by The Digital Artist on Pixabay

What is a Genetic Algorithm (GA)?

Genetic Algorithms are random, adaptive heuristic search algorithms that act on a population of doable solutions. they need loosely supported the mechanics of population biology and choice.

Genetic algorithms are based on the ideas of natural selection and genetics. New solutions are typically made by ‘mutating’ members of this population, and by ‘mating’ 2 resolutions along to create a replacement solution.

The upper solutions are selected to breed and change and so the more severe ones are discarded. They are probabilistic search methods; this implies that the states that they explore are not determined entirely by the properties of the problems. A random method helps to guide the search. Genetic algorithms are utilized in AI like different search algorithms utilized in AI – to seem for potential solutions to hunt out one that solves the matter.

What is Reinforcement Learning?

Mechanism of Operation for Reinforcement Learning algorithms | Image by Author
Mechanism of Operation for Reinforcement Learning algorithms | Image by Author

Reinforcement learning is often known as a goal-driven and highly adaptive machine learning technique. It consists of two basic elements: State and Action.

The strategy of the algorithm is to perform an action in a certain state. The learner must constantly explore to generate an optimal strategy.

Reinforcement learning is distinct in its algorithmic implementation from supervised and unsupervised learning since it regards learning as a process of interaction – between the agent and its environment through exploration and evaluation. A simple outlook of how the operation executes is shown in the image above. The agent first senses the current environment state, and based on this it selects an action to be applied. Once the environment accepts this updated action, the state changes, and a reward is attached to the agent. According to the new and evolved states of the environment, the agent continues to select the updated actions, and this is recursively repeated until it reaches the terminated state.

The Convergence between Reinforcement Learning and Genetic Algorithms

A genetic algorithm is a general heuristic search method designed for finding the optimal solution to a problem. To converge and use Reinforcmenet logic in a GA, there is a control structure added to the GA’s fitness function that dynamically adjusts the diversity of the population. The goal of reinforcement learning is to maximize the accumulated rewards by adjusting strategies and the goal of a Genetic Algorithm is to perform mutations until the desired fitness of function is maximized.

A Reinforcement Learning mechanism is introduced to the crossover and mutation operation of a Genetic Algorithm to determine the cross fragments and mutation points that would result in the best possible optimization.

Adding the Reinforcement Learning (RL) Layer into a Genetic Algorithm (GA) | Image by Author
Adding the Reinforcement Learning (RL) Layer into a Genetic Algorithm (GA) | Image by Author

How do Genetic Algorithms work?

GA(s) function by taking in a pool of possible solutions to a given problem. All the possibilities then undergo a set of recombination and mutations (similar to what we see in natural genetics). They then, produce children and this process is repeated for multiple generations. Every individual child that comes in a generation is assigned a fitness value. This fitness value is based on the objective that the GA is trying to solve and the generations that yield higher fitness values are given a chance to mate and yield even fitter individuals. This continues until the stopping criterion (exit function) is reached. GAs is a great implementation of the Darwinian Theory of Survival of the Fittest.

Genetic Algorithm structure is greatly randomized, and this nature of implementation gives great incentive for optimizing image processing algorithms. GAs performs a much better job in local search (given their attribute of working with historical data) than all other search algorithms and since images are part of a complex vector-based environment, this optimized way of searching allows for better processing and therefore faster execution of computer vision tasks. Following are the steps and stages that Genetic Algorithms work through. These steps are generally always sequential, and some might be repetitive based on the accuracy of the algorithm.

Implementing a Genetic Algorithm to Recreate an Image

  • Step 1: The input is read, and the first step is to randomly generate a possible solution, irrespective of its accuracy.
  • Step 2: The initial solution is assigned a fitness value. This fitness value is kept as the comparable for all the future generation solutions.
  • Step 3: Mutations and crossover operations are applied to the selected solution and these are then recombined. From this combination of solutions, the best fitness value is extracted.
  • Step 4: The offspring of this newly generate best fitness solution is inserted into the population that initially gave us the first possible solution. Both these solutions are then crossed over and mutated. Their mutated output is checked for its fitness value.
  • Step 5: If this new solution meets the stop condition, mutations are stopped and this is selected as the main solution, otherwise step 4 continues with more mutations and crossovers until the best fit solution based on the stop condition is met.
A General Image Processing Workflow | Image by Author
A General Image Processing Workflow | Image by Author
  1. Converting the image to a one-dimensional vector

The first step of most Image Processing algorithms is to change the image file format to a numerical array since machines perform on numbers. We do the same with our input image and convert it to a vector.

def image_to_vector(img_array):
     return numpy.reshape(a=img_array, newshape =              (functools.reduce (operator.mul, img_array.shape)))

2. Convert the one-dimensional vector to an array

On the converted vector, we standardize the shape of the vector to create a defined image size.

def vector_to_array(input_vector, shape):
   #Checking whether reshaping is possible
   if len(input_vector) != functools.reduce(operator.mul, shape):
      raise ValueError("Reshaping failed")
   return numpy.reshape(a=input_vector, newshape=shape)

3. Defining the Fitness function

The fitness function simply defined is a recursive function that takes a candidate solution to the population as input and produces an output stating **** how "fit" or in other words how "efficiently optimized" the solution is with respect to the population in consideration.

An ideal fitness function should possess the following characteristics:

` It should be considerably fast to compute since multiple (thousands) iterations of the function are run before reaching a solution.

` It must quantitatively measure the solution’s fitness or determine how fit individuals can be produced from the given solution.

image_encode = image_to_vector(input_image)
def fitness_func(int_one, int_two):
     fitness_value = numpy.sum(numpy.abs(image_encode-int_one))
     fitness_value = numpy.sum(image_encode) - fitness_value
     return fitness_value

4. Defining the Callback function

A callback function is executed with every generation of the population and its mutations. The parameters for this function are the GA algorithm itself, the number of processed evaluations so far, and the current population size.

def callback_func(genetic_var):
    if genetic_var.generations_completed % 500 == 0:
    matplotlib.pyplot.imsave( 'Final_GA_Image_ ' + str(   genetic_var.generations_completed )+'.png', vector_to_array(genetic_var.best_solution()[0], input_image.shape))

5. Initiating the Genetic Algorithm class with all of its parameters

As explained in the PyGAD documentation, the Genetic Algorithm initialization takes in multiple parameters that are used in its construction. The above-defined fitness and callback functions are used. The number of populations that need to be iterated through is specified (these can increase based on the complexity of the input). Importantly, the number of generations and number of parents mating are also defined which helps the algorithm in building subsequent child populations. Finally, from the documentation mentioned above, there are a bunch of mutation types to choose from (we have chosen ‘random’ in this example)

# Initiate the Genetic Algorithm class with the given parameters
# Number of Parent Solutions to consider
genetic_var = pygad.GA(num_generations=40999, num_parents_mating=12,
# Choosing which fitness function to use
fitness_func=fitness_func,
# Lower scale entry point (Should be integer between 0-1)
init_range_low=0,
# Higher scale exit point (Should be integer between 0-1)
init_range_high=1,                              
# Number of populations to work through
sol_per_pop=44,
# Number of genes to use
num_genes=input_image.size,        
mutation_by_replacement=True,
# % of genes from the population that need to be mutated
mutation_percent_genes=0.02,        
# Type of mutation
mutation_type="random",                 
callback_generation=callback_func,
random_mutation_min_val=0,
# Mutation minimum and maximum values (range 0-1)
random_mutation_max_val=1)

6. Running the GA and finding the best Solution

The run() function initiates the Genetic Algorithm and finally the best_solution() attribute gives us the best output of the reconstructed image.

# Run the GA instance
genetic_var.run()
# Metrics of the best solution
int_one, result_fit, int_two = genetic_var.best_solution()

OUTPUT

These are the images (side-by-side) the input and the reconstructed one. This output was generated after 40998 generations of the initial population. All generations and resulting outputs are present in the repository linked below. We see how the image gradually gets closer to the original input image post multiple generations of processing.

For the detailed implementation of the Genetic Algorithm code using Python, kindly refer to the below-mentioned repository. The number of generations needed for reciprocating an image or other objects depends highly on the nature of the input and its complexity. Therefore, it is important to create a fitness function that evaluates populations extremely fast.

rjrahul24/ga-reinforcement-learning-image-restoration


The majority of Robot Applications we see today are constructed using GAs | Photo by Sebastian Kurpiel on Unsplash
The majority of Robot Applications we see today are constructed using GAs | Photo by Sebastian Kurpiel on Unsplash

Why use Genetic Algorithms?

  • GAs are inherently robust in their application.
  • These algorithms are capable of providing optimizations over extremely large problem spaces.
  • Unlike traditional Artificial Intelligence solutions, GAs do not break on a slight change in the given input or with the presence of noise in data.

Conclusion

Genetic algorithms are commonly used for generating high-quality solutions for optimization and randomized search problems. Their application relies on biologically inspired operators such as mutation, crossover, and selection. GAs are used in several diversified industries today ranging from building creative robotics to satellite communication scheduling (practiced by NASA). This article was aimed at giving an enhanced tutorial of how GAs can be used to recreate images the this is one of the main applications of Robotic Sciences where artificial machines are taught human vision. There are several other tutorials that can be followed to learn in-depth applications of GAs as mentioned in references [7].

About Me

I am a Software Engineer turned Data Science Researcher at Columbia University in New York and I am currently researching ways to reduce the impact of climate changes on underprivileged populations of the world. These are people most affected by our actions of cutting trees and pushing concrete on the Earth’s surface. If your research or work ambitions are also aligned with me, do connect with me to Twitter or LinkedIn, and we can together work towards building Responsible Artificial Intelligence.


[References]

  1. https://arxiv.org/pdf/1905.04100.pdf
  2. https://www.sciencedirect.com/science/article/abs/pii/S0957417408006064
  3. https://www.hindawi.com/journals/mpe/2020/1698323/
  4. https://pygad.readthedocs.io/en/latest/
  5. https://www.staracle.com/general/evolutionaryAlgorithms.php
  6. https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
  7. https://en.wikipedia.org/w/index.php?title=Genetic_algorithm&action=edit&section=32

Related Articles