genetic_toolkit.py

importrandom
importlinecache
importcopy
fromcollectionsimportnamedtuple

# Class to represent biological processes
classBiologicalProcessManager:
'''
 Crossover Function

 - The process of One-Point crossover is exercised in this function.
 '''
defcrossover(crossover_rate, parentOne, parentTwo):
random_probability=random.random()

ifrandom_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.
 '''
defmutate(mutation_rate, child, numberOfKnapsacks):
forindex, positioninenumerate(child.genotype_representation):
random_probability=random.random()
'''
 (Random Resetting) "Flip" the position with another knapsack if probability < mutation_rate
 '''
ifrandom_probability<mutation_rate:
child.genotype_representation[index] =random.randint(0,numberOfKnapsacks)

# Class to represent chromosome
classChromosome:

fitness=None# Chromosomes fitness
phenotype_representation=None# Phenotype representation

def__init__(self, numOfKnapsacks, numOfObjects, genotype_representation=None):
self.numberOfKnapsacksReference=numOfKnapsacks
self.numberOfObjectsReference=numOfObjects

ifgenotype_representation==None:
self.genotype_representation= [random.randint(0,(numOfKnapsacks)) forxinrange(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
 '''
defgenerateFitness(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
fori, placement_of_objectinenumerate(self.genotype_representation):
ifplacement_of_object==0:
continue
else:
forknapsackinknapsacks:
ifknapsack.id==placement_of_object:
# if it's over the capacity, change it's bag and revaluate
ifself.phenotype_representation[i].weight>knapsack.capacity:
while(notdone):

self.genotype_representation[i] =random.randint(0,(self.numberOfKnapsacksReference))

ifself.genotype_representation[i] ==0:
break
else:
current_knapsack=next((sackforsackinknapsacksifsack.id==self.genotype_representation[i]),None)
ifself.phenotype_representation[i].weight>current_knapsack.capacity:
continue
ifself.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




classKnapsack:
def__init__(self, id, capacity):
self.id=id
self.capacity=capacity

classPopulation:

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

defselect_parents(self,tournament):
'''
 Tournament selection is being used to find two parents
 '''
first_fittest_indiv=None
second_fittest_indiv=None

forindividualintournament:
# Check if this indivudal is fitter than the current fittist individual
iffirst_fittest_indiv==Noneorindividual.fitness>first_fittest_indiv.fitness:
first_fittest_indiv=individual

tournament.remove(first_fittest_indiv)

forindividualintournament:
# Check if this indivudal is fitter than the current fittist individual
ifsecond_fittest_indiv==Noneorindividual.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)


definitialize_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: {} \n".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= []
fornuminrange(0, numOfKnapsacks):
lines_to_read.append(num)

dataFile.seek(0,0)
fori,lineinenumerate(dataFile):
ifi==0:
continue
elifi>0andi<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
foriinrange(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
forjinrange(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()