Genetic Algorithm in Artificial Intelligence

A genetic algorithm is used to solve complicated problems with a greater number of variables & possible outcomes/solutions. The combinations of different solutions are passed through the Darwinian based algorithm to find the best solutions. The poorer solutions are then replaced with the offspring of good solutions.

It all works on the Darwinian theory, where only the fittest individuals are chosen for reproduction. The various solutions are considered the elements of the population, and only the fittest solutions are allowed to reproduce (to create better solutions). Genetic algorithms help in optimizing the solutions to any particular problem.

The whole process of genetic algorithms is a computer program simulation in which the attributes of the problem & solution are treated as the attributes of the Darwinian theory. The basic processes which are involved in genetic algorithms are as follows:

A population of solutions is built to any particular problem. The elements of the population compete with each other to find out the fittest one.
The elements of the population that are fit are only allowed to create offspring (better solutions).
The genes from the fittest parents (solutions) create a better offspring. Thus, future solutions will be better and sustainable.

Operators used in GA

When the initial generation is generated, the GA evolves the generation using the op-
erators, discussed as follows.

Operator for Selection

In this kind of operator, the individuals have a preference with better fitness score and
enable them to pass their gene to the successive generation of the individual.

Operator for Crossover

This reflects a generation of breeding among persons. Randomly choose two individu-
als using selection operators and crossover operators. After chosen, genes are at the
crossover sites exchanged, so building a completely new offspring or individual.

Figure 2 shows the crossover operator.Paper— Genetic Algorithm: Reviews, Implementation and Applications

Operator for Mutation

To use this tool, introduce random genes into offspring to retain the genetic heteroge-
neity to prevent excessive divergences. Figure 3 shows the mutation process.

Benefits and Uses of Genetic Algorithms

The solutions created through genetic algorithms are strong & reliable as compared to other solutions.
They increase the size of solutions as solutions can be optimized over a large search scale. This algorithm also can manage a large population.
The solutions produced by genetic algorithms do not deviate much on slightly changing the input. They can handle a little bit of noise.
Genetic algorithms have a stochastic distribution that follows probabilistic transition rules, making them hard to predict but easy to analyze.
Genetic algorithms can also perform in noisy environments. It can also work in case of complex & discrete problems.
Due to their effectiveness, genetic algorithms have many applications like neural networks, fuzzy logic, code-breaking, filtering & signal processing. You can learn more about the genetic algorithms in AI via the top courses offered by upGrad.

My New Genetic Algorithm For Time Series | by Barış Can Tayiz | Becoming Human: Artificial Intelligence Magazine

Fitness score is the number of characters which differ from characters in target string at a particular index. So individual having lower fitness value is given more preference.

// C++ program to create target string, starting from
// random string using Genetic Algorithm
 
#include <bits/stdc++.h>
using namespace std;
 
// Number of individuals in each generation
#define POPULATION_SIZE 100
 
// Valid Genes
const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}";
 
// Target string to be generated
const string TARGET = "I love Ntirawen";
 
// Function to generate random numbers in given range
int random_num(int start, int end)
{
    int range = (end-start)+1;
    int random_int = start+(rand()%range);
    return random_int;
}
 
// Create random genes for mutation
char mutated_genes()
{
    int len = GENES.size();
    int r = random_num(0, len-1);
    return GENES[r];
}
 
// create chromosome or string of genes
string create_gnome()
{
    int len = TARGET.size();
    string gnome = "";
    for(int i = 0;i<len;i++)
        gnome += mutated_genes();
    return gnome;
}
 
// Class representing individual in population
class Individual
{
public:
    string chromosome;
    int fitness;
    Individual(string chromosome);
    Individual mate(Individual parent2);
    int cal_fitness();
};
 
Individual::Individual(string chromosome)
{
    this->chromosome = chromosome;
    fitness = cal_fitness();
};
 
// Perform mating and produce new offspring
Individual Individual::mate(Individual par2)
{
    // chromosome for offspring
    string child_chromosome = "";
 
    int len = chromosome.size();
    for(int i = 0;i<len;i++)
    {
        // random probability
        float p = random_num(0, 100)/100;
 
        // if prob is less than 0.45, insert gene
        // from parent 1
        if(p < 0.45)
            child_chromosome += chromosome[i];
 
        // if prob is between 0.45 and 0.90, insert
        // gene from parent 2
        else if(p < 0.90)
            child_chromosome += par2.chromosome[i];
 
        // otherwise insert random gene(mutate),
        // for maintaining diversity
        else
            child_chromosome += mutated_genes();
    }
 
    // create new Individual(offspring) using
    // generated chromosome for offspring
    return Individual(child_chromosome);
};
 
 
// Calculate fitness score, it is the number of
// characters in string which differ from target
// string.
int Individual::cal_fitness()
{
    int len = TARGET.size();
    int fitness = 0;
    for(int i = 0;i<len;i++)
    {
        if(chromosome[i] != TARGET[i])
            fitness++;
    }
    return fitness;   
};
 
// Overloading < operator
bool operator<(const Individual &ind1, const Individual &ind2)
{
    return ind1.fitness < ind2.fitness;
}
 
// Driver code
int main()
{
    strand((unsigned)(time(0)));
 
    // current generation
    int generation = 0;
 
    vector<Individual> population;
    bool found = false;
 
    // create initial population
    for(int i = 0;i<POPULATION_SIZE;i++)
    {
        string gnome = create_gnome();
        population.push_back(Individual(gnome));
    }
 
    while(! found)
    {
        // sort the population in increasing order of fitness score
        sort(population.begin(), population.end());
 
        // if the individual having lowest fitness score ie.
        // 0 then we know that we have reached to the target
        // and break the loop
        if(population[0].fitness <= 0)
        {
            found = true;
            break;
        }
 
        // Otherwise generate new offsprings for new generation
        vector<Individual> new_generation;
 
        // Perform Elitism, that mean 10% of fittest population
        // goes to the next generation
        int s = (10*POPULATION_SIZE)/100;
        for(int i = 0;i<s;i++)
            new_generation.push_back(population[i]);
 
        // From 50% of fittest population, Individuals
        // will mate to produce offspring
        s = (90*POPULATION_SIZE)/100;
        for(int i = 0;i<s;i++)
        {
            int len = population.size();
            int r = random_num(0, 50);
            Individual parent1 = population[r];
            r = random_num(0, 50);
            Individual parent2 = population[r];
            Individual offspring = parent1.mate(parent2);
            new_generation.push_back(offspring);
        }
        population = new_generation;
        cout<< "Generation: " << generation << "\t";
        cout<< "String: "<< population[0].chromosome <<"\t";
        cout<< "Fitness: "<< population[0].fitness << "\n";
 
        generation++;
     }
     cout<< "Generation: " << generation << "\t";
    cout<< "String: "<< population[0].chromosome <<"\t";
    cout<< "Fitness: "<< population[0].fitness << "\n";
}