Ufdjrw

Simple knapsack type, binary optimization with 1 constraint using the GA package in R.

With a known optimal solution of say 5% of total population size, a 0 solution set is always returned. For some reason the search space never seems to include sparse solutions (e.g. binary 10000000000000000000, 01000000000000000000).

Here the optimal solution is 1 item selected when the max cost is set to 5, however a 0 set is always returned unless we up the max cost constraint to allow ~30% of the total population to be optimal.

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, ]))

And Result:

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

I've tried ample combinations of parameters, including the pmutation, pcrossover, popSize, and run iterations, with no luck. I've also tried the genalg::rbga.bin() function with the same results.

No matter, when the optimal solution is sparse, I'm unable to return any solution.

I'm assuming it's either my design, fitness function, or possibly something to do with the stochastic GA approach. Any help is greatly appreciated.