遺伝的アルゴリズムとは
私は遺伝的アルゴリズムに関しては全くの門外漢ですので，Wikipediaの概要から引用します：
遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。
（中略）
また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。
approx-SVPとは
格子問題は少なくとも門外漢ではないので，特にWikipediaから引用することはしないが，適宜見てみると面白いかも知れない．
approx-SVPとは格子問題の1つで，与えられた格子
$$
L:= \mathcal{L}(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n)=\left\lbrace\left.\sum_{i=1}^n x_i\boldsymbol{b}_i~\right|~x_1,\ldots,x_n\in \mathbb{Z}\right\rbrace
$$
上の非零な最短ベクトルのノルムを$\lambda_1$としたとき，小さい$\gamma\ge 1$に対して$\lVert \boldsymbol{x}\rVert\le \gamma \cdot \lambda_1$なるベクトル$\boldsymbol{x}\in L$を見つけよ，という問題である．要するに，最短ベクトル問題（SVP）の近似解を求める問題である．
遺伝的アルゴリズムの実装
遺伝的アルゴリズムでは，選択，交叉，突然変異が殊に重要となるらしいので，それらの取り方を説明する．
選択
トーナメント選択を取る．
具体的には，適応度を格子ベクトル$\boldsymbol{x}\in L$に対して$\frac{1}{\lVert\boldsymbol{x}\rVert}$で与え，適応度の高い個体をトーナメント方式で決定する．
交叉
一様交叉を取る．
具体的には，格子ベクトル$\boldsymbol{x}, \boldsymbol{y}\in L$を与える係数ベクトル$(x_1,\ldots,x_n)$，$(y_1,\ldots,y_n)$に対して，各要素ごとに$\frac{1}{2}$の確率で取るようにする．
突然変異
係数ベクトルの各要素について，$0.01=1\%$の確率で$\pm 1$を加える．
実装
速さと実装の簡単さの面からC++で実装を行った．
実際の実装コードはGitHubで公開しているので，ぜひ見ていただけると嬉しいです．
実験
SVP-challengeのLLL簡約基底について，どの程度短いベクトルを発見できるのか実験してみる．パラメタ設定として，世代数は500，個体の数は500とした．また，全ての次元においてseedは0とした．
表において「GH」とあるものはGaussのヒューリスティックで，最短ベクトルのノルムの凡その評価を与えるものである．
| 次元 | GH | 今回のアルゴリズムで得られた（近似）解のノルム（10回の平均） | （近似）最短ベクトルのノルム |
|---|---|---|---|
| 40 | 1552.346274 | 2799.9005 | 1702 |
| 50 | 1552.346274 | 3717.1960 | 1893 |
| 60 | 1899.094437 | 4760.1132 | 1943 |
| 70 | 2069.307999 | 5946.0446 | 2143 |
| 80 | 2209.668078 | 8062.5575 | 2272 |
| 90 | 2344.511898 | 10429.8051 | 2419 |
まとめ
遺伝的アルゴリズムを利用して，approx-SVPの解の探索を行った．私のアルゴリズムが悪かったのが，対して短いベクトルを見つけられなかった．個体数を大きくしたり，世代を大きくしたりすればもっと短いものも見つかるかもわからないが本質的ではない．
個人的にはかなり面白いテーマなので引き続き適当に実装を続けてみようと思う．