On Fitness Landscape Analysis of Permutation Problems: From Distance Metrics to Mutation Operator Selection

• URL: http://arxiv.org/abs/2208.11188v1
• Date: Tue, 23 Aug 2022 20:46:49 GMT
• Title: On Fitness Landscape Analysis of Permutation Problems: From Distance Metrics to Mutation Operator Selection
• Authors: Vincent A. Cicirello
• Abstract summary: We explore the theory and expand upon the practice of fitness landscape analysis for optimization problems over the space of permutations. We begin with a survey of the available distance metrics for permutations, and then use principal component analysis to classify these metrics. Our implementations of the permutation metrics, permutation mutation operators, and associated evolutionary algorithm, are available in a pair of open source Java libraries.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we explore the theory and expand upon the practice of fitness landscape analysis for optimization problems over the space of permutations. Many of the computational and analytical tools for fitness landscape analysis, such as fitness distance correlation, require identifying a distance metric for measuring the similarity of different solutions to the problem. We begin with a survey of the available distance metrics for permutations, and then use principal component analysis to classify these metrics. The result of this analysis aligns with existing classifications of permutation problem types produced through less formal means, including the A-permutation, R-permutation, and P-permutation types, which classifies problems by whether absolute position of permutation elements, relative positions of elements, or general precedence of pairs of elements, is the dominant influence over solution fitness. Additionally, the formal analysis identifies subtypes within these problem categories. We see that the classification can assist in identifying appropriate metrics based on optimization problem feature for use in fitness landscape analysis. Using optimization problems of each class, we also demonstrate how the classification scheme can subsequently inform the choice of mutation operator within an evolutionary algorithm. From this, we present a classification of a variety of mutation operators as a counterpart to that of the metrics. Our implementations of the permutation metrics, permutation mutation operators, and associated evolutionary algorithm, are available in a pair of open source Java libraries. All of the code necessary to recreate our analysis and experimental results are also available as open source.

Related papers

• Symmetry Discovery for Different Data Types [52.2614860099811]
  Equivariant neural networks incorporate symmetries into their architecture, achieving higher generalization performance. We propose LieSD, a method for discovering symmetries via trained neural networks which approximate the input-output mappings of the tasks. We validate the performance of LieSD on tasks with symmetries such as the two-body problem, the moment of inertia matrix prediction, and top quark tagging.
  arXiv  Detail & Related papers  (2024-10-13T13:39:39Z)
• Permutation invariant functions: statistical tests, density estimation, and computationally efficient embedding [1.4316259003164373]
  Permutation invariance is among the most common symmetry that can be exploited to simplify complex problems in machine learning (ML) In this paper, we take a step back and examine these questions in several fundamental problems. Our methods for (i) and (iv) are based on a sorting trick and (ii) is based on an averaging trick.
  arXiv  Detail & Related papers  (2024-03-04T01:49:23Z)
• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  Evolving permutations directly requires specialized evolutionary operators. In this paper, we survey the breadth of evolutionary operators for permutations. We implement all of these in Chips-n-Salsa, an open source Java library for evolutionary computation.
  arXiv  Detail & Related papers  (2023-11-24T16:32:44Z)
• Benchmarking Differential Evolution on a Quantum Simulator [0.0]
  Differential Evolution (DE) can be used to compute the minima of functions such as the rastrigin function and rosenbrock function. This work is an attempt to study the result of applying the DE method on these functions with candidate individuals generated on classical Turing modeled computation.
  arXiv  Detail & Related papers  (2023-11-06T14:27:00Z)
• Equivariant Disentangled Transformation for Domain Generalization under Combination Shift [91.38796390449504]
  Combinations of domains and labels are not observed during training but appear in the test environment. We provide a unique formulation of the combination shift problem based on the concepts of homomorphism, equivariance, and a refined definition of disentanglement.
  arXiv  Detail & Related papers  (2022-08-03T12:31:31Z)
• Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group [8.40077201352607]
  "Shuffled data" is data in which the correct pairing of (X, Y)-pairs is represented via an unknown index permutation. We propose a flexible exponential family prior on the permutation group for this purpose. Inference is based on the EM algorithm in which the intractable E-step is approximated by the Fisher-Yates algorithm.
  arXiv  Detail & Related papers  (2021-11-02T17:43:28Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  Finding correspondences between shapes is a fundamental problem in computer vision and graphics. While isometries are often studied in shape correspondence problems, they have not been considered explicitly in the multi-matching setting. We present a suitable optimisation algorithm for solving our formulation and provide a convergence and complexity analysis.
  arXiv  Detail & Related papers  (2020-12-04T15:58:34Z)
• Evolutionary Algorithms with Self-adjusting Asymmetric Mutation [0.0]
  We analyze an asymmetric mutation operator that can treat zero- and one-bits differently. We show improved runtime results on the class of functions OneMax$_a$ describing the number of matching bits.
  arXiv  Detail & Related papers  (2020-06-16T13:16:50Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.