内積比較プロトコルに基づく分散巡回セールスマン問題のセキュアな最適化
スポンサーリンク
概要
- 論文の詳細を見る
本稿では分散化された組み合わせ最適化問題のためのセキュアな局所探索プロトコルを提案する.分散組み合わせ最適化問題とは、コスト関数に関する情報が複数のパーティーに分散している最適化問題であり、例えば分散巡回セールスマン問題では都市間移動コストや巡回する都市集合に関する情報が分散化されている。秘匿内積比較プロトコルに基づいた局所探索法では、分散巡回セールスマン問題において分散化された情報を共有することなく最適化を実行することが可能である。提案プロトコルは準備段階において都市数nに対してO(n^2)の時間計算量を必要とするが,コスト一評価あたりの計算量はO(1)である。計算機実験では都市数が1000を越える大規模分散TSPにおいても,実用的な時間で局所最適解に到達することが示された.
- 一般社団法人情報処理学会の論文
- 2006-07-20
著者
関連論文
- 論文特集「進化計算のフロンティア」にあたって
- UV構造を考慮した適応的複製選択による実数値GAの提案
- 適応的実数値交叉 AREX の提案と評価
- 機能分担多目的実数値GA: FS-MOGAの提案
- プライバシを保護した内積比較プロトコルの提案
- 実数値GAにおける生存選択モデルとしてのMGGとJGGの挙動解析
- 形質の遺伝を重視した遺伝的アルゴリズムに基づく巡回セールスマン問題の解法
- TSPにおける大域的多様性を考慮したGA
- TSPに対する枝組み立て交叉の挙動の分析
- 巡回セールスマン問題に対する交叉 : 枝組み立て交叉の提案と評価
- 実数値GAによるズームレンズ系の進化的設計
- プライバシ保護データマイニング
- 創発システム研究がめざすもの
- 論文特集「学習」にあたって
- 罰回避政策形成アルゴリズムの改良とオセロゲームへの応用
- 罰を回避する合理的政策の学習
- 罰を回避する合理的政策の学習
- 罰回避政策の境界維持による合理的政策の形成
- 強化学習に基づくオセロゲームの政策形成
- LIFE成果評価委員会報告(ファジィ思考によるヒューマンフレンドリシステムへの挑戦 : LIFE6年間の活動を終えて)
- インスタンスベース政策最適化のための実数値GAと非ホロノミック系制御への適用
- 関数最適化のための制約対処法 : パレート降下修正オペレータ
- Pareto Path Following による局所パレート最適解曲線の等間隔サンプリング
- ハイブリッドGAによる濃度制約付きポートフォリオ最適化
- 多親を用いた実数値GAのための世代交代モデル : Just Generation Gap(JGG) の提案と評価
- 実数値GAのための再初期化戦略の提案と性能評価
- インスタンスベース政策学習による非ホロノミック系制御の実験的考察
- ハイブリッドGAによるインスタンスベース政策学習 : SLIPの提案と評価
- Saving MGG : 実数値GA/MGGにおける適応度評価回数の削減
- 多目的関数最適化におけるGAと局所探索の組み合わせ : GA then LS の推奨
- 多目的関数最適化のための局所探索 : パレート降下法
- AI:過去・現在・未来
- 論文特集「進化計算パラダイムのフロンティア」にあたって
- プライバシを保護した内積比較プロトコルの提案
- 単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化
- 最小騙し問題を用いた世代交代モデルの解析
- 遺伝的アルゴリズムにおける世代交代モデルの提案と評価
- サブシーケンス交換交叉とGT法に基づくジョブショップスケジューリングの進化的解法
- GAにおける形質遺伝過程の可視化と解析
- 実数値GAのフロンティア(進化計算パラダイムのフロンティア)
- 実数値GAの新展開
- 高次元 κ-tablet 構造を考慮した実数値GA : 隠れ変数上の交叉LUNDX-mの提案と評価
- 確率分布推定に基づく実数値GAの新展開(遺伝的アルゴリズムの発展)
- 実数値GAにおけるサンプリングバイアスを考慮した外挿的交叉EDX
- κ-tablet 構造のための実数値GAとレンズ系設計への応用
- 実数値 GA のための正規分布交叉の多数の親を用いた拡張法の提案
- 距離情報を活用する世代交代モデルを用いた実数値GAによる高次多峰関数の最適化
- 実数値GAのための正規分布交叉に関する理論的考察
- 交叉的突然変異による適応的近傍探索 : 騙しのある多峰性関数の最適化
- 交叉的突然変異による適応的近傍探索 : 騙しのある多峰性関数の最適化
- カーネル密度推定器としての実数値交叉 : UNDXに基づく交叉カーネルの提案
- 情報理論的枠組に基づくマイノリティ集合の検出
- 内積比較プロトコルに基づく分散巡回セールスマン問題のセキュアな最適化
- 内積比較プロトコルに基づく分散巡回セールスマン問題のセキュアな最適化
- 単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによる光学系の最適化
- 「GAの研究に取り組んで十余年」へのコメントと回答(AIマップ)
- Profit Sharingを用いたマルチエージェントと強化学習における報酬配分の理論的考察
- マルチエージェント強化学習における報酬配分の理論的考察
- POMDPs環境下での決定的政策の学習
- マルチエージェント強化学習の方法論 : Q-LearningとProfit Sharingによる接近
- 動的環境における強化学習型マルチエージェント系の協調
- 把持・繰り動作のプランニングと強化学習
- 重点サンプリングを用いたGAによる強化学習
- α-domination 戦略に基づく分散強化学習と資源共有問題への応用
- 双方向意志決定を用いた分散強化学習による多段フローシステムの制御
- ロボットの強化学習における状態-行動空間の汎化
- 重み付けされた複数の正規分布を用いた政策表現 : 最適行動変化に追従できる実時間強化学習と環状ロボットへの適用
- 状態汎化とマルチエージェント化による大規模システムの強化学習
- 分散強化学習による下水送水系の制御
- 多次元連続空間における強化学習 : 離散的な状態遷移モデルの自動生成
- 分散型強化学習による上下水道系の制御
- 強化学習による環状ロボットの移動動作獲得
- 強化学習による4足ロボットの歩行動作獲得
- 確率的2分木の行動選択を用いた Antor-Critic アルゴリズム - 多数の行動を扱う強化学習 -
- 報酬の分散を推定するTDアルゴリズムと Mean-Variance 強化学習法の提案
- 生物的適応システム 〜 進化・学習のアルゴリズムと創発システム論 〜
- 確率的2分木の行動選択を用いた強化学習による多数の類似行動の扱いについて
- Actorに適正度の履歴を用いたActor-Criticアルゴリズム : 不完全なValue-Functionのもとでの強化学習
- 強化学習システムの設計指針
- Profit Sharing に基づく強化学習の理論と応用 (計算学習理論の進展と応用可能性)
- 確率的傾斜法を用いた強化学習とロボットへの適用
- ロボットアームのほふく行動の強化学習 : 確率的傾斜法による接近
- 満足化原理に基づく強化学習のための確率的探査戦略
- GAによるパレート最適な決定木集合の生成
- 属性の識別能力の局所性を考慮した確率的決定木の構築
- 並列化に適した遺伝的ローカルサーチによる非線形関数最適化
- EAXとILKの融合による大規模TSPの解法
- 独立制約充足による最適化と送水制御への適用
- 生得分離モデルを用いたGAとJSPへの適用
- GAの探索におけるUV現象とUV構造仮説
- 履歴を用いた状態評価関数の序列推定
- UV構造仮説に基づくGAの設計とJSPへの適用
- 高次結合バックプロパゲーションネットワークの能力について
- システム論の過去・現在・未来
- ファジィ・AI・ニューロとシステム理論
- 交叉の設計指針に基づくUNDXの拡張: ENDXの提案と評価
- UNDXの拡張に関する一考察 : ENDXの提案
- 配列情報からのタンパク質構造の進化的探索
- 原子位置の直接探索によるタンパク質の構造決定
- 事例に基づく操作的診断知識の生成および経験的診断知識の洗練化