論文の概要: Random is Faster than Systematic in Multi-Objective Local Search
- arxiv url: http://arxiv.org/abs/2601.06318v1
- Date: Fri, 09 Jan 2026 21:27:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-13 19:08:00.748873
- Title: Random is Faster than Systematic in Multi-Objective Local Search
- Title（参考訳）: 多目的局所探索におけるランダムは体系的よりも高速である
- Authors: Zimin Liang, Miqing Li,
- Abstract要約: 多目的局所探索アルゴリズムでは、これまでに見いだされた全ての非支配的なソリューションのアーカイブを維持するのが一般的である。
この過程における中心的な問題は、選択された解の近傍を探索する方法である。
ランダムサンプリング法は,多目的問題の範囲にわたる系統探索法よりも一貫して高速であることを示す。
- 参考スコア（独自算出の注目度）: 8.143459364469708
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Local search is a fundamental method in operations research and combinatorial optimisation. It has been widely applied to a variety of challenging problems, including multi-objective optimisation where multiple, often conflicting, objectives need to be simultaneously considered. In multi-objective local search algorithms, a common practice is to maintain an archive of all non-dominated solutions found so far, from which the algorithm iteratively samples a solution to explore its neighbourhood. A central issue in this process is how to explore the neighbourhood of a selected solution. In general, there are two main approaches: 1) systematic exploration and 2) random sampling. The former systematically explores the solution's neighbours until a stopping condition is met -- for example, when the neighbourhood is exhausted (i.e., the best improvement strategy) or once a better solution is found (i.e., first improvement). In contrast, the latter randomly selects and evaluates only one neighbour of the solution. One may think systematic exploration may be more efficient, as it prevents from revisiting the same neighbours multiple times. In this paper, however, we show that this may not be the case. We first empirically demonstrate that the random sampling method is consistently faster than the systematic exploration method across a range of multi-objective problems. We then give an intuitive explanation for this phenomenon using toy examples, showing that the superior performance of the random sampling method relies on the distribution of ``good neighbours''. Next, we show that the number of such neighbours follows a certain probability distribution during the search. Lastly, building on this distribution, we provide a theoretical insight for why random sampling is more efficient than systematic exploration, regardless of whether the best improvement or first improvement strategy is used.
- Abstract（参考訳）: 局所探索は操作研究と組合せ最適化の基本的な方法である。
それは、複数の、しばしば矛盾する、目的を同時に考慮する必要がある、多目的最適化など、様々な課題に広く適用されてきた。
多目的局所探索アルゴリズムでは、これまでに見いだされた全ての非支配的な解のアーカイブを維持することが一般的であり、そこからアルゴリズムは、その近傍を探索する解を反復的にサンプリングする。
この過程における中心的な問題は、選択された解の近傍を探索する方法である。
一般に、主なアプローチは2つある。
1【体系的な探究】
2)ランダムサンプリング。
前者は、停止状態が整うまで、例えば、近隣が枯渇している場合(すなわち、最高の改善戦略)や、より良い解が見つかるとき(すなわち、最初の改善戦略)に、ソリューションの隣人を体系的に探索する。
対照的に、後者は解の1つの近傍のみをランダムに選択し評価する。
体系的な探検は、同じ隣人を何度も再訪することを防ぐため、より効率的であると考えるかもしれない。
しかし,本論文では,そうでない可能性が示唆されている。
まず, ランダムサンプリング法は, 多目的問題の範囲にわたる系統探索法よりも一貫して高速であることを示す。
次に, おもちゃの例を用いて, この現象の直感的な説明を行い, 「良き隣人」の分布に依存するランダムサンプリング法の優れた性能を示す。
次に、これらの近傍の数は探索中にある確率分布に従うことを示す。
最後に, この分布に基づいて, ランダムサンプリングが系統探索よりも効率的である理由を理論的に考察する。
関連論文リスト
- A Review on Single-Problem Multi-Attempt Heuristic Optimization [6.778082328635129]
ある現実世界の最適化シナリオでは、実践者は複数の問題を解決することに関心がなく、単一の特定の問題に対する最良の解決策を見つけることに興味があります。
計算予算が候補解を評価するコストに対して大きい場合、同じ問題を解くために複数の選択肢を試すことができる。
次に試す選択肢のシーケンシャルな選択は、最良のソリューションを提供する選択肢を効率的に特定するために不可欠です。
論文 参考訳（メタデータ） (2025-09-30T14:28:28Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Dual-Directed Algorithm Design for Efficient Pure Exploration [9.728332815218181]
我々は、最良腕識別を超えたトップ2のアプローチを拡張する純粋探索問題のための新しい設計原理を開発する。
情報指向選択と組み合わせて、トップ2のトンプソンサンプリングがベストアーム識別に最適であることを示す。
また,しきい値と$varepsilon$-best-arm識別のための最適なアルゴリズムも作成する。
論文 参考訳（メタデータ） (2023-10-30T07:29:17Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳（メタデータ） (2023-10-19T13:57:38Z) - Fast Re-Optimization of LeadingOnes with Frequent Changes [0.9281671380673306]
Doerrらによって提案された再最適化アプローチは、問題インスタンスがより頻繁な変更の傾向にある場合に限界に達することを示す。
本稿では,前ベスト周辺における欲求探索と現在ベスト解を補間するアルゴリズムの修正を提案する。
論文 参考訳（メタデータ） (2022-09-09T16:51:41Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - A flexible outlier detector based on a topology given by graph
communities [0.0]
異常検出は機械学習手法と統計的予測モデルの最適性能に不可欠である。
トポロジーは、特徴空間内の互いに隣接する近傍を成す重み付きグラフのコミュニティを用いて計算される。
当社のアプローチは、ローカル戦略とグローバル戦略の両方において、複数のビュー設定と単一ビュー設定で総合的に優れています。
論文 参考訳（メタデータ） (2020-02-18T18:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。