チューリング機械への遺伝的アルゴリズムの応用に関する
考察 。
外部環境から受け取ったいくつかの情報がバイナリコードで表示され、チューリングマシンがあります。 そして、もし、遺伝的アルゴリズムを利用して
チューリングマシンプログラムをコンパイルしたらどうでしょう。
次に、特定のデータを変換し、変更されたプログラムの結果を標準ソリューションと比較します。
MTの最も単純なアルゴリズムを例にとります。 2進数を1つ増やします。 次のようになります。
1q1-> 1q1R
0q1-> 0q1R
Bq1-> Bq2L
1q2-> 0q2L
0q2-> 1q3L
Bq2-> 1STOP
0q3-> 0q3L
1q3-> 1q3L
Bq3-> BSTOPR
しかし、遺伝的アルゴリズムを使用して取得する必要があります。
1.遺伝子工学
遺伝的アルゴリズム、チューリングマシンプログラムの構築には、必要です。 限られた染色体変異のセットからゲノムを考え出します。 これは、チューリングマシン用のコマンドの特定のアルファベットで構成されます。
- シンボルが「ゼロ」の場合
- シンボルが「1」の場合
- コード番号の一部に移動します
- 文字が欠落している場合
- キャリッジを左に移動します
- キャリッジを右に移動します
- 上書き記号
- 文字0を書き込む
- 文字1を書く
- プログラムを停止する
ゲノムをコンパートメント、染色体に分割し、それぞれがチューリングマシンプログラムの位置を表し、マシンのアルファベットに比例して染色体を3つの別々の部分（つまり追加の染色体）に分割し、各部分でマシンが実行する必要のあるアクションをエンコードします。
3つのアクションがバイナリでエンコードされます。
- 1番目と2番目の文字は、読み取り可能なコードに入れる文字をエンコードします。
この例では。
文字なし00 ***
ゼロ01 ***
ユニット10 ***
- 3番目と4番目の文字は、行きたい染色体の番号をエンコードします。 プログラム停止
q1 ** 00 *
q2 ** 01 *
q3 ** 10 *
ストップ** 11 *
- 5番目の文字は、読み取りコードの上で読み取りヘッドを移動する方向をエンコードします。
R **** 0
L **** 1
そして、これから、バイナリコードの5ビットサイズのコマンドがあります。
上記から、ゲノムは3つの染色体で構成され、それらは5x3 = 15文字です。
個人は15x3 = 45文字で構成されます。
2.「ペトリ皿」の準備
アルゴリズムの生成を実装するには、必要です。
遺伝物質。生成されたバイナリラインランダムコード生成プログラム。
選択プログラム。選択された遺伝子型を横断します。
つまり、「チューリングマシンは正反対です。」遺伝的アルゴリズムによって生成されたゲノムを通過した後、最初の「Infinite」テープが保存され、必要なバージョンが保存されます。
テープの例：
開始リボン-最終結果。
0001-0010
0100-0101
1011-1100
「チューリングマシンの要件は逆です」
- 遺伝物質を読み取り、処理できるようにします。
- テープで得られた結果を、一致の割合で、結果の標準と比較します。
- 最終結果を持たないゲノムを特定できるようにするため。
- テストに合格しなかったゲノムを破壊します。
3.初期集団の生成
初期集団はバイナリコードワードから生成されます。 5文字、個人ごとに9ワード。
4.人口の選択
結果リボンと参照テープの一致の割合が大きい個人は、種の選択に進みます。
また同じ結果で。 遺伝子の長さが他より短い個体が勝ちます。
5.交配
種の選択は、結果と標準の一致率が最も高い2つの亜種のゲノムの単語の交換によって行われます。
6.突然変異
進化の不可欠な部分。 この場合、種の代表の個々の単語の突然変異があります。 突然変異はまた、より複雑な問題を解決するために重要な追加の染色体の追加を意味します。 MTアルファベットの拡張子を持つ染色体に追加の単語を追加します。
アルファベットまたは染色体の同調の場合、MTの指示、読み取り規則は、ゲノムの最初に必要です。 染色体の数とアルファベットの文字の数の変化は、ゲノムのビット/遺伝子の数に影響を与えるためです。
7.合計
理論的には、この形式で得られるアルゴリズムは最もコンパクトで効率的です。
そして最も重要なことは、人間が理解できることです。
ご清聴ありがとうございました。
これはHabrahabに関する私の最初の記事です。 この記事をさらに書いて、理論から実践に移行する予定です。