Fast Re-Optimization of LeadingOnes with Frequent Changes
- URL: http://arxiv.org/abs/2209.04391v1
- Date: Fri, 9 Sep 2022 16:51:41 GMT
- Title: Fast Re-Optimization of LeadingOnes with Frequent Changes
- Authors: Nina Bulanova, Arina Buzdalova, Carola Doerr
- Abstract summary: We show that the re-optimization approach suggested by Doerr et al. reaches a limit when the problem instances are prone to more frequent changes.
We propose a modification of their algorithm which interpolates between greedy search around the previous-best and the current-best solution.
- Score: 0.9281671380673306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In real-world optimization scenarios, the problem instance that we are asked
to solve may change during the optimization process, e.g., when new information
becomes available or when the environmental conditions change. In such
situations, one could hope to achieve reasonable performance by continuing the
search from the best solution found for the original problem. Likewise, one may
hope that when solving several problem instances that are similar to each
other, it can be beneficial to ``warm-start'' the optimization process of the
second instance by the best solution found for the first. However, it was shown
in [Doerr et al., GECCO 2019] that even when initialized with structurally good
solutions, evolutionary algorithms can have a tendency to replace these good
solutions by structurally worse ones, resulting in optimization times that have
no advantage over the same algorithms started from scratch. Doerr et al. also
proposed a diversity mechanism to overcome this problem. Their approach
balances greedy search around a best-so-far solution for the current problem
with search in the neighborhood around the best-found solution for the previous
instance.
In this work, we first show that the re-optimization approach suggested by
Doerr et al. reaches a limit when the problem instances are prone to more
frequent changes. More precisely, we show that they get stuck on the dynamic
LeadingOnes problem in which the target string changes periodically. We then
propose a modification of their algorithm which interpolates between greedy
search around the previous-best and the current-best solution. We empirically
evaluate our smoothed re-optimization algorithm on LeadingOnes instances with
various frequencies of change and with different perturbation factors and show
that it outperforms both a fully restarted (1+1) Evolutionary Algorithm and the
re-optimization approach by Doerr et al.
Related papers
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.
We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.
We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
arXiv Detail & Related papers (2024-11-04T15:17:19Z) - Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
Quality-Diversity (QD) algorithms aim to find a set of high-performing, yet diverse solutions.
This paper tries to shed some light on the optimization ability of QD algorithms via rigorous running time analysis.
arXiv Detail & Related papers (2024-01-19T07:40:24Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form.
This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method.
A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
arXiv Detail & Related papers (2023-12-28T23:15:18Z) - Learning to repeatedly solve routing problems [5.08128537391027]
We present a learned for the reoptimization of a problem after a minor change in its data.
Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution.
This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution.
arXiv Detail & Related papers (2022-12-15T19:33:54Z) - Socio-cognitive Optimization of Time-delay Control Problems using
Evolutionary Metaheuristics [89.24951036534168]
Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches.
In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
arXiv Detail & Related papers (2022-10-23T22:21:10Z) - Enhanced Opposition Differential Evolution Algorithm for Multimodal
Optimization [0.2538209532048866]
Most of the real-world problems are multimodal in nature that consists of multiple optimum values.
Classical gradient-based methods fail for optimization problems in which the objective functions are either discontinuous or non-differentiable.
We have proposed an algorithm known as Enhanced Opposition Differential Evolution (EODE) algorithm to solve the MMOPs.
arXiv Detail & Related papers (2022-08-23T16:18:27Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
We use a Noise Contrastive approach to motivate a family of surrogate loss functions.
We address a major bottleneck of all predict-and-optimize approaches.
We show that even a very slow growth rate is enough to match the quality of state-of-the-art methods.
arXiv Detail & Related papers (2020-11-10T19:09:12Z) - Stochastic Optimization Forests [60.523606291705214]
We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm.
We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
arXiv Detail & Related papers (2020-08-17T16:56:06Z) - First Steps Towards a Runtime Analysis When Starting With a Good
Solution [8.34061303235504]
In practical applications it may be possible to guess solutions that are better than random ones.
We show that different algorithms profit to a very different degree from a better initial solution.
This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found.
arXiv Detail & Related papers (2020-06-22T11:46:42Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.