| 講演名 | 1993/5/26 多点探索型シミュレーティッドアニーリング 上坂 吉則, 西下 創, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 組合せ的最適化問題の確率的な解法としてシミュレーティッドアニーリング(SA)と遺伝アルゴリズム(GA)がある.SAは一つの解の候補を摂動・受理することによって解の集合を探索する.一方,GAの特徴は解の候補を″複数個″用意し,それらを同時に確率的に山登りさせる点にある.本論文では,GAの複数探索の特徴を取り入れたSAについて考察し,この多点探索型のアルゴリズムによって唯一の平衡分布(ギブス分布)に収束するようなマルコフ連鎖を生成できることをまず示す.つぎに,平衡分布における探索成功率を与える式を導き,目的関数がいわゆるゴルフホール型の場合にMSAは最も効果があり,値が一様ランダムに分布しているタイプの目的関数にはほとんど寄与しないことを示す.この事実は,与えられた目的関数にうまく符合したポテンシャル関数を選ぶことによって,MSAを効率の良い探索手法とできることを示唆している. |
| 抄録(英) | For solving combinatorial optimization problems there are two stochastic methods,that is,the simulated annealing(SA)and the genetic algorithm(GA).With only one candidate of solutions,SA searches in the set of all solutions by the pertubation and acceptance of the candidate.On the other hand,GA makes many candidates of solutions simultaneously climb the mountaion of an objective function.Taking this kind of multisearching method into SA,we discuss a multitype of simulated annealing(MSA)and show first that it generates a morkov chain converging into the unique stationary distribution(Gibbs distribution).Next we give a formula by which the success probability of searching will be calculated at the stationary distribution.As a result,MSA is shown to be most effective for the golf-hole type of objective function but noi for objective functions with uniformly random values.These indicate that MSA is able to be more effective than SA under the suitable selection of potential functions for a given objective function. |
| キーワード(和) | 組合せ的最適化問題 / シミュレーティッドアニーリング / 遺伝アルゴリズム / マルコフ連鎖 |
| キーワード(英) | combinatorial optimization problem / simulated annealing / genetic algorithm / marcov chain |
| 資料番号 | NC93-9 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1993/5/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多点探索型シミュレーティッドアニーリング |
| サブタイトル（和） | |
| タイトル（英） | Multipoint type of simulated annealing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ的最適化問題 / combinatorial optimization problem |
| キーワード(2)（和/英） | シミュレーティッドアニーリング / simulated annealing |
| キーワード(3)（和/英） | 遺伝アルゴリズム / genetic algorithm |
| キーワード(4)（和/英） | マルコフ連鎖 / marcov chain |
| 第 1 著者 氏名（和/英） | 上坂 吉則 / Yoshinori Uesaka |
| 第 1 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences,Faculty of Science and Technology,Science University of Tokyo |
| 第 2 著者 氏名（和/英） | 西下 創 / Hajime Nishishita |
| 第 2 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences,Faculty of Science and Technology,Science University of Tokyo |
| 発表年月日 | 1993/5/26 |
| 資料番号 | NC93-9 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 67 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |