Multi-Objective Evolutionary Algorithms
Multiobjective Optimization Problems
With ecr, both single- and multi-objective optimization problems can be addressed. In the former, an attempt is made to find to find a single solution that maximizes a fitness value corresponding directly to a single underlying measure of quality. Often, however, we look at problems in which we try to optimize different (conflicting) goals at the same time. Examples of these so-called multi-objective problems (MOPs) include:
- Hotel search: Close to the beach and at the same time reasonably priced
- Feature Selection in Machine Learning: Few features with high accuracy
- Real estate purchase: location, price, number of rooms, square meter, …
Different objectives can also mean different optimization goals: When buying a new apartment, one hopes for a low price (minimization problem) and a large living space (maximization problem).
In the following, we will look at the example of Feature Selection to see how multi-objective problems can be solved with ecr.
For this purpose, we will iteratively train a RandomForest-Classifier on the Wisconsin Breast Cancer data set and analyze the effect on the prediction accuracy by including or omitting features of the data set in the training. The goal is to achieve high accuracy along while using a minimum number of features. To train the RandomForest-Classifier we use the R-Package mlr. The BreastCancer data set is taken from the package mlbench.
## Id Cl.thickness Cell.size Cell.shape Marg.adhesion
## Length:699 1 :145 1 :384 1 :353 1 :407
## Class :character 5 :130 10 : 67 2 : 59 2 : 58
## Mode :character 3 :108 3 : 52 10 : 58 3 : 58
## 4 : 80 2 : 45 3 : 56 10 : 55
## 10 : 69 4 : 40 4 : 44 4 : 33
## 2 : 50 5 : 30 5 : 34 8 : 25
## (Other):117 (Other): 81 (Other): 95 (Other): 63
## Epith.c.size Bare.nuclei Bl.cromatin Normal.nucleoli Mitoses
## 2 :386 1 :402 2 :166 1 :443 1 :579
## 3 : 72 10 :132 3 :165 10 : 61 2 : 35
## 4 : 48 2 : 30 1 :152 3 : 44 3 : 33
## 1 : 47 5 : 30 7 : 73 2 : 36 10 : 14
## 6 : 41 3 : 28 4 : 40 8 : 24 4 : 12
## 5 : 39 (Other): 61 5 : 34 6 : 22 7 : 9
## (Other): 66 NA's : 16 (Other): 69 (Other): 69 (Other): 17
## Class
## benign :458
## malignant:241
##
##
##
##
## First, we remove the observations with missing data (see Bare.nuclei’s 16 NA entries) along with the Id column which is irrelevant for the training of the model. The data set is then divided into a feature data set and a target data set. The prediction target is the column “Class”.
cancer = BreastCancer[, 2:11]
cancer = cancer[!(rowSums(is.na(cancer)) > 0),]
cancer.features = cancer[, 1:9]
cancer.target = cancer[, 10]Next, we define the fitness function. First a few conceptual considerations: The fitness of an individual results from the number of features used for prediction and the accuracy of the prediction. In order to determine the accuracy, the model must be trained on the features encoded in the individual. Consequently, each time the fitness function is called, the model is first trained and then the fitness is determined. We use a resampling strategy to determine the performance of the learning algorithm on the selected features. The fitness corresponds to the average accuracy of the individual samples.
fitness.fun = function(ind) {
ind = as.logical(ind)
# all features deselected is not a supported solution.
# Thus, we set the accuracy to 0 and number of features to its maximum.
if (!any(ind))
return(c(0, length(ind)))
# add target column to individual
task = makeClassifTask(data = cancer[, c(ind, TRUE)],
target = "Class",
id = "Cancer")
# Subsampling with 5 iterations and default split ratio 2/3
rdesc = makeResampleDesc("Subsample", iters = 2)
# Classification tree
lrn = makeLearner("classif.randomForest")
r = do.call(resample, list(lrn, task, rdesc, list(acc), show.info = FALSE))
measure = r$aggr[[1]]
nFeatures = sum(ind)
return(c(measure, nFeatures))
}Black-box approach
Since ecr supports multi-objective optimization as a standard task, we can use the black-box function ecr() to execute the feature selection. We decide to use an evolutionary (5 + 10)-strategy, i.e., an algorithm that keeps a population of size mu = 5, in each generation creates lambda = 10 offspring by variation and selects the best mu out of mu + lambda individuals to survive. In the context of our multi-objective optimization problem, two important arguments should be noticed. First, n.objectives has to reflect the number of objectives and minimize has to be a vector of length = n.objectives, indicating for each objective as to whether it should be minimized or maximized. For the problem at hand, our two objectives (accuracy, number of features) are to be maximized and minimized respectively.
MU = 5; LAMBDA = 1L; MAX.ITER = 25; N.BITS = ncol(cancer.features);
res = ecr(fitness.fun = fitness.fun,
n.objectives = 2L,
minimize = c(FALSE, TRUE),
representation = "binary",
n.bits = N.BITS,
mu = MU,
lambda = LAMBDA,
survival.strategy = "plus",
mutator = setup(mutBitflip, p = 1 / N.BITS),
p.mut = 0.3,
p.recomb = 0.7,
terminators = list(stopOnIters(MAX.ITER)),
log.pop = TRUE,
initial.solutions = list(rep(1,N.BITS)))The resulting Pareto-set consists of all non-dominated solutions and can be plotted by using plotFront.
Pareto front on multi-objective optimization problem
White-box approach
Writing the evolutionary loop by hand, we first create a control object that stores the information about the target function and the evolutionary operators. Note that the number of objectives is passed explicit.
control = initECRControl(fitness.fun, n.objectives = 2L, minimize = c(FALSE, TRUE))
control = registerECROperator(control, "mutate", mutBitflip, p = 0.3)
control = registerECROperator(control, "selectForSurvival", selNondom)Here, we decide to perform mutation only. The best mu individuals
(regarding fitness values) are going to be selected to build up the next
generation. However, as we are looking at a multi-objective optimization
problem, the “best mu individuals” must be determined by applying
non-dominated sorting of the objective vectors and subsequent
computation of the crowding distance. An alternative multi-objective ecr
selection operator is the selDomHV. Furthermore, you can
write your own selector via makeSelector. Now, an initial
population is sampled, their respective fitness evaluated and a
Pareto-archive initialized. A Pareto-archive is usually used to store
all or a part of the non-dominated points during a run of an
multi-objective evolutionary algorithm.
population = genBin(MU, N.BITS)
fitness = evaluateFitness(control, population)
archive = initParetoArchive(control)Finally, the evolutionary loop is implemented. In each iteration, the
Pareto-set is updated in the Pareto-archive via the function
updateParetoArchive.
for (i in seq_len(MAX.ITER)) {
# sample lambda individuals at random
idx = sample(1:MU, LAMBDA, replace = TRUE)
# generate offspring by mutation and evaluate their fitness
offspring = mutate(control, population[idx], p.mut = 1)
fitness.o = evaluateFitness(control, offspring)
# now select the best out of the union of population and offspring
sel = replaceMuPlusLambda(control, population, offspring, fitness, fitness.o)
population = sel$population
fitness = sel$fitness
updateParetoArchive(archive, population,fitness)
}Let’s have a look at our Pareto-front:
Pareto front on multi-objective optimization problem