第6章 担当:日下部 議事録:笠原) 浦田:そもそもなんで必要なのか。 日下部:最適解を求めるときでも局所解において最適が求められないときに、 このアルゴリズムを使う 浦田:最適解を求めるのはどういうときに必要か。 このアルゴリズムはいつ使うのか。 タブー探索法 近傍のみで探索してしまうため、本当の最小値に到達しない 笠原:どっちが近傍? 日下部:。。。? 笠原:繰り返す回数は最初に設定? 森部:例だと連続的にタブーを広げている。連続的じゃなくても大丈夫? 日下部:探索の刻み幅による。それぞれの点をタブーにする。 ここでは説明が分かりやすいように連続的に説明した。 芝原:焼きなましは連続的で、遺伝アルゴリズムは離散的? 日下部:焼きなまし法は連続関数もある意味で点の集合と捉えることで、 離散的と捕らえることも可能 芝原:改悪を許す?離散量だとどう説明できる? 日下部:GAのほうが遺伝子をたくさん用意しているから、それが結構はやそう 今泉:焼きなましの方が簡単だから計算が早そう 芝原:次の解が最適かを調べて更新するかしないかを決める? 日下部:大きくランダムに変えるようなことは、近傍の定義があれば起こらない。 大きな変化は却下される確率が高い 今泉:焼きなましは自分で設定しなければならないパラメータが一番多い。 パラメータによって解の収束の速さが決まる。 自分ではまりのよいパラメータを探す必要がある。 伊藤:4つの手法でどれがいいのか。 日下部:焼きなまし法は一番大変な方法だと思う。 どのように温度を下げればいいのかを設定しなくてはいけないから。 遺伝アルゴリズムは,あらゆることがランダムに進む印象があるから、 とっかかりやすいと思った 今泉:焼きなまし法が、個人的には使いやすいと思う。 確率的に改悪を許す、大局的な最適解にたどり着くから。 遺伝は計算が雑過ぎる。タブーはタブーの設定が難しい。 焼きなましはパラメータの設定さえすれば、解が求まるし、 解の精度の保障もあるから一番やりやすい。 浦田:厳密解が求まらないときに、メタヒューリスティックという手法がある。 局所探索で最適解がもとまるならそれが一番よい。 組み合わせ最適化でどう違うのかは、問題によってどれが当てはまりがよいかによる。 関数系の凹凸が多いとか、改悪を繰り返す計算が遅いとかだったら、 GAでランダムに計算したほうがいい。 離散問題で山がどうちらばっているのかなど、問題を見極めることが重要。