I\'m trying to figure out how this code works it\'s suppose to use a genetic alg
ID: 3871640 • Letter: I
Question
I'm trying to figure out how this code works it's suppose to use a genetic algorithm to solve the multiple knapsack problem in python. Could someone eplain how this program reads the data file in, what I mean is what is everything that's in the data file already provided what is what? I mean is it a weight, the capacity of the knapsack things like that. and give me another workable instance of a data file. The code is in three files including one data file:
knapsakc_prob.py code:
from genetic_toolkit import Population,Chromosome,BiologicalProcessManager
import statistics
import random
'''
Generation Evaluation Function
'''
def find_the_best(population):
best = None
for individual in population:
if best == None or individual.fitness > best.fitness:
best = individual
return best.fitness
# Global Variables
crossover_rate = 0.70
# Initialize population with random candidate solutions
population = Population(500)
population.initialize_population()
# Set the mutation rate
mutation_rate = 1/population.populationSize
# Get a reference to the number of knapsacks
numberOfKnapsacks = population.numberOfKnapsacks
generation_counter = 0
while(generation_counter != 100):
current_population_fitnesses = [chromosome.fitness for chromosome in population.population]
print("CURRENT GEN FITNESS: {} ".format(current_population_fitnesses))
new_gen = []
while(len(new_gen) != population.populationSize):
# Create tournament for tournament selection process
tournament = [population.population[random.randint(1, population.populationSize-1)] for individual in range(1, population.populationSize)]
# Obtain two parents from the process of tournament selection
parent_one, parent_two = population.select_parents(tournament)
# Create the offspring from those two parents
child_one,child_two = BiologicalProcessManager.crossover(crossover_rate,parent_one,parent_two)
# Try to mutate the children
BiologicalProcessManager.mutate(mutation_rate, child_one, numberOfKnapsacks)
BiologicalProcessManager.mutate(mutation_rate, child_two, numberOfKnapsacks)
# Evaluate each of the children
child_one.generateFitness(population.knapsackList)
child_two.generateFitness(population.knapsackList)
# Add the children to the new generation of chromsomes
new_gen.append(child_one)
new_gen.append(child_two)
# Replace old generation with the new one
population.population = new_gen
generation_counter += 1
genetic-toolkit.py code:
import random
import linecache
import copy
from collections import namedtuple
# Class to represent biological processes
class BiologicalProcessManager:
'''
Crossover Function
- The process of One-Point crossover is exercised in this function.
'''
def crossover(crossover_rate, parentOne, parentTwo):
random_probability = random.random()
if random_probability < crossover_rate:
return (parentOne, parentTwo)
else:
pivot = random.randint(0, len(parentOne.genotype_representation)-1)
child_one_genotype = parentOne.genotype_representation[:pivot] + parentTwo.genotype_representation[pivot:]
child_two_genotype = parentTwo.genotype_representation[:pivot] + parentOne.genotype_representation[pivot:]
child_one = Chromosome(parentOne.numberOfKnapsacksReference, parentOne.numberOfObjectsReference, child_one_genotype)
child_two = Chromosome(parentOne.numberOfKnapsacksReference, parentOne.numberOfObjectsReference, child_two_genotype)
child_one.phenotype_representation = parentOne.phenotype_representation
child_two.phenotype_representation = parentOne.phenotype_representation
return (child_one, child_two)
'''
Mutation function
- The process of Random Resetting is exercised in this function.
'''
def mutate(mutation_rate, child, numberOfKnapsacks):
for index, position in enumerate(child.genotype_representation):
random_probability = random.random()
'''
(Random Resetting) "Flip" the position with another knapsack if probability < mutation_rate
'''
if random_probability < mutation_rate:
child.genotype_representation[index] = random.randint(0,numberOfKnapsacks)
# Class to represent chromosome
class Chromosome:
fitness = None # Chromosomes fitness
phenotype_representation = None # Phenotype representation
def __init__(self, numOfKnapsacks, numOfObjects, genotype_representation = None):
self.numberOfKnapsacksReference = numOfKnapsacks
self.numberOfObjectsReference = numOfObjects
if genotype_representation == None:
self.genotype_representation = [random.randint(0,(numOfKnapsacks)) for x in range(0, numOfObjects)]
else:
self.genotype_representation = genotype_representation
self.length_of_encoding = len(self.genotype_representation)
'''
Generates a fitness for all the chromosomes by aggregating their benefits/values
'''
def generateFitness(self, knapsackList):
''' Make a copy of the knapsack list to be used to evaluate if objects in the chromsome
exceed C using the 'amountUsed' attribute
'''
#print("ORIGINAL CHROM: {}".format(self.genotype_representation))
knapsacks = copy.deepcopy(knapsackList)
fitnessScore = 0
done = False
for i, placement_of_object in enumerate(self.genotype_representation):
if placement_of_object == 0:
continue
else:
for knapsack in knapsacks:
if knapsack.id == placement_of_object:
# if it's over the capacity, change it's bag and revaluate
if self.phenotype_representation[i].weight > knapsack.capacity:
while(not done):
self.genotype_representation[i] = random.randint(0,(self.numberOfKnapsacksReference))
if self.genotype_representation[i] == 0:
break
else:
current_knapsack = next((sack for sack in knapsacks if sack.id == self.genotype_representation[i]),None)
if self.phenotype_representation[i].weight > current_knapsack.capacity:
continue
if self.phenotype_representation[i].weight <= current_knapsack.capacity:
fitnessScore += self.phenotype_representation[i].value
'''We now subtract the objects weight by the knapsacks capacity
so that we can keep track of how much space the knapsack has left
in the event that another object goes into the same knapsack
'''
current_knapsack.capacity = (current_knapsack.capacity - self.phenotype_representation[i].weight)
break
else:
fitnessScore += self.phenotype_representation[i].value
'''We now subtract the objects weight by the knapsacks capacity
so that we can keep track of how much space the knapsack has left
in the event that another object goes into the same knapsack
'''
knapsack.capacity = (knapsack.capacity - self.phenotype_representation[i].weight)
# update the chromosomes fitness
self.fitness = fitnessScore
class Knapsack:
def __init__(self, id, capacity):
self.id = id
self.capacity = capacity
class Population:
Phenotype = namedtuple('Phenotype', 'id weight value')
knapsackList = [] # list of knapsacks
knapSackEvaluationList = [] # used for generating fitness of chromosomes
population = []
def __init__(self, size):
self.populationSize = size
self.numberOfKnapsacks = 0
def select_parents(self,tournament):
'''
Tournament selection is being used to find two parents
'''
first_fittest_indiv = None
second_fittest_indiv = None
for individual in tournament:
# Check if this indivudal is fitter than the current fittist individual
if first_fittest_indiv == None or individual.fitness > first_fittest_indiv.fitness:
first_fittest_indiv = individual
tournament.remove(first_fittest_indiv)
for individual in tournament:
# Check if this indivudal is fitter than the current fittist individual
if second_fittest_indiv == None or individual.fitness > second_fittest_indiv.fitness:
second_fittest_indiv = individual
#print("FIRST: {}, SECOND: {}".format(first_fittest_indiv.fitness,second_fittest_indiv.fitness))
return (first_fittest_indiv,second_fittest_indiv)
def initialize_population(self):
'''
Read from a file and create the chromosomes
'''
# Open data file
dataFile = open('data.txt','r')
# Read how many knapsacks there will be. (We read the first byte)
numOfKnapsacks = int(dataFile.read(1))
self.numberOfKnapsacks = numOfKnapsacks
#print("NUMBER OF KNAPSACKS: {} ".format(numOfKnapsacks))
dataFile.seek(0,0);
# Read how many objects there will be.
numOfObjects = int(dataFile.readlines()[numOfKnapsacks+1])
# Create knapsack dictionary
lines_to_read = []
for num in range(0, numOfKnapsacks):
lines_to_read.append(num)
dataFile.seek(0,0)
for i,line in enumerate(dataFile):
if i == 0:
continue
elif i > 0 and i < numOfKnapsacks + 1:
capacity = int(line)
self.knapsackList.append(Knapsack((i), capacity))
# Create phenotype representation of chromosome
phenotype_representation = []
lineNumberOffset = numOfKnapsacks + 3 # file offset used to find the objects in the file
for i in range(0,numOfObjects):
value,weight = linecache.getline("data.txt", lineNumberOffset+i).split()
# Create the phenotype representation for each chromsome
phenotype_representation.append(self.Phenotype(i, int(value),int(weight)))
# Create the initial population
for j in range(0,self.populationSize):
# Create a new chromosome
new_chromosome = Chromosome(numOfKnapsacks,numOfObjects)
# Give each chromosome it's phenotype representation
new_chromosome.phenotype_representation = phenotype_representation
# Evaluate each chromosome
new_chromosome.generateFitness(self.knapsackList)
# Add the chromsome to the population
self.population.append(new_chromosome)
dataFile.close()
data.txt:
4
60
92
120
200
12
20 92
34 57
22 49
48 68
51 60
39 43
61 67
82 84
84 87
87 72
20 87
10 72
Explanation / Answer
In your code it is having Read for a file and create chromosomes
so this part is uded to read the data from a data.txt file given to you
and the code is given below which are the lines used to read the data from data.txt
and the explanation is given in comments
# this below line is used to open the data file
dataFile = open('data.txt','r')
# the below line is used to Read how many knapsacks there will be. (We read the first byte)
numOfKnapsacks = int(dataFile.read(1))
self.numberOfKnapsacks = numOfKnapsacks
#print("NUMBER OF KNAPSACKS: {} ".format(numOfKnapsacks))
dataFile.seek(0,0);
# the below line is used to Read how many objects there will be.
numOfObjects = int(dataFile.readlines()[numOfKnapsacks+1])
# The Below line is used to Create knapsack dictionary
lines_to_read = []
for num in range(0, numOfKnapsacks):
lines_to_read.append(num)
dataFile.seek(0,0)
As you asked for another workable datafile which consistes of weight and values is given below
180
92 23
57 31
49 29
68 44
60 53
43 38
67 63
84 85
87 89
72 82
Hope This Helps, if you have any doubts Please comment i will get back to you, thank you and please thumbs up