iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
0
AI & Data

GA Note - 基因演算法的世界系列 第 24

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

昨天的文章已經有在更新過了
實在是太趕了xddd
這個題目可能會一點一點跟大家介紹
期盼在雙十連假講完(受不了自己拖拖拉拉)
要給自己信心(?)


可以先把昨天的內容補上
(其實只有引入套件和設定path cost而已)

路徑成本

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

路徑圖形
path-cost

適應函數

那昨天定義完各條路徑的成本後,
我們來思考要怎麼去計算旅行一條路的成本
需要求解最小值
但是路徑的花費是正數
所以我們就用1/X這樣的方式取倒數
加起來就是變成最小值

  1. 計算旅程的長度
    tourLength用來求解整個旅程的長度
tourLength <- function(tour, distMatrix) {
  tour <- c(tour, tour[1])
  route <- embed(tour, 2)[, 2:1]
  sum(route)
}
  1. 計算成本
    將剛剛tourLength的總和用倒數呈現
tspfitness  <- function(tour, ...) 1/tourLength(tour, ...)

執行GA

執行迭代數(run):100

GA.fit <- ga(type = "permutation", 
             fitness = tspfitness, 
             distMatrix = data,
             lower  = 1, 
             upper = 5,
             popSize = 100,
             maxiter = 20,
             run = 10, 
             pmutation = 0.05, 
             monitor = NULL)

結果

GA.fit@solution結果

> GA.fit@solution
     x1 x2 x3 x4 x5
[1,]  4  3  1  5  2
[2,]  5  3  2  4  1
[3,]  4  5  1  3  2
[4,]  5  3  1  4  2
[5,]  2  5  1  4  3
[6,]  1  3  2  4  5

或是使用

summary(GA.fit)

今天的程式碼Github
剛剛在客運上刻完這篇 差點沒發成功(暈倒)


相關資料參考:
R Documentation-GA
GA包--遗传算法
RPubs - Optimized Delivery Route using Genetic Algorithm: Cost cutting for e-commerce
RPubs - Genetic Algorithm on TSP


上一篇
【Day23】GA with you - R 基因演算法應用於旅行銷售員問題 (1)
下一篇
【Day25】GA with you - R 基因演算法應用於旅行銷售員問題 (3)
系列文
GA Note - 基因演算法的世界30

尚未有邦友留言

立即登入留言