Quantum Genetic Algorithm

Main function to execute a Quantum Genetic Algorithm

QGA(
  popsize = 20,
  generation_max = 200,
  nvalues_sol,
  Genome,
  thetainit = 3.1415926535 * 0.05,
  thetaend = 3.1415926535 * 0.025,
  pop_mutation_rate_init = NULL,
  pop_mutation_rate_end = NULL,
  mutation_rate_init = NULL,
  mutation_rate_end = NULL,
  mutation_flag = TRUE,
  plotting = TRUE,
  verbose = TRUE,
  progress = TRUE,
  eval_fitness,
  eval_func_inputs,
  stop_limit = NULL,
  stop_iters = NULL
)

Arguments

popsize

the number of generated solutions (population) to be evaluated at each iteration (default is 20)

generation_max

the number of iterations to be performed (default is 200)

nvalues_sol

the number of possible integer values contained in each element (gene) of the solution

Genome

the length of the genome (or chromosome), representing a possible solution

thetainit

the angle (expressed in radiants) to be used when applying the rotation gate when starting the iterations (default is pi * 0.05, where pi = 3.1415926535)

thetaend

the angle (expressed in radiants) to be used when applying the rotation gate at the end of the iterations (default is pi * 0.025, where pi = 3.1415926535)

pop_mutation_rate_init

initial mutation rate to be used when applying the X-Pauli gate, applied to each individual in the population (default is 1/(popsize+1))

pop_mutation_rate_end

final mutation rate to be used when applying the X-Pauli gate, applied to each individual in the population (default is 1/(popsize+1))

mutation_rate_init

initial mutation rate to be used when applying the X-Pauli gate, applied to each element of the chromosome (default is 1/(Genome+1)))

mutation_rate_end

final mutation rate to be used when applying the X-Pauli gate, applied to each element of the chromosome (default is 1/(Genome+1))

mutation_flag

flag indicating if the mutation gate is to be applied or not (default is TRUE)

plotting

flag indicating plotting during iterations

verbose

flag indicating printing fitness during iterations

progress

flag indicating progress bar during iterations

eval_fitness

name of the function that will be used to evaluate the fitness of each solution

eval_func_inputs

specific inputs required by the eval_fitness function

stop_limit

value to stop the iterations if the fitness is higher than a given value

stop_iters

number of iterations without improvement of fitness before stopping

Value

A numeric vector (positive integers) giving the best solution obtained by the QGA

Details

This function is the 'engine', which performs the quantum genetic algorithm calling the function for the evaluation of the fitness that is specific for the particulare problem to be optmized.

Examples

#----------------------------------------
# Fitness evaluation for Knapsack Problem
#----------------------------------------
KnapsackProblem <- function(solution,
                            eval_func_inputs) {
  solution <- solution - 1
  items <- eval_func_inputs[[1]]
  maxweight <- eval_func_inputs[[2]]
  tot_items <- sum(solution)
  # Penalization
  if (sum(items$weight[solution]) > maxweight) {
    tot_items <- tot_items - (sum(items$weight[solution]) - maxweight)  
  }
  return(tot_items)
}
#----------------------------------------
# Prepare data for fitness evaluation
items <- as.data.frame(list(Item = paste0("item",c(1:300)),
                            weight = rep(NA,300)))
set.seed(1234)
items$weight <- rnorm(300,mean=50,sd=20)
hist(items$weight)

sum(items$weight)
#> [1] 15078.17
maxweight = sum(items$weight) / 2
maxweight
#> [1] 7539.085
#----------------------
# Perform optimization
popsize = 20
Genome = nrow(items)
solutionQGA <- QGA(popsize = 20,
                generation_max = 500,
                nvalues_sol = 2,
                Genome = nrow(items),
                thetainit = 3.1415926535 * 0.05,
                thetaend = 3.1415926535 * 0.025,
                pop_mutation_rate_init = 1/(popsize + 1),
                pop_mutation_rate_end = 1/(popsize + 1),
                mutation_rate_init = 1,
                mutation_rate_end = 1,
                mutation_flag = TRUE,
                plotting = FALSE,
                verbose = FALSE,
                progress = FALSE,
                eval_fitness = KnapsackProblem,
                eval_func_inputs = list(items,
                                        maxweight),
                stop_iters = NULL)
#> 
#>  *** Best fitness:  291

#----------------------
# Analyze results
solution <- solutionQGA[[1]]
solution <- solution - 1
sum(solution)
#> [1] 291
sum(items$weight[solution])
#> [1] 7524.877
maxweight
#> [1] 7539.085