Оптимизация генетического алгоритма в R не учитывает разреженных решений - PullRequest
Новая
       54

Оптимизация генетического алгоритма в R не учитывает разреженных решений

0 голосов
/ 08 марта 2019

Простой тип ранца, двоичная оптимизация с 1 ограничением с использованием пакета GA в R.

При известном оптимальном решении, скажем, 5% от общей численности населения, всегда возвращается 0 набор решений.По какой-то причине в область поиска никогда не входят разреженные решения (например, двоичные 10000000000000000000, 01000000000000000000).

Здесь оптимальным решением является 1 элемент, выбранный при максимальной стоимости, равной 5, однако всегда возвращается 0 наборовесли мы не увеличим ограничение максимальной стоимости, чтобы ~ 30% от общей численности населения были оптимальными. 

library(GA)
options(scipen = 999)

set.seed(348821)
n <- 20
optim_n <- 1
a <- data.frame(item = c(1:n),
            cost = c(rep(5, optim_n), sample(1000:5000, n - optim_n)),
            value = sample(1:500, n))

a <- a[order(a$cost), ]
a$cum.cost <- cumsum(a$cost)

head(a)
   item cost value cum.cost
1     1    5   208        5
19   19 1087    48     1092
20   20 1472   179     2564
5     5 1521   449     4085
15   15 1801   102     5886
13   13 2192    41     8078

# RHS Constraint
max_cost <- 5

# Fitness Function
fit_func <- function(x) {
    iter_cost <- x %*% a$cost
    iter_value <- x %*% a$value

    if(iter_cost > max_cost) {
        return(0)
    } else {
        return(iter_value)
    }
}

# Run
select <- ga(type = "binary",
             nBits = nrow(a),
             maxiter = 1000,
             run = 250,
             fitness = fit_func,
             popSize = 1000)

# Print Results
cat("\n","Fitness Value:        ", select@fitnessValue, "\n",
"Items Selected:       ", if(select@fitnessValue == 0) { 0 } else { sum(select@solution) }, "\n",
"Min Optimal Selection:", nrow(a[a$cum.cost <= max_cost, ]))

И Результат: 

Fitness Value:         0 
Items Selected:        0 
Min Optimal Selection: 1

Я пробовал множество комбинаций параметров,включая pmutation, pcrossover, popSize и запускать итерации, не повезло.Я также попробовал функцию genalg :: rbga.bin () с теми же результатами.

Независимо от того, когда оптимальное решение редкое, я не могу вернуть любое решение.

Я предполагаю, что это либо мой дизайн, фитнес-функция, либо, возможно, что-то связанное со стохастическим подходом ГА.Любая помощь очень ценится.

...