Flipping the switch on local exploration: Genetic Algorithms with Reversals

• URL: http://arxiv.org/abs/2202.00912v2
• Date: Wed, 24 Aug 2022 14:30:59 GMT
• Title: Flipping the switch on local exploration: Genetic Algorithms with Reversals
• Authors: Ankit Grover, Vaishali Yadav, Bradly Alicea
• Abstract summary: Authors show that gradient-free search techniques are suitable for providing an optimal solution in the discrete domain. They also show that the use of multiple local searches can improve performance on local searches. It is observed that the proposed GA variants have the least average cost across all benchmarks including the problem proposed and IC performs better than its constituents.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One important feature of complex systems are problem domains that have many local minima and substructure. Biological systems manage these local minima by switching between different subsystems depending on their environmental or developmental context. Genetic Algorithms (GA) can mimic this switching property as well as provide a means to overcome problem domain complexity. However, standard GA requires additional operators that will allow for large-scale exploration in a stochastic manner. Gradient-free heuristic search techniques are suitable for providing an optimal solution in the discrete domain to such single objective optimization tasks, particularly compared to gradient-based methods which are noticeably slower. To do this, the authors turn to an optimization problem from the flight scheduling domain. The authors compare the performance of such common gradient-free heuristic search algorithms and propose variants of GAs. The Iterated Chaining (IC) method is also introduced, building upon traditional chaining techniques by triggering multiple local searches instead of the singular action of a mutation operator. The authors will show that the use of multiple local searches can improve performance on local stochastic searches, providing ample opportunity for application to a host of other problem domains. It is observed that the proposed GA variants have the least average cost across all benchmarks including the problem proposed and IC algorithm performs better than its constituents.

Related papers

• Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
  Genetic Algorithms (GAs) are known for their efficiency in solving optimization problems. This paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts.
  arXiv  Detail & Related papers  (2023-09-28T13:05:30Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill? [10.882329986831087]
  We investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS) We show that exploiting more sophisticated strategies using measures of node relatedness can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures.
  arXiv  Detail & Related papers  (2022-09-09T22:08:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
  We study the connection between network topology and convergence rates for different algorithms on a real world problem of sensor localization. We also show interesting connections between ADMM and lifted Markov chains besides providing an explicitly characterization of its convergence.
  arXiv  Detail & Related papers  (2020-09-05T21:44:39Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)
• Cross-Domain Facial Expression Recognition: A Unified Evaluation Benchmark and Adversarial Graph Learning [85.6386289476598]
  We develop a novel adversarial graph representation adaptation (AGRA) framework for cross-domain holistic-local feature co-adaptation. We conduct extensive and fair evaluations on several popular benchmarks and show that the proposed AGRA framework outperforms previous state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-08-03T15:00:31Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)
• Locally-Adaptive Nonparametric Online Learning [12.018422134251384]
  We introduce efficient online algorithms that adapt to arbitrary data sequences. We use a technique based on tree experts to efficiently compete against all such prunings. Our technique delivers regret bounds that are significantly better than those proven using the previous approach.
  arXiv  Detail & Related papers  (2020-02-05T17:42:04Z)

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.