0
$\begingroup$

I have a set of 31390 individuals with an associated weight (kg) and I want to select a number of them such that the maximum weight is 3000kgs and that the weight distribution around several variables describing the sample are close to some targets.

I was approaching the problem by considering each individual as a gene of a chromosome and then multiplying the chromosome by the weight of the sample. In this case 1 is for being included in the sample while 0 is being excluded from the sample.

I followed the example used in https://www.r-bloggers.com/genetic-algorithms-a-simple-r-example/ although my constraint is different as I want to minimize the difference between the weight distribution I get from the selected sample and my target.

Taking 1000 iterations and populations of 50 and 100 I don't get satisfactory solutions. I have read that people take populations that are (# genes)^2 but I will run out of memory if I take a population of that size.

I think crossover could help but it seems as if the genalg library only uses mutation.

Any suggestions on how to solve the problem? Thanks. I have posted the code below

Weight.Limit<-30*100

evalFunc <- function(x) {
  current_weight <- as.numeric(x %*% ind.data$weight)
  sample.dist<-x %*% as.matrix(ind.data[,4:ncol(ind.data)])/current_weight
  current_solution_dist <-  sum(sqrt(abs(constraints.data-sample.dist)))

  if (current_weight> Weight.Limit) 
    return(0) else return(current_solution_dist)
}


GAmodel <- rbga.bin(size = 31390, popSize = PopSize, iters = iter, mutationChance = MutationChance, elitism = T, evalFunc = evalFunc)

cat(summary(GAmodel))
$\endgroup$
1
$\begingroup$

There's nothing super special about a population size of L^2. Larger populations are often better, but don't worry about trying to hit some threshold needed for the algorithm to work.

There are a couple of potential issues here that I see. I'm making some assumptions that when you say "individuals", you mean people. Which means an average person is going to contribute something on the order of 50-100 kg toward your limit, which puts you at like 50 people in the sample in order to stay under the 3000kg limit.

With your encoding scheme, that's going to mean only very sparse vectors are feasible solutions. You can deal with that, but it likely means a standard GA pulled from a library won't work as well as one that included some prior knowledge. For example, when initializing your population, you might want to bias things pretty heavily in favor of setting bits to 0 rather than 1.

In any case, you have constraints, so you'll want to include some type of constraint handling scheme. A simple thing you can do in this case is to perform a simple local search on every individual you generate. For example, suppose I have an individual i selected from my population. If the total weight of the sample encoded by i is less than 3000kg, iterate over every bit of i (in random order) and see if you can flip a 0 bit to a 1 bit without exceeding your weight capacity. Similarly, if you generate a sample that weighs more than 3000kg, try to find 1 bits you can flip to remove weight until you're under the limit. When you're done, you have a feasible individual and you insert it into the child population.

You can incorporate more sophisticated measures or search schemes as well. You could have your local search operator consider those other variables. You can replace the simple hill-climbing operator with a more sophisticated method like tabu search or simulated annealing. There's a spectrum of algorithms with all sorts of different ways of combining the ideas of the global search of a GA with more targeted local search operators, and there's no general "right answer". You mostly just need to experiment a bit to see what works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.