生物進化の原理をもとにした最適化手法である遺伝的アルゴリズムのご紹介

この記事では遺伝的アルゴリズムという最適化手法についてご紹介します。

JungHyeonjae

2021.07.16

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、ジョン・ヒョンジェです。

皆さんは「適者生存」という用語を聞いたことがありますか？

ある環境において、最も適応できる生物だけが生き残り、適応できない生物は淘汰される

これが適者生存の基本概念です。遺伝的アルゴリズムはこの適者生存という生物進化論をもとにして、生物が環境に適応し進化していく様子を模倣した最適化手法の一つです。今回はこの遺伝的アルゴリズムについてお話ししたいと思います。

遺伝的アルゴリズムとは

遺伝的アルゴリズムは生物進化論の以下のルールを模倣します。

環境に一番適応できる、つまり一番優秀な個体が生き残る
生き残った個体は繁殖する
生き残った個体は親として子孫を生成する。子孫は親の遺伝子を継承して次の世代を生きていく。ここで時々突然変異遺伝子を継承した子孫ができる。

遺伝的アルゴリズムでは進化論での個体を「染色体」と呼びます。染色体は最適化問題で可能な解の候補になります。そして、その染色体は数字やアルファベットで表された「遺伝子」の組み合わせで表現します。

この例では0と1が遺伝子で、この遺伝子の組み合わせが染色体です。遺伝的アルゴリズムの目的は「遺伝子の組み合わせを変化していきながら、最適な組み合わせを見つける」ことです。

遺伝的アルゴリズムは数学的に定義されていない問題や複雑すぎて計算できない問題での最適解を求める時よく使います。決められた方式がありませんので、その原理と流れをはっきり理解して、解決したい問題にどうやって遺伝的アルゴリズムを適用するかを設計するのが最も重要なところです。

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

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

第0世代の染色体をN個生成
- 染色体の遺伝子情報はランダムに設定
染色体を評価
- 適応度関数を作成して評価を行う
- 適応度は染色体の優劣を判断する基準
- 一番よく使われる方式は各染色体の適応度を評価して点数を付与する方式
染色体を二つ選択し、交叉
- 2段階で評価した染色体の中で二つを選択
- 選択した二つの染色体の遺伝子情報を交叉させて新しい染色体をN個生成
- 選択基準は決められていない（以下で代表的な選択方式をいくつか紹介します）
突然変異生成
- 3段階で生成した新しい染色体の中でいくつかの染色体の遺伝子情報を任意に変更
- 親にはなかったいい遺伝子情報を見つけるために必要
世代交代
- 既存の世代の染色体を3、4段階で生成した染色体に交代　
2~5段階を繰り返す
- 新しい世代で2~5段階を繰り返す
- 最大世代数のG回まで繰り返す
- 第G世代で一番適応度が高い染色体が最適解に一番近い解になる

このように染色体は親のいい遺伝子情報を継承して世代を経るたびに段々進化していきます。

遺伝的アルゴリズムの演算方式

遺伝的アルゴリズムでは決められた方式はありませんが、よく使われる代表的な演算方式はあります。それで、いくつか紹介したいと思います。

選択

Roulette wheel selection

Roulette wheel selectionは一番よく使われる選択方式です。仮想のルーレットがあると仮定して染色体に適応度に比例してルーレットの持ち分を配分します。配分が終わったら、ルーレットを回して染色体を選択します。ルーレットを回すのは乱数を生成することで実装します。この方式を使うと、適用度が高ければ高いほど選ばれやすいです。

Ranking selection

染色体	適応度	ランキング	持ち分(%)
A	90	1	40
B	10	4	10
C	12	3	20
D	15	2	30

Ranking selectionはRoulette wheel selectionと似ていますが、少し違います。Ranking selectionはランクごとにあらかじめルーレットの持ち分を決めておく方式です。適応度によって染色体のランクをつけて、ランクごとに決められた持ち分を付与します。上の票は「1位：40%、2位：30%、3位：20％、4位：10％」に持ち分を決めておいた例です。それで、染色体Aは圧倒的に適応度が高いですが、染色体Dの持ち分と10%しか差がないことがわかります。

Elitist preserving selection

Elitist preserving selectionはその名の通り、一番適応度が高い染色体は次の世代にもそのまま残す方式です。