論文の概要: Quadratic speedup of global search using a biased crossover of two good solutions

• arxiv url: http://arxiv.org/abs/2111.07680v1
• Date: Mon, 15 Nov 2021 11:25:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-16 17:50:22.952638
• Title: Quadratic speedup of global search using a biased crossover of two good solutions
• Title（参考訳）: 2つの良い解のバイアス付きクロスオーバーを用いたグローバルサーチの2次高速化
• Authors: Takuya Isomura
• Abstract要約: この研究は、高次元離散状態空間の下で定義されるコスト関数のクラスに対して、近似大域最小値を特定するための計算コストを解析的に表現する。 計算コストを最小化する最適なグローバル検索方式を導出する。 提案手法の単純な計算アーキテクチャと最小の計算コストは、生物やニューロモルフィックハードウェアにとって非常に望ましい。
• 参考スコア（独自算出の注目度）: 1.14219428942199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The minimisation of cost functions is crucial in various optimisation fields. However, identifying their global minimum remains challenging owing to the huge computational cost incurred. This work analytically expresses the computational cost to identify an approximate global minimum for a class of cost functions defined under a high-dimensional discrete state space. Then, we derive an optimal global search scheme that minimises the computational cost. Mathematical analyses demonstrate that a combination of the gradient descent algorithm and the selection and crossover algorithm--with a biased crossover weight--maximises the search efficacy. Remarkably, its computational cost is of the square root order in contrast to that of the conventional gradient descent algorithms, indicating a quadratic speedup of global search. We corroborate this proposition using numerical analyses of the travelling salesman problem. The simple computational architecture and minimal computational cost of the proposed scheme are highly desirable for biological organisms and neuromorphic hardware.
• Abstract（参考訳）: コスト関数の最小化は様々な最適化分野において不可欠である。 しかし、計算コストが膨大であるため、グローバルな最小値の特定は依然として困難である。 この研究は、高次元離散状態空間の下で定義されるコスト関数のクラスに対して、近似大域最小値を特定するための計算コストを解析的に表現する。 そこで,計算コストを最小限に抑える最適なグローバル検索手法を提案する。 数学的解析により、勾配降下アルゴリズムと選択とクロスオーバーアルゴリズムの組み合わせが、偏りのあるクロスオーバー重みによって探索効率を最大化することを示した。 驚くべきことに、計算コストは従来の勾配降下アルゴリズムとは対照的に平方根次であり、大域探索の二次的な高速化を示している。 我々は,旅行セールスマン問題の数値解析を用いて,この提案を裏付ける。 提案手法の単純な計算アーキテクチャと最小計算コストは生物や神経形態学のハードウェアにとって非常に望ましい。

関連論文リスト

• Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization [6.896308995955336]
  グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。 本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
  論文  参考訳（メタデータ） (2023-12-06T01:16:10Z)
• Speeding-up Evolutionary Algorithms to solve Black-Box Optimization Problems [0.0]
  集団ベースの進化的アルゴリズムは計算コストの高いブラックボックス最適化問題にアプローチする際によく考慮される。 最適化アルゴリズムの実行時に適切な近似関数コストを選択する技術を提案する。 提案手法は, 解が適切にランク付けされている場合の最小評価コストを推定し, 精度の低下を最小限に抑えながら, 同一時間でより多くの評価を計算できることを示した。
  論文  参考訳（メタデータ） (2023-09-23T11:54:46Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• How to escape sharp minima with random perturbations [48.095392390925745]
  平らなミニマの概念とそれらを見つける複雑さについて研究する。 一般的なコスト関数に対して、近似平坦な局所最小値を求める勾配に基づくアルゴリズムについて論じる。 コスト関数がトレーニングデータよりも経験的リスクであるような環境では、シャープネス認識最小化と呼ばれる最近提案された実用的なアルゴリズムにインスパイアされたより高速なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-25T02:12:33Z)
• Fighting the curse of dimensionality: A machine learning approach to finding global optima [77.34726150561087]
  本稿では,構造最適化問題におけるグローバル最適化の方法を示す。 特定のコスト関数を利用することで、最適化手順が確立された場合と比較して、グローバルをベストに得るか、最悪の場合、優れた結果を得るかのどちらかを得る。
  論文  参考訳（メタデータ） (2021-10-28T09:50:29Z)
• A Granular Sieving Algorithm for Deterministic Global Optimization [6.01919376499018]
  リプシッツ連続関数に対する大域的最適化問題を解くために、勾配のない決定論的手法を開発した。 この方法は、目的関数の領域と範囲の両方で同期解析を行うグラニュラーシービングとみなすことができる。
  論文  参考訳（メタデータ） (2021-07-14T10:03:03Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)

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

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