Estudo Geralhttps://estudogeral.sib.uc.ptThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Mon, 18 Nov 2019 15:49:38 GMT2019-11-18T15:49:38Z5031Globally convergent evolution strategieshttp://hdl.handle.net/10316/45499Title: Globally convergent evolution strategies
Authors: Diouane, Y.; Gratton, S.; Vicente, Luís Nunes
Abstract: In this paper we show how to modify a large class of evolution strategies (ES’s) for unconstrained optimization to rigorously achieve a form of global convergence, meaning convergence to stationary points independently of the starting point. The type of ES under consideration recombines the parent points by means of a weighted sum, around which the offspring points are computed by random generation. One relevant instance of such an ES is covariance matrix adaptation ES (CMA-ES). The modifications consist essentially of the reduction of the size of the steps whenever a sufficient decrease condition on the function values is not verified. When such a condition is satisfied, the step size can be reset to the step size maintained by the ES’s themselves, as long as this latter one is sufficiently large. We suggest a number of ways of imposing sufficient decrease for which global convergence holds under reasonable assumptions (in particular density of certain limit directions in the unit sphere). Given a limited budget of function evaluations, our numerical experiments have shown that the modified CMA-ES is capable of further progress in function values. Moreover, we have observed that such an improvement in efficiency comes without weakening significantly the performance of the underlying method in the presence of several local minimizers.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10316/454992015-01-01T00:00:00ZGlobally convergent evolution strategies for constrained optimizationhttp://hdl.handle.net/10316/45496Title: Globally convergent evolution strategies for constrained optimization
Authors: Diouane, Y.; Gratton, S.; Vicente, Luís Nunes
Abstract: In this paper we propose, analyze, and test algorithms for constrained optimization when no use of derivatives of the objective function is made. The proposed methodology is built upon the globally convergent evolution strategies previously introduced by the authors for unconstrained optimization. Two approaches are encompassed to handle the constraints. In a first approach, feasibility is first enforced by a barrier function and the objective function is then evaluated directly at the feasible generated points. A second approach projects first all the generated points onto the feasible domain before evaluating the objective function. The resulting algorithms enjoy favorable global convergence properties (convergence to stationarity from arbitrary starting points), regardless of the linearity of the constraints. The algorithmic implementation (i) includes a step where previously evaluated points are used to accelerate the search (by minimizing quadratic models) and (ii) addresses the particular cases of bounds on the variables and linear constraints. Our solver is compared to others, and the numerical results confirm its competitiveness in terms of efficiency and robustness.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10316/454962015-01-01T00:00:00ZA parallel evolution strategy for an earth imaging problem in geophysicshttp://hdl.handle.net/10316/45245Title: A parallel evolution strategy for an earth imaging problem in geophysics
Authors: Diouane, Y.; Gratton, S.; Vasseur, X.; Vicente, Luís Nunes; Calandra, H.
Abstract: In this paper we propose a new way to compute a rough approximation solution, to be later used as a warm starting point in a more refined optimization process, for a challenging global optimization problem related to earth imaging in geophysics. The warm start consists of a velocity model that approximately solves a full-waveform inverse problem at low frequency. Our motivation arises from the availability of massively parallel computing platforms and the natural parallelization of evolution strategies as global optimization methods for continuous variables. Our first contribution consists of developing a new and efficient parametrization of the velocity models to significantly reduce the dimension of the original optimization space. Our second contribution is to adapt a class of evolution strategies to the specificity of the physical problem at hands where the objective function evaluation is known to be the most expensive computational part. A third contribution is the development of a parallel evolution strategy solver, taking advantage of a recently proposed modification of these class of evolutionary methods that ensures convergence and promotes better performance under moderate budgets. The numerical results presented demonstrate the effectiveness of the algorithm on a realistic 3D full-waveform inverse problem in geophysics. The developed numerical approach allows us to successfully solve an acoustic full-waveform inversion problem at low frequencies on a reasonable number of cores of a distributed memory computer.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10316/452452016-01-01T00:00:00Z