インスタンスの進化に注目したTSPの発見的解法の提案と評価
スポンサーリンク
概要
- 論文の詳細を見る
組合せ最適化問題を解く方法のひとつとして,生物が環境に適応して進化していく過程を模倣した進化計算の手法が知られている.一般に生物は,同じ種であっても置かれた環境が異なると少しずつ異なる進化をすると考えられている.これを最適化の観点から見ると,各個体によって解かれている問題は,固定された同一のインスタンスではなく,環境によって変異させられたエネルギー空間の形状が少しずつ異なる個別のインスタンスであると考えることができる.このような進化計算に関する新しい考え方は,1998年にPapadimitriouとSideriによって提案された.本稿では彼らの手法を出発点とし,良質の解をさらに効率よく生成できるように改良した方法を提案する.実験はインスタンスの進化を評価することに重点を置いて行われた.実験の結果,提案手法は従来手法によって得られる解の精度を大きく向上させることが明らかとなった.
- 一般社団法人電子情報通信学会の論文
- 2003-07-25
著者
関連論文
- P2Pファイル共有システムにおける効率的なインデックスキャッシュ手法(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- 確率的な遷移を含んだ部分観測マルコフ決定過程における強化学習法
- Minority Gameを利用した輻輳制御手法の評価
- ネットワーク再構成を用いたインタレストマイニング法の改良(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- BitTorrent型並列ダウンロードシステムにおける効率的なマッチメーキング手法の提案(コンテンツ配信)
- グループの動的形成に基づく無線LANのための適応的メディアアクセス制御手法(MAC,4Gに向けたモバイルマルチメディア,モバイル通信品質,モバイルコンテンツマネジメント,モバイルセキュリティ)
- ノードの近接性を考慮したP2P DHTの構築手法(ルーチング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ベンディング法を用いたセンサネットワークのためのナビゲーション手法(ユビキタスネットワーキング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ノードのFree Degreeに基づいたMANETのための適応的ルーティングプロトコルの評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- DARTを用いたアドホックネットワークのアドレス空間均等化手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- PeerCQにおける効率的な条件付き情報監視手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- パッシブ型RFIDを用いた方向検出システム(MoMuC研セッション,超高速モバイル通信時代のマルチメディアアプリケーション及び一般)
- 分散ネットワーク上の故障診断問題について(新世代の計算限界-その解明と打破-招待解説論文)
- P2P環境における機能並列性に着目した分枝限定法の評価
- アドホックネットワークのためのQ-routing Protocolの性能評価
- 組合せオークションの勝者決定問題に対する並列分枝限定解法(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 組合せオークションの勝者決定問題に対する発見的解法
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- メモリ制限のあるP2P DHT上の連言検索手法(P2P,コンテンツ配信,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- クーポン収集方式に基づくデマンドバススケジューラの設計と評価
- 検索サマリの流通による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システムにおける負荷分散を考慮したCAN構成法(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-2情報管理)
- 無線センサネットワーク上の低遅延な耐故障ルーティングアルゴリズム(モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- 階層型ピア・ツー・ピアファイル共有システムのためのタイムラインベースドなクエリ駆動キャツシュプロトコル(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- 周辺情報検索におけるプロキシシステムのためのキャッシュ置換アルゴリズム(モバイルコンピューティング)
- 周辺情報獲得のためのプロキシキャッシュシステム(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- Content-Addressable Networkにおける効率的なキャッシング手法の提案
- P2P型サービスのための協調的な動的ユーザ管理システム(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- コーラムコンセンサスを用いた分散相互排除命令ライブラリの設計と評価
- マルチプロセッサスケジューラHMSSの標準タスクグラフセットSTGを用いた性能評価(EVA-2:並列処理と評価)
- インスタンスの進化に基づくTSPのための発見的解法の改良
- mTreeboneに基づく離脱耐性のあるツリー型ライブストリーミング(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- リンケージ同定を導入したTSPのための進化計算解法の提案
- 転送遅延を考慮したWMN上のアクセスポイント削減手法(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- インスタンスの進化に注目したTSPの発見的解法の提案と評価
- mTreebone に基づく離脱耐性のあるツリー型ライブストリーミング