introduction genetic algorithms machine learning
例を使用した回帰テストとは
この遺伝的アルゴリズムのチュートリアルでは、遺伝的アルゴリズムとは何か、および機械学習におけるそれらの役割について詳しく説明します。 :
の中に 前のチュートリアル 、人工ニューラルネットワークモデル–多層パーセプトロン、バックプロパゲーション、ラジアルバイアス、およびアーキテクチャを含むKohonen自己組織化マップについて学習しました。
ニューラルネットワークよりもずっと前に登場した遺伝的アルゴリズムに焦点を当てますが、現在はGAがNNに引き継がれています。ただし、GAには、スケジューリング、ゲームのプレイ、ロボット工学、ハードウェア設計、巡回セールスマン問題などの最適化問題など、実際のアプリケーションがまだあります。
遺伝的アルゴリズムは、自然淘汰と遺伝学の進化論に基づいたアルゴリズムです。 GAは適応型ヒューリスティック検索アルゴリズムです。つまり、アルゴリズムは時間とともに変化する反復パターンに従います。これは強化学習の一種であり、正しい道をたどることなくフィードバックが必要です。フィードバックは正または負のいずれかになります。
=> 完全な機械学習トレーニングシリーズを読む
学習内容:
遺伝的アルゴリズムを使用する理由
GAは、さまざまな最適化問題に使用できる、より堅牢なアルゴリズムです。これらのアルゴリズムは、他のAIアルゴリズムとは異なり、ノイズが存在しても簡単に逸脱することはありません。 GAは、大きな空間またはマルチモーダル空間の検索に使用できます。
遺伝的アルゴリズムの生物学的背景
遺伝学は、成長することを意味するギリシャ語の「ジェネシス」に由来しています。遺伝学は、進化の過程における子孫間の遺伝因子、類似点、および相違点を決定します。遺伝的アルゴリズムも自然進化から派生しています。
生物学的染色体のいくつかの用語
- 染色体: 種のすべての遺伝情報は保存された染色体です。
- 遺伝子: 染色体は遺伝子と呼ばれるいくつかの部分に分かれています。
- 対立遺伝子: 遺伝子は、個人の特徴を識別します。遺伝子の組み合わせが特性を形成する可能性は、対立遺伝子と呼ばれます。遺伝子は異なる対立遺伝子を持つことができます。
- 遺伝子プール: 集団プール内のすべての対立遺伝子である遺伝子のすべての可能な組み合わせは、遺伝子プールと呼ばれます。
- ゲノム: 種の遺伝子のセットはゲノムと呼ばれます。
- 軌跡: 各遺伝子は、遺伝子座と呼ばれるゲノム内の位置を持っています。
- 遺伝子型: 個人の遺伝子の完全な組み合わせは、遺伝子型と呼ばれます。
- 表現型: デコードされた形式の遺伝子型のセットは、表現型と呼ばれます。
遺伝的アルゴリズムとは
遺伝的アルゴリズムは、進化のための自然なシステムのようにプロセスを刺激します。チャールズ・ダーウィンは、自然進化において、生物学的存在は「適者生存」の原則に従って進化するという進化論を述べました。 GA検索は、「適者生存」の理論を奨励するように設計されています。
GAは、最適化問題を解決するためにランダム検索を実行します。 GAは、以前の履歴情報を使用する手法を使用して、新しい検索スペースでの最適化に向けて検索を指示します。
染色体とGAの相関
人体には遺伝子でできた染色体があります。特定の種のすべての遺伝子のセットは、ゲノムと呼ばれます。生物では、ゲノムはさまざまな染色体に保存されますが、GAではすべての遺伝子が同じ染色体に保存されます。
自然進化と遺伝的アルゴリズムの用語の比較
自然な進化 | 遺伝的アルゴリズム |
---|---|
染色体 | ストリング |
遺伝子 | 特徴 |
アレル | 機能値 |
遺伝子型 | コード化された文字列 |
表現型 | デコードされた構造 |
GAの重要な用語
- 人口: それは個人のグループです。母集団には、テストされる個人の数、検索スペース情報、および表現型パラメーターが含まれます。通常、母集団はランダムに初期化されます。
- 個人: 個人は人口の単一の解決策です。個人は遺伝子と呼ばれるパラメータのセットを持っています。遺伝子が組み合わさって染色体を形成します。
- 遺伝子: 遺伝子は遺伝的アルゴリズムの構成要素です。染色体は遺伝子で構成されています。遺伝子は問題の解決策を決定するかもしれません。それらは、ランダムな長さのビット(0または1)文字列で表されます。
- フィットネス: 適合性は、問題の表現型の価値を示します。適応度関数は、解が最適解にどれだけ近いかを示します。適応度関数は、問題に関連するすべてのパラメーターの合計(ユークリッド距離など)など、さまざまな方法で決定されます。適応度関数を評価する規則はありません。
単純な遺伝的アルゴリズム
単純なGAには、個々の染色体の集団があります。これらの染色体は可能な解決策を表しています。複製演算子は、突然変異と組換えを実行するためにこれらの染色体のセットに適用されます。したがって、GAの動作はそれに依存しているため、適切な複製演算子を見つけることが重要です。
簡単な遺伝的アルゴリズムは次のとおりです。
#1) ランダムに作成された母集団から始めます。
#二) 各染色体の適応度関数を計算します。
#3) n個の子孫が作成されるまで、この手順を繰り返します。子孫は以下のように作成されます。
- 母集団から染色体のペアを選択します。
- 確率pでペアをクロスオーバーしますc子孫を形成する。
- 確率pでクロスオーバーを突然変異させるm。
#4) 元の母集団を新しい母集団に置き換えて、手順2に進みます。
この反復プロセスで実行される手順を見てみましょう。染色体の初期集団が生成されます。初期集団には、任意のソリューションを生成できるように十分な遺伝子が含まれている必要があります。人口の最初のプールはランダムに生成されます。
- 選択: 適応度関数に応じて、最適な遺伝子セットが選択されます。適応度関数が最も良い弦が選択されます。
- 再生: 新しい子孫は、組換えと突然変異によって生成されます。
- 評価: 生成された新しい染色体は、それらの適合性について評価されます。
- 置換: このステップでは、古い母集団が新しく生成された母集団に置き換えられます。
ルーレットホイールの選択方法
ルーレットホイールの選択は、広く使用されている選択方法です。
以下に示すように、選択プロセスは短いです。
この方法では、ルーレットホイールを介して線形探索が行われます。ホイールのスロットは、個々の適応度の値に応じて計量されます。目標値は、母集団の適応度の合計の割合に応じてランダムに設定されます。
次に、目標値に達するまで母集団が検索されます。この方法は、個人の最適性を保証するものではありませんが、最も適切である可能性があります。
ルーレットホイールの選択に関連する手順を見てみましょう。
個人の期待値=個人の適応度/母集団の適応度。ホイールスロットは、個人の適応度に基づいて割り当てられます。ホイールはN回回転します。ここで、Nは母集団内の個体の総数です。 1回のローテーションが終了すると、選択した個人が親のプールに入れられます。
- 母集団内の多数の個人の合計期待値をSとします。
- 手順3〜5をn回繰り返します。
- 0からSまでの整数sを選択します。
- 母集団内の個人をループし、合計がsより大きくなるまで期待値を合計します。
- 期待値が合計を制限sを超える個人が選択されます。
ルーレットホイールの選択の欠点:
- 適応度が大きく異なる場合、ルーレットホイールの円周は、最も高い適応度関数の染色体によって最大になります。そのため、他の人が選択される可能性はほとんどありません。
- うるさいです。
- 進化は、人口の適応度の分散に依存します。
その他の選択方法
で使用される他の多くの選択方法があります '選択' 遺伝的アルゴリズムのステップ。
他に広く使用されている2つの方法について説明します。
#1)ランクの選択: この方法では、すべての染色体にランク付けから適合度の値が与えられます。最悪の適合度は1で、最高の適合度はNです。これは遅い収束方法です。この方法では、多様性が維持され、検索が成功します。
潜在的な親が選択され、トーナメントが開催されて、どの個人が親になるかが決定されます。
#2)トーナメントの選択: この方法では、選択圧戦略が母集団に適用されます。最高の個人は、最高の適応度を持つ人です。この個人は、人口のNu個人間のトーナメント競争の勝者です。
トーナメントの人口と勝者が再びプールに追加され、新しい子孫が生成されます。勝者と交配プール内の個体の適応度の値の違いは、最適な結果を得るための選択圧を提供します。
クロスオーバー
それは2人の個人を取り、それらから子供を生み出すプロセスです。選択後の複製プロセスは、良い刺し傷のクローンを作ります。クロスオーバー演算子は、より良い子孫を生成するために弦に適用されます。
クロスオーバー演算子の実装は次のとおりです。
- 子孫を生み出すために、集団から2個体がランダムに選択されます。
- クロスサイトは、文字列の長さに沿ってランダムに選択されます。
- サイトの値が交換されます。
実行されるクロスオーバーは、シングルポイントクロスオーバー、2ポイントクロスオーバー、マルチポイントクロスオーバーなどです。シングルポイントクロスオーバーには1つのクロスオーバーサイトがあり、2ポイントクロスオーバーサイトには値が交換される2つのサイトがあります。
これは、以下の例で確認できます。
シングルポイントクロスオーバー
2点クロスオーバー
クロスオーバー確率
Pc、クロスオーバー確率は、クロスオーバーが実行される頻度を表す用語です。 0%の確率は、新しい染色体が古い染色体の正確なコピーになることを意味し、100%の確率は、すべての新しい染色体がクロスオーバーによって作成されることを意味します。
突然変異
突然変異はクロスオーバーの後に行われます。クロスオーバーは現在の解にのみ焦点を合わせますが、突然変異操作は検索空間全体を検索します。この方法は、失われた遺伝子情報を回復し、遺伝情報を配布することです。
このオペレーターは、集団の遺伝的多様性を維持するのに役立ちます。これは、極小値を防ぎ、母集団から役に立たないソリューションを生成するのを防ぎます。
突然変異は、各遺伝子の値を小さな確率で反転したり、ソリューションの品質が向上する場合にのみ突然変異を実行したりするなど、さまざまな方法で実行されます。
突然変異の方法のいくつかは次のとおりです。
- フリッピング: 0から1または1から0に変更します。
- 交換: 2つのランダムな位置が選択され、値が交換されます。
- 逆転: ランダムな位置が選択され、その隣のビットが逆になります。
それぞれの例をいくつか見てみましょう。
フリッピング
交換
逆転
突然変異の確率
Pm、突然変異確率は、染色体が突然変異する頻度を決定する用語です。突然変異の確率が100%の場合、染色体全体が変化していることを意味します。突然変異が実行されない場合、新しい子孫はクロスオーバーの直後に生成されます。
一般的な遺伝的アルゴリズムの例 突然変異の確率: Pm、突然変異確率は、染色体が突然変異する頻度を決定する用語です。突然変異の確率が100%の場合、染色体全体が変化していることを意味します。
突然変異が実行されない場合、新しい子孫はクロスオーバーの直後に生成されます。染色体の初期集団はA、B、C、Dとして与えられます。集団サイズは4です。
適応度関数は、文字列内の1の数と見なされます。
染色体 | フィットネス |
---|---|
宛先:00000110 | 二 |
B:11101110 | 6 |
C:00100000 | 1 |
D:00110100 | 3 |
適応度の合計は12です。これは、平均適応度関数が〜12 / 4 = 3になることを意味します。
クロスオーバー確率= 0.7
突然変異確率= 0.001
#1) BとCが選択されている場合、Cの適応度値が平均適応度を下回っているため、クロスオーバーは実行されません。
#二) Bが変異している=> B:11101110-> B':人口の多様性を維持するための01101110
#3) BとDを選択すると、クロスオーバーが実行されます。
B:11101110 E:10110100 –> D:00110100 F:01101110
#4) Eが変異している場合、
E:10110100-> E':10110000
対応する染色体を下の表に示します。注文はランダムに行われます。
染色体 | フィットネス |
---|---|
A:01101110 | 5 |
B:00100000 | 1 |
C:10110000 | 3 |
D:01101110 | 5 |
適応度の値が6の適者生存は失われますが、母集団の全体的な平均適応度は増加し、次のようになります。14/ 4 = 3.5
遺伝的アルゴリズムをいつ停止するか
以下にリストされているいくつかの条件が満たされると、遺伝的アルゴリズムは停止します。
#1)最高の個人の収束: 最小適合レベルが収束値を下回ると、アルゴリズムは停止します。それはより速い収束につながります。
#2)最悪の個人の収束: 母集団の中で最も適合度の低い個体が収束を下回る最小適合度値に達すると、アルゴリズムは停止します。この方法では、母集団の最小適合基準が維持されます。これは、最高の個人が保証されているわけではありませんが、最小の適応度の個人が存在することを意味します。
#3)フィットネスの合計: この方法では、適合度の合計が収束値以下の場合、検索は停止されます。これにより、すべての母集団がフィットネス範囲内にあることが保証されます。
#4)適応度の中央値: この方法では、母集団の少なくとも半分の個体が収束値以上になります。
いくつかの収束基準または停止条件は次のとおりです。
- 指定された世代数が進化したとき。
- アルゴリズムを実行するための指定された時間に達したとき。
- 母集団の適応度の値が反復によってそれ以上変化しない場合。
遺伝的アルゴリズムの長所と短所
遺伝的アルゴリズムの利点は次のとおりです。
- それはより広い解空間を持っています。
- グローバル最適を見つけるのは簡単です。
- 並列処理: 複数のGAは、互いに干渉することなく、同じCPUを使用して一緒に実行できます。それらは単独で並行して実行されます。
Limitations of GA:
- 適応度関数の識別は制限です。
- アルゴリズムの収束が速すぎたり遅すぎたりする可能性があります。
- クロスオーバー、突然変異確率、母集団のサイズなどのパラメーターの選択には制限があります。
遺伝的アルゴリズムの応用
GAは高次元の問題を解決するのに効果的です。 GAは、検索スペースが非常に大きく、数学的な問題解決手法が利用できず、他の従来の検索アルゴリズムが機能しない場合に効果的に使用されます。
GAが使用されるいくつかのアプリケーション:
- 最適化問題: 最適化問題の最良の例の1つは、GAを使用する巡回セールスマン問題です。ジョブスケジューリング、音質最適化GAなどの他の最適化問題が広く使用されています。
- 免疫システムモデル: GAは、進化の時期に個々の遺伝子および複数遺伝子ファミリーの免疫系のさまざまな側面をモデル化するために使用されます。
- 機械学習: GAは、分類、予測に関連する問題を解決し、学習と分類のルールを作成するために使用されてきました 。
結論
遺伝的アルゴリズムは、自然進化の方法に基づいています。これらのアルゴリズムは、エンコードされたパラメーター(0または1)を使用し、母集団に複数の個体があり、収束に確率的手法を使用するため、他の分類アルゴリズムとは異なります。
クロスオーバーと突然変異のプロセスにより、GAは次の世代に収束します。 GAアルゴリズムの実行は、常に成功するソリューションを保証するものではありません。遺伝的アルゴリズムは、最適化、つまりジョブスケジューリング問題において非常に効率的です。
このチュートリアルが遺伝的アルゴリズムの概念に関する知識を深めることを願っています!!
=> 独占的な機械学習シリーズについては、こちらをご覧ください
推奨読書
- 遺伝的アルゴリズムを使用したモデルベースのテスト
- データマイニングvs機械学習vs人工知能vsディープラーニング
- 機械学習チュートリアル:MLとそのアプリケーションの概要
- 機械学習の種類:教師なし学習と教師なし学習
- 機械学習における人工ニューラルネットワークの完全ガイド
- 112021年に最も人気のある機械学習ソフトウェアツール
- トップ13の最高の機械学習会社[2021年のリストを更新]
- 機械学習におけるサポートベクターマシン(SVM)とは