巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 巡回セールスマン問題の遣伝的アルゴリズムに対して凸包による訪問順序制限定理を用いた求解性能向上方法の提案を行う. 凸包とは点集合の任意の2要素を結ぶ閉線分を内部に含む最小の凸多角形であり, 要素数nの点集合の凸包を求めるアルゴリズムの計算量の下界はO (n log n) である. 訪問順序制限定理は凸包を用いてユークリッド平面上の巡回セールスマン問題の最短巡回路となる為の必要条件を示している. また, 遣伝的アルゴリズムは自然界の自然淘汰の過程をモデルとした解法であり, 巡回セールスマン問題の近似解探索アルゴリズムの中でも優れた解法の一つとして知られている. 本論文では, 凸包によって与えられる最短巡回路の必要条件を充足する巡回路を初期染色体とする事により, 遺伝的アルゴリズムの求解性能の向上を図る. ベンチマーク問題を用いたシミュレーションによる性能評価の結果, 都市数の大きい問題において訪問順序制限定理を用いた解法の求解精度が向上した.
- 1998-01-29
著者
関連論文
- Webサービス情報の統合のためのレポジトリ連携手法の提案
- 最小極大マッチング問題のニューラルネットワーク並列解法の提案
- 組合せ最適化問題に対する離散値ニューラルネットワーク解法の安定性の一考察
- ニューロ・GAによるデータ転送路最適化問題解法の提案
- 無線通信網の通信経路割当て問題を対象としたグリーディニューラルネットワーク解法の提案
- マルチキャストパケット交換方式におけるワンショットスケジューリング問題のニューラルネットワーク解法
- N-Queen問題を対象としたマキシマムニューロンモデルの競合解消方式の提案
- 無線通信網の通信経路割当問題に対するグリーディ・ニューラルネットワーク解法の提案
- 巡回セールスマン問題を対象としたニューロンフィルタの提案
- N-Queen問題を対象としたニューラルネットワークの半同期式更新方式の提案
- バイナリニューロンを用いたグラフ分割解法の研究
- 巡回セールスマン問題の従来アルゴリズムの評価と新しいニューラルネットワークアルゴリズムの提案
- N-Queen問題を対象としたマキシマムニューロンモデルの"Winner-take-all"方式に関する研究
- 無線通信網における通信経路選択問題のマキシマム・ニューロンを用いたニューラルネットワーク解法の提案
- マキシマムニューロンを用いたN-Queen問題のニューラルネット解法の提案
- グラフ分割問題に対するニューラルネットワーク解法の提案
- 立体構造情報と機能情報によるタンパク質間相互作用予測法の改良
- 無線通信網における信頼度制約通信経路割当問題に対するニューラルネットワーク併用2段階解法の提案
- Tanimoto係数を用いた類似化合物検索のクラスタリングによる高速化手法
- 5ZK-10 大規模な化合物データベースからの類似化合物探索手法(情報爆発時代におけるマルチメディアデータと位置依存情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- Tanimoto係数の性質に基づく化合物の類似度検索の高速化手法
- 化合物活性予測のためのTanimoto係数とRandom ForestのProximity Measureの組合せ手法
- TF-IDFフィルタリングによる機能的に類似した生物情報解析ワークフローの検索手法
- TF-IDFフィルタリングによる機能的に類似した生物情報解析ワークフローの検索手法
- 反応分類番号によるパスウェイアライメントの提案
- 絶対値発現量を用いた外れ値検出法に基づく組織特徴的な代謝反応パスウェイの抽出手法
- 遺伝子発現プロファイルを用いた遺伝子制御ネットワーク推定のためのバイクラスタリングの利用
- 完全線形符号による部分配列エンコード法の提案と多重アライメントへの応用(アルゴリズム)
- D-7-9 CAGEデータに基づく組織特異的な代謝反応パスウェイの抽出(D-7.MEとバイオサイバネティックスA(バイオサイバネティックス),一般講演)
- D-4-16 Webサービス統合環境実現のためのメディェータシステムの設計と実装(D-4.データ工学,一般講演)
- 系統プロファイルを利用した代謝反応ネットワーク中の保存領域抽出手法(Pathway and database)
- 遺伝子発現プロファイルを用いた遺伝子制御ネットワーク推定のためのバイクラスタリングの利用(セッション1)
- FPGA間配線問題に対するニューロンフィルタアルゴリズムの提案
- LA-008 遺伝子の機能分類を利用した遺伝子制御ネットワーク推定手法(A. モデル・アルゴリズム・プログラミング)
- 生物学的知見を利用したModule Bayesian Networkによる遺伝子制御ネットワークの推定(バイオインフォマティック)
- 細胞分化クロストークのモデル化と細胞分化クロストーク遺伝子の推定手法
- プレスブルカー文真偽判定アルゴリズムのためのBDDの応用とそれを用いた回路検証 (電子システムの設計技術と設計自動化)
- 巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- 遺伝的プログラミングを用いた関数合成アルゴリズムの改良法の提案
- SMIL風シナリオ群からのQoSを考慮したプロトコル合成
- SMIL風シナリオ群からのQoSを考慮したプロトコル合成
- マキシマムニューロンを用いたN-Queen問題の準同期並列解法の提案
- FPGA配線問題に対する貪欲法とニューラルネットワークを併用した3段階アルゴリズムの提案
- チャネル割当問題を対象とした拡張マキシマムニューラルネットワーク解法の提案
- セルラー通信網のあるチャンネル割当問題に対するマキシマムニューラルネットワーク解法の提案
- 生物情報解析ワークフローのためのRESTサービスのSOAPサービス変換手法(合同企画セッション:バイオデータマイニング,機械学習によるバイオデータマインニング,一般)
- 動的再構成可能FPGAの設計とそれへの並列アルゴリズムの実装
- 近隣リードを考慮したショートリードクラスタリングによる塩基配列構造情報の有向非循環グラフ表現
- 時系列発現プロファイルのための遺伝子機能グループ解析手法
- 地方自治体の例規比較に用いる条文対応表の作成支援
- 時系列発現プロファイルのための遺伝子機能グループ解析手法(一般,機械学習によるバイオデータマインニング,一般)
- 複数時系列遺伝子発現プロファイルを利用した遺伝子制御ネットワーク推定の精度向上手法
- 混合正規分布モデルを用いた経時観測蛍光画像からの細胞核の検出と追跡手法