論文の概要: A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures
- arxiv url: http://arxiv.org/abs/2608.08898v1
- Date: Sun, 09 Aug 2026 20:19:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:36.989908
- Title: A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures
- Title（参考訳）: プログラム表現と複雑度対策を用いた最適化問題評価のための新しいアプローチ
- Abstract要約: 本稿では,プログラムとして実装されたインスタンスの表現に基づく問題特徴化手法を提案する。
我々はHalsteadボリュームを,プログラムのエントロピーを単純化したバージョンと見なすことのできる,コードの複雑さの尺度とみなす。
提案手法は,アルゴリズム性能と負の相関性を示し,アルゴリズム選択や他の問題解析のための予測メタ機能としての可能性を示す。
- 参考スコア（独自算出の注目度）: 0.8422257363944294
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Characterising optimisation problem instances is a fundamental part of understanding the behaviour and performance of different algorithms as well as providing information for algorithm selection and configuration. In this paper we propose a novel approach to problem characterisation based on the representation of instances when implemented as a program. The intuition is that the complexity of the code required to express an objective function should relate to the complexity of the search landscape. We identify the Halstead volume as a measure of code complexity, which can be seen as a simplified version of the entropy of the program. Given a code implementation of the objective function, the Halstead volume and entropy can be quickly calculated using existing libraries. We apply the proposed complexity measures to the well-known BBOB optimisation problem suite and the simple feed-forward neural network training task. We also show that the measures are negatively correlated with algorithm performance and therefore show potential as predictive meta-features for algorithm selection and other problem analysis. We envisage the proposed measures as complementary to other problem characterisation approaches, but with the advantages of not requiring any sampling of the search space, being invariant to transformations, and being very quick to calculate automatically.
- Abstract（参考訳）: 最適化問題インスタンスの特徴付けは、アルゴリズムの選択と設定のための情報を提供するだけでなく、異なるアルゴリズムの振る舞いとパフォーマンスを理解する基本的な部分である。
本稿では,プログラムとして実装されたインスタンスの表現に基づく問題特徴化手法を提案する。
目的関数を表現するのに必要なコードの複雑さは、検索ランドスケープの複雑さに関係しているはずだ、という直感である。
我々はHalsteadボリュームを,プログラムのエントロピーを単純化したバージョンと見なすことのできる,コードの複雑さの尺度とみなす。
目的関数のコード実装を考えると、Halsteadボリュームとエントロピーは既存のライブラリを使って素早く計算できる。
提案手法をBBOB最適化問題スイートと単純なフィードフォワードニューラルネットワークトレーニングタスクに適用する。
また,提案手法はアルゴリズム性能と負の相関を示し,アルゴリズム選択や他の問題解析のための予測メタ機能としての可能性を示す。
提案手法は, 探索空間のサンプリングを一切必要とせず, 変換に不変であり, 自動的に計算できるという利点がある。
関連論文リスト
- Optimal Centered Active Excitation in Linear System Identification [48.09783075634403]
最適中心雑音励振を用いた線形システム同定のための能動学習アルゴリズムを提案する。
まず、任意の能動学習アルゴリズムに対して、所定の精度と信頼レベルを達成するために、サンプルの複雑さの低い境界を確立する。
論文 参考訳（メタデータ） (2026-04-07T07:16:16Z) - Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints [0.0]
変分不等式は、生成的敵ネットワーク、強化学習、敵対的訓練、生成モデルなど、機械学習研究において重要な役割を果たしている。
本稿では,反復における関数的制約の値に応じて,生産的ステップと非生産的ステップを切り替えるミラー降下型アルゴリズムを提案する。
有界および単調な作用素やリプシッツ凸関数的制約のある問題に対して、それらの最適収束率を所望の精度で解を達成するために証明する。
論文 参考訳（メタデータ） (2026-02-24T18:56:00Z) - Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation [27.378185644892984]
本稿では,Large Language Models (LLM) をアルゴリズム選択に導入する。
LLMはアルゴリズムの構造的・意味的な側面を捉えるだけでなく、文脈的認識とライブラリ機能理解も示している。
選択されたアルゴリズムは、与えられた問題と異なるアルゴリズムの一致度によって決定される。
論文 参考訳（メタデータ） (2023-11-22T06:23:18Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Algorithm Instance Footprint: Separating Easily Solvable and Challenging
Problem Instances [0.7046417074932257]
ブラックボックス最適化では、アルゴリズムインスタンスが問題インスタンスのセットで動作し、他のインスタンスにフェールする理由を理解することが不可欠である。
本稿では,解き易い問題インスタンスの集合と解き易い問題インスタンスの集合からなるアルゴリズムインスタンスフットプリントの定式化手法を提案する。
論文 参考訳（メタデータ） (2023-06-01T09:28:06Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。
提案手法は, 目的関数の断片的なアフィンサロゲートを, 実現可能なサンプル上に構築することに基づいている。
この2つのアルゴリズムは、制約なしおよび制約付き混合変数ベンチマーク問題に対して評価される。
論文 参考訳（メタデータ） (2023-02-09T15:04:35Z) - Self-adaptive algorithms for quasiconvex programming and applications to
machine learning [0.0]
凸線探索技術や,軽微な仮定の下での汎用的アプローチを含まない,自己適応的なステップサイズ戦略を提案する。
提案手法は,いくつかの計算例から予備的な結果によって検証される。
大規模問題に対する提案手法の有効性を実証するため,機械学習実験に適用した。
論文 参考訳（メタデータ） (2022-12-13T05:30:29Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Activation Relaxation: A Local Dynamical Approximation to
Backpropagation in the Brain [62.997667081978825]
活性化緩和(AR)は、バックプロパゲーション勾配を力学系の平衡点として構成することで動機付けられる。
我々のアルゴリズムは、正しいバックプロパゲーション勾配に迅速かつ堅牢に収束し、単一のタイプの計算単位しか必要とせず、任意の計算グラフで操作できる。
論文 参考訳（メタデータ） (2020-09-11T11:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。