論文の概要: Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup
- arxiv url: http://arxiv.org/abs/2611.16013v1
- Date: Wed, 11 Nov 2026 21:13:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.274335
- Title: Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup
- Title(参考訳): Max上でのモンテカルロ遺伝的プログラミングの実行時解析--指数的高速化の証明
- Abstract要約: 本稿では,最適プログラム長$n$のランタイムスーパーリニアを持つ TGP に対して,厳密に研究されている Max 問題に対する CGP の解析を行う。
1$+$1$)CGPが、同じ出力の等価な最適値を進化させるために共通の突然変異演算子を用いるという期待時間は、$n$で、特に$O(log9n)$である。
我々の結果は、プログラムのグラフベース表現の利点とコンパクトさ、およびCGPがその探索とフィットネス空間をナビゲートする方法に光を当てた。
- 参考スコア(独自算出の注目度): 5.276232626689568
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length $n$. We prove that the expected time for the ($1$+$1$)~CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in $n$, specifically at most $O(\log^9{n})$. This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.
- Abstract(参考訳): 遺伝的プログラミング(GP、英: Genetic Programming)は、表現、関数、コンピュータプログラムの自動発見のための自然進化から着想を得た探索パラダイムである。
カルテシアンGP (CGP) は、従来のツリーベースGP (TGP) とは対照的に、グラフベースのモデルを用いて候補プログラムを符号化するGPのフレーバーである。
20年前の開始以来、CGPは主に実験的に分析されてきたため、その理論的性能保証についてはほとんど知られていない。
本稿では,最適プログラム長$n$のランタイムスーパーリニアを持つ TGP に対して,厳密に研究されている Max 問題に対する CGP の解析を行う。
1$+$1$)~CGPが共通突然変異演算子を用いて同じ出力の等価な最適値を進化させる期待時間は、少なくとも$O(\log^9{n})$において、$n$の多元対数であることが証明されている。
これは、CGPに切り替えることによる指数的なスピードアップを示すため、驚くべきことである。
その結果、プログラムのグラフベース表現の利点とコンパクト性、CGPが探索空間やフィットネス空間を効率的にナビゲートする方法が明らかになった。
これは、確立されたベンチマーク問題におけるCGPの性能保証として初めて証明されたものである。
実験は理論的な結果を補完する。
関連論文リスト
- Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions [5.276232626689568]
我々は、CGPの適合度評価の期待値に対して、$O(n D5)$を有界に証明し、$n$入力の結合を構成する。
また、CGPが排他的解離を進化させるために指数時間を必要とすることを示す負の結果も証明する。
論文 参考訳(メタデータ) (2026-06-14T16:58:26Z) - Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration [9.421242935448722]
木に基づく遺伝的プログラミング(TGP)は、記号回帰、分類、ロボット制御などのタスクに広く用いられている進化的計算アルゴリズムである。
EvoGPは、TGPのGPUアクセラレーションに適した高性能なフレームワークである。
論文 参考訳(メタデータ) (2025-01-21T07:42:54Z) - Interactive Segmentation as Gaussian Process Classification [58.44673380545409]
クリックベースのインタラクティブセグメンテーション(IS)は、ユーザインタラクション下で対象オブジェクトを抽出することを目的としている。
現在のディープラーニング(DL)ベースの手法のほとんどは、主にセマンティックセグメンテーションの一般的なパイプラインに従っている。
本稿では,各画像上でガウス過程(GP)に基づく画素単位のバイナリ分類モデルとしてISタスクを定式化することを提案する。
論文 参考訳(メタデータ) (2023-02-28T14:01:01Z) - Scaling Gaussian Process Optimization by Evaluating a Few Unique
Candidates Multiple Times [119.41129787351092]
GPに基づく逐次ブラックボックス最適化は,複数の評価ステップの候補解に固執することで効率よく行うことができることを示す。
GP-UCB と GP-EI の2つのよく確立されたGP-Opt アルゴリズムを改良し,バッチ化された GP-Opt の規則を適応させる。
論文 参考訳(メタデータ) (2022-01-30T20:42:14Z) - Non-Gaussian Gaussian Processes for Few-Shot Regression [71.33730039795921]
乱変数ベクトルの各成分上で動作し,パラメータを全て共有する可逆なODEベースのマッピングを提案する。
NGGPは、様々なベンチマークとアプリケーションに対する競合する最先端のアプローチよりも優れています。
論文 参考訳(メタデータ) (2021-10-26T10:45:25Z) - Incremental Ensemble Gaussian Processes [53.3291389385672]
本稿では,EGPメタラーナーがGP学習者のインクリメンタルアンサンブル(IE-) GPフレームワークを提案し,それぞれが所定のカーネル辞書に属するユニークなカーネルを持つ。
各GP専門家は、ランダムな特徴ベースの近似を利用してオンライン予測とモデル更新を行い、そのスケーラビリティを生かし、EGPメタラーナーはデータ適応重みを生かし、熟練者ごとの予測を合成する。
新たなIE-GPは、EGPメタラーナーおよび各GP学習者内における構造化力学をモデル化することにより、時間変化関数に対応するように一般化される。
論文 参考訳(メタデータ) (2021-10-13T15:11:25Z) - Using Traceless Genetic Programming for Solving Multiobjective
Optimization Problems [1.9493449206135294]
トレーレス・ジェネティック・プログラミング(Traceless Genetic Programming、TGP)は、プログラム自体よりもプログラムの出力に焦点をあてる場合に使われる遺伝的プログラミング(GP)の変種である。
TGPと組み合わせて2つの遺伝子操作子(クロスオーバーと挿入)が使用される。
数値実験により、TGPは非常に高速かつ十分に検討されたテスト問題を解くことができることが示された。
論文 参考訳(メタデータ) (2021-10-07T05:55:55Z) - GSGP-CUDA -- a CUDA framework for Geometric Semantic Genetic Programming [2.275405513780208]
Geometric Semantic Genetic Programming (GSGP) は進化計算に基づく最先端の機械学習手法である。
C++におけるGSGPの効率的な実装は、この事実を悪用するが、その潜在能力は十分ではない。
結果は、最先端のシーケンシャル実装と比較して1000倍以上のスピードアップを示す。
論文 参考訳(メタデータ) (2021-06-08T00:58:39Z) - Speed Benchmarking of Genetic Programming Frameworks [1.1470070927586016]
遺伝的プログラミング(GP)は、設計による計算コストの負担に悩まされていることが知られている。
本研究では,ベクトル化および反復的実装手法の性能と進化性を比較するために,一連のベンチマークを用いている。
論文 参考訳(メタデータ) (2021-05-25T22:06:42Z) - Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning
via Gaussian Processes [144.6048446370369]
グラフ畳み込みニューラルネットワーク(GCN)は近年,グラフに基づく半教師付き半教師付き分類において有望な結果を示した。
グラフに基づく半教師付き学習のためのGCN(GPGC)を用いたGP回帰モデルを提案する。
GPGCを評価するための広範囲な実験を行い、他の最先端手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2020-02-26T10:02:32Z) - Near-linear Time Gaussian Process Optimization with Adaptive Batching
and Resparsification [119.41129787351092]
BBKBは非回帰GP最適化アルゴリズムで、ほぼ直線的に実行し、バッチで候補を選択する。
また,同じバウンダリを用いて,スパルスGP近似の更新コストを適応的に遅延させることで,ステップ毎の償却コストをほぼ一定に抑えることができることを示した。
論文 参考訳(メタデータ) (2020-02-23T17:43:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。