論文の概要: Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

• arxiv url: http://arxiv.org/abs/2606.15923v1
• Date: Sun, 14 Jun 2026 16:58:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:33.944114
• Title: Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
• Title（参考訳）: ブール関数の進化におけるモンテカルロ遺伝的プログラミングの実行時解析
• Abstract要約: 我々は、CGPの適合度評価の期待値に対して、$O(n D5)$を有界に証明し、$n$入力の結合を構成する。 また、CGPが排他的解離を進化させるために指数時間を必要とすることを示す負の結果も証明する。
• 参考スコア（独自算出の注目度）: 5.276232626689568
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound $O(n D^5)$ for the expected number of fitness evaluations of CGP to construct a conjunction of $n$ inputs using at most $D \geq n-1$ binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to $O(n D^4)$. Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.
• Abstract（参考訳）: カルテシアン遺伝的プログラミング(Cartesian Genetic Programming, CGP)は、グラフベースのプログラム表現を使用する遺伝的プログラミングの実践的かつ一般的な形式の一つである。 本稿では,完全学習セットを用いたブール関数の進化におけるCGPの初回実行時解析について述べる。 我々は,最大$D \geq n-1$バイナリゲート,最小限の関数セット,厳密な生存選択を用いて,CGPの適合度評価を期待する数に対して,漸近的境界$O(n D^5)$を証明した。 非制限選択を使用すると、境界は$O(n D^4)$に改善される。 解析の結果,CGPによる探索の興味深い特徴が明らかとなった。 特に、フィットネスに寄与しない接続ゲートを含む等しく良い解が受け入れられることによって、スピードアップが起こり、結果として漸近的な時間制限がより良くなる。 接続とは対照的に、CGPが排他的解法を進化させるために指数時間を必要とすることを示す負の結果も証明する。 共同で進化する実験は、我々の理論的な発見を補完する。 不完全トレーニングセットの使用は、優れた一般化を維持しながら、フィットネス評価の平均回数をさらに減少させる。

関連論文リスト

• Analysing the Influence of Reorder Strategies for Cartesian Genetic Programming [0.0]
  CGPで定義されるグラフのジェノタイプを並べ替える3つの新しい作用素を導入する。 そこで本研究では,CGPをリオーダー法で使用することにより,解が見つかるまでの反復数や適合度が向上することを示す。 しかし、最良のリオーダー演算子は存在しない。
  論文  参考訳（メタデータ） (2024-10-01T08:59:01Z)
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error [16.075339182916128]
  GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。 GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
  論文  参考訳（メタデータ） (2023-03-13T20:24:21Z)
• Neural Greedy Pursuit for Feature Selection [72.4121881681861]
  我々は,非線形予測問題に対する$P$入力機能のうち,$N$重要な特徴を選択するための欲求アルゴリズムを提案する。 ニューラルネットワークをアルゴリズムの予測子として使用し、損失を計算します。
  論文  参考訳（メタデータ） (2022-07-19T16:39:16Z)
• 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)
• Evolutionary Construction of Perfectly Balanced Boolean Functions [7.673465837624365]
  遺伝的プログラミング (GP) と遺伝的アルゴリズム (GA) を用いて, 特性, 完全均衡性, および優れた非線形性プロファイルを満たすブール関数を構築する。 意外なことに、重み付けされた表現を持つGAは、非常に非線形なWPB関数を見つける際に、古典的真理表表現型でGPより優れていた。
  論文  参考訳（メタデータ） (2022-02-16T18:03:04Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  本稿では、時間差学習(TD)による政策評価の世代的視点について考察する。 OS-GPTDアプローチは、状態-逆ペアのシーケンスを観測することにより、与えられたポリシーの値関数を推定するために開発された。 1つの固定カーネルに関連する限られた表現性を緩和するために、GP前の重み付けアンサンブル(E)を用いて代替のスキームを生成する。
  論文  参考訳（メタデータ） (2021-12-01T23:15:09Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Genetic Programming is Naturally Suited to Evolve Bagging Ensembles [0.0]
  適合度評価と選択の微妙な変化は、単純で従来のGPアルゴリズムを効率的に進化させるのに十分であることを示す。 我々のアルゴリズムは、最先端のアンサンブルと非アンサンブルGPアルゴリズムと非常によく比較できる。
  論文  参考訳（メタデータ） (2020-09-13T16:28:11Z)
• Obtaining Basic Algebra Formulas with Genetic Programming and Functional Rewriting [0.0]
  我々は、関数型プログラミングの書き直しを用いて、帰納的遺伝的プログラミングを促進する。 親はトーナメント選択機構に従って選択され、次の人口は定常的な戦略に従って取得される。 古典的遺伝プログラミングにおける)難題の集合において,本手法の性能を比較した。
  論文  参考訳（メタデータ） (2020-05-03T23:32:36Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  グラフ畳み込みニューラルネットワーク(GCN)は近年,グラフに基づく半教師付き半教師付き分類において有望な結果を示した。 グラフに基づく半教師付き学習のためのGCN(GPGC)を用いたGP回帰モデルを提案する。 GPGCを評価するための広範囲な実験を行い、他の最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-02-26T10:02:32Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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