我正在使用 R 編程語言。
我發現這個（非常好的）教程展示了如何在 R 中實作旅行推銷員問題（針對一組歐洲城市）的遺傳演算法：
我的問題：
是否可以通過添加一些約束來“自定義”這個問題？例如，假設您絕對想從維也納開始您的旅行 - 有沒有辦法告訴遺傳演算法開始搜索第一個城市是維也納的最佳路徑？
是否可以指示遺傳演算法使某些城市處于某些位置？例如，您希望第一個城市是維也納，第六個城市是雅典——然后，在這些限制條件下尋找最佳路徑？
在優化旅行商問題時，是否可以自定義 R 中的遺傳演算法以考慮這些“考慮因素”？
uj5u.com熱心網友回復：
擴展我的評論。在處理遺傳演算法中的約束時，您有兩種選擇：
- 在適應度函式中加入條件
- 確保遺傳運營商創造可行的解決方案
使用第一種方法，您需要決定如何處理不可行的解決方案（例如懲罰），這非常依賴于問題。如果條件難以達到，進化演算法在這個程序中產生的大部分解都是不可行的，會導致過早收斂。
哪種適應方法取決于問題，我將向您展示如何針對此問題實施第二種方法。
矩陣變換：
transformMatrix <- function(fixed_points, D){
if(length(fixed_points) == 0) return(D)
p <- integer(nrow(D))
pos <- match(names(fixed_points), colnames(D))
p[fixed_points] <- pos
p[-fixed_points] <- sample(setdiff(seq_len(nrow(D)), pos))
D[p, p]
}
此函式的目標是置換矩陣的行和列以使城市到達指定位置：
popSize <- 100
fixed_points <- c(
"Vienna" = 1,
"Athens" = 6
)
D_perm <- transformMatrix(fixed_points, D)
可行初始種群
feasiblePopulation <- function(n, size, fixed_points){
positions <- setdiff(seq_len(n), fixed_points)
m <- matrix(0, size, n)
if(length(fixed_points) > 0){
m[, fixed_points] <- rep(fixed_points, each = size)
for(i in seq_len(size))
m[i, -fixed_points] <- sample(positions)
} else {
for(i in seq_len(size))
m[i,] <- sample(positions)
}
m
}
此功能創建可行的解決方案
突變
mutation <- function(n, fixed_points){
positions <- setdiff(seq_len(n), fixed_points)
function(obj, parent){
vec <- obj@population[parent,]
if(length(positions) < 2) return(vec)
indices <- sample(positions, 2)
replace(vec, indices, vec[rev(indices)])
}
}
我們需要確保變異算子保持固定位置。該函式回傳一個這樣的變異算子。
適應度函式
fitness <- function(tour, distMatrix) {
tour <- c(tour, tour[1])
route <- embed(tour, 2)[,2:1]
1/sum(distMatrix[route])
}
我們希望最小化距離，因此取倒數。
優化步驟
res <- ga(
type = "permutation",
fitness = fitness,
distMatrix = D_perm,
lower = 1,
upper = nrow(D_perm),
mutation = mutation(nrow(D_perm), fixed_points),
crossover = gaperm_pmxCrossover,
suggestions = feasiblePopulation(nrow(D_perm), popSize, fixed_points),
popSize = popSize,
maxiter = 5000,
run = 500,
pmutation = 0.2
)
gaperm_pmxCrossover will insure that fixed positions stay fixed during the crossover process (that is why I didn't write custom crossover operator)
solution
colnames(D_perm)[res@solution[1,]]
solution_distance <- 1 / fitness(res@solution[1,], D_perm)
Also first city is last (route)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452515.html
上一篇：在陣列中查找并不總是一致的模式