R package for multi objective integer evolutionary algorithm

Question

I have a discrete event simulation (simmer package) based on probability distributions in R. I would like to optimize the variables according to several (2 or more) objectives. I used the NSGA-II algorithm, but this is only working with continous optimization. Is there a similar approach for integer optimization?

Answer 1

A short look into the literature shows that mixed integer multi objective algorithms are still in an early stage with people proposing different formulations and approaches. I am not aware of any open solvers that could be readily used even outside the R ecosystem. So i see multiple options for you:

• Weighted sum approach and use the package GA as prubin suggested.
• Contact authors of papers such as these to see if you could learn whether there code works for you and could be used from R.
• Run a series of NSGA-II problems where you increasingly punish the distance from integer points.
• Run NSGA-II where you punish non integerness harshly from the beginning
• If you only have a few integer variables, solving it as independent problem with all the integer variables assigned in all combinations
• Implement your own branch and bound based multi objective which i have a sketch below.

Branch and Bound over evolutionary algorithm in a multi-ojective context

I assume that your NSGA-II implementation is hot startable (you can give it an initial population). Luckily NSGA-II is an algorithm which resumeable, running it for 10 iterations and then getting the population and then running it for another 10 iterations is as roughly good as running it for 20 iterations.

There are two core concepts for branch and bound, namely a node in the branch and bound tree and the continous relaxation of a node. A node represents a hypercube in the space defined by a cartesian product of your integer variables. All variables have an interval associated with it in each node. A continous relaxtion is a pessimistic bound of the objectives that can be achieved over a node.

The idea of branch and bound is to evaluate the continous relaxations of nodes, branch on some variable by making the intervals of one variable smaller or even assign an integer and once integer solutions are found to remove nodes whose continous relaxation is dominated by an integer solution.

Due to the fact that we don't have access to a continous relaxation, we will call the pareto front found by NSGA-II inside our box a continous relaxation, we might miss optima but that is the inherent nature of evolutionary algorithms. Luckily nsga2R which i allows you to use allows box constraints. I assume that your integers are not necessarily a choice between two numbers.

I haven't made any attempts to prove anything about this algorithm i propose. So it probably has weaker properties then NSGA-II.

Each nodes stores the lower bound and the upper bound of the interval of each variable, the current population and information for an early stopping criteria of your choice. Furthermore you need a list to store the points on the pareto front, it is essential that you only add integer solutions to this. You also need a queue of nodes.

You make progress by processing nodes and adding at the end of the queue either the same node, no node, or child-nodes to the list. When you add the same node again, you do so after running a few rounds of NSGA-II. When you branch, you want to such that the least promosing parts (so that they can be isolated and discarded quickly) and the most promising parts (so you can find a good approximation of the pareto front quickly helping you discard not so promising parts) get branched on early.

When you process a node:

1. You run a few rounds of NSGA-II restricted to the box described by the node

2. Check for Integerness of the solution

   • If all the population members are the same integer in a variable, or after rounding in that variable dominate their previous value and land on that integer then take those branching decisions and add a new node with all those branching decision taken, don't add this node back as it is dominated by the much smaller search space we found. Still run 3. though

3. Attempt to add integer solutions to pareto front

   • Round all integer variables to the nearest integer for the entire population (thereby making the solution worst) and try to add it to the pareto front. Maintain that the pareto front is a pareto front if you added solutions. This pareto front behaves as a pessimal bound of the parteo front that appraoches the pareto front

4. Decide wheter to either throw away the node, work more on it later or branch on this node

   1. If the number NSGA-II iterations, rate of improvement, the past glory of Interger solutions added to the pareto front in 3. expired and the populatino in this node is not better than the pareto front and the distance to the pareto front so large that is tells you won't find anything here, don't add the node back to the list
   2. If the number NSGA-II iterations, rate of improvement tell you won't make improvement but your population (which has non integer values for pareto variables) is better than the pareto front, find a variable to branch upon produce multiple childreen you add to the list
      1. Calculate the average objective vector $a$, for each variable take the midpoint $m_i$ in the interval of $i$-th variable then calculate the sum of $||\sum_{x\in\text{Pop}}(x_i-m_i)(f(x)-a)||_2$ and select the i with the largest value.
      2. If the $i$-th variables interval contains more than two Integers then apply the above formula for every pair of neighboring integers $(n, n+1)$ in the interval with $n+1/2$ being the $m_i$ and all population numbers, choose $n$ such that this term is minial and the create two childreen with same constraints except in the ith where one now has the upperbound $n$ and the otherone the lower bound $n+1$. Discard the part of the population that doesn't fit in the box and replace it by randomly sampled points.
      3. If the $i$-th variables interval contains two integer $n, n+1$, create two childreen with the $i$-th variable set to those values respectively and set the $i$-th component of all the population to that integer too.
      • This is one branching heuristic, i could think of different ones. It is based on a scale as analogy that we want to find the most out of balance variable and balance it.
      • Since we divided the integer search space completly we don't add the parent we branched from back to queue.
      • If you have constraints, those would need to go here too.
   3. If none of these criterions apply we do all the book keeping and add the node with new population, same bounds and information for an early stopping criteria updated back to the list.

Answer 2

Your question title mentions "evolutionary algorithm", so (a) I assume you are comfortable with a heuristic solution and (b) I assume you have some familiarity with evolutionary algorithms.

There is an excellent genetic algorithm package for R, named GA. I think there may be a few other genetic algorithm packages for R, but this is the only one with which I am familiar. It provides for three variable types: real, binary and permutation. So you can require your decision variables to be integer-valued by using a binary encoding, or you can just use a typical encoding as real numbers and then round the chromosomes to integers.

I do not believe that GA directly supports multiple objectives. There are research papers on multiobjective genetic algorithms, but I don't think I've seen a GA library that supports multiple objectives. Since you get to define the fitness function, you can have it use a weighted sum of your objectives, if that fits your goals.