論文版はてなブックマーク（その3）の話。

Quantum-inspired evolutionary algorithmの論文2本。Fuzzy time series forecastingの論文2本。Quantum-inspired evolutionary algorithmとFuzzy time series forecastingを組み合わせて株価指数とビットコインの価格を予測してみたっていう論文1本。

Quantum-inspired evolutionary algorithmは、日本語にしたら疑似量子進化アルゴリズムみたいな感じ。あくまで量子計算の考え方を取り入れたってだけなので、一般的なパソコンで動く進化アルゴリズム。

最初は、Quantum-inspired evolutionary algorithmの論文を調べていたが、たまたまFuzzy time series forecastingという言葉を知って、こっちの論文も読んだ。折角なので、Quantum-inspired evolutionary algorithmとFuzzy time series forecastingをベースに株式の自動売買プログラムを開発したいと思う今日この頃。

blog.sun-ek2.com

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

ieeexplore.ieee.org

著者・掲載誌。

Kuk-Hyun Han, Jong-Hwan Kim

IEEE Transactions on Evolutionary Computation, January 2003

内容。

その名の通り、進化アルゴリズム、特に遺伝的アルゴリズムに量子計算の考え方を加えた新たなアルゴリズムを提案する論文。

従来の遺伝的アルゴリズムは、ランダム生成したビット列を評価関数の引数として加え、より高い（もしくは、より低い）戻り値を返すビット列を複数選択し、ビット列間で一部を組み替えたり、ビット反転を行ったりして、新たなビット列群を生成し、再び評価関数に加えて、、、といった工程をずっと繰り返して、評価関数の最適解を探索するアルゴリズム。

疑似量子進化アルゴリズムで使われるビット列は疑似量子ビット列から生成される。

$\displaystyle |ψ \gt =\left(\alpha_{1}|0 \gt+\beta_{1}|1 \gt\right)\otimes\left(\alpha_{2}|0 \gt+\beta_{2}|1 \gt\right)\otimes$

$\displaystyle \ldots\otimes\left(\alpha_{m-1}|0 \gt+\beta_{m-1}|1 \gt\right)\otimes\left(\alpha_{m}|0 \gt+\beta_{m}|1 \gt\right)$

疑似量子進化アルゴリズムは、0と1が任意の状態で重なりあった量子ビットを観測すると、それぞれのケットの係数の絶対値の自乗の確率に従って、0もしくは1が観測されるという点を遺伝的アルゴリズムに加えた新たなアルゴリズムである。量子計算だと、量子もつれ状態を取っている量子ビット列を使うが、疑似量子進化アルゴリズムの疑似量子ビット列は、もつれていない。

疑似量子ビットの実体は、|0>と|1>の係数が保存された配列。

$q_{n} = (\begin{matrix} α_{1} & α_{2} & \dots & α_{m - 1} & α_{m} \\ β_{1} & β_{2} & \dots & β_{m - 1} & β_{m} \end{matrix})$

この配列から得られる確率に従って、ビット列を複数生成する。遺伝的アルゴリズム同様に生成されたビット列を評価関数の引数として加え、より高い（もしくは、より低い）戻り値を返すビット列を1つ選択し、暫定最適解として保存する。

その後、疑似量子ビット列にユニタリ変換を行い、それぞれのケットの係数（ビット列生成の確率分布）を更新する。ユニタリ演算子には、回転行列を使っている。回転角度、方向は、暫定最適解のビット列が出る確率が高くなるように決める。0をx軸、1をy軸、暫定最適解のnビット目が1だとすると、nビット目の疑似量子ビットのベクトルが少しy軸に近づくように回転させる。

疑似量子ビット列の更新を終えたら、更新された疑似量子ビット列の確率分布に従って、ビット列を複数生成し、先ほどと同様のことを繰り返す。保存していた暫定最適解よりも良い解が得られたら、保存していた値を削除し、新たにその解を暫定最適解とする。

このサイクルを複数の疑似量子ビット列を用いて並列で行う。そして、ある条件で、複数の疑似量子ビットに対応する暫定最適解を入れ替える。また、複数の疑似量子ビットに対応する暫定最適解の中で一番良い解を最良の暫定最適解として保存し、ある条件で、それぞれの暫定最適解を全て最良の暫定最適解に置き換える。「ある条件」は、解きたい問題に合わせて、適切に決める。

論文では、疑似量子進化アルゴリズムを用いて、組合せ最適化問題の中でも有名なナップサック問題を解いていた。結果・考察はちゃんと読んでいないが、疑似量子進化アルゴリズムの利点は、少ないビット列数で解が求まることと、局所最適解に落ちにくいことだと思う。

「量子」というとなんか取っ付きにくいが、単にある確率分布に従ってビット列が生成され、評価され、暫定最適解が出やすいように確率分布が更新されているだけで、要は確率モデル。

Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, $\displaystyle H_{\varepsilon}$ Gate, and Two-Phase Scheme

ieeexplore.ieee.org

著者・掲載誌。

Kuk-Hyun Han, Associate Member, IEEE, and Jong-Hwan Kim

IEEE Transactions on Evolutionary Computation, April 2004

内容。

疑似量子進化アルゴリズムを改良したっていう論文。

< $\displaystyle H_{\varepsilon}$ ゲート>

従来の疑似ビット列の更新に使われていたユニタリ変換は、回転行列（回転ゲート）であった。回転ゲートを使うと、nビット目の疑似量子ビットが0か1に収束する可能性がある。局所最適解に落ち、疑似量子ビットが1つの値に収束してしまったら、そこから脱出することができない。

それを解決するのが $\displaystyle H_{\varepsilon}$ ゲート。ほぼ、回転ゲートであるがそれぞれの量子ビットの係数が $\displaystyle \sqrt{\varepsilon}$ 、 $\displaystyle \sqrt{1-\varepsilon}$ に到達すると、回転行列ではなく、恒等行列を作用させる（εは十分小さな値）。

<二段階方式>

最適解の収束時間、最適解の良さは、疑似量子ビット列の初期状態に大きく左右される。1回目は、パラメータ空間全体を粗々と探索できるように疑似量子ビット列を生成し、おおよそ良さそうな初期値候補を探索し、2回目は、1回目に得られた結果をもとに疑似量子ビット列を初期化して計算を始めるというのが二段階方式。

1回目の初期値は以下のように決める。

N次元のパラメータ空間にある一辺の長さが1-2δの超立方体の対角線を $\displaystyle N_{g}$ で分割している。それぞれの辺が[0, 1]ではなく [δ, 1-δ]になっているのは、疑似量子ビットが0か1に収束しないようにするため。複数の疑似量子ビット列を $\displaystyle N_{g}$ 個のグループに分けて、その中で時々、暫定最適解の入れ替えを行う。最良最適解の保存、最良最適解による他の最適解更新は行わない。

<終了条件>

従来：n個の疑似量子ビット列それぞれから最良最適解が得られる確率を算出し、その平均が $\displaystyle \gamma_{0}$ 以上になれば、終了。

提案手法：それぞれの疑似量子ビットが平均 $\displaystyle \gamma_{1}$ 以上、0か1に収束していたら、終了。

$\displaystyle C_{av} =\frac{1}{n} \sum^{n}_{i} \frac{1}{m} \sum^{m}_{j} |1-2|\alpha_{ij}|^2|$

j番目の疑似量子ビットが0に近づいても0に近づいても、 $\displaystyle |1-2|\alpha_{ij}|^2|$ は、1になる。

Handling Forecasting Problems Based on Two-Factors High-Order Fuzzy Time Series

ieeexplore.ieee.org

著書・雑誌名。

Li-Wei Lee, Li-Hui Wang, Shyi-Ming Chen, Yung-Ho Leu

IEEE Transactions on Fuzzy Systems, November 2006

内容。

fuzzy set理論を使った時系列データ予測の論文。この論文では、気温（main factor α）と空を占める雲の割合(second factor β)を入力に翌日の気温を予測している。

気温の最高値を $\displaystyle \alpha_{max}$ 、最低値を $\displaystyle \alpha_{min}$ とし、universe of discourseを $\displaystyle U = \left[\alpha_{min}-\alpha_{1}, \alpha_{max}+\alpha_{2}\right]$ と定義する。 $\displaystyle \alpha_{1}$ 、 $\displaystyle \alpha_{2}$ は、Uの最小値と最大値がきりのいい数字になるように決める。Uをn個に分割し、分割した区間のそれぞれの最大値を $\displaystyle u_{1}、u_{2}、\ldots、u_{n}$ とする。βのuniverse of discourseをVも同様。分割した区間のそれぞれの最大値を $\displaystyle v_{1}、v_{2}、\ldots、v_{m}$ とする。

linguistic term Aを以下の通り、定義する。

$\displaystyle A_{i}=\frac{0.5}{u_{i-1}}+\frac{1}{u_{i}}+\frac{0.5}{u_{i+1}}$

境界は、こんな感じ。

$\displaystyle A_{1}=\frac{1}{u_{1}}+\frac{0.5}{u_{2}}$

$\displaystyle A_{n}=\frac{0.5}{u_{n-1}}+\frac{1}{u_{n}}$

second factor βに対応するlinguistic term Bも同様。

main factor αをXへFuzzificationする。境界の取り扱いは、Step2と同様。

$\displaystyle X_{i}=\frac{0.5}{A_{i-1}}+\frac{1}{A_{i}}+\frac{0.5}{A_{i+1}}$

second factor βも同様にYへFuzzificationする。

k th order fuzzy logical relationship groupsっていうのをリストを作る。論文では、k=3でやっていた。kth order fuzzy logical relationshipは、こんな感じ。

$\displaystyle \left(X_{ik}, Y_{ik} \right), \left(X_{i(k-1)}, Y_{i(k-1)} \right),\ldots, \left(X_{i1}, Y_{i1} \right)→X_{j}$

具体例出して説明するのは面倒なので、詳細は論文を読んでください。

$\displaystyle \left(A, B \right), \left(C, D \right), \left(E, F \right)→S, S,T,T,U$

ある $\displaystyle \left(A, B \right), \left(C, D \right), \left(E, F \right)$ という時系列データが続いたときに $\displaystyle X_{j}$ が一意に定まるとか限らない。ある時点では、SになることもTになることもある。

Fuzzificationされた予測したいデータを $\displaystyle X_{final}$ とするとkth order fuzzy logical relationshipは、

$\displaystyle \left(X_{ik}, Y_{ik} \right), \left(X_{i(k-1)}, Y_{i(k-1)} \right),\ldots, \left(X_{i1}, Y_{i1} \right)→X_{j}$

$\displaystyle \left(X_{ik}, Y_{ik} \right), \left(X_{i(k-1)}, Y_{i(k-1)} \right),\ldots, \left(X_{i1}, Y_{i1} \right)$ の組み合わせが、過去の時系列データに存在する場合、予測したい未来のα、 $\displaystyle t_{j}$ は、

$\displaystyle t_{j} =\frac{n_{j1}t_{j1}+n_{j2}t_{j2}+\ldots+n_{jp}t_{jp}}{n_{j1}+n_{j2}+\ldots+n_{jp}}$

$\displaystyle t_{jp} =\frac{0.5m_{j-1}+m_{j}+0.5m_{j+1}}{0.5+1+0.5}$

と定義される。 $\displaystyle m_{j}$ は、 $\displaystyle u_{j-1}$ と $\displaystyle u_{j}$ の中点。 $\displaystyle t_{jp}$ の境界は、今までと同じように処理する。nは、 $\displaystyle t_{j}$ に対応するX（u）が時系列データに出現する個数。上の例の場合、 $\displaystyle \left(A, B \right), \left(C, D \right), \left(E, F \right)$ というデータが続いた場合、Sが2回、Tが2回、Uが1回出現する。

$\displaystyle \left(X_{ik}, Y_{ik} \right), \left(X_{i(k-1)}, Y_{i(k-1)} \right),\ldots, \left(X_{i1}, Y_{i1} \right)$ の組み合わせが、過去の時系列データに存在しない場合、直近のデータが重くなるように加重平均が取られる。

$\displaystyle t_{j} =\frac{1×t_{ik}+2×t_{i(k-1)}+\ldots+k×t_{i1}}{1+2+\ldots+k}$

Multivariate stochastic fuzzy forecasting models

www.sciencedirect.com

著者・雑誌名。

Tahseen Ahmed Jilani, Syed Muhammad Aqil Burney

Expert Systems with Applications: An International Journal, October 2008

内容。

3番目の論文と同様にfuzzy set理論を使った時系列データ予測の論文。この論文では、main factor αと多次元のsecond factors [tex: \displaystyle \beta_{n}を入力に未来のαを2つの提案手法で予測している。

大半は、3番目の論文と一緒。second factor βの次元が1次元から多次元に拡張されただけ。

<提案手法1>

$\displaystyle t_{jp}$ の定義が3番目の論文と違う。

$\displaystyle t_{jp} =\left\{\frac{0.5+1+0.5}{\frac{0.5}{(m_{j-1})^c}+\frac{1}{(m_{j})^c}+\frac{0.5}{(m_{j+1})^c}}\right\}^{\frac{1}{c}}$

境界の処理の仕方は、

$\displaystyle t_{1p} =\left\{\frac{1+0.5}{\frac{1}{(m_{1})^c}+\frac{1}{(m_{2})^c}}\right\}^{\frac{1}{c}}$

$\displaystyle t_{np} =\left\{\frac{0.5+1}{\frac{0.5}{(m_{n-1})^c}+\frac{1}{(m_{n})^c}}\right\}^{\frac{1}{c}}$

<提案手法2>

前回は、データαをuで表して、Aに変換し、Xに変換していたが、提案手法では、Aとラベル付けしていたところをXとラベル付けして、計算を簡素化していた。

従来は、、、

$\displaystyle A_{i}=\frac{0.5}{u_{i-1}}+\frac{1}{u_{i}}+\frac{0.5}{u_{i+1}}$

提案手法は、、、

$\displaystyle X_{i}=\frac{0.5}{u_{i-1}}+\frac{1}{u_{i}}+\frac{0.5}{u_{i+1}}$

A Quantum based Evolutionary Algorithm for Stock Index and Bitcoin Price Forecasting

thesai.org

著者・雑誌名。

Usman Amjad, Tahseen Ahmed Jilani, Humera Tariq, Amir Hussain

International Journal of Advanced Computer Science and Applications, January 2018

内容。

Quantum-inspired evolutionary algorithmとFuzzy time series forecastingを組み合わせて株価指数とビットコインの価格を予測してみたっていう論文。

Fuzzy time series forecastingは、まず初めにuniverse of discourse $\displaystyle U = \left[\alpha_{min}-\alpha_{1}, \alpha_{max}+\alpha_{2}\right]$ をn個に分割しなければならない。この分割の仕方によってアルゴリズムの性能は大きく変わる。3番目の論文は、n個に”等”分割していた。

一方で、今回のアルゴリズムは、最適な分割法をQuantum-inspired evolutionary algorithmを使って求めたのちにFuzzy time series forecastingしている。つまり、Quantum-inspired evolutionary algorithmで $\displaystyle u_{1}、u_{2}、\ldots、u_{n}$ を決めている。

疑似量子ビット数は、ceil(Log2(α_max+ α_2))。疑似量子ビット列の数は、n分割したければ、n-1個。それぞれの疑似量子ビット列の暫定最適解間で入れ替えは行われない。一般的なものとは違い、ビット列は確率的には生成されない。|0>の係数が $\displaystyle \sqrt{0.5}$ よりも大きければ、0が生成される。その他は、1番目の論文と同じ。それぞれの疑似量子ビット列から得られた暫時最適解を小さい順に $\displaystyle u_{1}、u_{2}、\ldots、u_{n-1}$ ラベル付けする。（多分、 $\displaystyle u_{n}=\alpha_{max}+\alpha_{2}$ ?）生成されたビット列が $\displaystyle \alpha_{max}+\alpha_{2}$ より大きければ、適当な乱数で $\displaystyle \alpha_{max}+\alpha_{2}$ より小さくなるまで引かれる。

Fuzzy time series forecastingは、3番目の論文とほぼ同じ。 $\displaystyle t_{j}$ の定義が3番目の論文と違ったが、定義の仕方がちょっと謎なので割愛。

Quantum-inspired evolutionary algorithmに使われた評価関数は、AFERとMSE。AFERは以下の通り。MSEは、平均自乗誤差。

$\displaystyle AFER=\frac{1}{n}\sum^{n}_{j=1}\left|\frac{予測値-実際の値}{実際の値}\right|×100$

この文章を読んで、面白い！役に立った！...と思った分だけ、投げ銭していただけると嬉しいです。

ofuse.me

にほんブログ村

目次。

はじめに。

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

著者・掲載誌。

内容。

Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, Gate, and Two-Phase Scheme

著者・掲載誌。

内容。

Handling Forecasting Problems Based on Two-Factors High-Order Fuzzy Time Series

著書・雑誌名。

内容。

Multivariate stochastic fuzzy forecasting models

著者・雑誌名。

内容。

A Quantum based Evolutionary Algorithm for Stock Index and Bitcoin Price Forecasting

著者・雑誌名。

内容。

Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, $\displaystyle H_{\varepsilon}$ Gate, and Two-Phase Scheme