今回はフラット型膜構造と膜アルゴリズムならではの可能性を紹介します。
まず、下の図で示されるフラット型の膜構造を使うものです。この構造は粒子群最適化と相性が良いようです。粒子群最適化は素早く解を改善できますが、下手にやると局所解に落ち込みやすくなります。
そこで、この皮膜領域(領域0)と基本領域(領域1からn)の区別を使い、基本領域でそれぞれ別々の粒子群最適化をやり、皮膜領域で基本領域の解を混ぜ合わせる。あるいは皮膜領域で基本領域から来た解の集団に粒子群最適化を行い、各基本領域では別の探索をやる。などなど、この膜構造を設定することにより、局所解を避けられる粒子群最適化の進化形を試すことができます。私は粒子群最適化が嫌いなので(食わず嫌いかも)自分でやったことはありません。外国の研究者は色々やっており、membrane algorithm と particle swarm optimization あるいは最適化問題例(ナップザック問題、巡回セールスマン問題など)をキーワードに検索すると、ぞろぞろ出てきます。
次に、その2で紹介した入子型膜アルゴリズムならではの可能性を紹介します。それは近似アルゴリズムが解を改良していく過程を観察できるということです。
図のように各領域で改善された解が「その領域で解が改良された」「全ての領域を通じてこれまでの最良解だった」かどうか色を使って表します。その解が移動した方向を楔形の記号で示します。色は解の性質で緑はどうということのない解です。巡回セールスマン問題を解いた実際の計算結果の一部を示します。
上の図は領域2で21334の解が生成され、領域1へ移動、そこで21282の解が出来て領域0に移動したことを示しています。21282はこの問題の最適解の値です。領域2は局所探索、領域1はGAを行っています。局所探索とGAの組み合わせが働いていることが見て取れます。4810はステップ数です。このように入れ子型の膜アルゴリズムで解の改良と移動を視覚化することができます。他の近似アルゴリズムでも出来なくはありませんが、例えばGAだと何千もの個体(解)を使うので非常に複雑になります。膜アルゴリズムは膜で分離しているからこそ視覚化が容易なのです。
このように膜アルゴリズムは有用な近似アルゴリズム組み合わせスキームだと自画自賛しています。しかし、外国の研究者には受けても国内では全然ダメ。このブログをご覧になった方、ぜひ膜アルゴリズムを流行らせましょう。
