Genetic Algorithm in R

Question

I have such problem: i need to find best combination of items which will not exceed max weight. For this problem i used genetic algorithm.

Here is my data

dataset <- data.frame(name = paste0("x",1:11),
                  Weight = c(2.14083022,7.32592911,0.50945094,4.94405846,12.02631340,14.59102403,0.07583312,0.36318323,10.64413370,3.54882187,1.79507759),
                  stringsAsFactors = F)

Here is my cost function:

max_weight = 10
fitness_function <- function(x){
   current_weight <- x %*% dataset$Weight
          if ( current_weight > max_weight){
      return(0)
   } else {
      return( -1* current_weight)
   }
}

Then i tried ga from two packages: genalg and GA

genalg

    ga_genalg <- rbga.bin(size = 11,
                          popSize = 100, 
                          mutationChance = .1,
                          evalFunc = fitness_function)

Okay, here is result:

cat(summary(ga_genalg))
GA Settings
  Type                  = binary chromosome
  Population size       = 100
  Number of Generations = 100
  Elitism               = 20
  Mutation Chance       = 0.1

Search Domain
  Var 1 = [,]
  Var 0 = [,]

GA Results
  Best Solution : 0 1 1 0 0 0 0 1 0 0 1 

I checked best solution, looks nice:

genalg_best_solution = c(0,1,1,0,0,0,0,1,0,0,1)
dataset$Weight %*% genalg_best_solution 
         [,1]
[1,] 9.993641

PS. Anybody knows how to get this best solution vector without typing and regular expressions?

GA

ga_GA <- ga(type = "binary", fitness = fitness_function, popSize = 100, pmutation = .1, nBits = 11)
ga_best_solution = ga_GA@solution 
dim(ga_best_solution)
[1] 73 11

Solutions are matrix with 73 rows. Also ga_GA@bestSol returns list()

Where is my best solution in this package? Or i need to check all 73 rows and find best(I've tried and got 73 zeros)?

PPS. Second question solution: GA maximize function and genalg minimize function =/. Anybody knows how to extract best solution from genalg package?

Answer 1

There's lots of questions here. My opinion is that GA provides as easier output for what you want: the best solution and the fitness score.

You're right that GA maximized fitness score, while genalg minimizes - I created a second fitness function that does not return the fitness value multiplied by -1. This results in the same solution for both.

Also, I don't get the dimensions that you present for the output of ga(). In my case, this is simply a single row with the 11 binary values:

library(GA)
library(genalg)

dataset <- data.frame(name = paste0("x",1:11),
  Weight = c(
    2.14083022,7.32592911,0.50945094,4.94405846,
    12.02631340,14.59102403,0.07583312,0.36318323,
    10.64413370,3.54882187,1.79507759
  ),
  stringsAsFactors = F
)

max_weight = 10


# genalg ------------------------------------------------------------------

# fitness function for genalg 
fitness_function <- function(x){
   current_weight <- x %*% dataset$Weight
   if ( current_weight > max_weight){
      return(0)
   } else {
      return(-current_weight)
   }
}


ga_genalg <- rbga.bin(size = 11,
  popSize = 100, 
  mutationChance = .1,
  evalFunc = fitness_function
)
tail(ga_genalg$best, 1) # best fitness
summary(ga_genalg, echo=TRUE)

plot(ga_genalg) # plot

# helper function from ?rbga.bin
monitor <- function(obj) {
    minEval = min(obj$evaluations);
    filter = obj$evaluations == minEval;
    bestObjectCount = sum(rep(1, obj$popSize)[filter]);
    # ok, deal with the situation that more than one object is best
    if (bestObjectCount > 1) {
        bestSolution = obj$population[filter,][1,];
    } else {
        bestSolution = obj$population[filter,];
    }
    outputBest = paste(obj$iter, " #selected=", sum(bestSolution),
                       " Best (Error=", minEval, "): ", sep="");
    for (var in 1:length(bestSolution)) {
        outputBest = paste(outputBest,
            bestSolution[var], " ",
            sep="");
    }
    outputBest = paste(outputBest, "\n", sep="");

    cat(outputBest);
}

monitor(ga_genalg)
# 100 #selected=4 Best (Error=-9.99364087): 0 1 1 0 0 0 0 1 0 0 1 



# GA ----------------------------------------------------------------------

# fitness function for GA (maximizes fitness)
fitness_function2 <- function(x){
   current_weight <- x %*% dataset$Weight
   if ( current_weight > max_weight){
      return(0)
   } else {
      return(current_weight)
   }
}

ga_GA <- ga(type = "binary", fitness = fitness_function2, popSize = 100, pmutation = .1, nBits = 11)
ga_GA@solution 
#     x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
# [1,]  0  1  1  0  0  0  0  1  0   0   1
dim(ga_best_solution)
# [1]  1 11

ga_GA@fitnessValue
# [1] 9.993641