Defining Problems in the MOEADr Package

Felipe Campelo

2023-01-06

Introduction

This is a short guide to defining the problem structure for running MOEA/Ds using the MOEADr package. In this document, we cover:

A general description of the algorithm and the component-based interpretation behind the MOEADr package is available in our paper1

Problem structure

In the MOEADr package, all information regarding the problem is input as a list variable problem. This parameter must contain enough information for the algorithm to correctly evaluate all the objective and constraint functions, as documented in function moead() and replicated below for convenience.

The problem list must contain the following required fields:

Fields $xmin and $xmax provide information for the internal variable standardization performed by the MOEADr package, as well as information about the number of problem variables. This information is also used for the definition of the initial population, but it does not guarantee that the points will remain within this interval as the iterations progress - for that, variation operators such as truncate or explicit constraints (see below, Section Constraint Functions Routine) must be employed.

Besides these fields, problem should contain any other relevant inputs for the routine listed in problem$name.

problem may also contain the optional field problem$constraints, which is itself a list object containing information about the problem constraints. If present, problem$constraints must contain the following fields:

Besides these fields, problem$constraints should contain any other relevant inputs for the routine listed in problem$constraints$name.

To guide us through the steps required to define a problem structure for the MOEADr package, assume that we want to use the MOEADr framework to solve a 10-variable, 2-objective DTLZ1 benchmark function2. Assume that the feasible space is defined by the interval [0, 1] for all variables, and by \(x_1^2 + 2x_2^2 \leq 1.2\) and \(x_3x_4 = 0.5\). In this case, the problem variable would be defined as:

problem <- list(name        = "moeadr_dtlz1",  # objective function routine
                xmin        = rep(0, 10),      # lower limits
                xmax        = rep(1, 10),      # upper limits
                m           = 2,               # number of objectives
                constraints = list(
                  name      = "my_constraints",# constraint function routine
                  epsilon   = 0.05))           # tolerance for equality constraints

The specific requirements regarding functions problem$name and problem$constraints$name are provided in the following sections.

Objective Functions Routine

The routine indicated in problem$name must be able to receive a [ N x nv ] matrix, where each row represents one candidate solution. The name of the input argument that receives the population matrix must be either or .

This routine must return a [ N x nf ] matrix, where each row contains the nf objective function values for one solution.

To illustrate these requirements, we provide below the example function moeadr_dtlz1.3 This function is simply a MOEADr-compliant wrapper for the DTLZ1 implementation available in the smoof package.

moeadr_dtlz1 <- function(X,     # population matrix
                         ...    # allow function to receive extra parameters. 
                                # These are unused in most cases, but it is useful 
                                # for preventng errors due to unwanted parameters 
                                # being passed
){

  # "smoof" is listed in the Suggests field MOEADr's DESCRIPTION, but we need to 
  # be sure that it is available, so:
  if(!("smoof" %in% rownames(utils::installed.packages()))){
    stop("Please install package 'smoof' to continue")
  }
  
  # make 10-variable, 2-objective DTLZ1
  smoof_dtlz1 <- smoof::makeDTLZ1Function(dimensions   = 10, 
                                          n.objectives = 2)
  
  # Evaluate points in a vectorized manner:
  Y <- t(apply(X,
               MARGIN = 1,
               FUN = smoof_dtlz1))
  
  # Return [N x n_f] matrix
  return(Y)
}

Notice that the objective functions routine does not use the information from xmin, xmax, m, or constraints - these fields are used elsewhere in the MOEADr structure to define the initial population, weight matrices, truncation operators etc.

Constraint Functions Routine

As in the objective functions case, the routine indicated in problem$constraints$name must be able to receive a [ N x nv ] matrix, where each row represents one candidate solution. The name of the input argument that receives the population matrix must be either or .

This function must return a list object containing the following fields:

\[v[k] = v(x_k) = \sum_i max(~g_i(x_k),~~0) + \sum_j max(~|h_j(x_k)| - \epsilon,~~0)\] v is calculated simply as rowsums(Vmatrix), but returning it prevents having to re-compute v in different places of the MOEA/D structure.

To illustrate these requirements, we provide below the example function my_constraints.4 Recall that we have a number of different constraints that were stated in the problem definition:

my_constraints <- function(X,           # population matrix
                           epsilon = 0, # tolerance for equality constraints
                                        # (defaults to zero if not provided)
                           ...)
{
  
  nv <- 10 # number of variables of the problem
  
  # Prepare output matrix of constraint function values
  Cmatrix <- matrix(numeric(), 
                    nrow = nrow(X),
                    ncol = 2 * nv + 2) # 20 inequality box constraints, plus g1 and h1
  
  # Set informative column names (be nice to your users!)
  colnames(Cmatrix) <- c(paste0("x", 
                                rep(1:nv, times = 2), 
                                rep(c("min","max"), each = nv)),
                         "g1",
                         "h1")
                    
  # Box limits of the feasible space
  Xmin <- matrix(0, nrow = nrow(X), ncol = nv)
  Xmax <- matrix(1, nrow = nrow(X), ncol = nv)
  
  # Calculate "x_i >= 0" and "x_i <= 1" constraints
  Cmatrix[, 1:nv]              <- Xmin - X
  Cmatrix[, (nv + 1):(2 * nv)] <- X - Xmax
  
  # g1 and h1 functions
  g1 <- function(X){
    return(X[, 1] ^ 2 + 2 * X[, 2] ^ 2 - 1.2)
  }
  h1 <- function(X){
    return(X[, 3] * X[, 4] - 0.5)
  }
  
  # Calculate g1(x) and h1(x)
  Cmatrix[, 2 * nv + 1] <- g1(X)
  Cmatrix(, 2 * nv + 2) <- h1(X)
  
  # Assemble matrix of *violations*
  Vmatrix <- Cmatrix
  Vmatrix[, 1:(2 * nv + 1)] <- pmax(Vmatrix[, 1:(2 * nv + 1)], 0)        # inequality constraints
  Vmatrix[, 2 * nv + 2] <- pmax(abs(Vmatrix[, 2 * nv + 2]) - epsilon, 0) # equality constraint h1
  
  # Return necessary variables
  return(list(Cmatrix = Cmatrix,
              Vmatrix = Vmatrix,
              v       = rowSums(Vmatrix)))
  
}

Some VERY important points:


The MOEADr package already provides a convenient implementation for a “box constraints” (function box_constraints()) and “unitary constraints” (function unitary_constraints()). See the specific documentation for details.

To use these functions, simple make constraints = list(name = "box_constraints") (or "unitary_constraints", if that is the case) in your definition of the problem input. And don’t forget the epsilon in the case of unitary constraints!


  1. F. Campelo, L.S. Batista and C. Aranha, “A Component-Wise Perspective on Multiobjective Evolutionary Algorithms based on Decomposition”, in preparation.↩︎

  2. https://deap.readthedocs.io/en/master/api/benchmarks.html#deap.benchmarks.dtlz1↩︎

  3. This function is not available in the MOEADr package - instead we provide the more general function make_vectorized_smoof(). See the documentation for details.↩︎

  4. Also not available in the MOEADr package, since it does not make much practical sense.↩︎