bug in SA code

jmsallan · Jul 1, 2018 · 343e39c · 343e39c
1 parent d5f50e5
commit 343e39c
Show file tree

Hide file tree

Showing 7 changed files with 54 additions and 59 deletions.
diff --git a/.DS_Store b/.DS_Store
diff --git a/FlowShop/code/functionsFS2.R b/FlowShop/code/functionsFS2.R
@@ -452,7 +452,7 @@ SAFS <- function(Instance, inisol, Tmax=1000, mu=1, eval=FALSE){
   bestfit <- fit
   T <- Tmax
   n <- length(inisol)
-  num.moves <- n*(n-3)/2
+  num.moves <- (n-1)^2
 
   #generating list of moves
 
@@ -485,7 +485,7 @@ SAFS <- function(Instance, inisol, Tmax=1000, mu=1, eval=FALSE){
       } 
 
     }else{
-      if(exp(-mu*(testfit-fit)) > runif(1)){
+      if(exp(-mu*(testfit-fit)/T) > runif(1)){
         sol <- testsol
         fit <- testfit
       }

diff --git a/KP/.Rhistory b/KP/.Rhistory
@@ -1,52 +1,47 @@
+setwd("~/Documents/heuristics/FlowShop")
+load("instances/TaillardFS.RData") #load instances
+source("code/FSfunctions.R")       #load code with functions
+SA(test$tij, 1:20, 500, 10000)  #simulated annealing
+test <- tai20.5[[1]]
+makespan(test$tij, 1:20)
+HillClimbing(test$tij, 1:20)
+SA(test$tij, 1:20, 500, 10000)  #simulated annealing
+TS(test$tij, 1:20, 1000)        #tabu search
+rm(list=ls())
+source("code/functionsFS2.R")
+Instance <- matrix(sample(10:50, 100, replace = TRUE), 5, 20)
+SA01 <- SAFS(Instance, 1:20, Tmax=10000)
+TS01 <- TSFS(Instance, 1:20, eval = TRUE)
+setwd("~/Documents/heuristics/TSP")
+source("code/functionsTSP2.R")
+TestSample <- SampleTSP(30, seed=1313)
+set.seed(1313)
+SA01 <- SATSP2opt(TestSample, sol, Tmax=3000, mu=10, eval = TRUE)
+sol <- 1:30
+SA01 <- SATSP2opt(TestSample, sol, Tmax=3000, mu=10, eval = TRUE)
+SA01 <- SATSP2opt(TestSample$distances, sol, Tmax=3000, mu=10, eval = TRUE)
+TS01 <- TSTSP2opt(TestSample$distances, sol, asp=TRUE, eval=TRUE)
+View(TS01)
+SA01 <- SATSP2opt(TestSample$distances, sol, Tmax=30000, mu=10, eval = TRUE)
+SA01 <- SATSP2opt(TestSample$distances, sol, Tmax=300000, mu=10, eval = TRUE)
+set.seed(1313)
+SA01 <- SATSP2opt(TestSample$distances, sol, Tmax=300000, mu=100, eval = TRUE)
 setwd("~/Documents/heuristics/KP")
 source("code/functionsKP.R")
-easy <- list(w=c(30, 45, 15, 40, 35, 5), u=c(24, 108, 30, 100, 80.5, 3), W=100)
-hard <- list(w=c(30, 45, 15, 70, 35, 5), u=c(24, 108, 30, 175, 80.5, 3), W=100)
-InstanceKP10 <- KPInstance01(1000, 10, 40)
-InstanceKP50 <- KPInstance01(1000, 50, 40, 2424)
-InstanceKP100  <- KPInstance01(1000, 100, 40, 3333)
-bandb.easy <- BandBKP(easy)
-bandb.hard <- BandBKP(hard)
-bandb.KP10 <- BandBKP(InstanceKP10)
-bandb.KP50 <- BandBKP(InstanceKP50)
-bandb.KP100 <- BandBKP(InstanceKP100)
-source("code/functionsKP.R")
 #generating large instance
 set.seed(111)
 LargeInstance <- EasyInstance(1000, 0.4)
 #starting solution
 inisolLIEmpty <- sample(c(TRUE, FALSE), 1000, replace = TRUE, prob = c(0.1, 0.9))
-#solving with heuristic
-LIheuristic <- HeuristicKP(LargeInstance)
+Tmax <- 1000
+SA01 <- SAKP(Inst=LargeInstance, Tmax=Tmax, inisol = inisolLIEmpty, eval=TRUE)
 #optimal solution with LP
 LILP <- LPKP(LargeInstance)
-Tmax <- 1000
+Tmax <- 10000
 SA01 <- SAKP(Inst=LargeInstance, Tmax=Tmax, inisol = inisolLIEmpty, eval=TRUE)
-plot(1:100, SA01$evalfit[1:100], type="l", col="red", xlab = "", ylab = "")
-lines(1:100, SA01$evalbest[1:100], col="blue")
-lines(1:100, SA01$evaltest[1:100], col="green")
-#simulated annealing with same evals of objective function as TS
 Tmax <- 500000
 SA02 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1, inisol = inisolLIEmpty, eval=FALSE)
+#aspiration condition
 TS01 <- TSKP(Inst=LargeInstance, inisol = inisolLIEmpty, tabu.size = 100, iter=500, asp = TRUE, eval=TRUE)
-plot(1:500, TS01$evalfit[1:500], type="l", col="red", xlab = "", ylab = "")
-lines(1:500, TS01$evalbest[1:500], col="blue")
-TS02 <- TSKP(Inst=LargeInstance, inisol = inisolLIEmpty, tabu.size = 100, asp=FALSE, iter=500, eval=TRUE)
-plot(1:500, TS02$evalfit, type="l", col="red", xlab = "", ylab = "")
-lines(1:500, TS02$evalbest, col="blue")
-#analyzing last iterations
-plot(350:500, TS01$evalfit[350:500], type="l", col="red", xlab = "", ylab = "")
-lines(350:500, TS01$evalbest[350:500], col="blue")
-plot(350:500, TS02$evalfit[350:500], type="l", col="red", xlab = "", ylab = "")
-lines(350:500, TS02$evalbest[350:500], col="blue")
-#behaviour of last iterations with aspiration condition
-TS01$move[450:500]
-TS01$evalfit[450:500]
-LargeInstance$u[c(781, 777, 380, 485, 721, 768, 679)]
-TS03 <- TSKP(Inst=LargeInstance, inisol = LIheuristic$sol, tabu.size = 100, asp=FALSE, iter=500, eval=TRUE)
-SA03 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1, inisol = LIheuristic$sol, eval=FALSE)
-SA04 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1, inisol = inisolLIEmpty, eval=FALSE)
-plot(1:500, TS03$evalfit, type="l", col="red", xlab = "", ylab = "")
-lines(1:500, TS03$evalbest, col="blue")
-plot(1:10, TS03$evalfit[1:10], type="l", col="red", xlab = "", ylab = "")
-lines(1:10, TS03$evalbest[1:10], col="blue")
+SA02 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=100, inisol = inisolLIEmpty, eval=FALSE)
+SA02 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1000, inisol = inisolLIEmpty, eval=FALSE)
diff --git a/KP/code/functionsKP.R b/KP/code/functionsKP.R
@@ -84,7 +84,7 @@ SAKP <- function(Inst, inisol, Tmax=1000, mu=1, eval=FALSE){
       } 
 
     }else{
-      if(exp(-mu*(fit-testfit)) > runif(1)){
+      if(exp(-mu*(fit-testfit)/T) > runif(1)){
         sol <- testsol
         fit <- testfit
       }

diff --git a/KP/demoTSandSA.R b/KP/demoTSandSA.R
@@ -33,7 +33,7 @@ lines(1:100, SA01$evaltest[1:100], col="green")
 #simulated annealing with same evals of objective function as TS
 
 Tmax <- 500000
-SA02 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1, inisol = inisolLIEmpty, eval=FALSE)
+SA02 <- SAKP(Inst=LargeInstance, Tmax=500000, mu=1000, inisol = inisolLIEmpty, eval=FALSE)
 
 
 #tabu search behaviour

diff --git a/TSP/code/functionsTSP2.R b/TSP/code/functionsTSP2.R
@@ -312,7 +312,7 @@ SATSP2opt <- function(D, inisol, Tmax=1000, mu=1, eval=FALSE){
       } 
 
     }else{
-      if(exp(-mu*(testfit-fit)) > runif(1)){
+      if(exp(-mu*(testfit-fit)/T) > runif(1)){
         sol <- move2opt(sol, i, k)
         fit <- testfit
       }

diff --git a/TSP/testing2opt.R b/TSP/testing2opt.R
@@ -44,15 +44,15 @@ solnn <- NearestNeighbour(Instance10)
 TestSample <- SampleTSP(30, seed=1313)
 
 sol <- 1:30
-sol2 <- NearestNeighbour(TestSample)
-TSP(TestSample, sol)
+sol2 <- NearestNeighbour(TestSample$distances)
+TSP(TestSample$distances, sol)
 
-HC01 <- HillClimbing2opt(TestSample, sol)
-HC02 <- HillClimbing2opt(TestSample, sol2$sol)
+HC01 <- HillClimbing2opt(TestSample$distances, sol)
+HC02 <- HillClimbing2opt(TestSample$distances, sol2$sol)
 
 #----testing tabu search----
 
-TS01 <- TSTSP2opt(TestSample, sol, asp=TRUE, eval=TRUE)
+TS01 <- TSTSP2opt(TestSample$distances, sol, asp=TRUE, eval=TRUE)
 
 pdf("tabu.pdf", height=5, width = 10)
 par(mfrow=c(1,2))
@@ -66,7 +66,7 @@ plot(1:100, TS01$evalgain, type = "l", col = "blue", lwd=2, xlab="", ylab="")
 
 #----search without tabu list----
 
-Silly01 <- SillyTSP2opt(TestSample, sol)
+Silly01 <- SillyTSP2opt(TestSample$distances, sol)
 
 pdf("silly.pdf", height=5, width = 10)
 par(mfrow=c(1,2))
@@ -81,7 +81,7 @@ plot(1:100, Silly01$evalgain, type = "l", col = "blue", lwd=2, xlab="", ylab="",
 #----testing simulated annealing----
 
 set.seed(1313)
-SA01 <- SATSP2opt(TestSample, sol, Tmax=3000, mu=10, eval = TRUE)
+SA01 <- SATSP2opt(TestSample$distances, sol, Tmax=300000, mu=100, eval = TRUE)
 
 pdf("SAevol.pdf", height=5, width = 10)
 par(mfrow=c(1,2))
@@ -95,31 +95,31 @@ lines(2500:3000, SA01$evalfit[2500:3000], col ="red")
 dev.off()
 
 set.seed(1313)
-SA02 <- SATSP2opt(TestSample, sol, Tmax=40500, mu=10, eval = FALSE)
+SA02 <- SATSP2opt(TestSample$distances, sol, Tmax=40500, mu=10, eval = FALSE)
 
 
 #----testing GRASP----
 
-for(i in 1:10) print(GRASP(TestSample, 2))
+for(i in 1:10) print(GRASP(TestSample$distances, 2))
 
 set.seed(1111)
-GRASP01 <- GRASP2opt(TestSample, rcl.size = 2, tries = 10)
+GRASP01 <- GRASP2opt(TestSample$distances, rcl.size = 2, tries = 10)
 
 set.seed(1111)
-GRASP02 <- GRASP2opt(TestSample, rcl.size = 2, ls="SA", tries = 10)
+GRASP02 <- GRASP2opt(TestSample$distances, rcl.size = 2, ls="SA", tries = 10)
 
 GRASP01$report
 GRASP02$report
 
 #---- testing ILS ----
 
 sol <- 1:30
-ILS01 <- ILSTSTSP2opt(TestSample, sol)
+ILS01 <- ILSTSTSP2opt(TestSample$distances, sol)
 
 #---- testing GA ----
 
-GA01.TestSample <- GATSP(TestSample, npop=100, iter = 500, pmut = 1)
-GA02.TestSample <- GATSP(TestSample, npop=100, crOX=FALSE, iter = 500, pmut = 1)
-GA03.TestSample <- GATSP(TestSample, npop=100, crOX=FALSE, iter = 100, pmut = 1, memetic = TRUE, verbose=TRUE, alpha=0.1)
+GA01.TestSample <- GATSP(TestSample$distances, npop=100, iter = 500, pmut = 1)
+GA02.TestSample <- GATSP(TestSample$distances, npop=100, crOX=FALSE, iter = 500, pmut = 1)
+GA03.TestSample <- GATSP(TestSample$distances, npop=100, crOX=FALSE, iter = 100, pmut = 1, memetic = TRUE, verbose=TRUE, alpha=0.1)