BETA

進化計算アルゴリズム入門 1+2途中

投稿日:2019-11-02
最終更新:2019-11-02

画像

第1章 最適化とアルゴリズム

解が組み合わせ・順列で表現される問題を組み合わせ最適化問題という。

この組み合わせ最適化問題は、「制約下」で「最も良い適応関数の適応値となる適応解」を探すものである。

しかし、非常に計算が大きいため、厳密な最適解は求められない。
そこで、近似解を生物の動きに着想を得た・生活に着想を得たアルゴリズムで求める。

これによって、現実的な時間で良い解を得ることが可能となる。

第2章 遺伝的アルゴリズム

遺伝的アルゴリズムは、生物の遺伝子・染色体・環境適応性の進化の過程に着想を得たアルゴリズムである。

問題の解1つに、生物の染色体を対応させる。
染色体は$N$個の遺伝子からなり、巡回セールスマン問題なら、$N$の長さの染色体に、どのように訪問するか?という遺伝子が入っている。
よって、$N$次元ベクトル$x$で表れる。

大量の個体を世代と用意し、適応度関数に個体(染色体)を入れて、適応度を求める。
適応している個体を強く交配し、うまく残しながら、ある程度突然変異させる。
$fitness(I_i)$で適用度が求まる。

そして、世代を作る、適用度を取る、残す、進化させるを繰り返して、良い計算量で良い解を求める。

親の選択

親の選択は、適応度の割合で考える。
個体$I_i$の適応度$fitness(I_i)$を求める。
そして合計を求めて割合を求める。

最小値を予め引くと、負が消えるので嬉しい。

ランキング形式

適応度をランキングつけて、順位でやる。
比が消えてしまうので、うーん

交叉

親2つから、個を交配する。
一点交叉二点交叉、一様交叉などがある。

突然変異

突然変異をつける。
局所解を抜け出せるように、一気に新しい個を作るようにする。

巡回セールスマン問題

順列系は、交叉で矛盾が起きやすい。
パス表現で
部分写像交叉や順序交叉などをすると、パス表現でうまく交叉ができて嬉しい。

感想

面倒だなぁになる。
でも便利なんだろうなぁ

明日2章の続きをやる
本のクオリティが低い気がする(分かりづらい、コード貼っているだけ)

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

雑多まとめ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!