この記事は、遺伝的アルゴリズムとは何かの簡単な概要です。 バイオインフォマティクスの初心者である私は、専門分野の人々にとって身近で理解しやすいものから始めます：アルゴリズムの並べ替え、次に、遺伝プログラミングの問題の1つと、生物学者がアルゴリズムで理解することについて説明します。
仕分け
すべてのプログラマーは、このテーマについてすべてではないとしても、ほとんどすべてを知っていると暗黙的に信じていると思います。 たぶんそれはそうであり、これらの行の読者はドナルド・クヌースによる「プログラミングの芸術」の第3巻を研究しました。 しかし、実験してみましょう。お気に入りのアルゴリズムを使用し、紙に鉛筆で実装してみてください。 お気に入りのアルゴリズムがなければ、バブルでソートすることをお勧めします。 うまくいきましたか？ 私はインタビューでこのタスクを繰り返し申し出られましたが、提案された選択肢のいくつかは労働者であることが判明し、「バブル」のように見えたのはわずかでした。 最近、たまたまPythonについての講義ノートを見ました。そこでは、教師は、バブルによるソートを装って、次のコードを提供します。
def bubble_sort(numbers): for first in range(0, len(numbers)-1): for second in range(first+1, len(numbers)): if numbers[first] > numbers[second]: numbers[first], numbers[second] = numbers[second], numbers[first]
アルゴリズムは機能しており、ソートされますが、これは明らかに「バブル」ではありません。 わずかなストレッチでは、選択による並べ替えと呼ぶことができますが、残念な見落としがあります：選択による並べ替えの利点は、置換の数を最小限に抑えることです。つまり、要素をスワップする回数は、上記のコードでは観察されないO（n）に制限されるべきです。
アルゴリズムをテーマにした会話では、クイックソートの問題を反転させることが興味深い場合があります。 原則として、人々はそれがどれほど優れているかという質問に簡単に答えます。これは平均的にはアルゴリズムの複雑さであり、追加のメモリは必要ありません（通常はスタックを忘れます）。 しかし、彼女に加えて他の多くのアルゴリズムがあるので、なぜ悪いのでしょうか？ この質問に対する答えははるかに少なく、単調です。 また、クイックソートにはどのような欠点がありますか？
私の喜びとして、エキゾチックな方法、たとえばgnome sortの知識を示す麻酔に会えることもあります。
結論：
1.面接でエステに合格したい場合は、あまり知られていないいくつかのソート方法を学びます。
2.面接を受け入れた場合、異なる方法を互いに区別できるようにします。そうしないと、候補者がわからない、次の段落1 ...
パンケーキ選別
上記のヒントに従って、実用的な意味はありませんが、理論的な観点から興味深いタスクであるパンケーキソートを検討します。 その非実用性は、このアルゴリズムでは要素の比較の数がまったく考慮されていないという事実にあり（これらの操作は非常に安価で高速であると考えられています）、価格のある唯一の操作はソートされた「パンケーキ」のスタックを反転させることです もちろん、最初はランダムな順序で配置されており、望みの結果はハノイの塔のようなもので、大きな直径のパンケーキが下にあり、小さなパンケーキが上にあります。
この問題に関して、2つの興味深い事実に注目したいと思います。 最初に、悪名高いビル・ゲイツによって、彼がまだ学生であった間に、十分に効果的な（最適ではないにせよ）ソリューションを見つける方法が一度に提案されました。 1979年に提案されたこのアルゴリズムは、結果が上回る2008年まで最も効率的でした。 第二に、後で証明されたように、最適解を見つける問題はNP完全解のクラスに属します。 ゲイツと彼の指導者クリストス・パパディミトリオウはまた、焼けたパンケーキ問題として知られる問題の複雑なバージョンを提案しました。
焦げたパンケーキの問題
この形式の問題では、各要素はサイズに加えてバイナリ属性「方向」も持っています。つまり、「パンケーキ」ごとに片側が焼け、もう片側がバラ色です。 問題を解決した結果、サイズで並べ替えられたスタックになりますが、さらに、すべての「パンケーキ」が横向きに焼かれます。 詳細に説明することなく、この問題はNP完全であり、一般的な場合、十分に効果的だが最適ではない解決策が知られていると言います。 ただし、データには制限があり、完了するとタスクは多項式になります。 この問題では、そのようなデータは単純な順列です。 それが何であるかを理解するために、1から7までの数字の順列を考えてください：2 6475 13.太字のシーケンス自体は4から7までの数字の順列（ ブロックと呼ばれる）であることに注意してください。 単純な順列は、重要なブロック（長さ1およびnのブロック）がない場合です。
問題の比formulation的な定式化の背後で、要素が焦げたパンケーキで表される場合、それが生物学的に重要であるという事実を識別することは困難です。 ただし、一般的な突然変異はDNA分子のフリップであり、1つの分子を別の分子に変換するのに必要なフリップの最小数を（小さな点突然変異を考慮せずに）計算すると、生物の親和性を大まかに推定できます。 たとえば、ヒトとマウスのゲノムは、約120のグローバルな変異によってのみ分離されています。 私は認める、私はこれらのタイプの間にはるかに違いがあると信じていた...
焦げたパンケーキの問題を解決するための遺伝的アルゴリズム
比較ゲノミクスでは、アルゴリズムを使用して、生物を分離する突然変異の数を分析的に見つけますが、別の予測で問題を見てみましょう。 次に、分析問題の解決策を目標として宣言し、生体とその中で行われるプロセスを解決策のツールにします。
ご存知のように、バクテリアは、必要な条件が与えられている場合、人口の指数関数的な成長を提供するように分割することができます。 もちろん、しばらくするとバクテリアのコロニーには栄養培地がなくなり、コロニーの成長に影響する他の要因も現れますが、これには時間がかかります。 実験的に、特定の種の細菌がDNAの一部の反転に関連する全体的な変異に現れるまでにかかる平均時間を見つけることができます。
次に、バクテリアのタスクを設定しましょう。 私たちはそれらの1つを遺伝的に改変します（生物学者はそのような実験で大腸菌を使用するのが好きです）、抗生物質耐性遺伝子をいくつかの部分に分けて混合し、順序だけでなくいくつかの部分の方向も変えます。 したがって、私たちの場合、遺伝子のそれぞれの逆向きに並べ替えられた部分は、「焼きパンケーキ」になります。
バクテリアの課題が提起され、実験を開始できます。 それを栄養培地に入れ、突然変異フリップDNAの出現が予想される割り当てられた時間を待ちます。 私たちが1つの突然変異と考えるものに注意を引きます。それはコロニー全体に固有のものではありません（コロニーにはこれらの突然変異の多くがあります）。 これは、それぞれの生きている細菌の前駆細胞と比較した、予想される隆起の数です。
1つのパンケーキフリップで問題を解決できますか？ コロニーの一部を危険な環境に置くことで、これを簡単に確認できます。 抗生物質に入れられたバクテリアは生き残りませんでした。残りのバクテリアの監視を続けます。 さらに2つか3つの期間が経過し、最終的に抗生物質に入れられた細菌のグループで、それらは生きたままになります。 「集合的な心」は仕事に対処しました！
まとめ
もちろん、解決された問題の有用性は私たちに感銘を与えそうにありません：実施された実際の実験では、ソートされた「パンケーキ」の数は4を超えず、割り当てられた時間内に発生する突然変異の数は確率的にのみ推定できます。 それでも、個人的には、実験を設定できる生物学者の想像力に驚かされました。 生物学的手法によって巡回セールスマンの問題を解決できた人たちも、想像力に欠けていませんでした（この実験の詳細はこの記事の範囲外です）。 多くの点で、遺伝的アルゴリズムによって解決されるタスクの複雑さは量子コンピューティングに匹敵し、非古典的なコンピューティングの両方の領域が、現代の状況ではまだ達成できない結果をもたらすと信じたい。