非線形最適化GO

世間の出来事に疎い僕でさえわかるぐらい「ポケモンGO」が流行っている。僕は偏屈オヤジで、キャリアの不透明な料金体系が気に入らなくてスマホを持っていないので詳しくはよくわからないけど、全世界で1億ダウンロードだそうである。日本でもポケモンを求めて夜中に公園を徘徊する人がいっぱいいるらしい。僕は偏屈な上に貧乏性なので、そんなことに膨大なCPU時間が消費されているのがもったいない、という気がしてしまう。

そこでふと思った。非線形最適化問題に使えないか、というか、なんとかそういう方向に持っていけないか、と考えた．．．．

非線形最適化問題というのは例えば僕にとって身近なレンズ設計がある。もっと人の役に立つような例としては、特定の機能を持つたんぱく質の設計とかも典型的な非線形最適化問題である。非線形最適化は$n$次元のパラメータ空間の中でメリット関数の値を最小化する問題で、パラメータがメリット関数に非線形に効く場合である。非線形性が強いと、解の探索は絨毯爆撃的な方法しかないことが多い。

例えばたんぱく質設計では特定のDNA配列を作ることはできるようになってそれを使ってアミノ酸配列が指定できる。ところがそのアミノ酸配列のたんぱく質がどんな作用をするかは、まずどうやって折りたたまれるかがわからないといけないし、折りたたまれた形がどんな分子に作用するか、あるいはどのたんぱく質と結合するか、などがわからないといけない。折りたたまれ方は多くの水分子に囲まれた時にどういう形のときにエネルギーが最小になるかがわからないといけない。

任意のDNA配列をランダムに作ってもほとんどが何の役にも立たないジャンクたんぱく質になるだけなのに、何かの作用があるかどうかは、作ってみる、あるいは作ったとして計算してみるしかない。レンズ設計も同じでランダムにレンズを並べただけでは光が通過さえしない。解の候補になり得るのでさえ、パラメータ空間のほんとにほんのわずかな領域である。しかもさっき言ったようにその探索は、これまで成功した解の周辺を探すか、絨毯爆撃的な方法しかない。

たんぱく質の折りたたみ計算はfolding@homeみたいな個々人のパソコンの空き時間に計算してもらおう、それでCPU時間を稼ごうというプロジェクトがある。手法としてはseti@homeが元祖だけど、どちらもなかなかはかばかしくない。それはひとつにはプロジェクトに賛同して自分のパソコンの余剰時間をそれに割り当てるために必要なアプリをダウンロードして設定する、という作業が必要となるためで、無関心な人にとって敷居は高い。しかも脳の報酬系を直接刺激するような作用はなく、ユーザの行動をドライブできるのは知的好奇心のみである。

そこで、ポケモンGOに便乗したらどうだろうか。ARMとは言え$10^9$個あるということだぜ。GPSによる場所からパラメータ空間の特定の位置に対応させて、その場所でのメリット関数の値をスマホのCPUに計算させる。メリット関数の小さな場所にポケモンが現れる、という寸法である。周りより桁違いにいいメリット関数の場所にはレアポケモンが現れる。何桁もいい場所にはミュウ2が現れる。自動的に絨毯爆撃的解探索ができることになる。

ところで、$\mathbb{R}^2 \rightarrow \mathbb{R}^n \hspace{2mm}(2\ll n)$となるような全単射の連続写像って構成できるんだっけ？

コメント 2

人間の移動速度が、計算速度に対
してボトルネックになりそう…。
by Jun Hirabayashi (2016-07-26 06:15) 

コメントありがとうございます。
いえいえ、一人ひとりは自分の近傍をメリット関数のマップの上で探索してもらうだけです。たまたまメッリト関数の微係数が0でない付近にいる人には、こっちにポケモンがいるぞ、と探してもらうという考えです。
2次元平面からn次元パラメータ空間を単射かつ連続にマップするのは濃度が違うのでダメというのには後で気がつきました。何らかの方法で近傍が定義できる$\mathbb{Z}^2 \rightarrow \mathbb{Z}^n$みたいな、離散化した写像を作らないといけません。
それと局所最適解でもそれなりに意味があるような問題でないと、ミュウツーみたいな超レアポケモンだけで他は存在しないということになるので、少なくともたんぱく質折りたたみ問題には使えません。レンズ設計はいいんですけど1億人でやるようなものではないです。
今気がついたのですが、「1億」は$10^8$ですね。
by decafish (2016-07-27 08:47)