インスタンスの進化に基づくTSPのための発見的解法の改良
スポンサーリンク
概要
- 論文の詳細を見る
本稿では「与えられたインスタンスを簡単なインスタンスに進化させて解く」という考え方に基づいた、ユークリッド平面上のTSPに対する発見的解法の提案と評価を行う。提案手法は1998年にPapadimitriouとSideriによって提案された手法の改良になっている。提案手法の効果を評価するために行った実験の結果、提案手法を用いることで進化の効率が向上し,従来手法に比べてよりよい解がより高速に求められることが明らかとなった。
- 2004-06-22
著者
-
藤田 聡
広島大学大学院工学研究科情報工学専攻
-
Fujita Satoshi
Department Of Mechanical Engineering Tokyo Denki University
-
藤田 聡
広島大学大学院工学研究科
-
梅實 真一郎
広島大学大学院工学研究科情報工学専攻
-
梅實 真一郎
広島大学大学院工学研究科
関連論文
- P2Pファイル共有システムにおける効率的なインデックスキャッシュ手法(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- メモリ制限のあるP2P DHT上の連言検索手法 (情報ネットワーク)
- 確率的な遷移を含んだ部分観測マルコフ決定過程における強化学習法
- Minority Gameを利用した輻輳制御手法の評価
- 階層型P2Pを用いたセンサ情報の広域共有方式 (情報ネットワーク)
- ネットワーク再構成を用いたインタレストマイニング法の改良(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- BitTorrent型並列ダウンロードシステムにおける効率的なマッチメーキング手法の提案(コンテンツ配信)
- グループの動的形成に基づく無線LANのための適応的メディアアクセス制御手法(MAC,4Gに向けたモバイルマルチメディア,モバイル通信品質,モバイルコンテンツマネジメント,モバイルセキュリティ)
- ノードの近接性を考慮したP2P DHTの構築手法(ルーチング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ベンディング法を用いたセンサネットワークのためのナビゲーション手法(ユビキタスネットワーキング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ベンディング法を用いたセンサネットワークのためのナビゲーション手法
- 分散ハッシュテーブル型P2Pシステムにおけるブルームフィルタを用いた高速連言検索手法の評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- ノードのFree Degreeに基づいたMANETのための適応的ルーティングプロトコルの評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- DARTを用いたアドホックネットワークのアドレス空間均等化手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- PeerCQにおける効率的な条件付き情報監視手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- パッシブ型RFIDを用いた方向検出システム(MoMuC研セッション,超高速モバイル通信時代のマルチメディアアプリケーション及び一般)
- A Fault-Tolerant Content Addressable Network(Networks)
- 分散ネットワーク上の故障診断問題について(新世代の計算限界-その解明と打破-招待解説論文)
- P2P環境における機能並列性に着目した分枝限定法の評価
- アドホックネットワークのためのQ-routing Protocolの性能評価
- Distributed Zone Partitioning Schemes for CAN and Its Application to the Load Balancing in Pure P2P Systems (特集 新時代の分散処理とネットワーク(WebサービスとP2P))
- 組合せオｰクションの勝者決定問題に対する分枝限定解法の機能並列化手法
- 組合せオークションの勝者決定問題に対する分枝限定解法の機能並列化手法(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 組合せオークションの勝者決定問題に対する並列分枝限定解法(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 組合せオークションの勝者決定問題に対する発見的解法
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 無線センサネットワーク上の低遅延な耐故障ルーティングアルゴリズム (ユビキタス・センサネットワーク)
- 最悪性能比が2.7834二次元調和算法の提案と評価
- The Distributed Anonymous Resource Conflict Resolution Problem
- メモリ制限のあるP2P DHT上の連言検索手法(P2P,コンテンツ配信,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 小型乗合バスシステムにおける最適発車間隔問題のモデル化とその強化学習による獲得手法の提案
- クーポン収集方式に基づくデマンドバススケジューラの設計と評価
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 検索サマリの流通によるP2P上の情報共有の効率化(P2P,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 階層型P2Pを用いたセンサ情報の広域共有方式(P2P,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 偏りのあるインデックス配布手法とP2Pファイル検索への応用(P2P,コンテンツ配信,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- パッシブ型RFIDを用いた方向検出システム(MoMuC研セッション,超高速モバイル通信時代のマルチメディアアプリケーション及び一般)
- 並列プログラムの並列度を自律的に制御するアクティブスケジューラの実装と評価
- ピュア型P2Pシステムにおける匿名インデックス検索方式(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-2情報管理)
- P2Pシステム上でのリザルトキャッシングを用いた条件付検索手法(ブロードバンドサービス,CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- グラフの支配集合間の相互変換可能性について
- 平均乗車時間を最小にする路線バスの運行経路決定方式の提案と評価
- メモリ制限のあるP2P DHT上の連言検索手法
- ピュア型P2Pシステムにおける負荷分散を考慮したCAN構成法(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-2情報管理)
- FTS2000-23 クラッシュトレラントな動的プロセッサ集合操作プロトコル
- 無線センサネットワーク上の低遅延な耐故障ルーティングアルゴリズム(モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- 階層型ピア・ツー・ピアファイル共有システムのためのタイムラインベースドなクエリ駆動キャツシュプロトコル(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- 無線センサネットワークを利用した位置測位システムの構築(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 周辺情報検索におけるプロキシシステムのためのキャッシュ置換アルゴリズム(モバイルコンピューティング)
- 周辺情報獲得のためのプロキシキャッシュシステム(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- Content-Addressable Networkにおける効率的なキャッシング手法の提案
- P2P型サービスのための協調的な動的ユーザ管理システム(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- コーラムコンセンサスを用いた分散相互排除命令ライブラリの設計と評価
- デマンドバスシステムのための最適経路選択法の実装とそのオンライン配車システムへの応用
- デマンドバスシステムのための最適経路選択法の実装とそのオンライン配車システムへの応用
- 転送遅延を考慮したWMN上のアクセスポイント削減手法 (コミュニケーションクオリティ)
- マルチプロセッサスケジューラHMSSの標準タスクグラフセットSTGを用いた性能評価(EVA-2:並列処理と評価)
- インスタンスの進化に基づくTSPのための発見的解法の改良
- P2Pライブストリーミングのための離脱耐性のある課税スキーム(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- mTreeboneに基づく離脱耐性のあるツリー型ライブストリーミング(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- リンケージ同定を導入したTSPのための進化計算解法の提案
- 転送遅延を考慮したWMN上のアクセスポイント削減手法(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- インスタンスの進化に注目したTSPの発見的解法の提案と評価
- mTreebone に基づく離脱耐性のあるツリー型ライブストリーミング