Improving Performance Insensitivity of Large-Scale Multiobjective Optimization via Monte Carlo Tree Search

Haokai Hong, Min Jiang, Gary G. Yen

TL;DR

Large-scale multiobjective optimization (LSMOP) algorithms often suffer from "performance sensitivity," where results vary wildly between different runs. This paper introduces LMOMCTS, a novel framework that treats the optimization process as a game search using Monte Carlo Tree Search (MCTS) to consistently find high-quality solutions regardless of initialization. By sampling decision variables and using tree-based selection, the algorithm achieves state-of-the-art performance and, more importantly, high reliability across multiple runs.

What Problem Does This Paper Address?

In the world of engineering, many problems are "large-scale" (involving hundreds or thousands of decision variables) and "multiobjective" (requiring trade-offs between conflicting goals like cost vs. safety). While many Evolutionary Algorithms (EAs) can solve these, they have a "stochasticity problem." Because they rely on random initialization and probabilistic operators, one run might yield a perfect solution while the next gets stuck in a local optimum.

In industrial settings, computational resources are expensive. Engineers cannot always afford to run an algorithm 30 times to find the best result; they need an algorithm that is insensitive to randomness—one that provides a "good enough" and stable result every single time. This paper tackles the lack of focus on "performance insensitivity" in current large-scale optimization research.

Methods

The authors propose LMOMCTS (Large-scale Multiobjective Optimization via Monte Carlo Tree Search). The core innovation is reframing the evolutionary process as a tree search:

  1. MCTS Framework: The algorithm uses the Upper Confidence Bound applied to Trees (UCT) to navigate the search space. Each node in the tree represents a population of solutions.
  2. Decision Variable Sampling for Optimization (DVSO): To combat the "curse of dimensionality," the algorithm doesn't try to optimize all variables at once. When expanding a node, it randomly samples a subset of decision variables to evolve. This creates diverse "child" populations that explore different dimensions of the problem.
  3. Hypervolume (HV) Evaluation: To determine which "branch" of the tree is most promising, the algorithm estimates the Hypervolume of the population—a metric that measures both how close the solutions are to the ideal (convergence) and how well-spread they are (diversity).
  4. Backpropagation: The evaluation results are passed back up the tree to update the UCT values, ensuring the algorithm spends more time exploring "promising" regions of the decision space while still maintaining enough exploration to avoid local optima.

Datasets

The researchers evaluated LMOMCTS against eight state-of-the-art algorithms (including CCGDE3, WOF, and LMOCSO) using:

  • LSMOP1–LSMOP9: A standard suite of benchmark problems with varying Pareto Front shapes (linear, convex, disconnected).
  • WFG Benchmark: A secondary set of complex test problems to ensure the results weren't biased toward one specific suite.
  • TREE Dataset: A real-world dataset involving the configuration of voltage transformers, representing a practical industrial application.

Key Insights and Ideas

  • The "Insensitivity" Metric: The authors argue that standard variance isn't enough to measure reliability. They propose two new metrics—insensitive-IGD and insensitive-HV—which measure the degree of dispersion of an algorithm from the best possible result. This highlights how far a "bad run" falls from the peak performance.
  • Tree Search vs. Path Search: Traditional EAs follow a single "path" of evolution. By using a tree structure, LMOMCTS maintains multiple potential evolutionary directions, allowing it to "backtrack" or pivot if one direction proves to be a dead end.
  • Dimensionality Reduction via Sampling: By sampling variables ($d_n$) rather than grouping them statically, the algorithm avoids the pitfalls of incorrect variable linkage analysis, which often leads to poor performance in other large-scale methods.

Key Results

  • Superior Consistency: LMOMCTS achieved the best "insensitive-IGD" results in 34 out of 54 test instances. Crucially, its performance never fluctuated wildly; its results were always very close to the best-recorded run.
  • General Performance: It outperformed SOTA methods in 30 out of 54 cases for general convergence and diversity.
  • Real-World Success: On the TREE real-world dataset, LMOMCTS obtained the best mean results in 5 out of 6 instances, proving its utility outside of theoretical benchmarks.
  • Efficiency: Despite the complexity of maintaining a tree, the algorithm showed relatively low computation time and stable memory usage, making it practical for large-scale problems up to 5,000 variables.

Limitations and Future Work

The authors note that LMOMCTS performs slightly worse on problems with disconnected Pareto Fronts (like LSMOP9) compared to transformation-based methods like WOF. This suggests that while the tree search is robust, it may need more specialized operators to handle "gaps" in the solution space.

Future directions include: * Refining the offspring generation process within the tree nodes. * Integrating machine learning to more intelligently select which decision variables to sample. * Combining MCTS with other types of evolutionary strategies to improve performance on specific topological challenges like disconnected fronts.

Summary updated

Abstract

The large-scale multiobjective optimization problem (LSMOP) is characterized by simultaneously optimizing multiple conflicting objectives and involving hundreds of decision variables. Many real-world applications in engineering can be modeled as LSMOPs; simultaneously, engineering applications require insensitivity in performance. This requirement typically means that the algorithm should not only produce good results in terms of performance for every run but also the performance of multiple runs should not fluctuate too much. However, existing large-scale multiobjective optimization algorithms often focus on improving algorithm performance, but pay little attention to improving the insensitivity characteristic of algorithms. This directly leads to substantial limitations when solving practical problems. In this work, we propose an evolutionary algorithm called large-scale multiobjective optimization algorithm via Monte Carlo tree search, which is based on the Monte Carlo tree search and aims to improve the performance and insensitivity of solving LSMOPs. The proposed method samples decision variables to construct new nodes on the Monte Carlo tree for optimization and evaluation, and it selects nodes with good evaluations for further searches in order to reduce the performance sensitivity caused by large-scale decision variables. We propose two metrics to measure the sensitivity of the algorithm and compare the proposed algorithm with several state-of-the-art designs on different benchmark functions and metrics. The experimental results confirm the effectiveness and performance insensitivity of the proposed design for solving LSMOPs.
BibTeX
@article{hong2024improving,
  author = {Haokai Hong and Min Jiang and Gary G. Yen},
  title = {{Improving Performance Insensitivity of Large-Scale Multiobjective Optimization via Monte Carlo Tree Search}},
  journal = {IEEE Trans. Cybernetics},
  year = {2024},
  url = {https://openreview.net/forum?id=mYKWzZJKeb},
}
Figure