#############################################################
#
# Binarni genetski algoritem
#
#############################################################

#prenesemo paket
install.packages("genalg")
#uporabimo paket
library(genalg)
#preprost primer: iščemo gen(rešitev) s samimi enicami (1111111111)

evaluate <- function(string=c())
{
	returnVal = 1 / sum(string)
  	returnVal
}

#size - velikost gena/velikost problema 
#iter - število iteracij
#mutationChacne - verjetnost, da bo prišlo do mutacije
#zeroToOneRatio - začetno razmerje med enicami in ničlami v genih
#evalFunc - kriterijska funckija za ocenjevanje kakovosti gena
rbga.results = rbga.bin(size = 10, iter = 50, mutationChance=0.01, zeroToOneRatio=0.5, evalFunc=evaluate)

#plot(rbga.results)
summary(rbga.results, echo = T)

##############################################################
#
#reševanje 0-1 nahrbtnika
#
##############################################################

#rgba uporablja naključna števila, zato podamo seme, da dobimo enake rezultate
set.seed(123)

#nakljucno generiramo cene in teze predmetom ter kapaciteto nahrbtnika
Cene <- runif(40, 1, 100)
Teze <- runif(40, 1, 10)
Kapaciteta <- sum(Teze)*0.6

#izpis podatkov
data.frame(Cene, Teze)
Kapaciteta

#kriterijska funkcija, ki se uporablja za 0-1 nahrbtnik
evaluate.ks <- function(izbira)
{
	t <- sum(Teze[izbira==1])
	c <- sum(Cene[izbira==1])

	#negativno ocenimo prevelike teze
	if(t > Kapaciteta)
	{
		c <- - t * 10
	}
	#obrnemo rezultat, ker iscemo minimum 
	return(-c)
}

rbga.results = rbga.bin(size = 40, iter = 150, mutationChance=0.01, zeroToOneRatio=20, evalFunc=evaluate.ks, verbose = TRUE)

summary(rbga.results, echo = TRUE)

bestIndex <- which.min(rbga.results$evaluations)
best <- rbga.results$population[bestIndex,]
best

plot(rbga.results)

#poglejmo kako dobro smo napolnili nahrbtnih ter preostale vrednosti
Kapaciteta
sum(Teze[best==1])
sum(Cene[best==1])
Teze[best == 0]



#############################################################
#
# Prikaz delovanja GA s spreminjanjem parametrov
#
#############################################################

library(genalg)

#definiramo kriterisko funkcijo, ki se poskuša približati številim pi in koren iz 50
evaluate <- function(string=c())
{
	returnVal = NA;
  	if(length(string) == 2)
	{
    		returnVal = abs(string[1]-pi) + abs(string[2]-sqrt(50))
  	}
  	else 
	{
    		stop("Expecting a chromosome of length 2!")
  	}
  	returnVal
}

#definiramo monitor, da lahko opazujemo dogajanje posamezne generacije
monitor <- function(obj)
{
	xlim = c(obj$stringMin[1], obj$stringMax[1])
  	ylim = c(obj$stringMin[2], obj$stringMax[2])
  	plot(obj$population, xlim=xlim, ylim=ylim, xlab="pi", ylab="sqrt(50)")
  	bestgene <- which(min(obj$evaluations) == obj$evaluations)
  	points(obj$population[bestgene,], col="red")
  	abline(v = pi)
  	abline(h = sqrt(50))
  	Sys.sleep(0.1)
}

#poskusamo poiskati ti dve vrednosti z genetskim algoritmom (R based genetic algorithm - rbga)
rbga.results = rbga(c(0, 0), c(5, 10), monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.01)

#poglejmo povzetek rezultatov
summary(rbga.results, echo = TRUE)

#najboljsi rezultat, ki smo ga dobili (iscemo lahko v zadnji generaciji, ker uporabljamo elitizem)
best <- which.min(rbga.results$evaluations)
rbga.results$population[best,]

#graficni prikaz rezultatov (kako se najboljsa in povprecna resitev spreminjata s casom)
plot(rbga.results)

#histogram, ki prikazuje frekvenco vrednosti v populaciji
plot(rbga.results, type="hist")


#prikaz zakaj potrebujemo mutacijo
#zgenerirajmo zacetne gene, ki so slabi

#ce ne uporabimo mutacije, ostanemo v zacetnem prostoru (ne moremo preiskati vseh vrednosti)
sug <- matrix(c(runif(1999, 1, 2), runif(1999,3,4)), nrow=1999, ncol=2)
rbga.results = rbga(c(0, 0), c(5, 10),iters = 50, suggestions = sug, popSize = 2000, elitism = 0.05*2000, monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.0)
plot(rbga.results)

#z mutacijo lahko gremo iz tega prostora in dobimo boljso resitev
rbga.results = rbga(c(0, 0), c(5, 10),iters = 50, suggestions = sug, popSize = 2000, elitism = 0.05*2000, monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.01)
plot(rbga.results)

#prikaz vpliva posamezne spremenljivke na funkcijo uspesnosti
plot(rbga.results, type="vars")


#prevelika mutacija in brez elitizma (nakljucno iskanje)
rbga.results = rbga(c(0, 0), c(5, 10), iter = 50, monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.1, elitism = 0)

plot(rbga.results)

summary(rbga.results, echo = TRUE)

#ohrani samo najboljšo vrednost
rbga.results = rbga(c(0, 0), c(5, 10), iter = 50, monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.01, elitism = 1)
plot(rbga.results)

#ohrani 10 najboljših vrednosti (povprečna vrednost se hitreje približuje najboljši rešitvi)
rbga.results = rbga(c(0, 0), c(5, 10), iter = 50, monitorFunc=monitor, evalFunc=evaluate, verbose=TRUE, mutationChance=0.01, elitism = 10)
plot(rbga.results)