What is Genetic Algorithm? - Naukri Code 360

Introduction

The Genetic Algorithm is an optimization technique that identifies optimal solutions from different possibilities. Inspired by biological evolution, this algorithm mimics the natural selection process, where only the fittest individuals survive to pass their genes to the next generation. It effectively solves the complex problems characterized by vast search spaces. By iterating through generations, the algorithm refines its solutions, continuously selecting the best candidates for further evolution. This approach ensures that each subsequent generation is better than the last, following the principle of "Survival of the Fittest."

Source: www.growthbusiness.co.uk

Foundation of Genetic Algorithms

Genetic algorithms are a class of optimization algorithms that are inspired by the principles of natural selection and genetics found in biological evolution. They are used to solve complex problems by simulating the process of evolution on a population of potential solutions.
The foundation of genetic algorithms lies in the idea that a population of individuals can evolve over generations to produce better solutions to a given problem. Each individual in the population represents a potential solution, and the quality of each solution is evaluated using a fitness function.

Main Steps of a Genetic Algorithm

The Genetic Algorithm is a Heuristic Search algorithm that we use to find the optimal solution from the search space and optimization problems.

Population: Genetic algorithms work with a population of individuals, where each individual represents a potential solution to the problem at hand. The population is typically initialized randomly, and the size of the population remains constant throughout the algorithm's execution.
Chromosomes: Each individual in the population is represented by a chromosome, which is a data structure that encodes the solution. Chromosomes are usually represented as strings of bits, integers, or other data types, depending on the problem's nature.
Fitness Function: The fitness function is a crucial component of genetic algorithms. It evaluates the quality or fitness of each individual in the population. The fitness function assigns a fitness score to each individual based on how well it solves the problem. The higher the fitness score, the better the solution.
Selection: Selection is the process of choosing individuals from the population to create the next generation. The selection process is based on the fitness scores of the individuals, with fitter individuals having a higher probability of being selected. Common selection methods include tournament selection, roulette wheel selection, and rank-based selection.

Operators of Genetic Algorithms

Crossover: Crossover is a genetic operator that combines genetic information from two parent individuals to create offspring. It involves exchanging segments of the chromosomes between the parents to produce new individuals. The crossover operator aims to exploit the best features of the parents to create potentially better offspring.
Mutation: Mutation is another genetic operator that introduces random changes in the chromosomes of individuals. It helps maintain diversity in the population and allows the algorithm to explore new solutions. The mutation prevents the algorithm from getting stuck in local optima.

Examples of Genetic Algorithms

Route Optimization: Traveling Salesman Problem (TSP): Genetic algorithms are particularly effective for problems like the Traveling Salesman Problem (TSP), where the objective is to find the shortest possible route that visits each city once and returns to the starting point; by simulating processes such as selection, crossover, and mutation, GAs generate multiple routes, evaluate their efficiency, and iteratively refine them to approach an optimal solution. This method is beneficial for logistics and delivery route planning, where reducing travel distance directly correlates with time and cost savings.
Scheduling Problems: Job-shop Scheduling: In environments like manufacturing, where multiple jobs must be processed across various machines, genetic algorithms help optimize job-shop scheduling; the algorithm evaluates different sequences of job assignments to minimize overall completion time or maximize throughput. By exploring a vast array of configurations and selectively breeding the best performers, GAs adapt to complex constraints and dependencies typical in industrial operations.
Portfolio Management: Financial Portfolio Optimization: Genetic algorithms can also be applied to the complex decision-making process of financial portfolio management; they evaluate various combinations of stocks, bonds, or other assets to determine the mix that offers the best return for a given risk level. This approach allows investors to systematically and efficiently explore and exploit the financial landscape to meet their investment goals.
Game Development:In the gaming industry, genetic algorithms enhance the strategic depth and challenge of AI by evolving complex behaviors and strategies; these algorithms can simulate evolutionary processes to develop competitive game-playing agents that adapt to player actions and strategies, creating a dynamic and challenging gaming experience.

CODE

Python
Java
C++
C#
Javascript

Python

# Importing necessary libraries
import numpy as np
import matplotlib.pyplot as plt
 
# Defining the range of the plot
x1 = [-100, 100]
x2 = [-100, 100]
 
# This list will store the population
populations = []
def generatePopulation(features, size = 1000):
     
   initial = []
     
   for _ in range(size):
       entity = []
       for feature in features:
           
           val = np.random.randint(*feature)
           entity.append(val)
       initial.append(entity)
     
   return np.array(initial)
 
virusArray = np.array([5, 5])
 
# size 100 implies that only 100 individuals will survive
def fitness(populations, virusArray, size = 100):
     
   scores = []
     
   for index, entity in enumerate(populations): 
       score = np.sum((entity-virus)**2)
       scores.append((score, index))
     
   scores = sorted(scores)[:size]
     
   return np.array(scores)[:, 1]      
     
def reduction(populations, virusArray, size = 100):
     
   fitIndividuals = fitness(populations, virusArray, size) 
 
   new_pop = []
     
   for item in fitIndividuals:
       new_pop.append(populations[item])
         
   return np.array(new_pop)
 
def crossMutation(populations, size = 1000):
     
   new_pop = []
     
   for _ in range(size):
       p = populations[np.random.randint(0, len(populations))]
       m = populations[np.random.randint(0, len(populations))]
     
       entity = []
       entity.append(*p[:len(p)//2])
       entity.append(*m[len(m)//2:])
         
       new_pop.append(entity)
     
   return np.array(new_pop)
def mutations(populations):
     
   return populations + np.random.randint(-10, 10, 2000).reshape(1000, 2)
 
 
# the complete cycle of the above steps
populations = generatePopulation([x1, x2], 1000)
def cycle(populations, virusArray, generations): 
   # changing value of generations will give more fitter next generation
   for _ in range(generations):
       populations = reduction(populations, virusArray, 100)
       populations = crossMutation(populations, 1000)
       populations = mutations(populations)
         
   return populations
def plotGraph(populations, virusArray):
   plt.xlim((-100, 100))
   plt.ylim((-100, 100))
   plt.scatter(populations[:, 0], populations[:, 1], c ='green', s = 12)
   plt.scatter(virusArray[0], virusArray[1], c ='red', s = 60) 
 
populations = cycle(populations, virusArray, 0)
plotGraph(populations, virusArray)

You can also try this code with Online Python Compiler

Run Code

Java

import java.util.Arrays;
import java.util.Random;

public class GeneticAlgorithm {
    static Random random = new Random();
    static int[][] generatePopulation(int[] x1, int[] x2, int size) {
        int[][] population = new int[size][2];
        for (int i = 0; i < size; i++) {
            population[i][0] = random.nextInt(x2[1] - x1[0] + 1) + x1[0];
            population[i][1] = random.nextInt(x2[1] - x2[0] + 1) + x2[0];
        }
        return population;
    }

    static int[] fitness(int[][] populations, int[] virusArray, int size) {
        int[] scores = new int[size];
        for (int i = 0; i < size; i++) {
            int score = (populations[i][0] - virusArray[0]) * (populations[i][0] - virusArray[0])
                        + (populations[i][1] - virusArray[1]) * (populations[i][1] - virusArray[1]);
            scores[i] = score;
        }
        Arrays.sort(scores);
        return Arrays.copyOfRange(scores, 0, size);
    }

    static int[][] reduction(int[][] populations, int[] virusArray, int size) {
        int[] fitIndividuals = fitness(populations, virusArray, size);
        int[][] newPop = new int[size][];
        for (int i = 0; i < size; i++) {
            newPop[i] = populations[fitIndividuals[i]];
        }
        return newPop;
    }

    static int[][] crossMutation(int[][] populations, int size) {
        int[][] newPop = new int[size][2];
        for (int i = 0; i < size; i++) {
            int[] p = populations[random.nextInt(populations.length)];
            int[] m = populations[random.nextInt(populations.length)];
            newPop[i][0] = p[0];
            newPop[i][1] = m[1];
        }
        return newPop;
    }

    static int[][] mutations(int[][] populations) {
        for (int i = 0; i < populations.length; i++) {
            populations[i][0] += random.nextInt(21) - 10;
            populations[i][1] += random.nextInt(21) - 10;
        }
        return populations;
    }

    public static void main(String[] args) {
        int[] x1 = {-100, 100};
        int[] x2 = {-100, 100};
        int[][] populations = generatePopulation(x1, x2, 1000);
        int[] virusArray = {5, 5};
        for (int i = 0; i < 50; i++) { // 50 generations
            populations = reduction(populations, virusArray, 100);
            populations = crossMutation(populations, 1000);
            populations = mutations(populations);
        }
        // Plotting would go here, if it were implemented
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

class GeneticAlgorithm {
public:
    static std::vector<std::vector<int>> generatePopulation(std::vector<int> x1, std::vector<int> x2, int size) {
        std::vector<std::vector<int>> population(size, std::vector<int>(2));
        srand(time(NULL));
        for (int i = 0; i < size; i++) {
            population[i][0] = x1[0] + rand() % (x1[1] - x1[0] + 1);
            population[i][1] = x2[0] + rand() % (x2[1] - x2[0] + 1);
        }
        return population;
    }

    static std::vector<int> fitness(const std::vector<std::vector<int>>& populations, const std::vector<int>& virusArray, int size) {
        std::vector<std::pair<int, int>> scores;
        for (int i = 0; i < populations.size(); i++) {
            int score = (populations[i][0] - virusArray[0]) * (populations[i][0] - virusArray[0])
                        + (populations[i][1] - virusArray[1]) * (populations[i][1] - virusArray[1]);
            scores.push_back({score, i});
        }
        sort(scores.begin(), scores.end());
        std::vector<int> indices(size);
        for (int i = 0; i < size; i++) {
            indices[i] = scores[i].second;
        }
        return indices;
    }

    static std::vector<std::vector<int>> reduction(const std::vector<std::vector<int>>& populations, const std::vector<int>& virusArray, int size) {
        std::vector<int> fitIndividuals = fitness(populations, virusArray, size);
        std::vector<std::vector<int>> newPop(size, std::vector<int>(2));
        for (int i = 0; i < size; i++) {
            newPop[i] = populations[fitIndividuals[i]];
        }
        return newPop;
    }

    static std::vector<std::vector<int>> crossMutation(const std::vector<std::vector<int>>& populations, int size) {
        std::vector<std::vector<int>> newPop(size, std::vector<int>(2));
        for (int i = 0; i < size; i++) {
            const std::vector<int>& p = populations[rand() % populations.size()];
            const std::vector<int>& m = populations[rand() % populations.size()];
            newPop[i][0] = p[0];
            newPop[i][1] = m[1];
        }
        return newPop;
    }

    static std::vector<std::vector<int>> mutations(std::vector<std::vector<int>>& populations) {
        for (auto& entity : populations) {
            entity[0] += rand() % 21 - 10;
            entity[1] += rand() % 21 - 10;
        }
        return populations;
    }
};

int main() {
    std::vector<int> x1 = {-100, 100};
    std::vector<int> x2 = {-100, 100};
    std::vector<std::vector<int>> populations = GeneticAlgorithm::generatePopulation(x1, x2, 1000);
    std::vector<int> virusArray = {5, 5};

    for (int i = 0; i < 50; i++) {
        populations = GeneticAlgorithm::reduction(populations, virusArray, 100);
        populations = GeneticAlgorithm::crossMutation(populations, 1000);
        populations = GeneticAlgorithm::mutations(populations);
    }
    // Plotting would be here if included
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

class GeneticAlgorithm {
    static Random random = new Random();

    static List<List<int>> GeneratePopulation(List<int> x1, List<int> x2, int size) {
        var population = new List<List<int>>();
        for (int i = 0; i < size; i++) {
            population.Add(new List<int> {
                x1[0] + random.Next(x1[1] - x1[0] + 1),
                x2[0] + random.Next(x2[1] - x2[0] + 1)
            });
        }
        return population;
    }

    static List<int> Fitness(List<List<int>> populations, List<int> virusArray, int size) {
        var scores = populations.Select((entity, index) => new {
            Score = (entity[0] - virusArray[0]) * (entity[0] - virusArray[0]) +
                    (entity[1] - virusArray[1]) * (entity[1] - virusArray[1]),
            Index = index
        }).OrderBy(score => score.Score).Take(size).Select(score => score.Index).ToList();

        return scores;
    }

    static List<List<int>> Reduction(List<List<int>> populations, List<int> virusArray, int size) {
        var fitIndividuals = Fitness(populations, virusArray, size);
        return fitIndividuals.Select(index => populations[index]).ToList();
    }

    static List<List<int>> CrossMutation(List<List<int>> populations, int size) {
        var newPop = new List<List<int>>();
        for (int i = 0; i < size; i++) {
            var p = populations[random.Next(populations.Count)];
            var m = populations[random.Next(populations.Count)];
            newPop.Add(new List<int> { p[0], m[1] });
        }
        return newPop;
    }

    static List<List<int>> Mutations(List<List<int>> populations) {
        foreach (var entity in populations) {
            entity[0] += random.Next(21) - 10;
            entity[1] += random.Next(21) - 10;
        }
        return populations;
    }
}

class Program {
    static void Main() {
        List<int> x1 = new List<int> { -100, 100 };
        List<int> x2 = new List<int> { -100, 100 };
        var populations = GeneticAlgorithm.GeneratePopulation(x1, x2, 1000);
        List<int> virusArray = new List<int> { 5, 5 };

        for (int i = 0; i < 50; i++) {
            populations = GeneticAlgorithm.Reduction(populations, virusArray, 100);
            populations = GeneticAlgorithm.CrossMutation(populations, 1000);
            populations = GeneticAlgorithm.Mutations(populations);
        }
    }
}

Javascript

class GeneticAlgorithm {
    static generatePopulation(x1, x2, size) {
        let population = [];
        for (let i = 0; i < size; i++) {
            population.push([
                x1[0] + Math.floor(Math.random() * (x1[1] - x1[0] + 1)),
                x2[0] + Math.floor(Math.random() * (x2[1] - x2[0] + 1))
            ]);
        }
        return population;
    }

    static fitness(populations, virusArray, size) {
        let scores = populations.map((entity, index) => ({
            score: (entity[0] - virusArray[0]) ** 2 + (entity[1] - virusArray[1]) ** 2,
            index: index
        }));
        scores.sort((a, b) => a.score - b.score);
        return scores.slice(0, size).map(score => score.index);
    }

    static reduction(populations, virusArray, size) {
        let fitIndividuals = this.fitness(populations, virusArray, size);
        return fitIndividuals.map(index => populations[index]);
    }

    static crossMutation(populations, size) {
        let newPop = [];
        for (let i = 0; i < size; i++) {
            let p = populations[Math.floor(Math.random() * populations.length)];
            let m = populations[Math.floor(Math.random() * populations.length)];
            newPop.push([p[0], m[1]]);
        }
        return newPop;
    }

    static mutations(populations) {
        return populations.map(entity => [
            entity[0] + Math.floor(Math.random() * 21) - 10,
            entity[1] + Math.floor(Math.random() * 21) - 10
        ]);
    }
}

let x1 = [-100, 100];
let x2 = [-100, 100];
let populations = GeneticAlgorithm.generatePopulation(x1, x2, 1000);
let virusArray = [5, 5];

for (let i = 0; i < 50; i++) {
    populations = GeneticAlgorithm.reduction(populations, virusArray, 100);
    populations = GeneticAlgorithm.crossMutation(populations, 1000);
    populations = GeneticAlgorithm.mutations(populations);
}

You can also try this code with Online Javascript Compiler

Run Code

OUTPUT

Plot for the First Generation-

Plot for the Second Generation-

Plot for the Third Generation-

Plot for the Fourth Generation-

Application of Genetic Algorithms

Optimization Problems: Solving complex optimization tasks, such as finding the best allocation of resources or route planning in logistics.
Machine Learning: Enhancing machine learning models through feature selection and hyperparameter tuning to improve performance.
Robotics: Developing control systems for autonomous robots, where GAs can be used to optimize the behavior and response strategies of robots.
Financial Modeling: Optimizing portfolios to maximize returns and minimize risks by selecting the best combination of stocks.
Bioinformatics: Analyzing and predicting structures of proteins and other biological data.
Engineering Design: Assisting in the design of complex systems such as aircraft, automotive components, and architectural layouts, where traditional methods are inefficient.

Advantages of Genetic Algorithms

Flexibility: Can be applied to virtually any problem, provided it can be encoded in a suitable way.
Robustness: Capable of handling noisy or dynamic environments which might disable other algorithms.
Global Search Capability: Excellent at searching through large and complex spaces to find global solutions, not just local optima.
Parallelism: Easily parallelizable, which means they can take advantage of modern multi-processor and distributed computing systems to speed up performance.
Adaptability: They can adapt to changes in the problem specifications or operating environment without needing significant changes to the algorithm.

Disadvantages of Genetic Algorithms

Computationally Intensive: Often require a lot of computational resources, as they involve operations on large populations over many generations.
Premature Convergence: Can converge too early on suboptimal solutions if not properly tuned or if diversity in the population is not maintained.
Parameter Sensitivity: Performance is highly sensitive to the settings of parameters like mutation rate, crossover rate, and population size, which can be difficult to tune optimally.
Lack of Guarantee: There’s no guarantee of finding the absolute best solution, especially in very complex or deceptive problem landscapes.
Randomness: The stochastic nature of GAs can lead to inconsistencies in performance, which might be problematic for applications requiring high reliability.

Frequently Asked Questions

Who invented the genetic algorithm?

John Holland invented the genetic algorithm in the 1960s as part of his studies on adaptive systems at the University of Michigan.

What is the best language for genetic algorithms?

There is no single best language for genetic algorithms; Python, Java, and C++ are commonly used due to their extensive libraries and robust support.

Why is it called a genetic algorithm?

It is called a genetic algorithm because it mimics the process of natural selection and genetics, using operations akin to biological reproduction and mutation.

Is genetic algorithm AI?

Yes, genetic algorithms are considered a part of artificial intelligence, specifically within the field of evolutionary computation, used to solve optimization and search problems.

What are the four techniques used in genetic algorithms?

Genetic algorithms have four key techniques: selection of the fittest individuals, crossover to combine genetic information, mutation for introducing variations, and replacement to enhance population fitness by substituting less fit individuals with new offspring.

Conclusion

In this article, we talked about genetic algorithms and discussed their operation through selection, crossover, mutation, and replacement steps. We also explained these with the help of code implementation to make everything easy to understand. We showed how these algorithms mimic natural evolutionary processes to solve complex optimization problems efficiently. We also saw their applications, advantages and disadvantages.

What is a Genetic Algorithm?

Introduction

Foundation of Genetic Algorithms

Main Steps of a Genetic Algorithm

Operators of Genetic Algorithms

Examples of Genetic Algorithms

CODE

Python

Java

C++

C#

Javascript

OUTPUT

Application of Genetic Algorithms

Advantages of Genetic Algorithms

Disadvantages of Genetic Algorithms

Frequently Asked Questions

Who invented the genetic algorithm?

What is the best language for genetic algorithms?

Why is it called a genetic algorithm?

Is genetic algorithm AI?

What are the four techniques used in genetic algorithms?

Conclusion