kivantium活動日記

プログラムを使っていろいろやります

制約付き最適化問題をD-Waveと同じ方法で解く

まだ古典コンピュータで消耗してるの?

イジングモデルとQUBO

D-Waveが提供しているのは量子アニーリングを使った量子コンピュータです。
量子アニーリング方式では次の形の最適化問題を高速に解くことができます。
 {\displaystyle \text{min.}\ \sum_{i \lt j} J_{ij} s_{i} s_{j} - \sum_{i=1}^{N} h_i s_i }
ここで J_{ij}, h_{i} \in \mathbb{R} s_i \in \{1, -1\}です。

1と-1よりは0と1の方が扱いやすいので、 x_i = (s_i+1)/2と変数変換して得られる以下のQUBO (Quadratic unconstrained binary optimization) という形に変形してから使うことが多いようです。
 {\text{min. } \displaystyle \sum_{i=1}^{N} c_i x_i + \sum_{i=1}^{N} \sum_{j=1}^{i} q_{ij} x_i x_j }

制約付き最適化問題とQUBO

QUBOでは変数間の制約がありませんでしたが、実際には  x_1+x_2=1 のような制約が必要になることがあります。
その場合、最適化したい関数 f(x)と十分大きい \lambda > 0を使って
 {\displaystyle \text{min.} f(x) + \lambda (x_1+x_2-1)^2 }
を解けば、(実行可能解が存在するなら)最小値を取るときには自動的に制約が満たされることになるので、QUBOの形で制約付き最適化問題が解けることになります。
なお、QUBOには x_i^2 の項がありませんが、 x_i は0または1なので  x_i^2=x_i が成り立ち、2乗の項が出てきてもQUBOの形に変形することができます。

qbsolv

qbsolv はD-Waveが開発しているQUBOのソルバです。
設定すればD-Waveの実機上でも動かせるようですが、デフォルトではローカル環境でのシミュレーションを使って解く設定になっているようです。
ここではコマンドライン環境を使います。

コンパイル

git clone https://github.com/dwavesystems/qbsolv.git
cd qbsolv
mkdir build; cd build
cmake ..
make

qbsolvは.quboファイルを読み込んでその解を出力します。
.quboファイルの仕様は以下の通りです。(READMEより引用)

qbsolv "qubo" input file format

   A .qubo file contains data which describes an unconstrained
quadratic binary optimization problem.  It is an ASCII file comprised
of four types of lines:

1) Comments - defined by a "c" in column 1.  They may appear
    anywhere in the file, and are otherwise ignored.

2) One program line, which starts with p in the first column.
    The program line must be the first non-comment line in the file.
    The program line has six required fields (separated by space(s)),
    as in this example:

  p   qubo  topology   maxNodes   nNodes   nCouplers

    where:
  p         the problem line sentinel
  qubo      identifies the file type
  topology  a string which identifies the topology of the problem
            and the specific problem type.  For an unconstrained problem,
            target will be "0" or "unconstrained."   Possible, for future
            implementations, valid strings might include "chimera128"
            or "chimera512" (among others).
  maxNodes   number of nodes in the topology.
  nNodes     number of nodes in the problem (nNodes <= maxNodes).
            Each node has a unique number and must take a value in the
            the range {0 - (maxNodes-1)}.  A duplicate node number is an
            error.  The node numbers need not be in order, and they need
            not be contiguous.
  nCouplers  number of couplers in the problem.  Each coupler is a
            unique connection between two different nodes.  The maximum
            number of couplers is (nNodes)^2.  A duplicate coupler is
            an error.

3) nNodes clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be integers and are the number for this node
            (repeated).  The node number must be in {0 , (maxNodes-1)}.
            The third value is the weight associated with the node, may be
            an integer or float, and can take on any positive or negative
            value, or zero.

4) nCouplers clauses.  Each clause is made up of three numbers.  The
            numbers are separated by one or more blanks.  The first two
            numbers must be different integers and are the node numbers
            for this coupler.  The two values (i and j) must have (i < j).
            Each number must be one of the nNodes valid node numbers (and
            thus in {0, (maxNodes-1)}).  The third value is the strength
            associated with the coupler, may be an integer or float, and can
            take on any positive or negative value, but not zero.  Every node
            must connect with at least one other node (thus must have at least
            one coupler connected to it).

Here is a simple QUBO file example for an unconstrained QUBO with 4
nodes and 6 couplers.  This example is provided to illustrate the
elements of a QUBO benchmark file, not to represent a real problem.

        | <--- column 1
        c
        c  This is a sample .qubo file
        c  with 4 nodes and 6 couplers
        c
        p  qubo  0  4  4  6
        c ------------------
        0  0   3.4
        1  1   4.5
        2  2   2.1
        3  3   -2.4
        c ------------------
        0  1   2.2
        0  2   3.4
        1  2   4.5
        0  3   -2
        1  3   4.5678
        2  3   -3.22

最短路問題をQUBOで解く

制約付き最適化問題の例として、最短路問題をQUBOに変換して解きます。
良い子のみんなはダイクストラなどを使いましょう。

f:id:kivantium:20180617163419p:plain
今回考えるグラフ

最短路問題を最適化問題として解く時は、辺  e_i を通るときは  x_i=1、通らない時は  x_i=0 として、重みの和  \sum w_i x_i が最小になるようにする問題と見ます。( w_i は辺  e_i の重み)
これだけだと何も辺を選ばないのが最適になってしまうので、辺の選び方が経路になるように各頂点に制約を加えます。

  •  v_0 からは1辺が出ていくので  x_0 + x_2 = 1
  •  v_1 に入って来る辺の数と出て行く辺の数は等しいので  x_0 - x_1 = 0
  •  v_2 には1辺が入ってくるので  x_1 + x_2 = 1

 (w_0, w_1, w_2) = (1, 1, 3) とすると、この最短路問題を解くためのQUBOは、
 {\displaystyle \text{min. } x_0 + x_1 + 3x_2 + \lambda \{(x_0+x_2-1)^2 + (x_0-x_1)^2+(x_1+x_2-1)^2\} }
となります。
 \lambda=100として、 x_i^2=x_iに気をつけながら変形すると
 {\displaystyle \text{min. } x_0 + x_1 +  (-197)x_3 + (-200) x_0x_1+200x_0x_2+200x_1x_2 }
となります。(間違ってたらごめんなさい)

これを.quboファイルにすると

p  qubo  0  3  3  3
c ------------------
0  0   1
1  1   1
2  2   -197
c ------------------
0  1   -200
0  2   200
1  2   200

となります。

./qbsolv -i test.qubo

のように実行すると

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
110
-198.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02363 seconds of classic cpu time

となり、 (x_0, x_1, x_2) = (1, 1, 0) という正しい答えが得られました。

 w_0=3にすると答えが

3 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
001
-197.00000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.02023 seconds of classic cpu time

に変わるので正しそうな挙動をしています。

2018年5月

5月はとても忙しかったのに特に進捗がなくてつらい

IguanaTex

  • LaTeX記法で数式を書くためのアドイン

IguanaTex - A Free Latex Add-In for PowerPoint on Windows

OBS Studio

  • YouTubeなどで生放送をするのに使えるソフト

Open Broadcaster Software | ホーム

Bulma

CSSフレームワーク。Bootstrapっぽくないものを作りたいと言ったら教えてもらった。

ナミキ商事

化合物データベースが充実しているらしい?

その他



Open Babelのビルドとインストール

Open Babel は化学で使われる分子フォーマット間の変換によく使われるソフトです。

開発されたばかりの機能を使うためには自分でビルドしてインストールする必要があるのですが、Pythonバインディングコンパイルするところにハマったのでメモしておきます。 基本的にはInstall Open Babelを見ればいいです。 環境はUbuntu 16.04を使いました。

必要なライブラリのインストール

sudo apt install cmake python3-dev libxml2-dev zlib1g-dev libeigen2-dev libcairo2-dev

ビルドとインストール

git clone https://github.com/openbabel/openbabel.git
cd openbabel
mkdir build
cd build
cmake .. -DPYTHON_BINDINGS=ON
make
sudo make install
echo 'export PYTHONPATH=/usr/local/lib:$PYTHONPATH' >> ~/.bashrc
source ~/.bashrc

pythonを起動して import pybel を実行してエラーが起きなければ成功です。

問題点

この方法でインストールできるのはaptで入れたpython 2.7だけで、Python 3やpyenvで入れたPythonではリンクに失敗します。 General discussion - OpenBabel for Python 3?Python 3向けにインストールする方法が書いてありますが、今のところうまくいっていません。 成功したら追記します。

C++で使う

インストールすると obabelなどの通常のコマンドラインツールが使えるようになります。

より複雑なことをするにはC++Pythonなどでコードを書くことになります。 以下に標準入力からSMILESを読んで、3次元座標を計算した後、標準出力にSDFを吐くコード例を示します。 エラー処理は省略しています。

#include <iostream>

#include <openbabel/mol.h>
#include <openbabel/obconversion.h>
#include <openbabel/builder.h>

int main(int argc,char **argv) {
    OpenBabel::OBConversion conv(&std::cin, &std::cout);
    OpenBabel::OBMol mol;
    OpenBabel::OBBuilder builder;

    conv.SetInAndOutFormats("SMI", "SDF");
    conv.Read(&mol);
    builder.Build(mol);
    conv.Write(&mol);
}

コンパイルは以下のように行います。ディレクトリは環境によって異なるかもしれません。

g++ -I /usr/local/include/openbabel-2.0/  -L /usr/local/lib/openbabel/2.4.90/ hoge.cpp  -lopenbabel

Makefileの例を示します。ディレクトリ名は適宜変更してください。

CC = g++
CXXFLAGS = -I /usr/local/include/openbabel-2.0/
LDFLAGS = -L /usr/local/lib/openbabel/2.4.90/
LDLIBS = -lopenbabel

all: hoge fuga

2018年4月後半

何もしないうちに4月が過ぎ去ろうとしている……

書いたもの

RVM の特許回避について


その他






リズと青い鳥」感想

タイムラインでの評判が非常に良かったので見てきました。
ネタバレですが、別にネタバレして面白さが失われる映画というわけでもないと思います。

時系列はユーフォ2期の続きで、鎧塚先輩とフルートの人の話です。
ユーフォ2期では何も言わずに部活やめておきながら今さら戻ってくるなんて、みたいな僕としてはどうでもいいことを問題にしていたのであまり面白く思えませんでした。
この映画では自分の道を歩んでいくことが最も良いと決断できるようになった過程をきれいに描いていて良かったです。

友情・愛情をテーマにした作品には自分の自己実現を犠牲にして相手と一緒にいることを選ぶものが多くて自分としては腑に落ちませんでした。
この作品では、相手と離れることになったとしても自己実現することが相手を大事にすることなのだという結論を出していて大変納得できました。

結局ぼくは自己実現の欲求の追求を価値あるものだと思っていて、人間関係の欲求を重視していないのでしょう。
欲求が満たされない初期状態にいる主人公が物語内での行動を通して欲求を満たしていくところを自分に重ね合わせることで自分も満足するというのが物語の一つの楽しみかたなのだと思います。(いま考えた)
バトルものやパニックものでは安全の欲求、恋愛ものでは社会欲求と愛の欲求(欲求段階説)、というように満たされない欲求はジャンルによって異なります。
安全欲求が満たされるものはそれだけで十分なのですが、自分には愛の欲求が薄いのでそれが満たされただけで終了してしまう作品はいまいちだと感じるのかもしれません。

ユーフォでは高坂麗奈さんが好きなのですが、それはまさにトランペットを通して自己実現をしようとしているからなのでしょう。
この映画ではよりよい音楽のために先輩であっても容赦なく指摘していくシーンや、オーボエの演奏が遠慮していると言った後に見せつけるようにトランペットを吹くシーンがとても良かったです。

arXivのリンクを貼ったら展開するSlack bot

Slackにはリンクを貼ったときに展開 (unfurl) する機能があります。
f:id:kivantium:20180418193058p:plain

この展開はリンクが貼られたときにoEmbedサーバー, Twitterカード/Facebook Open Graph, HTML metaタグの順に見にいくことで行われています
しかし、arXivにはその情報がないのでリンクを貼っても展開されません。

そこでリンクを貼ったら展開するSlackボットを作りました。

仕組み

SlackのReal Time Messaging APIを使ってメッセージを監視しておき、arxivへのリンクが貼られたら情報を取得して、Slackのattachmentという機能でタイトルとabstractの最初の140文字を取得してそれっぽく表示します。

使い方

https://slack.com/apps/A0F7YS25R-bots から自分のワークスペースに新しいbotを作成してAPI Tokenを下のコードの伏せ字になっている部分にコピペします。
必要なチャンネルにbotをinviteしておき、下のコードを実行しておくとarxivのリンクが貼られたときに展開してくれます。サーバーとかでずっと動かしておいてください。
f:id:kivantium:20180418200140j:plain

gist.github.com

bot名が表示されてほしくないんだけど

わかる。

Twitterの展開みたいな展開を行うためにはEvents APIをサポートするAppを作る必要があるのですが、そのためにはリンクが貼られたときにSlackがそのイベントを送信するURLを用意する必要があってとても面倒くさいのでやめました。

頑張りたい人は
api.slack.com
を読んでください。

2018年4月上旬

近況報告

大学院に進学しました。
23歳になりました。

この時期の話題

化合物の合成経路の自動設計

AlphaGoと同じようなMCTSニューラルネットワークを組み合わせる方法で化合物の合成方法を見つけられるという話。

日本人英語 : 英語発音の実態とその矯正法

日本人英語の矯正法について

東大英語部会の発音記号の指導
todai.tv

技術系英語Podcast

技術についてのPodcast。英語の勉強に良いかもしれない?

英語の形容詞の順番

Adjectives: order - English Grammar Today - Cambridge Dictionary

She was a beautiful tall thin young black-haired Scottish woman. というようなたくさんの形容詞が付く場合にちゃんと順番が決まっているよという話。

ターミナルでVimを起動したときの色



テレンス・タオのルベーグ積分本 PDF

公開されているのを知らなかった。

moedict

中国語辞典。特に萌えとは関係ないっぽい。

メンヘラちゃん。(LINEスタンプ)

中国で流行っているらしい。かわいい。

富岡製糸場のブリュナエンジン





その他








読んだ本

百合ドリル (MFC キューンシリーズ)

百合ドリル (MFC キューンシリーズ)

ときめく、はじめての。 (百合姫コミックス)

ときめく、はじめての。 (百合姫コミックス)

2018年3月 第1,2,3週

今週のTwitter


ニュース




スキー旅行



その他

  • ELSAという発音矯正アプリが良さそう

Rosetta Code

プログラミング言語の比較サイト。ロゼッタストーンのように同じ処理を異なる言語で書いて紹介している。
Category:Programming Tasks - Rosetta Codeを見るのが見やすそう。

日本の古本屋

古書店の在庫を横断検索できる。

Blender Guru

Blenderのすごいチュートリアルがいっぱいあるらしい。

量子コンピューティングの講義

読んだ本

三ツ星カラーズ5

最後にして最初のアイドル【短篇版】ひとりぼっちの○○生活(4)
最後にして最初のアイドル【短篇版】

最後にして最初のアイドル【短篇版】

きんいろモザイク アンソロジーコミック (1) 川柳少女(1) われはロボット 〔決定版〕

特定商取引法に定められた事項は請求により遅滞なく提供する