Using a Genetic-esque Algorithm To Solve The 0/1 Knapsack Problem

11_genetic algorithm

Below is an example of a genetic algorithm that was coded in R as a solution to a specific 0/1 knapsack problem.  This algorithm is called a genetic algorithm because the methods it uses to maximize the value of our solution vectors are based on the types of things that occur within the reproduction of chromosomes. The basic idea behind the maximization effect in the genetic algorithm runs parallel to the basic ideas behind the reproductive mechanisms at play in survival of the fittest (SOF) type of evolutionary activity in populations.  In a population that is expanding along a survival of the fittest type of trajectory the members of the population that are the fittest for survival are also the members of the population that reproduce the most. These fit parents will give rise to offspring that contain some blend of the parent’s genetic material and through this blending of genetic material, there will be a general increase in the fitness of the offspring over the long run. That is, fit parents make fitter offspring and allowing fitter parents to reproduce more will produce a population that is increasingly fit.  The algorithm takes an initial collection of chromo- some (solutions) and uses them to create generation after generation of increasingly fit chromosomes through the action of fitness, selection, crossover, and mutation. The simulation requires ‘plyr’ and ‘Rcpp’ be installed.

set.seed(23)
pop_size=500
growth_bound=3000
initial_size=pop_size
library(plyr)

#Enter the list of items, weights, and values
item=c("map","compass","water","sandwich","glucose","tin","banana","apple","cheese", 
	"beer","suntan_cream","camera","T-shirt","trousers","umbrella", 
	"waterproof_trousers","waterproof_overclothes","note-case","sunglasses","towel", 
	"socks","book")
weight=c(9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30)
value=c(150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10)
V=400
i=1

pop_value<-c(rep(0,pop_size))
pop_weight<-c(rep(0,pop_size))
population<-matrix(nrow=pop_size,ncol=22)
population_1<-matrix(nrow=pop_size,ncol=24)

####################################################
###Generate the initial pool of 'nsim' chromosomes
####################################################
while(i<=pop_size){
x<-rbinom(22,1,prob=.5)
	if(sum(x*weight)<V){
		population[i,]=x;i=i+1
	}
}
for(i in 1:pop_size){
	pop_weight[i]=sum(population[i,]*weight);
	pop_value[i]=sum(population[i,]*value);
	}
pop_select<-as.data.frame(cbind(population,pop_weight,pop_value))
sorted_pop<-arrange(pop_select,desc(pop_value))

####################################################	
###items needed for the main loop
####################################################
k=pop_size
#Selection Function
grp0=1;grp1=k/4;grp2=k/2;grp3=3*k/4;grp4=k
parents<-c(rep(0,2))
group_select<-c(1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4)
pop_index<-c(1:pop_size)
N=1;j=1
maxfitness<-c()

####################################################
##Begin selection, reproduction loop
####################################################
while(N<growth_bound){	

#######selection###
parent_groups<-sample(group_select,2,replace=TRUE)
parent_groups
selected<-c(rep(0,2))
for(i in 1:2){
	if(parent_groups[i]==1){selected[i]=floor(runif(1,grp0,grp1))}
	if(parent_groups[i]==2){selected[i]=floor(runif(1,grp1,grp2))}
	if(parent_groups[i]==3){selected[i]=floor(runif(1,grp2,grp3))}
	if(parent_groups[i]==4){selected[i]=floor(runif(1,grp3,grp4))}
}

######crossover##
crossover<-sample(1:21,1)
child_1<-c(rep(0,24))
child_2<-c(rep(0,24))

child_1[1:crossover]=sorted_pop[selected[1],1:crossover]
child_1[(crossover+1):22]=sorted_pop[selected[2],(crossover+1):22]
child_2[1:crossover]=sorted_pop[selected[2],1:crossover]
child_2[(crossover+1):22]=sorted_pop[selected[1],(crossover+1):22]

######mutation##
for(i in 1:22){
	if(child_1[i]==0){child_1[i]=1-rbinom(1,1,.995)}
	if(child_1[i]==1){child_1[i]=1-rbinom(1,1,.005)}	
	if(child_2[i]==0){child_2[i]=1-rbinom(1,1,.995)}
	if(child_2[i]==1){child_2[i]=1-rbinom(1,1,.005)}
}

child_1_wt=sum(as.data.frame(child_1[1:22])*weight)
child_1_val=sum(as.data.frame(child_1[1:22])*value)
child_2_wt=sum(as.data.frame(child_2[1:22])*weight)
child_2_val=sum(as.data.frame(child_2[1:22])*value)

######check fitness of offspring##
while(child_1_wt>V){
	flip<-sample(1:22,1)
	if(child_1[flip]==0){child_1[flip]=0}
	if(child_1[flip]==1){child_1[flip]=0}
	child_1_wt=sum(as.data.frame(child_1[1:22])*weight)	
}
while(child_2_wt>V){
	flip<-sample(1:22,1)
	if(child_2[flip]==0){child_2[flip]=0}
	if(child_2[flip]==1){child_2[flip]=0}
	child_2_wt=sum(as.data.frame(child_2[1:22])*weight)	
}
child_1[23]=child_1_wt
child_2[23]=child_2_wt
child_1[24]=sum(as.data.frame(child_1[1:22])*value)	
child_2[24]=sum(as.data.frame(child_2[1:22])*value)	

######Insert the two offspring into the population
sorted_pop[initial_size+N,1:24]<-as.data.frame(child_1)
sorted_pop[initial_size+N+1,1:24]<-as.data.frame(child_2)

sorted_pop<-arrange(sorted_pop,desc(pop_value))
maxfitness[j]=sorted_pop[1,24]
cat(paste0("iteration: ", j,"\n"))
j=j+1
N=N+2
######End Loop
}

######Output Solution
sorted_pop[1,]
plot(maxfitness)
lines(maxfitness)

Quartz %d

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s