Evolution)とはStornとPriceが1997年に提案した最適化アルゴリズムである1。簡単に言えば、入力Xに対して何らかの出力Yを返す評価関数Y=F(X)を使ってXを最適化する手法である。このとき、評価関数Fはなんでもよく、ブラックボックス2であっても良い3。Optimizationとも呼ばれる)評価関数Fの目的は、入力されたXに対して結果Yを出力し、得られた結果Yの良し悪しを定量的に評価できれば良い。差分進化の欠点としては、得られた結果が大域的最適解となることを保証していないことが挙げられる。差分進化の構成要素としては、N個の候補Xを作成し、それらを評価する(初期化)。全ての候補x∈Xに対して:候補xに対して他の候補と組み合わせた変異体mを作成し、評価する(評価)。生成した変異体mがxよりも優れた特性を示すのであればxの中身をmで更新する(更新)。設定した停止条件を満たすまで(評価)→(更新)を繰り返していく。initialization()、evaluate()、そしてmutation()を実装する。実際には最低限の英語のコメントに留めている。Function)で表現された分布であるとする。評価する値(特性)}候補xを作成するにはarrayを与える4。結果的に下記のようになった。}}評価関数Fにxを入力すると結果tが返ってくる。今回は、結果tは高いほど良いとし、もしx.tより生成した候補のm.tが高かったらxの中身をmで書き換える。全候補数をNUMBER_OF_CANDSとする。停止条件を全ての候補が更新されなかったときとする。全体の処理としてはこんな感じになる。search_best(&candidates).print();}初期化PmfをNUMBER_OF_CANDS個格納するarrayを作成し返す。pmf);}全ての係数を足して1.0となるようにPmf.vを正規化するメソッド。{};とし、繰り返しの停止条件を「全ての候補が更新がされなくなるまで」とすることができる。停止条件は用途に合わせて設定することができる。.copy_from()は自分の中身を別のPmfの中身で更新するメソッド。候補xの変異体mの生成には、まず対象となる候補以外の3つの候補の係数を用いて中間体sと呼ばれるものを作る。c_i)}x^i$$ここで、$a_i$は候補aのPMFのi番目の次数の係数を表す。Factor)と呼称されるパラメータ。Rate)を用いて変異体mを作成する。CR)\newlinex_i&(\mathrm{otherwise})\end{cases}$$となる。ここで、$r$は[0、1)の値をとる乱数である。下記のソースコードを見た方がわかりやすいかもしれない。インデックスを3つ返す関数。0からNUMBER_OF_CANDS-1まで値を取るVecからランダムに3つ選んで、その中に自分のインデックスがなかったら返すようにする。事前に.filter()でidxをrangeから弾くよりも.clone()が一回少なく済む。}}最後に特性が最も良かった候補を返す関数を定義する。search_best(&candidates).print();}.print()は出力用のメソッド。}}まとめ今回はRustで差分進化の実装を行った。CRやSFを可変とする様々な亜種5が提案されているのでそちらも試してみるのも良いかも。↩すなわち、勾配法などとは異なり、対象とする関数の微分可能性を考えずに使える。↩Vec<>にしなかったのはマルチスレッド化を見越して。サイズがわかってるものしか受け付けてくれないArcを使いたいから。今回の場合だと別にVec<>でも良い。upLoginユーザーは見つかりませんでした。