論文の概要: Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity

• arxiv url: http://arxiv.org/abs/2604.17342v1
• Date: Sun, 19 Apr 2026 09:30:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 21:52:52.476604
• Title: Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity
• Title（参考訳）: モノトンだが励起:高い非線形性を持つモノトンブール関数の進化について
• Authors: Claude Carlet, Marko Čupić, Marko Ðurasevic, Domagoj Jakobovic, Luca Mariot, Stjepan Picek,
• Abstract要約: 進化的計算が高非線形性を持つ単調ブール関数を進化させるかどうかを考察する。 本稿では,標準真理表表現,ハミング重みを保存するバランスのとれた真理表符号化,木に基づく遺伝的プログラム表現の3つの解法について考察する。
• 参考スコア（独自算出の注目度）: 24.351129616050844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, both in the balanced and imbalanced settings. We consider three solution encodings: the standard truth table representation, a balanced truth table encoding that preserves Hamming weight, and a symbolic tree-based genetic programming representation. To guide the search toward monotone increasing functions, we introduce a non-monotonicity penalty and combine it with fitness functions targeting balancedness and nonlinearity. Experimental results are reported for dimensions from $n=5$ to $n=14$. The results show that evolutionary search can discover monotone Boolean functions with nonlinearities clearly exceeding those of majority functions, and in several cases approaching the best currently known values for monotone functions. At the same time, the experiments reveal substantial differences between encodings: the balanced truth table encoding performs poorly for larger dimensions, while the standard truth table and genetic programming encodings remain competitive, with genetic programming becoming especially relevant in the largest tested dimensions.
• Abstract（参考訳）: モノトンブール函数は構造的に重要なブール函数のクラスであるが、その制限形式は達成可能な非線形性に強い制限を与える。 本稿では,高非線形性を有するモノトンブール関数を,バランスの取れた状態と不均衡な状態の両方において,進化的計算が進化させるかどうかを考察する。 本稿では,標準真理表表現,ハミング重みを保存するバランスのとれた真理表符号化,木に基づく遺伝的プログラム表現の3つの解法について考察する。 非単調性ペナルティを導入し、バランス性や非線形性を目標としたフィットネス機能と組み合わせる。 実験結果は、$n=5$から$n=14$までの範囲で報告される。 この結果から, 非線形性を持つ単調ブール関数は, 多数関数よりも明らかに優れており, 幾つかの場合において, 単調関数の既知値に最も近い値に近づいた。 バランスのとれた真理表エンコーディングは大きな次元では性能が悪く、一方、標準的な真理表エンコーディングと遺伝的プログラミングエンコーディングは競争力を維持し、最大のテスト次元では遺伝的プログラミングが特に重要となる。

関連論文リスト

• IDEM Enough? Evolving Highly Nonlinear Idempotent Boolean Functions [25.80284220818612]
  Idempotent Boolean関数は暗号設計の候補として魅力的である。 軌道上の真理表を符号化することで、イデオポテンスを強制できることが示される。 次に、軌道上の真理表を符号化することで、イデオポテンスを強制できることを示し、異なる赤道軌道の数に匹敵する大きさのコンパクトなゲノムを生成する。
  論文  参考訳（メタデータ） (2026-01-31T18:06:38Z)
• On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach [60.00535100780336]
  本稿では, 等質屈曲ブール関数の進化における進化的アルゴリズム(EA)の利用について検討する。 等質な曲がり関数の密度の概念を導入し、異なる変数数の2次および3次曲がり関数を見つけるアルゴリズム設計を容易にする。
  論文  参考訳（メタデータ） (2025-11-16T15:33:40Z)
• A Systematic Study on the Design of Odd-Sized Highly Nonlinear Boolean Functions via Evolutionary Algorithms [32.90791284928444]
  遺伝的プログラミングは一般的に他の進化的アルゴリズムよりも優れていることを示す。 ビットストリングを符号化した対称遺伝的アルゴリズムは、非線形性241で9ドル可変ブール関数を進化させることを示す。
  論文  参考訳（メタデータ） (2025-04-24T15:35:53Z)
• Degree is Important: On Evolving Homogeneous Boolean Functions [32.90791284928444]
  本稿では,等質屈曲ブール関数の設計における進化的アルゴリズムの利用について検討する。 EAは2次等質な等質な曲がり関数を見つけることができるが、どちらのアプローチも立方等質な等質曲がり関数は見つからない。
  論文  参考訳（メタデータ） (2025-01-30T15:04:14Z)
• Range, not Independence, Drives Modularity in Biologically Inspired Representations [52.48094670415497]
  我々は、生物学的にインスピレーションを受けたネットワークが、ソース変数(ソース)の表現をモジュール化する理論を開発する。 我々は、最適な線形オートエンコーダのニューロンがモジュラー化するかどうかを決定するソースのサンプルに対して、必要かつ十分な条件を導出する。 我々の理論はどんなデータセットにも当てはまり、以前の研究で研究された統計的な独立性よりもはるかに長い。
  論文  参考訳（メタデータ） (2024-10-08T17:41:37Z)
• Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions [37.84234862910533]
  遺伝的プログラミングは、高い非線形性を持つバランスの取れたブール関数をもたらす構造を進化させることができることを示す。 以上の結果から,GP はよく一般化される構造,すなわち,複数のテストサイズに必要な関数を見つけることができることがわかった。 興味深いことに、GPによって発見された最も単純な解は、よく知られた間接和構成の特別な場合である。
  論文  参考訳（メタデータ） (2022-02-17T16:33:24Z)
• Evolutionary Construction of Perfectly Balanced Boolean Functions [7.673465837624365]
  遺伝的プログラミング (GP) と遺伝的アルゴリズム (GA) を用いて, 特性, 完全均衡性, および優れた非線形性プロファイルを満たすブール関数を構築する。 意外なことに、重み付けされた表現を持つGAは、非常に非線形なWPB関数を見つける際に、古典的真理表表現型でGPより優れていた。
  論文  参考訳（メタデータ） (2022-02-16T18:03:04Z)
• Exact Hard Monotonic Attention for Character-Level Transduction [76.66797368985453]
  非単調なソフトアテンションを用いたニューラルシークエンス・ツー・シーケンスモデルは、しばしば一般的な単調モデルよりも優れていることを示す。 我々は、厳密な単調性を強制し、トランスデューサの学習中に協調して潜時アライメントを学習するハードアテンションシーケンス・ツー・シーケンス・モデルを開発した。
  論文  参考訳（メタデータ） (2019-05-15T17:51:09Z)

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

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