Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process

• URL: http://arxiv.org/abs/2501.18184v3
• Date: Thu, 26 Jun 2025 04:26:22 GMT
• Title: Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process
• Authors: Qingchuan Lyu,
• Abstract summary: Genetic Algorithm with Border Trades (GAB) is a novel modification of the standard genetic algorithm that enhances exploration by incorporating new chromosome patterns in the breeding process.<n>GAB achieves up to 8x higher fitness and 10x faster convergence on complex job scheduling problems compared to standard Genetic Algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes Genetic Algorithm with Border Trades (GAB), a novel modification of the standard genetic algorithm that enhances exploration by incorporating new chromosome patterns in the breeding process. This approach significantly mitigates premature convergence and improves search diversity. Empirically, GAB achieves up to 8x higher fitness and 10x faster convergence on complex job scheduling problems compared to standard Genetic Algorithms, reaching average fitness scores of 888 versus 106 in under 20 seconds. On the classic Flip-Flop problem, GAB consistently finds optimal or near-optimal solutions in fewer generations, even as input sizes scale to thousands of bits. These results highlight GAB as a highly effective and computationally efficient alternative for solving large-scale combinatorial optimization problems.

Related papers

• The Pitfalls and Potentials of Adding Gene-invariance to Optimal Mixing [0.0]
  Optimal Mixing (OM) is a variation operator that integrates local search with genetic recombination.<n>We propose a solution inspired by the Gene Invariant Genetic Algorithm (GIGA), which preserves gene frequencies in the population throughout the process.<n>This technique is tailored to and integrated with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA), resulting in GI-GOMEA.
  arXiv  Detail & Related papers  (2025-06-18T08:06:44Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• A Lattice-based Method for Optimization in Continuous Spaces with Genetic Algorithms [0.0]
  This work presents a novel lattice-based methodology for incorporating multidimensional constraints into continuous decision variables. The proposed approach consolidates established transcription techniques for crossover of continuous decision variables. It aims to leverage domain knowledge and guide the search process towards feasible regions of the design space.
  arXiv  Detail & Related papers  (2024-10-16T03:14:09Z)
• Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
  The maximum clique problem (MCP) is a fundamental problem in graph theory and computational complexity. Various meta-heuristics have been used to approximate the MCP, including genetic and memetic algorithms, ant colony algorithms, greedy algorithms, Tabu algorithms, and simulated annealing. Our results indicate that Monte Carlo algorithms, which employ random searches to generate subgraphs, often surpass genetic algorithms in both speed and capability.
  arXiv  Detail & Related papers  (2024-09-26T12:50:00Z)
• Deep Graph Anomaly Detection: A Survey and New Perspectives [86.84201183954016]
  Graph anomaly detection (GAD) aims to identify unusual graph instances (nodes, edges, subgraphs, or graphs) Deep learning approaches, graph neural networks (GNNs) in particular, have been emerging as a promising paradigm for GAD.
  arXiv  Detail & Related papers  (2024-09-16T03:05:11Z)
• Predicting Genetic Mutation from Whole Slide Images via Biomedical-Linguistic Knowledge Enhanced Multi-label Classification [119.13058298388101]
  We develop a Biological-knowledge enhanced PathGenomic multi-label Transformer to improve genetic mutation prediction performances. BPGT first establishes a novel gene encoder that constructs gene priors by two carefully designed modules. BPGT then designs a label decoder that finally performs genetic mutation prediction by two tailored modules.
  arXiv  Detail & Related papers  (2024-06-05T06:42:27Z)
• GARA: A novel approach to Improve Genetic Algorithms' Accuracy and Efficiency by Utilizing Relationships among Genes [1.7226572355808027]
  We propose Gene Regulatory Genetic Algorithm (GRGA), which is the first time to utilize relationships among genes for improving GA's accuracy and efficiency. We use a directed multipartite graph encapsulating the solution space, called RGGR, where each node corresponds to a gene in the solution and the edge represents the relationship between adjacent nodes. The obtained RGGR is then employed to determine appropriate loci of crossover and mutation operators, thereby directing the evolutionary process toward faster and better convergence.
  arXiv  Detail & Related papers  (2024-04-28T08:33:39Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• GE-AdvGAN: Improving the transferability of adversarial samples by gradient editing-based adversarial generative model [69.71629949747884]
  Adversarial generative models, such as Generative Adversarial Networks (GANs), are widely applied for generating various types of data. In this work, we propose a novel algorithm named GE-AdvGAN to enhance the transferability of adversarial samples.
  arXiv  Detail & Related papers  (2024-01-11T16:43:16Z)
• Genetic Algorithm enhanced by Deep Reinforcement Learning in parent selection mechanism and mutation : Minimizing makespan in permutation flow shop scheduling problems [0.18846515534317265]
  The proposed RL+GA method was specifically tested on the flow shop scheduling problem (FSP) The hybrid algorithm incorporates neural networks (NN) and uses the off-policy method Q-learning. Results of the study highlight the effectiveness of the RL+GA approach in improving the performance of the primitive GA.
  arXiv  Detail & Related papers  (2023-11-10T08:51:42Z)
• 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)
• Hybrid Genetic Algorithm and Hill Climbing Optimization for the Neural Network [0.0]
  We propose a hybrid model combining genetic algorithm and hill climbing algorithm for optimizing Convolutional Neural Networks (CNNs) on the CIFAR-100 dataset. The proposed hybrid model achieves better accuracy with fewer generations compared to the standard algorithms.
  arXiv  Detail & Related papers  (2023-08-24T22:03:18Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. We analyze to what extent the $(lambda,lambda)$ genetic algorithm is robust to noise.
  arXiv  Detail & Related papers  (2023-05-08T08:49:01Z)
• Epigenetics Algorithms: Self-Reinforcement-Attention mechanism to regulate chromosomes expression [0.0]
  This paper proposes a new epigenetics algorithm that mimics the epigenetics phenomenon known as methylation. The novelty of our epigenetics algorithms lies primarily in taking advantage of attention mechanisms and deep learning, which fits well with the genes/silencing concept.
  arXiv  Detail & Related papers  (2023-03-15T21:33:21Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  Gradient Descent-Ascent (SGDA) is one of the most prominent algorithms for solving min-max optimization and variational inequalities problems (VIP) In this paper, we propose a unified convergence analysis that covers a large variety of descent-ascent methods. We develop several new variants of SGDA such as a new variance-reduced method (L-SVRGDA), new distributed methods with compression (QSGDA, DIANA-SGDA, VR-DIANA-SGDA), and a new method with coordinate randomization (SEGA-SGDA)
  arXiv  Detail & Related papers  (2022-02-15T09:17:39Z)
• Heterogeneous Face Frontalization via Domain Agnostic Learning [74.86585699909459]
  We propose a domain agnostic learning-based generative adversarial network (DAL-GAN) which can synthesize frontal views in the visible domain from thermal faces with pose variations. DAL-GAN consists of a generator with an auxiliary classifier and two discriminators which capture both local and global texture discriminations for better synthesis.
  arXiv  Detail & Related papers  (2021-07-17T20:41:41Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  This paper presents an alternate approach of mutation probability generation using chromosome rank to avoid any susceptibility to fitness distribution. Experiments are done to compare results of simple genetic algorithm (SGA) with constant mutation probability and adaptive approaches within a limited resource constraint.
  arXiv  Detail & Related papers  (2021-04-18T12:41:33Z)
• 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)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.