組合せ最適化アルゴリズムの最新手法―基礎から工学応用までを読みました。
80年代後半、90年代の論文がよく出てきており、20年前の最先端をまとめた本です。題材に半導体関連のネタが多く、興味を持って最後まで読めました。シミュレーティド・アニーリング手法（ＳＡ）、遺伝的アルゴリズム（ＧＡｓ）、タブー・サーチ手法（ＴＳ）、シミュレーティド・エボリューション手法（ＳｉｍＥ）、確率的進化手法（ＳｔｏｃＥ）について分かりやすく書いてありました。 ただ、この本を読んで実際の問題を解けるかどうかといわれると難しい気がします。
組み合わせ最適化について
この本にのっているアルゴリズムは、基本的にはすべてこのような手順になっています。
- 上手い初期値を設定する
- 上手く少しだけ良い方向へ変化する
- 上手く局所解を抜けて、大域解へ向かう。
局所解を抜けるために、どこかで乱数を使います。各アルゴリズムの違いはどこを重視するかです。 遺伝的アルゴリズムであれば、初期値を大量に作り生き残りを作っていくことで、上手い初期値としています。 タブーサーチ方では上手く良い方向へへの変化を求めるときに、過去の失敗をタブーとして参考にします。
直行している概念も多く、最後の章ではそれぞれの組み合わせの考察もありました。
実際はこのアルゴリズムにかける前に、上手いモデルの定義があって、それはそれで見るからに面倒でした。上手く行った事例が結構載っているのですが、それ以外は上手く行かなかったんだろうなという感じです。
並列コンピューティングやSIMDへの期待が高いのも興味深く読めました。
当時のニューラルネットワークの評価
面白いことに半導体の配置問題をニューラルネットワークを使って解くという89年の取り組みが紹介されています。30年前のニューラルネットワークの評価として貴重な資料です。
本の中では、このようにまとめられています。
ホップフィールド型ネットワークを配置問題に適用したユーの結果は、有望なものではなかった。いくつかの問題点は、シミュレーション時間が長いこと、解の質が低いこと、および、ネットワークのパラメータに対して、解の感度が高いことである。現段階では結論として、ニューラルネットワークを困難な最適化問題にてきようできるかどうかについては、さらに多くの研究が必要であると、述べるにとどめる。
