Multi-Gradient Pathfinder Algorithm

Multi-Gradient Pathfinder (MGP) algorithm uses Pareto frontier as a search space for multi-objective optimization, and performs in this way directed optimization on Pareto frontier.

Directed optimization on Pareto frontier means that a search algorithm steps along Pareto frontier from a given initial Pareto optimal point towards a desired Pareto optimal point. The search algorithm is supposed to stay on Pareto frontier throughout the optimization process until the desired Pareto optimal point will be reached. Then all (or most) of the evaluated points will also be Pareto optimal.

MGP starts from a given Pareto optimal point and performs steps along Pareto frontier in a direction of improvement of preferable objectives.

On each step MGP solves two tasks:

• Improves preferable objective's values-green arrows;
• Maintains a short distance from the current point to Pareto frontier-blue arrows

 

The following example illustrates a search on Pareto frontier performed by MGP algorithm:

Assigning one or more preferable objectives (see Minimize+ below) determines the search direction on the Pareto frontier:

All model evaluations have been performed on Pareto frontier-see the plane x3=1 on the right diagram.

Searching the Entire Design Space is Not Productive

The following benchmark problem has been solved by MGP and one of the best commercial algorithms for multi-objective optimization—NSGA-II. The solutions found illustrate the conceptual difference between directed optimization on Pareto frontier and a traditional search technique represented by NSGA-II algorithm.

Exact solution: {x1=0...1; x2=x3=...=x10=0}

The above diagrams show all projections of all points evaluated by two multi-objective optimization algorithms MGP and NSGA-II.

MGP was stepping along global Pareto frontier performing directed optimization with the preferable objective F1. Pareto optimal points (green markers) have values of the exact solution: {x1=0..1, x2=x3=...=x10=0}. Intermediate points (red markers) are located between disjoint segments of the global Pareto frontier. MGP has spent 250 evaluations, and covered all five segments of the global Pareto frontier.

NSGA-II algorithm performed optimization search in the entire design space, and spent 4000 model evaluations with noticeably worse results: it was able to approach 3 of 5 segments on the global Pareto frontier.

MGP Benefits:

• A new concept of directed optimization on Pareto frontier is introduced, and MGP algorithm is developed based on it;
• Similar to traditional gradient-based optimization algorithms, MGP performs just a few steps to solve an optimization task;
• In contrast with traditional optimization techniques, MGP uses Pareto frontier as a search space;
• Thus, MGP performs optimization search on Pareto frontier in a preferred direction. This allows the following:
  1. 80-95% of evaluated points are Pareto optimal;
  2. Only user's area of interest on the Pareto frontier is used for the optimization search, which reduces the computational effort-NO NEED TO COVER THE ENTIRE PARETO FRONTIER as Genetic Algorithms do;
  3. Precise approachment to a desired solution on Pareto frontier instead of inaccurate approachment typical of GAs;
• MGP has unparalleled efficiency because of the (1)-(3) reasons, and also because of an increased control over the optimization process given to the user.