遺伝的アルゴリズムの動作原理を 1 つの記事で理解する (Python 実装付き)

最近、「遺伝的アルゴリズムの紹介とデータサイエンスにおけるその応用」というタイトルの記事が Analyticsvidhya に掲載されました。著者の Shubham Jain 氏は、遺伝的アルゴリズムの包括的かつ簡潔な概要をわかりやすい言葉で説明し、遺伝的アルゴリズムのデータサイエンスへの応用に重点を置きながら、複数の分野での実用的な応用を列挙しました。

導入

数日前、私は実際的な問題、つまり大規模スーパーマーケットの売上問題を解決することに着手しました。いくつかのシンプルなモデルを使用して特徴エンジニアリングを行った後、リーダーボードで 219 位にランクされました。

結果は良いのですが、さらに上を目指したいと思っています。そこで、スコアを向上させることができる最適化方法を研究し始めました。ついに、遺伝的アルゴリズムと呼ばれるものを見つけました。これをスーパーマーケットの売上問題に適用したところ、私のスコアはついにリーダーボードのトップに躍り出ました。

そうです。遺伝的アルゴリズムを使用するだけで、219位から15位にジャンプアップしました。すごいと思いませんか？この記事を読んだ後、あなたも遺伝的アルゴリズムを非常に自由に応用できるようになり、あなたが取り組んでいる問題に使用すると、効果が大幅に向上することが分かると思います。

1. 遺伝的アルゴリズム理論の起源

まずはチャールズ・ダーウィンの言葉から始めましょう。

生き残るのは、最も大きな種でも、最も知能の高い種でもなく、環境に最も適応できる種であることが多い。

あなたはこう考えているかもしれません。「この文は遺伝的アルゴリズムとどう関係があるのだろう？」実は、遺伝的アルゴリズムの概念全体がこの文に基づいています。

基本的な例で説明しましょう:

シナリオを想定してみましょう。今、あなたは国の王様です。国を災難から救うために、一連の法律を施行します。

善良な人々全員を選び、子供を産んで国の人口を増やすように頼みます。
このプロセスは数世代にわたって続きました。
すでに優秀な人材が集まっていることに気づくでしょう。

この例はありそうにありませんが、概念を理解しやすくするために使用しています。つまり、入力値 (たとえば人口) を変更すると、より良い出力値 (たとえば、より良い国) が得られます。さて、皆さんはこの概念について大まかな理解をしており、遺伝的アルゴリズムの意味は生物学に関連しているはずだと想定しています。それでは、文脈の中で理解できるように、いくつかの小さな概念を簡単に見てみましょう。

2. 生物学からのインスピレーション

「細胞はすべての生物の基礎である」というこの一文を皆さんはまだ覚えていらっしゃると思います。このことから、生物のどの細胞も同じ染色体セットを持っていることがわかります。いわゆる染色体とは、DNA で構成されたポリマーを指します。

伝統的に、これらの染色体は数字 0 と 1 の文字列で表すことができます。

染色体は、DNA を構成する基本構造である遺伝子で構成されています。DNA 上の各遺伝子は、髪や目の色などの固有の特性をコード化します。読み進める前に、ここで述べた生物学的概念を思い出していただければ幸いです。この部分を終えて、いわゆる遺伝的アルゴリズムが実際に何を指しているのかを見てみましょう。

3. 遺伝的アルゴリズムの定義

まず、先ほど説明した例に戻って、何をしたかを要約してみましょう。

まず、国の初期人口規模を設定します。
次に、善人と悪人を区別する関数を定義しました。
ここでも、良い個体を選び、子孫を残せるようにします。
***、これらの子孫は元の市民から一部の悪い人々を置き換え、このプロセスを繰り返しました。

遺伝的アルゴリズムは実際にはこのように動作し、基本的には進化のプロセスをある程度シミュレートしようとします。

したがって、遺伝的アルゴリズムを正式に定義すると、最良の出力値または結果をもたらす特定の入力を見つけようとする最適化手法と考えることができます。遺伝的アルゴリズムの動作方法も生物学から派生したものです。具体的なプロセスは以下の図に示されています。

それでは、プロセス全体を段階的に理解していきましょう。

4. 遺伝的アルゴリズムの具体的な手順

説明をわかりやすくするために、まずは有名な組み合わせ最適化問題「ナップサック問題」について理解しましょう。それでもまだ理解できない場合は、私の説明を以下に示します。

たとえば、1 か月間ハイキングに行く予定ですが、持ち運べるバックパックの重量制限は 30 kg です。現在、必要なアイテムはそれぞれ異なり、それぞれに独自の「生存ポイント」があります (下の表を参照)。したがって、あなたの目標は、限られたバックパックの重量の中で「生存ポイント」を最大化することです。

4.1 初期化

ここでは遺伝的アルゴリズムを使用してこのナップサック問題を解決します。最初のステップは、人口を定義することです。集団は個体で構成され、各個体は独自の染色体セットを持っています。

染色体は 2 進数の文字列として表現できることはわかっています。この問題では、1 は次の位置に遺伝子が存在することを表し、0 は遺伝子が存在しないことを意味します。（訳者注：著者は染色体と遺伝子を使って先のナップサック問題を解いているため、特定の位置にある遺伝子は上記のナップサック問題の表の項目を表します。例えば、最初の位置が寝袋の場合、染色体に反映される「遺伝子」の位置は染色体の最初の「遺伝子」です。）

ここで、図の 4 つの染色体を集団の開始値として考えます。

4.2 適応度関数

次に、最初の 2 つの染色体の適応度スコアを計算してみましょう。染色体A1[100110]の場合、次のようになります。

同様に、染色体A2[001110]については次のようになります。

この問題では、染色体に生存スコアが多く含まれているほど、適応性が強いことを意味すると考えています。

したがって、図から、染色体 1 の方が染色体 2 よりも適応性が高いことがわかります。

4.3 選択

今、私たちは集団から適切な染色体を選択し、それらを互いに「交配」させて、次の世代を生み出すことができます。これが選択操作の一般的な考え方ですが、数世代後には染色体同士の差が少なくなり、多様性が失われてしまいます。したがって、通常はルーレットホイール選択方式を使用します。

[[200537]]

ルーレットのホイールを想像してください。これを m 個の部分に分割します。ここで、m は集団内の染色体の数を表します。ルーレットホイール上の各染色体が占める領域は、その適応度スコアに比例して表現されます。

上図の値を基に、次のような「ルーレットホイール」を構築します。

ここで、ルーレットが回転し始め、図の固定点が指す領域を最初の親として選択します。次に、2 番目の親に対して同じことを行います。場合によっては、次に示すように、途中で 2 つの固定ポインターをマークすることもあります。

このようにして、1 ラウンドで 2 つの親を取得できます。この方法を確率的普遍選択法と呼びます。

4.4 クロスオーバー

前のステップでは、子孫を生み出すことができる親の染色体を選択しました。したがって、生物学的な観点から言えば、いわゆる「交配」は実際には生殖を指します。次に、以下に示すように、染色体 1 と 4 (前の手順で選択) を「交差」させます。

これはクロスオーバーの最も基本的な形式であり、「シングルポイントクロスオーバー」と呼ばれます。ここでは、交差ポイントをランダムに選択し、交差ポイントの前後の染色体の部分を交差交換して、新しい子孫を生成します。

交差点を 2 つ設定する場合、この方法は「マルチポイント交差点」と呼ばれます。下の図を参照してください。

4.5 突然変異

この問題を生物学的観点から見ると、次のような疑問が湧きます。「上記のプロセスによって生み出された子孫は、親と同じ特徴を持っているでしょうか?」答えは「はい」です。子孫が成長するにつれて、遺伝子に何らかの変化が生じ、親とは異なる存在になります。このプロセスを「突然変異」と呼びます。これは染色体上で発生するランダムな変化として定義できます。突然変異があるために、集団に多様性が存在するのです。

次の図は、突然変異の簡単な例を示しています。

突然変異が完了すると、新しい個体が得られ、進化が完了します。全体のプロセスは次のとおりです。

「遺伝子変異」のラウンドの後、適応度関数を使用してこれらの新しい子孫を検証します。関数によって十分に適応していると判断された場合、それらは集団から適応度が不十分な染色体を置き換えるために使用されます。ここで疑問があります。子孫が最適な適応レベルに達したかどうかを判断するには、どのような基準を使用すればよいのでしょうか。

一般的に言えば、終了条件はいくつかあります。

X 回の反復後、全体的に大きな変化はありません。
アルゴリズムの進化回数を事前に定義します。
適応度関数が事前定義された値に達したとき。

さて、これで遺伝的アルゴリズムの基礎について基本的な理解が得られたと想定し、それをデータサイエンスのシナリオに適用してみましょう。

5. 遺伝的アルゴリズムの応用

5.1 特徴選択

考えてみてください。データサイエンスのコンテストに参加するたびに、ターゲット変数を予測するために重要な特徴を選択するためにどのような方法を使用していますか? 多くの場合、モデル内の特徴の重要性を判断し、しきい値を手動で設定して、そのしきい値よりも重要度が高い特徴を選択します。

では、この問題をよりうまく対処する方法はあるのでしょうか? 実際、特徴選択タスクの最も高度なアルゴリズムの 1 つは遺伝的アルゴリズムです。

ナップサック問題に対処するための以前のアプローチは、ここで完全に適用できます。さて、まずは「染色体」集団の構築から始めましょう。ここでの染色体は依然としてバイナリ文字列であり、「1」はモデルに特徴が含まれていることを意味し、「0」はモデルに特徴が含まれていないことを意味します。

ただし、違いが 1 つあります。それは、適応度関数を変更する必要があるということです。ここでの適合関数は、この競争における精度の基準となるはずです。つまり、染色体の予測値がより正確であればあるほど、その染色体の適応度は高いと言えます。

さて、この方法についてはある程度ご存知かと思います。この問題の解決策をすぐには説明しませんが、まずは TPOT ライブラリを使用して実装してみましょう。

5.2 TPOTライブラリを使用して実装する

この部分は、この記事を初めて読んだときに達成したかった究極の目標であると信じています。つまり、実現です。まず、scikit-learn ライブラリ上に構築された TPOT ライブラリ (ツリーベースのパイプライン最適化手法) を簡単に見てみましょう。次の図は基本的な転送構造を示しています。

図の灰色の領域は、TPOT ライブラリを使用して自動的に処理されます。この部分の自動処理を実現するには遺伝的アルゴリズムが必要です。

ここでは詳しく説明しません。直接適用します。 TPOT ライブラリを使用できるようにするには、まず TPOT の基盤となるいくつかの Python ライブラリをインストールする必要があります。早速インストールしてみましょう:

 # DEAP、update_checker、tqdm をインストール
 
 pip インストール deap update_checker tqdm
 # TPOTのインストール
pip インストール tpot

ここでは、Big Mart Sales（データセットアドレス：

https://datahack.analyticsvidhya.com/contest/practice-problem-big-mart-sales-iii/) データセットを使用します。実装の準備として、まずトレーニングファイルとテストファイルをすばやくダウンロードします。以下は Python コードです。

 # 基本ライブラリをインポートする
 
 numpyをnpとしてインポートする
pandasをpdとしてインポートする
matplotlib.pyplot を plt としてインポートします。
 %matplotlib インライン
sklearn インポート前処理から
sklearn.metricsからmean_squared_errorをインポートする
## 前処理
平均補完
 
 train['Item_Weight'].fillna((train['Item_Weight'].mean()), inplace = True )
 test['Item_Weight'].fillna((test['Item_Weight'].mean()), inplace = True )
 ### 脂肪含有量を2つのカテゴリーに減らす
 
 train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat'])
 train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['reg'], ['Regular'])
 test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat'])
 test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['reg'], ['Regular'])
 train['アウトレット設立年'] = 2013 - train['アウトレット設立年']
 test['アウトレット設立年'] = 2013 - test['アウトレット設立年'] 
 
 train['Outlet_Size'].fillna('Small', inplace = True )
 test['Outlet_Size'].fillna('Small', inplace = True ) 
 
トレーニング['Item_Visibility'] = np.sqrt(トレーニング['Item_Visibility'])
テスト['Item_Visibility'] = np.sqrt(テスト['Item_Visibility']) 
 
 col = ['アウトレットサイズ','アウトレット場所タイプ','アウトレットタイプ','アイテムの脂肪含有量']
 test['Item_Outlet_Sales'] = 0combi = train .append(test)for i in col:
 combi[i] = number.fit_transform(combi[i].astype('str'))
 combi[i] = combi[i].astype('オブジェクト')
列車=コンビ[:train.shape[0]]
テスト=コンビ[train.shape[0]:]
 test.drop('Item_Outlet_Sales', axis = 1 , inplace = True )
 ## ID変数の削除
 
 tpot_train = train.drop(['Outlet_Identifier','Item_Type','Item_Identifier'], axis = 1 )
 tpot_test = test.drop(['Outlet_Identifier','Item_Type','Item_Identifier'], axis = 1 )
ターゲット= tpot_train ['Item_Outlet_Sales']
 tpot_train.drop('Item_Outlet_Sales', axis = 1 , inplace = True )
 # 最後に tpot ライブラリを使用してモデルを構築します
 
 tpotからTPOTRegressorをインポートする
X_train、X_test、y_train、 y_test = train_test_split (tpot_train、ターゲット、
トレーニングサイズ= 0.75 、テストサイズ= 0.25 ) 
 
 tpot = TPOTRegressor (世代= 5 、 population_size = 50 、 verbosity = 2 )
 tpot.fit(X_train、y_train) を使います。
 tpot.score(X_test, y_test) を印刷します。
 tpot.export('tpot_boston_pipeline.py')

このコードが完成すると、パス最適化の Python コードが tpot_exported_pipeline.py に配置されます。 ExtraTreeRegressor がこの問題を完璧に解決できることがわかります。

 ## tpot最適化パイプラインを使用した予測
 
 tpot tpot_pred = tpot.predict(tpot_test)
 sub1 = pd .DataFrame(データ= tpot_pred )
 # sub1.index = np .arange(0, len(test)+1) 
 
 sub1 sub1 = sub1.rename(列= {'0':'Item_Outlet_Sales'})
 sub1['Item_Identifier'] = test['Item_Identifier']
 sub1['アウトレット識別子'] = test['アウトレット識別子']
 sub1.columns = ['Item_Outlet_Sales','Item_Identifier','Outlet_Identifier']
 sub1 sub1 = sub1[['Item_Identifier','Outlet_Identifier','Item_Outlet_Sales']]
 sub1.to_csv('tpot.csv',インデックス= False )

この csv を提出していただければ、私が最初に約束したことが完全には実行されていないことがわかります。嘘をついているでしょうか？もちろん違います。実際、TPOT ライブラリには単純なルールがあります。 TPOT を十分な時間実行しないと、問題に対する最も可能性の高い配信方法が見つかりません。

つまり、進化の数を増やし、コーヒーを飲んで散歩に出かければ、あとは TPOT がやってくれるのです。さらに、このライブラリを使用して分類問題を処理することもできます。詳細については、このドキュメントを参照してください: http://rhiever.github.io/tpot/。競争に加えて、遺伝的アルゴリズムは生活の中の多くの応用シナリオでも使用できます。

6. 実践的な応用

遺伝的アルゴリズムは現実世界で多くの応用があります。ここで興味深いシーンをいくつか挙げましたが、スペースの都合上、一つ一つ詳しく説明することはしません。

6.1 エンジニアリング設計

エンジニアリング設計では、設計サイクルプロセスを高速かつ経済的にするために、コンピューターモデリングとシミュレーションに大きく依存しています。遺伝的アルゴリズムはここで最適化を実行し、良好な結果をもたらすことができます。