DAY 25
0
AI & Data

## 【Day25】GA with you - R 基因演算法應用於旅行銷售員問題 (3)

(重複的地方還請大家多多見諒)

### 路徑成本

``````# fitness vector
A<-c(0,25,25,10,35)
B<-c(25,0,25,35,25)
C<-c(25,25,0,30,15)
D<-c(10,35,30,0,20)
E<-c(35,25,15,20,0)
city<-rbind(A,B,C,D,E)
colnames(city)<-c('A','B','C','D','E')
city<-as.matrix(city)
``````

### 適應函數

``````tourLength <- function(tour, distMatrix) {
tour <- c(tour, tour[1])
route <- embed(tour, 2)[,2:1]
sum(distMatrix[route])
}
``````

### 監控函數

``````#monitor
monitor<-function(obj){
len<-tourLength(obj@population[1:5,])
pop<-obj@population[1:5,]
print(cbind(pop, len))
}
``````

### 執行基因演算法

``````GA.fit <- ga(type = "permutation",
fitness = tspfitness,
distMatrix = as.matrix(city),
lower = 1,
upper = 5,
popSize = 10,
maxiter = 500,
run = 100,
pmutation = 0.2,
monitor = NULL)
``````

### 繪製結果

``````getAdj <- function(tour) {
n <- length(tour)
from <- tour[1:(n - 1)]
to <- tour[2:n]
m <- n - 1
A <- matrix(0, m, m)
A[cbind(from, to)] <- 1
A <- A + t(A)
return(A)
}
``````
``````# 2-d coordinates
mds <- cmdscale(city)
x <- mds[, 1]
y <- -mds[, 2]
n <- length(x)
``````
``````B <- 100
fitnessMat <- matrix(0, B, 2)
A <- matrix(0, n, n)
for (b in seq(1, B)) {
# run a GA algorithm
GA.rep <- ga(type = "permutation",
fitness = tspfitness,
distMatrix = as.matrix(city),
lower = 1,
upper = 5,
popSize = 10,
maxiter = 50,
run = 100,
pmutation = 0.2,
monitor = NULL)

tour <- GA.rep@solution[1, ]
tour <- c(tour, tour[1])
#fitnessMat[b, 1] <- GA.rep@bestSol[GA.rep@iter]
#fitnessMat[b, 2] <- GA.rep@mean[GA.rep@iter]
}

``````
``````plot.tour <- function(x, y, A) {
n <- nrow(A)
for (ii in seq(2, n)) {
for (jj in seq(1, ii)) {
w <- A[ii, jj]
if (w > 0)
lines(x[c(ii, jj)], y[c(ii, jj)], lwd = w, col = "lightgray")
}
}
}

plot(x, y, type = "n", asp = 1, xlab = "", ylab = "", main = "Tour after GA converged")
points(x, y, pch = 16, cex = 1.5, col = "grey")
abline(h = pretty(range(x), 10), v = pretty(range(y), 10), col = "lightgrey")
tour <- GA.fit@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 = 45,
col = "steelblue", lwd = 2)
text(x, y - 100, labels(city)[[1]], cex = 0.8)

``````