論文の概要: Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions
- arxiv url: http://arxiv.org/abs/2202.08743v1
- Date: Thu, 17 Feb 2022 16:33:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 12:49:44.597778
- Title: Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions
- Title(参考訳): 平衡・高非線形ブール関数の進化構成
- Authors: Claude Carlet, Marko Djurasevic, Domagoj Jakobovic, Luca Mariot,
Stjepan Picek
- Abstract要約: 遺伝的プログラミングは、高い非線形性を持つバランスの取れたブール関数をもたらす構造を進化させることができることを示す。
以上の結果から,GP はよく一般化される構造,すなわち,複数のテストサイズに必要な関数を見つけることができることがわかった。
興味深いことに、GPによって発見された最も単純な解は、よく知られた間接和構成の特別な場合である。
- 参考スコア(独自算出の注目度): 37.84234862910533
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding balanced, highly nonlinear Boolean functions is a difficult problem
where it is not known what nonlinearity values are possible to be reached in
general. At the same time, evolutionary computation is successfully used to
evolve specific Boolean function instances, but the approach cannot easily
scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean
functions is almost trivial, larger sizes become increasingly difficult, and
evolutionary algorithms perform suboptimally. In this work, we ask whether
genetic programming (GP) can evolve constructions resulting in balanced Boolean
functions with high nonlinearity. This question is especially interesting as
there are only a few known such constructions. Our results show that GP can
find constructions that generalize well, i.e., result in the required functions
for multiple tested sizes. Further, we show that GP evolves many equivalent
constructions under different syntactic representations. Interestingly, the
simplest solution found by GP is a particular case of the well-known indirect
sum construction.
- Abstract(参考訳): バランスの取れた高非線形ブール関数を見つけることは、一般にどの非線形値に到達できるかがわからないという難しい問題である。
同時に、進化的計算は特定のブール関数インスタンスの進化に成功しているが、より大きなブール関数サイズに対して容易にスケールできない。
実際、より小さなブール関数の進化はほぼ自明であるが、より大きなサイズはますます難しくなり、進化的アルゴリズムは亜最適に機能する。
本研究では,遺伝的プログラミング (gp) が高非線形性を持つブール関数のバランスを保った構成を進化させるかどうかを問う。
特に興味深いのは、そのような構成はごくわずかしか知られていないことである。
以上の結果から,GP はよく一般化される構造,すなわち,複数のテストサイズに必要な関数を見つけることができることがわかった。
さらに、GPは異なる構文表現の下で多くの等価な構成を進化させることを示す。
興味深いことに、GPによって発見された最も単純な解は、よく知られた間接和構成の特別な場合である。
関連論文リスト
- Degree is Important: On Evolving Homogeneous Boolean Functions [32.90791284928444]
本稿では,等質屈曲ブール関数の設計における進化的アルゴリズムの利用について検討する。
EAは2次等質な等質な曲がり関数を見つけることができるが、どちらのアプローチも立方等質な等質曲がり関数は見つからない。
論文 参考訳(メタデータ) (2025-01-30T15:04:14Z) - A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions
in Odd Sizes [35.305121158674964]
奇サイズの高非線形ブール関数の進化問題を考察する。
最適解を見つけることは、最小のテストサイズを除いて不可能である。
非線形性241の9つの入力にブール関数を求める。
論文 参考訳(メタデータ) (2024-02-15T13:39:34Z) - A New Angle: On Evolving Rotation Symmetric Boolean Functions [32.90791284928444]
本稿では、いくつかの進化的アルゴリズムを用いて、異なる性質を持つ回転対称ブール関数を進化させる。
驚いたことに、ビットストリングと浮動小数点エンコーディングはツリーエンコーディングよりもうまく機能している。
論文 参考訳(メタデータ) (2023-11-20T16:16:45Z) - Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean
Functions [8.382710169577447]
ビットストリング符号化における遺伝的演算子の非線形性を最適化する効果について検討する。
オペレータが提供できる可能性のある変更の範囲を観察することで、この情報を使用して、より効果的な遺伝子操作子の組み合わせを設計することができる。
論文 参考訳(メタデータ) (2023-02-12T10:34:01Z) - Evolutionary Construction of Perfectly Balanced Boolean Functions [7.673465837624365]
遺伝的プログラミング (GP) と遺伝的アルゴリズム (GA) を用いて, 特性, 完全均衡性, および優れた非線形性プロファイルを満たすブール関数を構築する。
意外なことに、重み付けされた表現を持つGAは、非常に非線形なWPB関数を見つける際に、古典的真理表表現型でGPより優れていた。
論文 参考訳(メタデータ) (2022-02-16T18:03:04Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z) - 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) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z) - The data-driven physical-based equations discovery using evolutionary
approach [77.34726150561087]
与えられた観測データから数学的方程式を発見するアルゴリズムについて述べる。
このアルゴリズムは遺伝的プログラミングとスパース回帰を組み合わせたものである。
解析方程式の発見や偏微分方程式(PDE)の発見にも用いられる。
論文 参考訳(メタデータ) (2020-04-03T17:21:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。