检索结果-内蒙古大学图书馆

Memory-Driven Metaheuristics: Improving optimization Performance

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Farahmand-Tabar, Salar Department of Civil Engineering Eng. Faculty of Engineering University of Zanjan Zanjan Iran

Metaheuristics are stochastic optimization algorithms that mimic natural processes to find optimal solutions to complex problems. The success of metaheuristics largely depends on the ability to effectively explore and exploit the search space. Memory mechanisms have been introduced in several popular metaheuristic algorithms to enhance their performance. This chapter explores the significance of memory in metaheuristic algorithms and provides insights from well-known algorithms. The chapter begins by introducing the concept of memory, and its role in metaheuristic algorithms. The key factors influencing the effectiveness of memory mechanisms are discussed, such as the size of the memory, the information stored in memory, and the rate of information decay. A comprehensive analysis of how memory mechanisms are incorporated into popular metaheuristic algorithms is presented, and concludes by highlighting the importance of memory in metaheuristic performance and providing future research directions for improving memory mechanisms. The key takeaways are that memory mechanisms can significantly enhance the performance of metaheuristics by enabling them to explore and exploit the search space effectively and efficiently, and that the choice of memory mechanism should be tailored to the problem domain and the characteristics of the search space. © 2024, CC BY-NC-SA.

关键词： optimization algorithms

OptEx: Expediting First-Order optimization with Approximately Parallelized Iterations

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Shu, Yao Fang, Jiongfeng He, Ying Tiffany Yu, Fei Richard China College of Computer Science and Software Engineering Shenzhen University China School of Information Technology Carleton University Canada

First-order optimization (FOO) algorithms are pivotal in numerous computational domains, such as reinforcement learning and deep learning. However, their application to complex tasks often entails significant optimization inefficiency due to their need of many sequential iterations for convergence. In response, we introduce first-order optimization expedited with approximately parallelized iterations (OptEx), the first general framework that enhances the optimization efficiency of FOO by leveraging parallel computing to directly mitigate its requirement of many sequential iterations for convergence. To achieve this, OptEx utilizes a kernelized gradient estimation that is based on the history of evaluated gradients to predict the gradients required by the next few sequential iterations in FOO, which helps to break the inherent iterative dependency and hence enables the approximate parallelization of iterations in FOO. We further establish theoretical guarantees for the estimation error of our kernelized gradient estimation and the iteration complexity of SGD-based OptEx, confirming that the estimation error diminishes to zero as the history of gradients accumulates and that our SGD-based OptEx enjoys an effective acceleration rate of Θ(√N) over standard SGD given parallelism of N, in terms of the sequential iterations required for convergence. Finally, we provide extensive empirical studies, including synthetic functions, reinforcement learning tasks, and neural network training on various datasets, to underscore the substantial efficiency improvements achieved by OptEx in practice. Our implementation is available at https://***/youyve/OptEx. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Universal Gradient Methods for Stochastic Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Rodomanov, Anton Kavis, Ali Wu, Yongtao Antonakopoulos, Kimon Cevher, Volkan CISPA Helmholtz Center for Information Security Germany UT Austin United States EPFL Switzerland

We develop universal gradient methods for Stochastic Convex optimization (SCO). Our algorithms automatically adapt not only to the oracle’s noise but also to the Hölder smoothness of the objective function without a priori knowledge of the particular setting. The key ingredient is a novel strategy for adjusting step-size coefficients in the Stochastic Gradient Method (SGD). Unlike AdaGrad, which accumulates gradient norms, our Universal Gradient Method accumulates appropriate combinations of gradient- and iterate differences. The resulting algorithm has state-of-the-art worst-case convergence rate guarantees for the entire Hölder class including, in particular, both nonsmooth functions and those with Lipschitz continuous gradient. We also present the Universal Fast Gradient Method for SCO enjoying optimal efficiency estimates. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Expected Maximin Fairness in Max-Cut and other Combinatorial optimization Problems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Salem, Jad Tate, Reuben Eidenbenz, Stephan Mathematics Department United States Naval Academy United States CCS-3: Information Sciences Los Alamos National Laboratory United States

Maximin fairness is the ideal that the worst-off group (or individual) should be treated as well as possible. Literature on maximin fairness in various decision-making settings has grown in recent years, but theoretical results are sparse. In this paper, we explore the challenges inherent to maximin fairness in combinatorial optimization. We begin by showing that (1) optimal maximin-fair solutions are bounded by non-maximin-fair optimal solutions, and (2) stochastic maximin-fair solutions exceed their deterministic counterparts in expectation for a broad class of combinatorial optimization problems. In the remainder of the paper, we use the special case of Max-Cut to demonstrate challenges in defining and implementing maximin fairness. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Decentralized optimization in Time-Varying Networks with Arbitrary Delays

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ortega, Tomas Jafarkhani, Hamid Center for Pervasive Communications & Computing and EECS Department University of California Irvine IrvineCA92697 United States

We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical *** Codes 68W10, 68W15, 68W40, 90C06, 90C35, 90C25 © 2024, CC BY-NC-ND.

关键词： optimization algorithms

ITERATIVE BELIEF PROPAGATION FOR SPARSE COMBINATORIAL optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Reifenstein, Sam Leleu, Timothée NTT Research Inc Japan Stanford University United States

In this note we study an iterative belief propagation (IBP) algorithm and demonstrate it’s ability to solve sparse combinatorial optimization problems. Similar to simulated annealing (SA) [1], our IBP algorithm attempts to sample from the Boltzmann distribution of the objective function but also uses belief propagation (BP) [2, 3] to improve convergence. © 2024, CC BY.

关键词： optimization algorithms

A New Fast Adaptive Linearized Alternating Direction Multiplier Method for Convex optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Boran College of Science Minzu University of China Beijing100081 China

This work proposes a novel adaptive linearized alternating direction multiplier method (LADMM) to convex optimization, which improves the convergence rate of the LADMM-based algorithm by adjusting step-size iteratively. The innovation of this method is to utilize the information of the current iteration point to adaptively select the appropriate parameters, thus expanding the selection of the subproblem step size and improving the convergence rate of the algorithm while ensuring convergence. The advantage of this method is that it can improve the convergence rate of the algorithm as much as possible without compromising the convergence. This is very beneficial for the solution of optimization problems because the traditional linearized alternating direction multiplier method has a trade-off in the selection of the regular term coefficients: larger coefficients ensure convergence but tend to lead to small step sizes, while smaller coefficients allow for an increase in the iterative step size but tend to lead to the algorithm’s non-convergence. This balance can be better handled by adaptively selecting the parameters, thus improving the efficiency of the algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms

Jaya R Package - A Parameter-Free Solution for Advanced Single and Multi-Objective optimization

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bokde, Neeraj Dhanraj Renewable and Sustainable Energy Research Center Technology Innovation Institute Abu Dhabi9639 United Arab Emirates

The Jaya R package offers a robust and versatile implementation of the parameter-free Jaya optimization algorithm, suitable for solving both single-objective and multi-objective optimization problems. By integrating advanced features such as constraint handling, adaptive population management, Pareto front tracking for multi-objective trade-offs, and parallel processing for computational efficiency, the package caters to a wide range of optimization challenges. Its intuitive design and flexibility allow users to solve complex, real-world problems across various domains. To demonstrate its practical utility, a case study on energy modeling explores the optimization of renewable energy shares, showcasing the package’s ability to minimize carbon emissions and costs while enhancing system reliability. The Jaya R package is an invaluable tool for researchers and practitioners seeking efficient and adaptive optimization solutions. © 2024, CC BY.

关键词： optimization algorithms

Biased Pareto optimization for Subset Selection with Dynamic Cost Constraints

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Dan-Xuan Qian, Chao National Key Laboratory for Novel Software Technology Nanjing University China School of Artificial Intelligence Nanjing University China

Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget, which has various applications such as influence maximization and maximum coverage. In real-world scenarios, the budget, representing available resources, may change over time, which requires that algorithms must adapt quickly to new budgets. However, in this dynamic environment, previous algorithms either lack theoretical guarantees or require a long running time. The state-of-the-art algorithm, POMC, is a Pareto optimization approach designed for static problems, lacking consideration for dynamic problems. In this paper, we propose BPODC, enhancing POMC with biased selection and warm-up strategies tailored for dynamic environments. We focus on the ability of BPODC to leverage existing computational results while adapting to budget changes. We prove that BPODC can maintain the best known (αf /2)(1 − e−αf )-approximation guarantee when the budget changes. Experiments on influence maximization and maximum coverage show that BPODC adapts more effectively and rapidly to budget changes, with a running time that is less than that of the static greedy algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： optimization algorithms