Jove
Visualize
お問い合わせ
JoVE
x logofacebook logolinkedin logoyoutube logo
JoVEについて
概要リーダーシップブログJoVEヘルプセンター
著者向け
出版プロセス編集委員会範囲と方針査読よくある質問投稿
図書館員向け
推薦の声購読アクセスリソース図書館諮問委員会よくある質問
研究
JoVE JournalMethods CollectionsJoVE Encyclopedia of Experimentsアーカイブ
教育
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab Manual教員リソースセンター教員サイト
利用規約
プライバシーポリシー
ポリシー

関連する実験動画

コンビネトリアル最適化における批判性と並列性

W G Macready1, A G Siapas, S A Kauffman

  • 1Santa Fe Institute, NM 87501, USA.

Science (New York, N.Y.)
|January 5, 1996
PubMed
まとめ

最適化問題のローカル検索の並列化は,ある程度までパフォーマンスを改善しますが,その後,性能は著しく低下します. この研究は,スピン・グラス・モデルと旅商人問題におけるこの移行を実証しています.

関連する実験動画

関連する概念動画

こちらも読む

関連記事

共著者、ジャーナル、引用グラフによってこの研究に関連する記事。

並び替え
Same author

Extrinsic and intrinsic effects setting viscosity in complex fluids and life processes: the role of fundamental physical constants.

The European physical journal. E, Soft matter·2025
Same author

Mixed anhydrides at the intersection between peptide and RNA autocatalytic sets: evolution of biological coding.

Interface focus·2023
Same author

Robustness analysis of a Boolean model of gene regulatory network with memory.

Journal of computational biology : a journal of computational molecular cell biology·2011
Same author

Cell-cell interaction and diversity of emergent behaviours.

IET systems biology·2011
Same author

Phase transition in a class of nonlinear random networks.

Physical review. E, Statistical, nonlinear, and soft matter physics·2010
Same author

On the dynamics of random Boolean networks subject to noise: attractors, ergodic sets and cell types.

Journal of theoretical biology·2010

科学分野:

  • 計算の複雑さ 計算の複雑さ
  • 最適化アルゴリズムの最適化について
  • 統計物理学 統計物理学とは

背景:

  • ローカル検索方法は,大規模な組み合わせ最適化に有効です.
  • これらのメソッドの並列化は,当初,パフォーマンスを向上させます.
  • 性能が劇的に低下する臨界点が存在します.

研究 の 目的:

  • パラレルローカル検索の性能低下を調査する.
  • オプティマイゼーションパフォーマンスの移行点を特定するために.
  • この現象の根本的なメカニズムを分析する.

主な方法:

  • 一般化されたスピン・グラス・モデルのデモ.
  • 旅行営業マン問題への応用.
  • 有限サイズのスケーリング分析を用いて.
  • 分析的な洞察のための平均フィールド近似を使用します.

主要な成果:

  • パラレルローカル検索で突然の性能低下が確認されました.
  • トランジションポイントの近くで,サイズに依存する効果を特徴づけた.
  • 平均場理論を通して分析的な理解を提供した.

結論:

  • ローカル検索の並列化には固有の制限があります.
  • この移行を理解することは,効果的なアルゴリズム設計に不可欠です.
  • この発見は,最適化技術のスケーラビリティに関する洞察を提供します.