非階層的クラスタリング手法による対称巡回セールスマン問題の近似解法
スポンサーリンク
概要
- 論文の詳細を見る
巡回セールスマン問題(TSP)への階層的な領域分割にもとづくアプローチの問題として、都市分布が均一な場合に精度が落ちることが指摘されている.本論文ではこれが分割過程の強固な階層性がもたらすものであると考え、非階層的な領域分割に基づくモデルの必要性を指摘している.この実現の為の一手法として著者らは非階層的なクラスタリングのダイナミクスを検討している.これは複雑な挙動を示す多変量解析手法の一つであるがその再帰的なクラスター生成能力によって柔軟な領域分割がもたらされる場合があることが知られている.また強い相互作用によって系全体がローカルミニマに収束しにくい設定が可能であることが期待される.そこで、著者らはこの注目すべき特徴をTSPに利用できるよう新しい問題表現を導入しモデル化を行っている.このモデルの挙動、性能を検証するために各種実験をおこなっており、システム特性、TSPLIBに含まれるテストデータによる比較、均一なデータ分布問題に対する良好なロバスト性、また動的な問題への対応能力について検証している.
- 2000-12-15
著者
-
嘉数 侑昇
北海道大学
-
和田 充雄
北海道大学 大学院 工学研究科
-
久保 正男
防衛大学校情報工学科
-
嘉数 侑昇
北海道情報大学
-
久保 正男
防衛大
-
久保 正男
防衛大学校
-
和田 充雄
北海道大学
-
和田 充雄
北海道大学大学院工学研究科
-
和田 充雄
北海道大学大学院工学研究科 複雑系工学講座
関連論文
- セル型倉庫問題における分散エージェント群の行動調整とその評価
- ラット前頭葉を模倣した脳モデルの構築に関する基礎研究 : セルラー場による順応学習の実現
- 強化学習による多足歩行ロボットの適応的歩様獲得に関する研究
- マルチエージェント系における機能創発
- 感情を模した内部状態を持つエージェント系における人工社会の形成
- 3次元ソリッド形状のスウィープ立体に関する理論的考察
- スウィープ補間曲面ソリッドのCSG表現法に関する研究
- フィレットのCSG表現法に関する研究 : 平面間稜線と頂点まわりの場合
- フィレットのCSG表現法に関する研究 : 二次曲面間相貫線まわりの場合
- N/C加工シミュレータ開発のための基礎研究 : 工具移動軌跡のモデリング
- 統計的手法を用いたAIBOの動作と印象の関係の解析
- object modelingにおける境界評価関数の研究
- 自動設計プロセサTIPS-1の開発
- 異方性エッチングを用いた生体電位計測のための多層構造型マイクロプローブの開発
- マルチエージェント強化学習による機械の社会行動の創発
- 人工生命と学習 : 生命に学ぶ新しい適応アルゴリズム (人工生命ワークショップ)
- 確率的ルール学習による動的タスク割当問題へのアプローチ
- CSG Ray-casting 法のハードウェア化に関する研究 : 形状集合演算の一手法
- CSGモデル向き濃淡面画作成専用ハードウェア・プロセッサの開発研究 : システム構成法の集合・写像による定式化
- CSGモデルの高速面画作成用ハードウェア・プロセッサの開発
- 予測機構による協調動作獲得の促進
- ロボティクス ・ メカトロニクス
- 自律分散ロボットの獲得する振る舞いの分化に関する研究
- 自律分散遊泳ロボットの障害物回避行動の獲得
- 分散制御型遊泳ロボットの自律的な目標物接近行動の獲得 : 振動運動パターンを予め導入した場合
- 分散制御型遊泳ロボットの自律的な目標物接近行動の獲得
- 行動の時系列記憶に基づく浮遊ロボットの推進運動制御
- スモールワールド理論を用いたAGVの経路設計評価に関する研究
- ジョブショップスケジューリングにおける多目的評価のペタル図による視覚化
- F-041 Webサービスにおける意思決定支援に関する研究(F.人工知能)
- LF-016 On-line Profit Sharingによる複数AGVの自律走行(F. 人工知能)
- スケールフリー構造を持つオートマタの状態遷移に関する研究
- 自律的Webサービスにおけるビジネスプロトコルの動的生成について(ネットワーク)
- 北海道大学工学研究科における高度情報技術者教育の実践例
- バイオミメティクスとモジュラーロボット
- 境界因子設計モデルのペトリネットによる制御 : 設計モデルの階層化に関する研究
- 境界因子設計モデルのペトリネットによる制御 : オブジェクト・オペレーション二元論によるモデルの表現
- 金型設計用3次元CADシステムの開発(第4報) : 金型彩状自動創成機能
- 巨視的状態量を用いたエージェント群の移動に関する基礎研究
- 自律移動ロボット群の集団挙動の複雑さに関する研究
- 群システム制御のための巨視的状態観測 : 熱力学とのアナロジーによる挙動特性の解析
- 自律ブロックエージェントによるブロック取り出し問題の基礎研究
- テーキングブロックアウト問題へのアプローチ -適応的パッキング法の提案-
- テーキングブロックアウト問題へのアプローチ(第2報)
- クラシファイアーシステムアーキテクチャの進化的合成に関する研究
- マルチエージェント環境における3次元箱詰め戦略の獲得 : GAによる階層型チューニング
- クラシファイアーシステムによる自律型ロボットナビゲーション問題に関する研究( インテリジェント・システム)
- 複数ブロックエージェントの自律行動の獲得に関する研究
- 非均質な群システムにおける知識共有型強化学習に関する研究
- 形態を持つマルチエージェントの挙動獲得に関する研究
- マルチブロックエージェントの自律的振る舞いに関する基礎研究
- ソリッドモデルベースNCシミュレータ GP/SIM の開発
- 3次元ソリッドモデルを用いたNC工具経路決定
- ビデオ・ローディング・システム・シミュレータの開発
- ポテンシャル場によるエージェントの協調作業の導入に関する研究
- ロボットトラクタシステム : 精密農法による食糧生産技術の新潮流
- 行動選択ネットワークに基づいた組織的行動の生成に関する研究
- 注視領域の適応的決定機構を有する遺伝的アルゴリズム
- 疲労度パラメータを導入した行動選択ネットワークによるエージェントの創発的組織化に関する考察
- 行動選択ネットワークに基づく社会的行動の創発
- 遺伝的監視によるラマルク進化の適応的制御
- ラマルク進化を導入したLLT-GAの構築
- フィルタリングGAによる多峰性関数の最適化
- 人工生命とシミュレーション(人工生命)
- Tierra型エコシステムにおける行動パターン表現に関する基礎研究
- オブジェクト指向型人工生命への自律的展開性の導入
- 人工生命における遺伝アルゴリズムと進化戦略
- スキーマ抽出法を用いた内部評価関数構築型GAの提案
- 遺伝的アルゴリズムにおける探索戦略の制御
- 学習・反学習法による連想記憶モデルの性質 : 想起過程の性質と記憶容量
- Q学習によるAGVの移動物体衝突回避(機械力学,計測,自動制御)
- Q学習による多数AGVの自律搬送に関する研究
- 簡易SDMを利用した強化学習によるAGVの経路獲得に関する研究
- Q学習によるAGV衝突回避通信プロトコルの獲得
- 非階層的クラスタリング手法による対称巡回セールスマン問題の近似解法
- 蟻の餌争奪ゲームによるマルチエージェントシステムの協調動作評価
- 学習オートマトンによる協調動作獲得への一手法
- 学習オートマトンによる変動情報を含むTSPへのアプローチ
- 階層型有向ハイパーグラフを用いた知識表現における推論
- 波動場を用いた生命体モデル : 巡回セールスマン問題への適用 (第2回人工生命ワークショップ)
- マルチエージェントシステムにおける学習エージェントの数理モデル
- ジョブのジグ・機械割り当てを考慮したスケジューラの開発
- 産官学連携の潮流
- 1A1-J8 EMGを用いた電動車椅子の制御に関する基礎研究(11. 医療・福祉ロボティクス・メカトロニクスI)
- 遺伝的進化による捕食関係の形成
- ピアノ問題における強化学習を用いた自律分散型エージェントの協調行動獲得
- 1A1-E10 階層型強化学習による非均質エージェント群の協調行動獲得 : ピアノ問題へのアプローチ
- 筋電位信号を用いた手話の動作認識
- コンストラクティブ型のリカレントニューラルネットワークを用いた迷路探索問題におけるエージェントの行動獲得に関する研究
- ポテンシャル場によるエージェントの協調作業の導入に関する研究
- ポテンシャル場によるエージェントの協調作業の導入に関する研究
- ポテンシャル情報に基づく作業環境のモデリングとエージェントのタスクシェアルールの抽出に関する研究
- 金型CAD用反転形状の自動生成に関する研究 : 抜取り可能性の判定
- 3次元形状モデル間の干渉認識に関する研究
- ソリッド形状モデリングにおけるCSGからB-Repsへの解析的変換の研究
- 低侵襲計測システムの構築に関する研究 : ラット体性感覚野における活動電位の解析
- 内部観測型相互作用スキーマの生態系モデル
- PROTEANにおける自己組織化ダイナミクスの時系列解析
- ハイパーサイクルの自己組織的区分化による巨視的保存系の創発
- トポロジカルマッピングによる空間構造認識 : 自律型マニピュレータの協調動作への応用