Evaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm

• URL: http://arxiv.org/abs/2010.03483v1
• Date: Wed, 7 Oct 2020 15:36:33 GMT
• Title: Evaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm
• Authors: Waleed Bin Owais, Iyad W. J. Alkhazendar and Dr.Mohammad Saleh
• Abstract summary: Genetic Algorithm is an evolutionary algorithm and a metaheuristic that was introduced to overcome the failure of gradient based method in solving the optimization and search problems. Our results indicate that convergence rate of combination of one point crossover with tournament selection, with respect to 0/1 knapsack problem that we considered, is the highest and thereby most efficient in solving 0/1 knapsack.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Genetic Algorithm is an evolutionary algorithm and a metaheuristic that was introduced to overcome the failure of gradient based method in solving the optimization and search problems. The purpose of this paper is to evaluate the impact on the convergence of Genetic Algorithm vis-a-vis 0/1 knapsack. By keeping the number of generations and the initial population fixed, different crossover methods like one point crossover and two-point crossover were evaluated and juxtaposed with each other. In addition to this, the impact of different selection methods like rank-selection, roulette wheel and tournament selection were evaluated and compared. Our results indicate that convergence rate of combination of one point crossover with tournament selection, with respect to 0/1 knapsack problem that we considered, is the highest and thereby most efficient in solving 0/1 knapsack.

Related papers

• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process [0.0]
  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.
  arXiv  Detail & Related papers  (2025-01-30T07:35:43Z)
• Benchmarking Randomized Optimization Algorithms on Binary, Permutation, and Combinatorial Problem Landscapes [8.337399973715396]
  We evaluate the performance of four randomized optimization algorithms: Randomized Hill Climbing (RHC), Simulated Annealing (SA), Genetic Algorithms (GA), and MIMIC. We compare these algorithms using a set of benchmark fitness functions that highlight the specific challenges and requirements of each problem category. Our study analyzes each algorithm's effectiveness based on key performance metrics, including solution quality, convergence speed, computational cost, and robustness.
  arXiv  Detail & Related papers  (2025-01-21T23:13:01Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Feature Selection via Robust Weighted Score for High Dimensional Binary Class-Imbalanced Gene Expression Data [1.2891210250935148]
  A robust weighted score for unbalanced data (ROWSU) is proposed for selecting the most discriminative feature for high dimensional gene expression binary classification with class-imbalance problem. The performance of the proposed ROWSU method is evaluated on $6$ gene expression datasets.
  arXiv  Detail & Related papers  (2024-01-23T11:22:03Z)
• Addressing The Knapsack Challenge Through Cultural Algorithm Optimization [0.0]
  We introduce a novel variant of Cultural Algorithms tailored specifically for solving 0-1 knapsack problems. Our proposed algorithm incorporates a belief space to refine the population and introduces two vital functions for dynamically adjusting the crossover and mutation rates. We provide compelling evidence of the algorithm's remarkable efficiency in consistently locating the global optimum.
  arXiv  Detail & Related papers  (2023-10-30T17:05:19Z)
• A Hybrid Chimp Optimization Algorithm and Generalized Normal Distribution Algorithm with Opposition-Based Learning Strategy for Solving Data Clustering Problems [0.0]
  This paper is concerned with data clustering to separate clusters based on the connectivity principle for categorizing similar and dissimilar data into different groups. Successful meta-heuristic optimization algorithms and intelligence-based methods have been introduced to attain the optimal solution in a reasonable time.
  arXiv  Detail & Related papers  (2023-02-16T23:29:01Z)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  Machine learning models, such as SVM, require a definition of distance/similarity between pairs of sequences. Exact methods yield better classification performance, but they pose high computational costs. We propose a series of ways to improve the performance of the approximate kernel in order to enhance its predictive performance.
  arXiv  Detail & Related papers  (2022-09-11T22:44:19Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Population based change-point detection for the identification of homozygosity islands [0.0]
  We introduce a penalized maximum likelihood approach that can be efficiently computed by a dynamic programming algorithm or approximated by a fast greedy binary splitting algorithm. We prove both algorithms converge almost surely to the set of change-points under very general assumptions on the distribution and independent sampling of the random vector. This new approach is motivated by the problem of identifying homozygosity islands on the genome of individuals in a population.
  arXiv  Detail & Related papers  (2021-11-19T12:53:41Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Multivariate feature ranking of gene expression data [62.997667081978825]
  We propose two new multivariate feature ranking methods based on pairwise correlation and pairwise consistency. We statistically prove that the proposed methods outperform the state of the art feature ranking methods Clustering Variation, Chi Squared, Correlation, Information Gain, ReliefF and Significance.
  arXiv  Detail & Related papers  (2021-11-03T17:19:53Z)
• Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms [10.984298685238445]
  This paper aims to answer whether binomial crossover can reduce the approximation error of evolutionary algorithms. It is proven that using binomial crossover leads to the dominance of transition matrices. An adaptive parameter strategy is proposed which can strengthen the superiority of binomial crossover on Deceptive.
  arXiv  Detail & Related papers  (2021-09-29T05:15:01Z)

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.