What is Genetic algorithms ?

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Knapsack problem

The Knapsack problem is a combinatorial optimization problem . The name is given due to the model of a situation in which it is necessary to fill a backpack with objects of different weights and values. The goal is to fill the backpack with the highest possible value, not exceeding the maximum weight.

For more details see Wikipedia.

Solving the Knapsack problem

First Population

First step is creating an initial population. N backpacks will be filled with random items until the weight limit is reached.

class Knapsack:
    def __init__(self, total_individual, total_chromosomes, total_generations, mutation_rate, crossover_rate, elite,  pack_weigth_limit, objects):
        self.total_individual = total_individual
        self.total_chromosomes = total_chromosomes
        self.total_generations = total_generations
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate
        self.elite = elite
        self.pack_weigth_limit = pack_weigth_limit
        self.objects = objects.get_objects_list()
        
        self.population = None
        self.fitness_list = []
        self.weight_list = []
        self.individual_dic = []


    def first_population(self):
        """this function create a random population"""
        self.population = [[0 for i in range(self.total_chromosomes)] for i in range(self.total_individual)]

        for individual in range(self.total_individual):
            for chromosome in range(self.total_chromosomes):
                self.population[individual][chromosome] = random.randint(0, 1)
            
        return self

Calculate Fitness

In this step we will implement the function to calculate the fitness score

def calc_fitness(self, individual):
    """calculate individual fitness"""
    sum_weight = 0
    fitness = 0
    index = 1
        
    for gen in individual:
        if gen == 1:
            sum_weight += int(self.objects[index].split(';')[1])
            fitness += int(self.objects[index].split(';')[2])
        index += 1

    self.weight_list.append(sum_weight)
    self.fitness_list.append(fitness)
    return fitness, sum_weight

Tournament Selection

Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm. Tournament selection involves running several “tournaments” among a few individuals chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover

def tournament_selection(self, index_individual1, index_individual2):
    """This function select the best individual"""
    if(abs(self.fitness_list[index_individual1]) > abs(self.fitness_list[index_individual2])):
        winner_index = index_individual1
    else:
        winner_index = index_individual2

    return winner_index

Mutation

The classic example of a mutation operator involves a probability that an arbitrary bit in a genetic sequence will be flipped from its original state. A common method of implementing the mutation operator involves generating a random variable for each bit in a sequence. This random variable tells whether or not a particular bit will be flipped. This mutation procedure, based on the biological point mutation, is called single point mutation. Other types are inversion and floating point mutation. When the gene encoding is restrictive as in permutation problems, mutations are swaps, inversions, and scrambles.

def mutation(self, index_individual):
    """this function is responsible for making a mutation in the individual"""
    mutated_index = random.randint(0, self.total_chromosomes - 1)
    if self.population[index_individual][mutated_index] == 0:
        self.population[index_individual][mutated_index] = 1
    else:
        self.population[index_individual][mutated_index] = 0

    return self

Crossover

In genetic algorithms, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population, and is analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

def crossover(self, index_individual1, index_individual2):
    crossover_index = random.randint(1, self.total_chromosomes - 1)
    
    child1 = self.population[index_individual1][:crossover_index] + self.population[index_individual2][crossover_index:]
    child2 = self.population[index_individual2][:crossover_index] + self.population[index_individual1][crossover_index:]
    return child1, child2

References