Reproduce “Random is Faster than Systematic in Multi-Objective Local Search” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zimin Liang, Miqing Li
Researchers at the University of Birmingham empirically and theoretically show that random neighborhood sampling is consistently faster than systematic exploration in Pareto-based Local Search for multi-objective combinatorial optimization. This work demonstrates that Randomized Pareto Local Search (r-PLS) achieves higher hypervolume values more quickly than Systematic Pareto Local Search (s-PLS) across various problems and scales better with increasing problem size.
Key insights
- Randomized neighborhood exploration consistently leads to faster progress in Pareto-based Local Search compared to systematic exploration, overturning conventional wisdom.
- The number of "good neighbors" for solutions in the archive follows a light-tailed geometric distribution throughout most of the search in multi-objective landscapes.
- The geometric distribution of good neighbors is the primary theoretical reason why r-PLS exhibits a lower expected number of evaluations to find the next archive-improving solution than s-PLS.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.