論文の概要: An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem

• arxiv url: http://arxiv.org/abs/2403.11307v1
• Date: Sun, 17 Mar 2024 19:05:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 17:36:46.795441
• Title: An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem
• Title（参考訳）: 一般的な0-1knapsack問題に対する遺伝的アルゴリズムにおける突然変異確率の上限
• Authors: Yang Yang,
• Abstract要約: 我々は,0-1knapsack問題(0-1KP)と改良された突然変異演算子(IMO)に対する新しい還元法を提案する。 大規模インスタンスにおいて1回の反復で最適解を打つIMOは、従来の突然変異演算子よりも優れていることを証明した。
• 参考スコア（独自算出の注目度）: 4.368211287521716
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: As an important part of genetic algorithms (GAs), mutation operators is widely used in evolutionary algorithms to solve $\mathcal{NP}$-hard problems because it can increase the population diversity of individual. Due to limitations in mathematical tools, the mutation probability of the mutation operator is primarily empirically set in practical applications. In this paper, we propose a novel reduction method for the 0-1 knapsack problem(0-1 KP) and an improved mutation operator (IMO) based on the assumption $\mathcal{NP}\neq\mathcal{P}$, along with the utilization of linear relaxation techniques and a recent result by Dey et al. (Math. Prog., pp 569-587, 2022). We employ this method to calculate an upper bound of the mutation probability in general instances of the 0-1 KP, and construct an instance where the mutation probability does not tend towards 0 as the problem size increases. Finally, we prove that the probability of the IMO hitting the optimal solution within only a single iteration in large-scale instances is superior to that of the traditional mutation operator.
• Abstract（参考訳）: 遺伝的アルゴリズム(GA)の重要な部分として、突然変異演算子は、個体の個体数の多様性を増大させるため、$\mathcal{NP}$-hard問題を解くために、進化アルゴリズムで広く用いられている。 数学的ツールの制限により、突然変異演算子の突然変異確率は、実際的な応用において実験的に設定される。 本稿では, 線形緩和技術の利用と, Dey et al (Math. Prog., pp 569-587, 2022) による最近の結果とともに, 仮定 $\mathcal{NP}\neq\mathcal{P}$ に基づく 0-1 knapsack 問題 (0-1 KP) と改良された突然変異演算子 (IMO) に対する新しい還元法を提案する。 この手法を用いて、0-1 KP の一般例における突然変異確率の上限を計算し、問題のサイズが大きくなるにつれて突然変異確率が 0 に近づかない場合を構築する。 最後に、大規模インスタンスにおいて1回の反復で最適解を打つ確率が従来の突然変異演算子よりも優れていることを証明した。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions [0.44241702149260353]
  Witt は (1+1) 進化的アルゴリズムの標準的なビット変異は任意の線形関数の最適値を見つけるのに時間を必要とすることを示した。 この結果は、標準ビット突然変異が任意の未バイアス突然変異演算子に置き換えられた場合にどのように一般化されるかを検討する。
  論文  参考訳（メタデータ） (2023-02-23T21:09:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。 より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。 我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
  論文  参考訳（メタデータ） (2022-05-17T15:28:46Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  本稿では,染色体ランクを用いた突然変異確率生成の代替手法を提案する。 単純な遺伝的アルゴリズム(SGA)と一定の突然変異確率と限られた資源制約内での適応的アプローチとの比較実験を行った。
  論文  参考訳（メタデータ） (2021-04-18T12:41:33Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。 我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。 我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
  論文  参考訳（メタデータ） (2020-04-22T07:47:00Z)
• The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
  我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。 また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
  論文  参考訳（メタデータ） (2020-04-18T17:04:57Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。