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