私の稼ぎ頭(論文被引用数で)の研究を紹介します。長くなるので何回かに分けて投稿します。また、これをやると身バレするのでプロフィールなどもそれなりにリアルの世界になります。
膜アルゴリズムとは何か
アルゴリズムは特定の問題の答えを求めるための手順の集まりです。しかし、膜アルゴリズムは最適化問題を解くいろいろな近似アルゴリズムを組み合わせるための枠組みです(リンクはいずれもWikipedia日本語)。解く問題や組み合わせるアルゴリズムによってさまざまな膜アルゴリズムができます。イメージしやすいよう図を出しましょう。
このように入れ子になった領域をいくつか用意します。それぞれの領域を仕切るのが「膜」です。各領域には近似アルゴリズムを配置します。異なるアルゴリズムでも良いし、同じアルゴリズムでも動作のパラメータを違えておいても良いとします。近似アルゴリズムは通常現在の解を少しずつ改良して、最良の解=最適解に近づいていきます。それで各アルゴリズムのための「現在の解」も領域に配置します。各領域のアルゴリズムは並列に動作して「現在の解」を改良します。その後、次の通り解の移動をします。
隣の領域との間で解をやりとりするわけですが、良い解は内側に(緑の矢印)、悪い解は外側に(赤の矢印)送ります。解の改良と移動を何回も繰り返すうちに、自然と全体の最良解が一番内側、領域0に来る、と言う寸法です。
なぜ「膜」というか
近似解の改良と移動の仕組みをでっち上げただけなのに、仰々しく「膜アルゴリズム」と言うのか。それは、膜計算、Membrane Computing (英語)という計算の原理を考案した人がいて、膜アルゴリズムの仕組みがその膜計算にピッタリはまるからです。膜計算では上図の入れ子型構造以外に
のように外側領域の中に同等の領域が並んだ構造や部分的に入れ子になった構造もありです。膜アルゴリズムでも解の改良や移動の仕方によってこれらの構造を選ぶことができます。上の「平等な」構造では領域1からnで改良された解全部を見て何かやらかしたい時に便利です。なぜなら、1からnの解が全て領域0に来るからです。膜計算の仕組みを応用して近似アルゴリズムを組み合わせる方式、だから膜アルゴリズムと名付けました。
次は具体的な問題について膜アルゴリズムはどう構成され、何が嬉しいのか解説しましょう。手っ取り早く知りたい人は次の本を買いましょう。
