Genetic Algorithm - Python code to solve this problem.

Assume that you have knapsack(bag) which can carry 35 kgs of weight. You have 10 items, each with a specific weight and price. Now, dilemma is to make such a selection of items that it maximizes the value (i.e. total price) without exceeding the knapsack weight. You have to make a selection.

 

Randomly initialise the list of items.
Print output as item No, weight, value.
Declare the initial population.
Each gene has a value 1 or 0 which tells whether the corresponding item is present or not.

Print initial population.
Write fitness function.
Write selection function to select the fittest individuals.
Write one point cross over function.
Write mutation function.
call all functions in the order of the flow chart to find the required parameters and make all the necessary initialisations.
Print Selected items that will maximize the knapsack without breaking it.
visualize how the fitness changes with every generation.
Please could you help me to make some changes to this code but keep it working exactly like now with an explanation?


import numpy as np
import pandas as pd
import random as rd
from random import randint

# Random initialisation the list of items
items = np.arange(1,11)
weight = np.random.randint(5, 25, size = 10)
value = np.random.randint(30, 850, size = 10)
#Maximum weight that the bag can hold
knapsack_bag = 35  
print('Item #.   Weight   Value')
for i in range(items.shape[0]):
   print('{0}          {1}         {2}\n'.format(items[i], weight[i], value[i]))

# Declare the initial population
solutions_per_pop = 8
pop_size = (solutions_per_pop, items.shape[0])
print('Population size = {}'.format(pop_size))
init_pop = np.random.randint(2, size = pop_size)
init_pop = init_pop.astype(int)
num_generations = 100
print('Initial population: \n{}'.format(init_pop))

# Fitness Function

def cal_fitness(weight, value, pop, threshold):
   fitness = np.empty(pop.shape[0])
   for i in range(pop.shape[0]):
       S1 = np.sum(pop[i] * value)
       S2 = np.sum(pop[i] * weight)
       if S2 <= threshold:
           fitness[i] = S1
       else :
           fitness[i] = 0
   return fitness.astype(int)        

def selection(fitness, num_parents, pop):
   fitness = list(fitness)
   parents = np.empty((num_parents, pop.shape[1]))
   for i in range(num_parents):
       max_fitness_idx = np.where(fitness == np.max(fitness))
       parents[i,:] = pop[max_fitness_idx[0][0], :]
       fitness[max_fitness_idx[0][0]] = -999999
   return parents

def crossover(parents, num_offsprings):
   offsprings = np.empty((num_offsprings, parents.shape[1]))
   crossover_point = int(parents.shape[1]/2)
   crossover_rate = 0.8
   i=0
   while (parents.shape[0] < num_offsprings):
       parent1_index = i%parents.shape[0]
       parent2_index = (i+1)%parents.shape[0]
       x = rd.random()
       if x > crossover_rate:
           continue
       parent1_index = i%parents.shape[0]
       parent2_index = (i+1)%parents.shape[0]
       offsprings[i,0:crossover_point] = parents[parent1_index,0:crossover_point]
       offsprings[i,crossover_point:] = parents[parent2_index,crossover_point:]
       i=+1
   return offsprings

def mutation(offsprings):
   mutants = np.empty((offsprings.shape))
   mutation_rate = 0.4
   for i in range(mutants.shape[0]):
       random_value = rd.random()
       mutants[i,:] = offsprings[i,:]
       if random_value > mutation_rate:
           continue
       int_random_value = randint(0,offsprings.shape[1]-1)    
       if mutants[i,int_random_value] == 0 :
           mutants[i,int_random_value] = 1
       else :
           mutants[i,int_random_value] = 0
   return mutants  

def optimize(weight, value, pop, pop_size, num_generations, threshold):
   parameters, fitness_history = [], []
   num_parents = int(pop_size[0]/2)
   num_offsprings = pop_size[0] - num_parents
   for i in range(num_generations):
       fitness = cal_fitness(weight, value, pop, threshold)
       fitness_history.append(fitness)
       parents = selection(fitness, num_parents, pop)
       offsprings = crossover(parents, num_offsprings)
       mutants = mutation(offsprings)
       pop[0:parents.shape[0], :] = parents
       pop[parents.shape[0]:, :] = mutants
       
   print('Last generation: \n{}\n'.format(pop))
   fitness_last_gen = cal_fitness(weight, value, pop, threshold)      
   print('Fitness of the last generation: \n{}\n'.format(fitness_last_gen))
   max_fitness = np.where(fitness_last_gen == np.max(fitness_last_gen))
   parameters.append(pop[max_fitness[0][0],:])
   return parameters, fitness_history

parameters, fitness_history = optimize(weight, value, init_pop, pop_size, num_generations, knapsack_bag)
print('The optimized parameters for the given inputs are: \n{}'.format(parameters))
selected_items = items * parameters
print('\nSelected items that will maximize the knapsack without breaking it:')
for i in range(selected_items.shape[1]):
   if selected_items[0][i] != 0:
       print('{}\n'.format(selected_items[0][i]))