Lipschitz-based Surrogate Model for High-dimensional Computationally Expensive Problems

• URL: http://arxiv.org/abs/2204.14236v1
• Date: Fri, 29 Apr 2022 17:07:34 GMT
• Title: Lipschitz-based Surrogate Model for High-dimensional Computationally Expensive Problems
• Authors: Jakub Kudela and Radomil Matousek
• Abstract summary: Surrogate-assisted evolutionary algorithms (SAEAs) have recently gained increased attention because of their search capabilities. In this paper, we propose a novel surrogate model based on a Lipschitz underestimation of the expensive-to-compute objective function. We also develop a differential evolution-based algorithm, that utilizes the Lipschitz-based surrogate model.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Standard evolutionary optimization algorithms assume that the evaluation of the objective and constraint functions is straightforward and computationally cheap. However, in many real-world optimization problems, the computations of the objective function or constraints involve computationally expensive numerical simulations or physical experiments. Surrogate-assisted evolutionary algorithms (SAEAs) have recently gained increased attention because of their search capabilities for solving these computationally expensive optimization problems. The main idea of SAEAs is the integration of an evolutionary algorithm with a selected surrogate model. In this paper, we propose a novel surrogate model based on a Lipschitz underestimation of the expensive-to-compute objective function. We also develop a differential evolution-based algorithm, that utilizes the Lipschitz-based surrogate model, along with a standard radial basis function surrogate model and a local search procedure. This algorithm, called Lipschitz Surrogate-assisted Differential Evolution (LSADE), is designed for high-dimensional computationally expensive problems. The experimental results on seven benchmark functions of dimensions 30, 50, 100, and 200 show that the proposed method utilizing the Lipschitz-based surrogate model is competitive compared with the state-of-the-art algorithms under a limited computational budget, being especially effective for the very complicated benchmark functions in high dimensions.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Large Language Models as Surrogate Models in Evolutionary Algorithms: A Preliminary Study [5.6787965501364335]
  Surrogate-assisted selection is a core step in evolutionary algorithms to solve expensive optimization problems. Traditionally, this has relied on conventional machine learning methods, leveraging historical evaluated evaluations to predict the performance of new solutions. In this work, we propose a novel surrogate model based purely on LLM inference capabilities, eliminating the need for training.
  arXiv  Detail & Related papers  (2024-06-15T15:54:00Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Landscape-Sketch-Step: An AI/ML-Based Metaheuristic for Surrogate Optimization Problems [0.0]
  We introduce a newimats for global optimization in scenarios where extensive evaluations of the cost function are expensive, inaccessible, or even prohibitive. The method, which we call Landscape-Sketch-and-Step (LSS), combines Machine Learning, Replica Optimization, and Reinforcement Learning techniques.
  arXiv  Detail & Related papers  (2023-09-14T01:53:45Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms. Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
  arXiv  Detail & Related papers  (2023-08-17T08:34:58Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Rank-Based Learning and Local Model Based Evolutionary Algorithm for High-Dimensional Expensive Multi-Objective Problems [1.0499611180329806]
  The proposed algorithm consists of three parts: rank-based learning, hyper-volume-based non-dominated search, and local search in the relatively sparse objective space. The experimental results of benchmark problems and a real-world application on geothermal reservoir heat extraction optimization demonstrate that the proposed algorithm shows superior performance.
  arXiv  Detail & Related papers  (2023-04-19T06:25:04Z)
• Exploring the effectiveness of surrogate-assisted evolutionary algorithms on the batch processing problem [0.0]
  This paper introduces a simulation of a well-known batch processing problem in the literature. Evolutionary algorithms such as Genetic Algorithm (GA), Differential Evolution (DE) are used to find the optimal schedule for the simulation. We then compare the quality of solutions obtained by the surrogate-assisted versions of the algorithms against the baseline algorithms.
  arXiv  Detail & Related papers  (2022-10-31T09:00:39Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Surrogate Assisted Evolutionary Algorithm for Medium Scale Expensive Multi-Objective Optimisation Problems [4.338938227238059]
  Building a surrogate model of an objective function has shown to be effective to assist evolutionary algorithms (EAs) to solve real-world complex optimisation problems. We propose a Gaussian process surrogate model assisted EA for medium-scale expensive multi-objective optimisation problems with up to 50 decision variables. The effectiveness of our proposed algorithm is validated on benchmark problems with 10, 20, 50 variables, comparing with three state-of-the-art SAEAs.
  arXiv  Detail & Related papers  (2020-02-08T12:06:08Z)

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.