 # Constrained Knapsnack problem with Genetic algorithm

Hello,

I have a very simple Knapsack problem. I would like to constrain it but I am not exactly sure how to get the GA package to do it. Essentially, I want to stop the optimization from being able to select more than one food item. So all best possible solutions can include one food item but not more than one. So in this case beans which is item 2 with profit 6 and weight 3 cannot be selected with "potatoes" which is item 3 with profit 6 and weight 3.

``````library(GA)
library(tidyverse)

# Define data
item = c("pocketknife", "beans", "potatoes", "unions",
"sleeping bag", "rope", "compass", "gps", "tar")
p <- c(6, 3, 6, 4, 6, 8, 6, 8, 10) # Profits
w <- c(3, 3, 3, 7, 2, 3, 1, 4, 5) # Weights
W <- 19 # Knapsack ’s capacity
n <- length(p) # Number of items

# Define fitness function
knapsack <- function(x) {
f <- sum(x * p)
penalty <- sum(w) * abs(sum(x * w) - W)
}

#Genetic Algorithm--------------------------------------------------------------
genetic_alg_output <- ga(type="binary",
fitness=knapsack ,
nBits=n,
maxiter=200, # Maximum number of generations
run=100,     # Stop if the best-so-far fitness
# hasn't improved for 'run' generations
popSize=1000,
keepBest = TRUE,
seed=101)

final_solutions <- genetic_alg_output@solution
print(final_solutions)

``````

This topic was automatically closed 21 days after the last reply. New replies are no longer allowed.