はじめに

本記事では、まずは遺伝的アルゴリズムの概念を理解することを趣旨に記述していきます。

この記事で流れがつかめたら以下の記事で数字を使って理解してみると良いです。
OneMax問題を例に遺伝的アルゴリズムを見る（概要編）

遺伝的アルゴリズムとは

Wikipediaから引用すると

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。

何言ってるかわかりませんね。

簡単に言うと「生物が遺伝によって進化する過程をモデルとしたアルゴリズム」です。

例えば、キリンは首と足の長い動物ですが、大昔は違った姿をしていたと言われています。

大昔のキリンはみんな首と足が短かったそうですが、ある時「突然変異」により首と足の長いキリンが生まれました。

低いところの葉っぱはみんなが食べるからどんどんなくなりますが、高いところにある葉っぱは首の長いキリンしか食べられないので簡単に食糧を得ることができます。
さらに、足が長いと走るのも早いので肉食動物に捕まることも少ないです。
自然への「適応度が高い」ということです。

すると首と足の長いキリンは他のキリンより生き残りやすくなります。
そしてこの首と足の長いキリンが子供を作ると、子供に首と足の長さが「遺伝」し、やはり生き残りやすくなります。

これを繰り返す中で首と足の短いキリンはどんどん「淘汰」され、キリンはみんな首と足が長くなったと言うわけです。

この一連の流れをモデルにしたアルゴリズムによって問題の最適解を出そうと言う手法を1975年にミシガン大学のジョン・H・ホランドさんが提案したんですね。

遺伝的アルゴリズムの流れ

キリンの例を基に遺伝的アルゴリズムの流れを見てみましょう。

① 個体集団の作成

まず個体集団を作ります。足と首の長いキリンから短いキリンまで適当にたくさん作ります。

キリンの集まりを「個体集団」、キリン一匹一匹を「個体」、それぞれのキリンを形成しているものを「遺伝子」と呼びます。

② 個体の評価

個体をそれぞれ評価して優劣を付けます。

今回の評価ポイントは「生き残りやすさ」です。前述したように首と足が長ければ長いほど生き残りやすくなるため”Good!”になります。
もちろん問題によってこの評価ポイントは変わってきます。

③ 個体の選択

評価の高いものを次の世代へと受け継ぐために残します。

④ 交叉

③で選択された個体同士で子供を作ります。

⑤ 突然変異

④で作成された新たな個体集団の中のごく一部に突然変異を起こします。

今まで「首と足の長さ」ばかりに着目してきました。
でも②で述べたように、今回の評価ポイントは「生き残りやすさ」です。
もしかしたら胴も長い方が生き残りやすいかもしれません！（胴が長いと動き辛そうなのでそんなことはないでしょうが、ものは試しです。）

この様に進化の多様性を保つために新たな風を吹き込むことを突然変異といいます。

⑥ ②〜⑤を繰り返す

⑤でできた個体たちにまた②の個体の評価を行い、優秀なキリンからまた子供を作ります。

このように②〜⑤を何度も繰り返していると、どんどん優秀なキリンが多くなり、最後の世代まで繰り返したらその中で最も評価の高い個体を最適解として導き出します。

まとめ

今回はキリンを例にして遺伝的アルゴリズムの流れについて見てきました。遺伝的アルゴリズムがどんなものかについて理解していただけたでしょうか？

以下の記事ではOneMax問題という問題を遺伝的アルゴリズムで解く流れを説明しています。見てもらえばよりイメージが付きやすいと思います。
OneMax問題を例に遺伝的アルゴリズムを見る（概要編）

Twitter@ruemura3