生物学の先生：数学の先生、行ってください、私がこの問題を解きます！

自然は人類にとって尽きることのない革新的なインスピレーションの源です。自然界の生物は並外れた適応力と知恵を持っています。アリのコロニーはどのようにして食料源への最短経路を見つけるのか、野生のガチョウはどのようにして餌を探すときに最短距離を飛ぶのか、生物はどのようにしてさまざまな特性を進化させるのか...これらの法則を合理的に利用することで、数学の問題を解決することができるのでしょうか?

（写真提供：veerフォトギャラリー）

そうです。従来の数学理論では解決が難しい問題を扱っています。

最適化問題とヒューリスティックアルゴリズム

まず、数学の問題を見てみましょう。

次の二次関数の最大値を計算します。

この単純な目的関数には、次の式を直接適用できます。独立変数 x=-b/2a の場合、目的関数の最大値は (4ac-b^2)/4a です (忘れた場合は、高校の数学の先生に問い合わせてください)。この直接式として表現できる解を解析解と呼びます。

簡単な質問であれば、1ステップで答えを得ることができます

関数の最大値/最小値を見つけるこの問題は最適化問題であり、この関数は目的関数と呼ばれます。最適化アルゴリズムは、目的関数の最小値を計算するアルゴリズムです。

実際には、最適化問題の目的関数は複雑であることが多く、解析的に解決することはできません。したがって、反復解法には勾配（多変量関数の導関数）がよく使用されます。

ただし、より複雑な目的関数の場合、勾配法は使用できません。例えば、次の関数の最小値を計算するには

複雑な目的関数、式は適用できません

従来の勾配法を使用すると、大域的最適値 (Global Optimum) 、つまり全体範囲内の最大点ではなく、局所的最適値 (Local Optimum) 、つまり一定の範囲内の最大点に収束する傾向があります。

勾配法は局所最適に陥りやすい

同様の複雑な機能を最適化することは、常に難しい問題でした。科学者たちは、特定の自然法則にヒントを得て、自然アルゴリズムをシミュレートし、従来の数学理論では解決が難しい最適化問題に対処するためのいくつかのヒューリスティックアルゴリズムを提案しました。

たとえば、アリのコロニーが食物を見つけて輸送する法則をシミュレートすることで、アリコロニーアルゴリズムが提案されました。空中で餌を探すガチョウの法則をシミュレートすることで、粒子群最適化アルゴリズムが提案されました。生物学的遺伝と進化の法則をシミュレートすることによって、遺伝的アルゴリズムが提案されました...

アルゴリズム科学者は生物遺伝学と進化についてどう考えているのでしょうか?

この記事で紹介するヒューリスティック アルゴリズムは、生物の遺伝学と進化の法則をシミュレートすることによって提案されています。では、アルゴリズム科学者の目から見ると、遺伝学と進化はどのように見えるのでしょうか?ここでは、キリンの進化を例に挙げます (遺伝的アルゴリズムは既知の進化法則を模倣したものであり、必ずしも生物学的法則と同等ではないことに注意してください)。

自然界には多くの種類の生物が存在し、その特性は遺伝子と外的要因の両方によって決定されますが、遺伝子が支配的な役割を果たすため、ここでは外的要因は無視されます。たとえば、キリンの首の長さは遺伝子によって決まります。

遺伝子は生物の遺伝物質であり、「AaBbCc」のように複数のヌクレオチドで構成されています。集団の進化は必然的に遺伝的変化を意味します。

自然選択は遺伝子に直接作用するのではなく、形質に作用します。個人はそれぞれ異なる特性を持ち、生き残るための能力も異なります。例えば、鹿の首が長ければ長いほど、食べられる葉が多くなり、生存能力が高まります。生存能力は数値化され、適応度と呼ばれます。

適応度は、鹿の首の長さ、体力、視力など、複数の要因によって決まるはずです。しかし、ここでは首の長さだけを考慮します。首が長いほど、フィットネスが高くなります。

（この記事では、遺伝子が形質を決定し、それが生存能力を決定すると仮定しています）

昔々、普通の鹿の群れがいました。それぞれの鹿は異なる遺伝子を持っており、したがって異なる特徴を持っています（ここでの特徴は具体的には首の長さを指します）。この世代の鹿は「鹿の群れ 0」として記録されました。

「鹿の群れ0」では、首の長い個体はより多くの葉を食べることができ、生き残る可能性が高いため、適応度が高いと言えます。首が短い個体は淘汰される可能性が高く、適応度も低くなります。このプロセスは選択と呼ばれ、選択を生き残った鹿だけが交尾することができます。

（写真提供：魂の画家、王莫一）

雄鹿が雌鹿と交配すると、単に自身の遺伝子をコピーするのではなく、雌鹿の遺伝子と交配して組み合わせます（ここでは、遺伝子は染色体と同等であると見なされます）。たとえば、「Aa BbCc」+「aa bbcc」=「Aa bbcc」+「aa BbCc」となります。

もちろん、2つの遺伝子が結合すると、遺伝子の1つまたは複数のヌクレオチドが変異する可能性があります。たとえば、遺伝子 b が遺伝子 B に変異します。

遺伝子の交差

遺伝的変異

このようにして、「Deer Herd 0」は新しい世代を生み出し、「Deer Herd 1」として記録されました。一般的に言えば、選択プロセスの後、「鹿の群れ 1」の適応度の最大値と平均値が増加します。つまり、首の長さの最大値と平均値が増加します。

繁殖を何世代も繰り返すと、遺伝的変化により、「鹿の群れ N」の首は「鹿の群れ 0」の首よりも大幅に長くなり、適応度も高くなります。この時点で、種は進化したと言えます。

人口は最適になる傾向がある

もちろん、最適な首の長さは環境、具体的には樹冠の高さによっても異なります。首が樹冠より高いと、利点よりも欠点の方が多いです。環境が大きく変化しない限り、「鹿の群れN」以降、集団の遺伝子は大きく変化せず、適応度も大きく変化せず、集団は最適解で安定します。

遺伝的アルゴリズムはどのように機能しますか?

アメリカのジョン・ホランドは、ダーウィンの生物進化論における自然選択と遺伝のメカニズムをシミュレートし、ヒューリスティック最適化アルゴリズムである遺伝的アルゴリズムを提案しました。

このアルゴリズムは、独立変数を個体に変換し、エンコードを通じて個体と遺伝子をマッチングさせ、解決すべき目的関数を適応度関数として取り、交差と突然変異を保持し、複数回の反復を経て、集団（複数の個体）が最適解に近づくことができます。

目的関数 F(x)=x+8sin(5x)+5cos(4x) の最大値を例にとると、遺伝的アルゴリズムは 6 つのステップで問題を解決します。

1. 初期化

遺伝的アルゴリズムは、独立変数の可能な値を個体とみなし、全体の集団を設定した後、初期化された集団を生成します。たとえば、母集団に100人の個体がいて、100個の初期値が区間[0,8]内でランダムに選択されたとします。

独立変数の特定の間隔内で初期集団をランダムに生成する

2. エンコードとデコード

独立変数である個体自体は遺伝子とはみなせないため、何らかの方法で変換する必要があります。通常、個体はコーディングと呼ばれる2進数の文字列に変換され、この2進数の文字列は遺伝子とみなすことができます。

たとえば、整数部を表すために 4 ビットのバイナリを使用し、小数部を表すために 2 ビットのバイナリを使用する場合、3.25 は「001101」と表すことができ、「001101」が個体の遺伝子になります。

個人の 3.25 の 2 進表現は 001101 であり、これは遺伝子のシミュレーションです。

コーディングの目的は、遺伝子をシミュレートして、その後の交差と突然変異を実行することです。デコードとは、遺伝子（2 進数）を個体（10 進数）に変換するプロセスです。適応度を計算するために、適応度関数に小数を代入することができます。

3. 適応度の計算

ただし、遺伝子（2 進数）を個体（10 進数）に変換した後、その 10 進数の個体を目的関数に代入することで適応度を得ることができます。

適応度関数は、多くの場合、解くべき目的関数 F(x)=x+8sin(5x)+5cos(4x) であることは理解しにくいことではありません。

4.選択

各個体は適応度に応じて選択されます。適応度が高いものは保持される可能性が高く、適応度が低いものは排除される可能性が高くなります。このプロセスは通常、「ルーレット」モデルを使用して実行されます。

もちろん、選考プロセス中は、個人の数が変わらないようにする必要があります。これを確実にするために、適応度の高い個体は保持されるだけでなく、コピーも行われます。

適応度が高い個体は生き残る可能性が高い

5. 交差と突然変異

残った個体は遺伝子がコード化された後に交配されます。たとえば、「001 101」+「010 010」=「001 010」+「010 101」となります。一般に、交差点はランダムに選択されます。

ここでは、2 つの遺伝子が交配して 2 つの新しい遺伝子が生成されます (両親が双子を産むのと同じ)。したがって、交差によって集団のサイズは変化しません。

交差後、各遺伝子も変異する可能性があります。一般的に言えば、突然変異ポイントもランダムです。たとえば、特定のビットの 1 が 0 に変更されたり、0 が 1 に変更されたりします。

2進数のクロス

2進数の変化

選択後、集団の適応度の最大値と平均値の両方が前世代と比較して向上します。具体的には、すべての個人が目的関数の最高点に向かって集中します。何度も繰り返した後、最大値に集中します。

6. 終わりましたか？

最適化アルゴリズムであるため、終了条件を設定する必要があり、アルゴリズムが無限にループすること（デッドループ）は許可されません。最も簡単な方法は、アルゴリズムの実行回数を設定することです。たとえば、アルゴリズムを 50 回ループさせて終了します。

遺伝的アルゴリズムの一般的なフローチャートは以下のとおりです。

進化が進むにつれて、つまりアルゴリズムが循環するにつれて、集団の平均適応度は世代ごとに増加し、最終的には最大値、つまり私たちが求めている目的関数の最大点に収束します。

遺伝的アルゴリズムを50回実行した後の人口分布：一点に集中

アルゴリズムが反復されるにつれて、集団の平均適応度も向上します。

あらゆるステップに小さな戦略がある

遺伝的アルゴリズムの効率を向上させるために、上記の手順には実際にいくつかのトリックがあります。

1. 初期化

最大点に関する事前情報、つまり最大点が位置するおおよその範囲がわかっている場合。初期人口はこの範囲内で生成できます。そうでない場合は、より広い範囲でランダムに生成する必要があります。

初期値の選択はアルゴリズムの収束速度に影響します。初期値が最適解に近いほど、収束速度は速くなります。さらに、初期値が不適切だと、アルゴリズムが局所最適に陥ってしまう可能性があります。

最適な解決策をより早く見つけることはできますか?

2. エンコードとデコード

デジタル信号処理では、測定値には最小値と最大値が必要です。つまり、変数の値は連続的で無限ではなく、不連続で有限です。測定によって生じる誤差を量子化誤差と呼びます。

たとえば、整数部分を表すために 4 ビットのバイナリを使用し、小数部分を表すために 2 ビットのバイナリを使用する場合、独立変数の最大値は 15.75 (バイナリでは 111111 に相当) のみになり、小数部分では 0.25 の差しか区別できなくなります。測定の最小値は解像度比とも呼ばれます。

F(x)=x+8sin(5x)+5cos(4x)の最適解は7.860ですが、アルゴリズムは7.875にしか収束しません。

もちろん、遺伝子の長さを非常に長くすることもできます。たとえば、整数部分を表すために 100 ビットのバイナリを使用し、小数部分を表すために 10 ビットのバイナリを使用することで、独立変数値の範囲を拡大し、解像度を向上させることができます。ただし、これにより、アルゴリズムの計算の複雑さとストレージ サイズが増加します。

3. 選択

選択の過程で、最も適応度の高い個体が保持され、複製される場合、それはエリート保存と呼ばれます。最も適応度の高い個体が必ずしも保持されず、排除される可能性がある場合、それはエリート保留がないと呼ばれます。

実験では、エリート保持機能を備えた遺伝的アルゴリズムは最適値に速く収束し、より安定していることが示されています。

4. 交差と突然変異

交叉は単点交叉と多点交叉に分けられ、突然変異も単点突然変異と多点突然変異に分けられます。交差と突然変異は、遺伝的多様性を高め、収束を加速し、局所最適性から脱出するために使用されます。

たとえば、すべての個体が局所最適値の近くに集中している場合、突然 1 つの個体が突然変異して全体最適値の近くに「ジャンプ」すると、集団はさらに進化することができます。

集団にとっては多様性よりも安定性が重要なので、交差と突然変異は単一のポイントで実行されることが多く、突然変異の確率は非常に低くなります。

5. 終わりましたか？

アルゴリズムの実行回数を設定することでアルゴリズムの終了を制御するのは簡単ですが、次の 2 つの問題があります。

（１）アルゴリズムの収束が遅い場合、例えば、集団が50回の反復後も最適解に収束しない場合は、結果は必然的に不正確になります。

（２）アルゴリズムが急速に収束する場合、例えば、集団が最適解に収束するのに２０回の反復しかかからない場合、多くの計算リソースが無駄になる。

もう 1 つのより信頼性の高い方法は、隣接する 2 つの操作間の集団の平均適応度の差、つまりそれが特定のしきい値未満であるかどうかを判断することです。はいの場合、アルゴリズムは収束したとみなされ、終了できます。いいえの場合、アルゴリズムは収束していないとみなされ、サイクルが継続されます。

平均適応度差に基づいてアルゴリズムの終了を制御する方が信頼性が高い

遺伝的アルゴリズムは絵を描くだけでなく、次のようなことも教えてくれます。

遺伝的アルゴリズムなどのヒューリスティックアルゴリズムには、極めて厳密な数学的導出はありませんが、自然界ではこれらの法則を利用して無数の問題を解決してきました。今日では、遺伝的アルゴリズムは、空気抵抗を減らすために車両の形状を設計する方法など、私たちの生活の多くの分野で広く使用されています。作業効率を向上させるためにロボットのワークフローをどのように配置するか。速達の距離を最短にするためのルート計画方法...

以前、遺伝的アルゴリズムを使用して特定の絵を描くプロジェクトを GitHub にアップロードした人がいました。以下は、上の写真に基づいて遺伝的アルゴリズムが次の作品をどのように「描く」かを確認するためのシミュレーション例です。

(画像出典: https://github.com/anopara/genetic-drawing)

まず、複数の初期カラーバーを指定してカラーバー画像を形成し、カラーバー画像と元の画像との差を目的関数として使用します。次に、遺伝的アルゴリズムを使用して、目的関数が最小化されるように、つまりカラーバー画像が元の画像に「最も類似」するようにカラーバーの配置を反復的に解決し、複数のカラーバーで元の画像を「描画する」という目標を達成します。

追記: プログラマーでない場合は、当面遺伝的アルゴリズムを使用する必要はありませんが、遺伝的アルゴリズムからいくつかの知恵を学ぶことはできます。

●完璧なアルゴリズムは存在しません。精度を確保するには、計算量を増やす必要があります。すべての戦略は、複数の要素間のバランスを見つける芸術です。

●安定だけを追い求めていては進歩は望めません。多様性だけを追求しても優位性を積み上げることはできません。したがって、安定性と多様性のバランスを見つける必要があります。しかし、長期的には、多様性よりも安定性（蓄積、継承）の方が重要になることが多いです。

●エリート層を維持することは重要ですが、エリート層以外の一般人を決して軽蔑してはいけません。普通の個人がいなければ、突然変異の土壌がなくなり、集団は単調になってしまうでしょう。そして単調さはしばしば脆弱性を意味します。

参考文献:

[1] 鄭淑全.産業知能技術と応用[M]上海：上海科学技術出版社。

[2] 李徳義、于建。人工知能入門、中国科学技術協会新世代情報技術シリーズ[M]。北京：中国科学技術出版社。

著者: 王 莫一

著者の所属: ノースウェスタン工科大学航海学部

この記事は「サイエンスアカデミー」の公開アカウントからのものです。転載の際は公開アカウントの出典を明記してください。