CODEWITHSUNDEEP
algorithmsearchoptimizationevolutionary-algorithm
STiGMa
STiGMa

Reputation: 946

Obtaining Pareto front for more than 2 objectives

I have a reasonably tractable problem withe >2 objectives in which I apply multi-objective evolutionary algorithms (MOEA) like PSO, ACO, GA.

I would like to compare the performance and quality of the Pareto produced by these algorithms against the Pareto front.

Since the range of the variables in the problem can be enumerated, and provided that the problem is tractable I am thinking to use brute force to obtain the Pareto front to make the comparison against the MOEAs.

However, it's not clear yet how to obtain the Pareto front using brute force? Is it possible to use dominance ranking in brute force?

Any ideas/suggestions are welcome.

Example

Consider a simplified instance of a multi-objective problem with:

  1. Integer variables x,y,z in [1,100]
  2. Objectives: objA, objB, objC

The goal is to run brute-force on x,y,z and evaluate objA,objB,objC and generate the Pareto front.

Upvotes: 3

Views: 3197

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79441

Maintain a running set of Pareto-optimal points and incrementally update it as you observe each new point. In practice this can perform much better than generating all points and then doing a brute force O(n2) calculation to find the Pareto-optimal ones.

Here's some Python code to demonstrate the idea.

S = {}
def update(p):
  if any(q > p for q in S):
    return
  for q in [q for q in S if p > q]:
    S.remove(q)
  S.add(p)

If the average size of S over n updates is k, then the complexity is O(nk).

Upvotes: 1

Related Questions