メタヒューリスティクス

第15章メタヒューリスティクス

放送授業の遺伝的アルゴリズムの数値例をRのGAパッケージでやってみる
参考
http://rstudio-pubs-static.s3.amazonaws.com/13578_fb1794c413a249d5bb891932c8cf34e9.html

library("GA")
#ga関数のパラメータ
population =400
selection =4 
mutation =8
crossover =380
r<-200
#授業サイトpos.citiesを使わせてもらいます
nc <- 30 #正30角形
pos.cities <- function(n) {
  th0 <- seq(0, 2*pi, length=(n+1))
  th <- th0[1:n]
  z <- matrix(numeric(2*n), ncol=2)
  z[,1] <- cos(th)
  z[,2] <- sin(th)
  return(z)
}
cities <- pos.cities(nc)
cdist<-dist(cities, method = "euclidean", diag = FALSE, upper = FALSE)
D <- as.matrix(cdist)
tourLength <- function(tour, distMatrix) {
  our <- c(tour, tour[1])
  route <- embed(tour, 2)[,2:1]
  sum(distMatrix[route]) 
}
tspFitness <- function(tour, ...) 1/tourLength(tour, ...)
GA <- ga(type = "permutation", fitness = tspFitness, distMatrix = D,min = 1, 
         max = attr(cdist, "Size"), popSize = 400, maxiter = r,
         run = r , pcrossover = 0.95, pmutation = 0.02)
summary(GA)

Genetic Algorithm

GA settings:
Type = permutation
Population size = 400
Number of generations = 200
Elitism = 20
Crossover probability = 0.95
Mutation probability = 0.02

GA results:
Iterations = 200
Fitness function value = 0.1649443
Solutions =
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18
[1,] 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 30 29 28
[2,] 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
x19 x20 … x30
[1,] 27 26 16
[2,] 30 29 19

#図の表示
mds <- cmdscale(cdist)
x <- mds[, 1]
y <- -mds[, 2]
plot(x, y, type = "n", asp = 1, xlab = "", ylab = "")
abline(h = pretty(range(x), 10), v = pretty(range(y), 10),col = "light gray")
tour <- GA@solution[1, ]
tour <- c(tour, tour[1])
n <- length(tour)
arrows(x[tour[-n]], y[tour[-n]], x[tour[-1]], y[tour[-1]],
       length = 0.15, angle = 25, col = "steelblue", lwd = 2)
text(x, y, labels(""), cex=0.8)
#tour
tourLength(tour,D);2*pi*1

[1] 6.271708
[1] 6.283185

ちなみに
nc <- 57
r<-1000

でやってみたら、

[1] 12.34934
[1] 6.283185

でした。