論文の概要: Instance Space Analysis for the Car Sequencing Problem
- arxiv url: http://arxiv.org/abs/2012.10053v1
- Date: Fri, 18 Dec 2020 05:26:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-02 04:05:21.350299
- Title: Instance Space Analysis for the Car Sequencing Problem
- Title(参考訳): 車両シークエンシング問題の事例空間解析
- Authors: Yuan Sun, Samuel Esler, Dhananjay Thiruvady, Andreas T. Ernst,
Xiaodong Li and Kerri Morgan
- Abstract要約: インスタンスが解決しにくい特性について検討する。
カーシーケンシング問題を解決するための6つのアルゴリズムの性能を比較する。
その結果,新しいアルゴリズムは最先端であることがわかった。
- 参考スコア(独自算出の注目度): 4.822624702094427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we investigate an important research question in the car
sequencing problem, that is, what characteristics make an instance hard to
solve? To do so, we carry out an Instance Space Analysis for the car sequencing
problem, by extracting a vector of problem features to characterize an instance
and projecting feature vectors onto a two-dimensional space using principal
component analysis. The resulting two dimensional visualizations provide
insights into both the characteristics of the instances used for testing and to
compare how these affect different optimisation algorithms. This guides us in
constructing a new set of benchmark instances with a range of instance
properties. These are shown to be both more diverse than the previous
benchmarks and include many hard to solve instances. We systematically compare
the performance of six algorithms for solving the car sequencing problem. The
methods tested include three existing algorithms from the literature and three
new ones. Importantly, we build machine learning models to identify the niche
in the instance space that an algorithm is expected to perform well on. Our
results show that the new algorithms are state-of-the-art. This analysis helps
to understand problem hardness and select an appropriate algorithm for solving
a given car sequencing problem instance.
- Abstract(参考訳): 本稿では,カーシークエンシング問題における重要な研究課題,すなわち,どの特徴がインスタンスの解決を困難にしているのかを検討する。
そこで本研究では,問題特徴のベクトルを抽出してインスタンスを特徴付け,特徴ベクトルを主成分分析を用いて2次元空間に投影することにより,カーシークエンシング問題に対するインスタンス空間解析を行う。
結果として得られた2次元の可視化は、テストに使用されるインスタンスの特性と、これらが異なる最適化アルゴリズムにどのように影響するかを比較するための洞察を提供する。
これにより、さまざまなインスタンスプロパティを持つ新しいベンチマークインスタンスのセットを構築するのに役立ちます。
これらは以前のベンチマークよりも多様であることが示されており、解決の難しいインスタンスが多数含まれている。
カーシークエンシング問題を解くための6つのアルゴリズムの性能を系統的に比較する。
テストされた手法には、文献からの既存の3つのアルゴリズムと、3つの新しいアルゴリズムが含まれる。
重要なのは、アルゴリズムがうまく機能すると思われるインスタンス空間のニッチを特定するために、機械学習モデルを構築することです。
その結果,新しいアルゴリズムは最先端であることがわかった。
この分析は、問題の難易度を理解し、与えられたカーシーケンシング問題のインスタンスを解決する適切なアルゴリズムを選択するのに役立つ。
関連論文リスト
- A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - Learning Linear Models Using Distributed Iterative Hessian Sketching [4.567810220723372]
観測データから線形システムのマルコフパラメータを学習する問題を考察する。
Hessian-Sketchingに基づくランダムに分散されたニュートンアルゴリズムは、$epsilon$-optimal Solutionを生成可能であることを示す。
論文 参考訳(メタデータ) (2021-12-08T04:07:23Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。
私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
論文 参考訳(メタデータ) (2021-04-19T14:35:14Z) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。
次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
論文 参考訳(メタデータ) (2021-03-24T23:11:32Z) - Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。
ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文 参考訳(メタデータ) (2020-12-24T16:33:17Z) - Isometric Multi-Shape Matching [58.75590108535401]
形状間の対応を見つけることは、コンピュータビジョンとグラフィックスの基本的な問題である。
アイソメトリーは形状対応問題においてしばしば研究されるが、マルチマッチング環境では明確には考慮されていない。
定式化を解くのに適した最適化アルゴリズムを提案し,コンバージェンスと複雑性解析を提供する。
論文 参考訳(メタデータ) (2020-12-04T15:58:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。