温度並列シミュレーテッドアニーリング法の巡回セールスマン問題への適用と実験的解析
スポンサーリンク
概要
- 論文の詳細を見る
本論文では組合せ最適化問題のための新しい汎用アルゴリズムとして提案済みの温度並列SA法を, 巡回セールスマン問題に適用し, 本アルゴリズムを実験的に評価した. 温度並列SA法は既にさまざまな応用問題に適用/利用されているものの, 他の優れた発見的手法との比較が行われていない, いずれの適用例も最適解未知の問題である, という点から詳細な評価が行われていなかった. そこで本論文では温度並列SA法を実質的に組合せ最適化問題のべンチマークである巡回セールスマン問題に適用し詳細な評価を行った. まず温度並列SA法とその巡回セールスマン問題への適用方法について報告する. そしてランダムデータを用いた評価結果から, 2-opt近傍という非常に基本的かつ古典的な近傍を用いているにもかかわらず, 他の手法と比較して優れた結果が得られることを確認した. また実行時間についても並列計算機上での実行により, 実用的な時間で実行可能であることを示すことができた. 更に実用面での有効性を調べるために, ベンチマーク問題集であるTSPLIBから50個のデータを選び実験を行った結果, ランダムデータと同様良好な結果を得た.
- 1997-02-25
著者
-
小西 健三
シャープ株式会社
-
小西 健三
神戸大学大学院自然科学研究科
-
瀧 和男
神戸大学工学部
-
屋鋪 正史
神戸大学大学院自然科学研究科
-
屋鋪 正史
神戸大学大学院自然科学研究科情報知能工学専攻:(現)シャープ株式会社
関連論文
- パルス動作型ニューロンモデル用高速大容量シミュレータ
- 実時間三次元CG仮想世界向けネットワーク配信手法
- 3次元CGアニメーションの実時間合成・出力システム
- 低消費電力ディジタル・マッチトフィルタ : プラスチック・ハード・マクロ技術の応用事例
- 低消費電力CMOSセルライブラリの設計と評価 (電子システムの設計技術と設計自動化)
- ソフトコアIPを用いた低消費電力LSI設計 : 低消費電力CMOSセルライブラリの応用と評価
- 低消費電力CMOSセルライブラリの試作
- パストランジスタ論理のためのセル開発とその応用 (機能論理設計, アーキテクチャ設計支援と一般)
- CMOS/パス・トランジスタ混在論理の合成とレイアウト(システムLSIの設計技術と設計自動化)
- 神戸大LISPマシンPROLOGマシン(特集知られざる計算機)
- 並列論理シミュレーション向きタイムワープ機構の効率的な実現手法
- タイムワープ機構の新しい応用 : 並列無格子配線
- タイムワープによる並列論理シミュレータのコンパクトな実現手法
- 大規模デジタル回路におけるグラウンド雑音の解析(信号解析,アルゴリズム,回路設計)
- バイトコード変換を用いたJava標準API拡張ツール
- C-12-15 HDTV対応低消費電力MPEG2/MP@HL動き検出プロセッサLSIの開発(3) : SIMDデータパスの構成
- 高速低消費電力論理回路方式ASDLのパイプライン化手法とその評価
- プラスチック・ハード・マクロ技術による低消費電力算術演算器
- パストランジスタ論理SPLとその設計事例
- ディジタルAV機器向けGUIソフトウェア開発システム
- CMOS/パス・トランジスタ論理の混在による低消費電力回路の合成
- 共有メモリ型並列計算機におけるキャッシュを意識したオブジェクト内レイアウト法
- 低電圧動作を視野にいれた高速演算用回路方式ASDLの提案
- 低閾値NMOSを用いるパストランジスタ論理回路方式(電子システムの設計技術と設計自動化)
- 実時間三次元アニメーションシステムの並列オブジェクトモデルを用いた実現手法 (並列処理)
- 低消費電力ディジタル・マッチトフィルタ : プラスチック・ハード・マクロ技術の応用事例
- 低消費電力ディジタル・マッチトフィルタ : プラスチック・ハード・マクロ技術の応用事例
- ソフトコアIPを用いた低消費電力LSI設計 : 低消費電力CMOSセルライブラリの応用と評価
- ソフトコアIPを用いた低消費電力LSI設計 : 低消費電力CMOSセルライブラリの応用と評価
- 低消費電力CMOSセルライブラリの試作
- 低消費電力CMOSセルライブラリの試作
- 高速低消費電力論理回路方式ASDLのパイプライン化手法とその評価
- 低電圧動作を視野にいれた高速演算用回路方式ASDLの提案
- 低電圧動作を視野にいれた高速演算用回路方式ASDLの提案
- プラスチック・ハード・マクロ技術による低消費電力算術演算器
- パストランジスタ論理による加算器の設計手法と設計事例 (電子システムの設計技術と設計自動化)
- BDD分割を用いたパス・トランジスタ論理の合成 (電子システムの設計技術と設計自動化)
- TD-CDMAによる輻輳制御を用いたRFIDシステム向けトランスポンダのIC設計と評価(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- TD-CDMAによる輻輳制御を用いたRFIDシステム向けトランスポンダのIC設計と評価(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- TD-CDMAによる輻輳制御を用いたRFIDシステム向けトランスポンダのIC設計と評価(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- TD-CDMAによる輻輳制御を用いたRFIDシステム向けトランスポンダのIC設計と評価(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非対称な信号遷移を用いた高速論理回路方式(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 非対称な信号遷移を用いた高速論理回路方式(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非対称な信号遷移を用いた高速論理回路方式(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非対称な信号遷移を用いた高速論理回路方式(回路設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- Precomputed tableを用いたパストランジスタ論理の遅延計算
- 低閾値NMOSを用いるパストランジスタ論理回路方式
- Precomputed tableを用いたパストランジスタ論理の遅延計算
- Precomputed tableを用いたパストランジスタ論理の遅延計算
- パストランジスタ論理に基づく低消費電力回路方式と設計事例
- 低閾値NMOSを用いるパストランジスタ論理回路方式
- パストランジスタ論理に基づく低消費電力回路方式
- パストランジスタ論理に基づく低消費電力回路方式
- スクリプト記述とプロダクションルールによる3次元コンピュータアニメーション生成
- 細粒度スレッド対応デバッガのポータブルな実装方式
- 温度並列シミュレーテッドアニーリング法の巡回セールスマン問題への適用と実験的解析
- 並列オブジェクト指向言語mosaicの塵集め方式
- 並列オブジェクト指向言語mosaicのランタイムシステム
- 温度並列シミュレーテッド・アニーリング法とその評価
- 適応的オブジェクトによる排他制御の実行時緩和 (並列処理)
- 並列処理と例外処理を統一的に扱う構造化言語
- 並列オブジェクト指向言語ABCL/STにおける共有メモリ型並列計算機上の自動負荷分散方式
- 膜電位時定数の長いニューロンによるコインシデンスディテクタ
- オブジェクト指向並列言語によるN体問題の並列化とその評価
- 温度並列シミュレーテッド・アニーリング法とその応用
- 共有メモリ型並列計算機上でのBDD動的変数順序付けの並列化
- ワークステーション複合体による並列処理システム : 中・小粒度オブジェクト指向並列処理の実現
- ルーズな時刻同期をとる並列論理シミュレータの性能評価
- 位相によって信号分離を行うネットワーク
- パストランジスタ論理SPLにおけるstuck-on故障のテスト生成法と検査容易化回路
- 三次元仮想空間において自律動作するアバター : 3D Actorオブジェクト
- 実行時メソッド置換を行なう並列言語の実装
- 並列処理のためのオブジェクト指向言語OPAの設計とその実装
- 分散共有メモリ型並列計算機KSR上の細粒度並列処理用実行方式の評価
- パストランジスタ論理のためのセル開発とその応用 (機能論理設計, アーキテクチャ設計支援と一般)