論文の概要: Memetic algorithms for Spatial Partitioning problems
- arxiv url: http://arxiv.org/abs/2208.02867v1
- Date: Thu, 4 Aug 2022 20:05:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-08 12:04:55.672080
- Title: Memetic algorithms for Spatial Partitioning problems
- Title（参考訳）: 空間分割問題に対するmemeticアルゴリズム
- Authors: Subhodip Biswas, Fanglan Chen, Zhiqian Chen, Chang-Tien Lu and Naren
Ramakrishnan
- Abstract要約: 本稿では,実世界のデータセットにおける空間分割という,特定のタイプのSOPに焦点を当てる。
我々は,Swarm-based spatial memetic algorithm (SPATIAL) と呼ばれる単純だが効果的なアルゴリズムを提案し,それを校内限定問題(restricting problem)で検証した。
- 参考スコア（独自算出の注目度）: 26.73720392872553
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spatial optimization problems (SOPs) are characterized by spatial
relationships governing the decision variables, objectives, and/or constraint
functions. In this article, we focus on a specific type of SOP called spatial
partitioning, which is a combinatorial problem due to the presence of discrete
spatial units. Exact optimization methods do not scale with the size of the
problem, especially within practicable time limits. This motivated us to
develop population-based metaheuristics for solving such SOPs. However, the
search operators employed by these population-based methods are mostly designed
for real-parameter continuous optimization problems. For adapting these methods
to SOPs, we apply domain knowledge in designing spatially-aware search
operators for efficiently searching through the discrete search space while
preserving the spatial constraints. To this end, we put forward a simple yet
effective algorithm called swarm-based spatial memetic algorithm (SPATIAL) and
test it on the school (re)districting problem. Detailed experimental
investigations are performed on real-world datasets to evaluate the performance
of SPATIAL. Besides, ablation studies are performed to understand the role of
the individual components of SPATIAL. Additionally, we discuss how SPATIAL~is
helpful in the real-life planning process and its applicability to different
scenarios and motivate future research directions.
- Abstract（参考訳）: 空間最適化問題(SOP)は、決定変数、目的変数、および/または制約関数を管理する空間関係によって特徴づけられる。
本稿では、離散空間単位の存在による組合せ問題である空間分割と呼ばれる特定の種類のSOPに焦点を当てる。
厳密な最適化手法は問題のサイズ、特に実践可能な時間制限の範囲内ではスケールしない。
このようなSOPを解くために,人口ベースメタヒューリスティックスを開発する動機となった。
しかし、これらの人口ベース手法で用いられる探索演算子は、主に実パラメータ連続最適化問題のために設計されている。
これらの手法をSOPに適用するために、空間制約を保ちながら離散探索空間を効率的に探索する空間認識探索演算子の設計にドメイン知識を適用する。
そこで我々は,Swarm-based spatial memetic algorithm (SPATIAL) と呼ばれる単純だが効果的なアルゴリズムを提案し,それを校内(再制限)問題で検証した。
SPATIALの性能を評価するために,実世界のデータセットについて詳細な実験を行った。
また,SPATIALの個々の構成要素の役割を理解するためのアブレーション研究も行われている。
さらに,SPATIALが現実の計画プロセスにどのように役立つか,その異なるシナリオへの適用性について論じ,今後の研究方向性を示唆する。
関連論文リスト
- Reclaiming the Source of Programmatic Policies: Programmatic versus Latent Spaces [10.654876600946865]
プログラム空間は、潜在空間で観測されたような行動損失の値を示す。
プログラム空間で探索するアルゴリズムは、LEAPSやHPRLよりも大幅に優れている。
論文 参考訳（メタデータ） (2024-10-16T02:10:04Z) - On Probabilistic Embeddings in Optimal Dimension Reduction [1.2085509610251701]
次元減少アルゴリズムは多くのデータサイエンスパイプラインの重要な部分である。
広く利用されているにもかかわらず、多くの非線形次元還元アルゴリズムは理論的観点からは理解されていない。
論文 参考訳（メタデータ） (2024-08-05T12:46:21Z) - Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。
我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-13T12:24:54Z) - AI planning in the imagination: High-level planning on learned abstract
search spaces [68.75684174531962]
我々は,エージェントが訓練中に学習する抽象的な検索空間において,エージェントが計画することを可能にする,PiZeroと呼ばれる新しい手法を提案する。
本研究では,旅行セールスマン問題,ソコバン問題,2048年,施設立地問題,パックマン問題など,複数の分野で評価を行った。
論文 参考訳（メタデータ） (2023-08-16T22:47:16Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Efficient Sensor Placement from Regression with Sparse Gaussian Processes in Continuous and Discrete Spaces [3.729242965449096]
センサ配置問題は、相関現象を監視する際に発生する一般的な問題である。
本稿では,勾配降下法を用いて最適化可能な変分近似に基づくSP問題に対する新しい定式化を提案する。
論文 参考訳（メタデータ） (2023-02-28T19:10:12Z) - Region-Based Semantic Factorization in GANs [67.90498535507106]
本稿では,任意の画像領域についてGAN(Generative Adversarial Networks)が学習した潜在意味を分解するアルゴリズムを提案する。
適切に定義された一般化されたレイリー商を通して、アノテーションや訓練なしにそのような問題を解く。
様々な最先端のGANモデルに対する実験結果から,本手法の有効性が示された。
論文 参考訳（メタデータ） (2022-02-19T17:46:02Z) - Learning Space Partitions for Path Planning [54.475949279050596]
PlaLaMは2次元ナビゲーションタスクにおける既存の経路計画手法よりも優れており、特に難解な局所最適化の存在下では優れている。
これらは高マルチモーダルな実世界のタスクに移行し、コンパイラフェーズでは最大245%、分子設計では最大0.4の強いベースラインを0-1スケールで上回ります。
論文 参考訳（メタデータ） (2021-06-19T18:06:11Z) - Spatio-temporal Sequence Prediction with Point Processes and
Self-organizing Decision Trees [0.0]
分割時間予測問題に対して,ポイントプロセスに基づく予測アルゴリズムを導入する。
本アルゴリズムは,勾配に基づく最適化手法により,これらの領域間の空間事象と相互作用を共同で学習することができる。
当社のアプローチと最先端のディープラーニングベースのアプローチを比較して,大幅なパフォーマンス向上を実現しています。
論文 参考訳（メタデータ） (2020-06-25T14:04:55Z) - Localized active learning of Gaussian process state space models [63.97366815968177]
多くの共通制御アプリケーションにおいて、優れた性能を達成するためには、グローバルに正確なモデルを必要としない。
本稿では,状態-作用空間の有界部分集合上の正確なモデルを得ることを目的としたガウス過程状態空間モデルに対する能動的学習戦略を提案する。
モデル予測制御を用いることで、探索中に収集した情報を統合し、探索戦略を適応的に改善する。
論文 参考訳（メタデータ） (2020-05-04T05:35:02Z) - Discrete Action On-Policy Learning with Action-Value Critic [72.20609919995086]
離散的な行動空間における強化学習(RL)は、実世界の応用では至るところで行われているが、その複雑さは行動空間次元とともに指数関数的に増大する。
我々は,行動値関数を推定し,相関行動に適用し,これらの評価値を組み合わせて勾配推定の分散を制御する。
これらの取り組みにより、分散制御技術に頼って、関連するRLアルゴリズムを実証的に上回る、新たな離散的なRLアルゴリズムが実現される。
論文 参考訳（メタデータ） (2020-02-10T04:23:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。