Stagnation Detection in Highly Multimodal Fitness Landscapes

• URL: http://arxiv.org/abs/2104.04395v3
• Date: Thu, 22 Apr 2021 13:58:31 GMT
• Title: Stagnation Detection in Highly Multimodal Fitness Landscapes
• Authors: Amirhossein Rajabi and Carsten Witt
• Abstract summary: Stagnation detection has been proposed as a mechanism for randomized searchs to escape from local optima. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully. We implement this idea in an algorithm called SD-RLS$textm$ and show compared to previous variants of stagnation detection that it yields speed-ups.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i.e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to $1$ without using gap sizes that were promising in the past. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully by giving preference to values that were successful in the past. We implement this idea in an algorithm called SD-RLS$^{\text{m}}$ and show compared to previous variants of stagnation detection that it yields speed-ups for linear functions under uniform constraints and the minimum spanning tree problem. Moreover, its running time does not significantly deteriorate on unimodal functions and a generalization of the Jump benchmark. Finally, we present experimental results carried out to study SD-RLS$^{\text{m}}$ and compare it with other algorithms.

Related papers

• Graspness Discovery in Clutters for Fast and Accurate Grasp Detection [57.81325062171676]
  "graspness" is a quality based on geometry cues that distinguishes graspable areas in cluttered scenes. We develop a neural network named cascaded graspness model to approximate the searching process. Experiments on a large-scale benchmark, GraspNet-1Billion, show that our method outperforms previous arts by a large margin.
  arXiv  Detail & Related papers  (2024-06-17T02:06:47Z)
• SpirDet: Towards Efficient, Accurate and Lightweight Infrared Small Target Detector [60.42293239557962]
  We propose SpirDet, a novel approach for efficient detection of infrared small targets. We employ a new dual-branch sparse decoder to restore the feature map. Extensive experiments show that the proposed SpirDet significantly outperforms state-of-the-art models.
  arXiv  Detail & Related papers  (2024-02-08T05:06:14Z)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS) We propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE) We empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios.
  arXiv  Detail & Related papers  (2023-12-28T01:24:42Z)
• Space-Time Attention with Shifted Non-Local Search [1.7676816383911753]
  Methods for long-range motion use an auxiliary network to predict the most similar key coordinates as offsets from each query location. Small spatial inaccuracies significantly impact the attention module's quality. This paper proposes a search strategy that combines the quality of a non-local search with the range of predicted offsets.
  arXiv  Detail & Related papers  (2023-09-28T20:59:51Z)
• A Large-scale Multiple-objective Method for Black-box Attack against Object Detection [70.00150794625053]
  We propose to minimize the true positive rate and maximize the false positive rate, which can encourage more false positive objects to block the generation of new true positive bounding boxes. We extend the standard Genetic Algorithm with Random Subset selection and Divide-and-Conquer, called GARSDC, which significantly improves the efficiency. Compared with the state-of-art attack methods, GARSDC decreases by an average 12.0 in the mAP and queries by about 1000 times in extensive experiments.
  arXiv  Detail & Related papers  (2022-09-16T08:36:42Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  Non-smooth finite-sum minimization is a fundamental problem in machine learning. This paper develops a distributed proximal-gradient algorithm with random reshuffling to solve the problem.
  arXiv  Detail & Related papers  (2021-11-06T07:29:55Z)
• AM-RRT*: Informed Sampling-based Planning with Assisting Metric [3.42658286826597]
  We present a new algorithm that extends RRT* and RT-RRT* for online path planning in complex, dynamic environments. Our method extends RRT-based sampling methods to enable the use of an assisting distance metric to improve performance in environments with obstacles.
  arXiv  Detail & Related papers  (2020-10-28T01:39:40Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. We present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. We show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets.
  arXiv  Detail & Related papers  (2020-03-06T00:06:20Z)
• Algorithms for Optimizing Fleet Staging of Air Ambulances [0.0]
  This research structured an optimal coverage problem with integer linear programming. A Gurobi was programmed with the developed model and timed for performance. A solution implementing base ranking followed by both local and Tabu search-based algorithms was created.
  arXiv  Detail & Related papers  (2020-01-10T04:32:28Z)

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.