シミュレーテッドアニーリングにおける重要温度領域に関す….ppt

《シミュレーテッドアニーリングにおける重要温度領域に関す….ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、シミュレーテッドアニーリングにおける重要温度領域に関する考察同志社大学工学部三木光範同志社大学工学部廣安知之○同志社大学大学院　米澤　基最適化とはある制約条件のもとで，目的となる関数の最小値(最大値)を求めること最適化問題LSI配置問題巡回セールスマン問題連続最適化問題タンパク質の立体構造予測エネルギーが最も安定する状態タンパク質の構造予測組合せ最適化問題LSI配置問題巡回セールスマン問題最短の経路低コスト，高性能化最適化：移動距離旅行代金研究背景最適解に近い解を実用的な計算コストで探索する技法シミュレーテッドアニーリング：金属の物理現象を模倣遺伝的アルゴリズム

2、：生物の進化を模倣ニューラルネット：脳の計算機能を模倣(50-1)!/2=3×10の巡回路50都市があれば‥62現実的に不可能組合せ最適化問題とはヒューリスティック探索現在の解SimulatedAnnealing(SA)組合せ最適化問題に有効な近似解法金属を溶融状態から緩慢に冷却する「焼き鈍し」を模倣改悪方向への推移を確率的に認めるため局所解に陥りにくい温度スケジュール：SA試行中の温度Tの推移温度スケジュールとSAの解探索能力が密接に関係受理判定次の解次の解推移高温の場合低温の場合温度スケジュール特定の温度のみ探索するSA[Connolly1990,Mark20

3、00]高い温度から緩慢に冷却する方法が一般的良好な解が得られる一般的な温度スケジュール特定の温度のみ探索を行うSAこの温度領域はSAの解探索おいて非常に重要重要な温度領域の検証一定温度の解探索で良好な解を得ることができる[Connolly1990,Mark2000]対象問題：巡回セールスマン問題(TSP)全ての都市を巡回する最短の経路長を探索代表的な組合せ最適化問題対象TSP：TSPLIBより[eil51,eil76,pr144,berlin52,st70]高温から低温まで等比的に分割各温度で一定温度の探索得られた解と各温度の関係重要温度領域の確認(eil51で

4、の実験結果)各温度によって解が異なる特定の温度領域で良好な解TSP都市数重要温度領域eil51511.1～2.2eil76760.9～1.5berlin525218.0～38.0st70701.1～2.7pr14414415.6～92.8問題によって重要温度領域の値，範囲が異なる誤差1%重要温度領域誤差1%重要温度領域重要温度のみの探索を行うSAと逐次SA重要温度のみの探索を行う単一温度SA高温から低温まで探索を行う逐次SA解の精度の比較パラメータ逐次SA単一温度SA最高温度最大の改悪となる推移を50%の確率で受理される温度重要温度最低温度最小の改悪となる推移がク

5、ーリング周期内の解探索で最低1回は受理される温度クーリング周期都市数×20アニーリングステップ都市数×3200試行回数30対象問題[eil51],[eil76],[berlin52],[st70],[pr144]研究目的問題名最適解との誤差pr144のみ重要温度で良好な解が得られない研究目的:重要温度領域に関して詳細な検証を行い，なぜこのような結果が得られたか考察するpr144の都市配置eil51の都市配置pr144の都市配置単一温度SAで良好な解が得られなかった単一温度SAで良好な解が得られた疎密な構成では重要な温度が複数ある単一温度のみの探索で良好な解が得られ

6、ない重要温度領域が複数存在する問題の作成均一な構成疎密な構成重要温度領域と平均都市間距離TSPにおける重要温度領域∝問題の平均都市間距離(最適解／都市数)[三木ら2001]10倍に拡大格子型に隣接[eil51-10][eil51*4]平均都市間距離：8.483.58.2温度1.5付近[eil51][eil51-10]の重要温度領域[eil51*4]の重要温度領域温度1.5付近温度15付近重要温度領域と平均都市間距離重要温度領域が平均都市間距離に比例することが確かめられた[eil51-10][eil51*4]重要温度領域が複数存在する問題の作成eil51を1000倍

7、に拡大eil51を4つ隣接eil51を対象としてスケールを拡大して組合せる254都市問題eil51*1-1000eil51*4-10eil51*4-100eil51*4-800eil51*4-1000eil51*4-10000eil51*9-1000eil51*16-1000作成した問題問題名：eil51*4-1000複数の重要温度領域を確認DistanceDistanceDistanceTemperatureTemperatureTemperatureTemperatureDistance(×104)(×105)(×105)(×105)重要温度領域が1つ存在する

8、それぞれの