年末年始が過ぎたので、BrainFuckのことを思い出しました。 あなた自身の海戦を書きたいという願望はありませんでしたが、私はおとぎ話の「まあ、プログラム、自分で書いてください！」で好きになりたかったです。
基礎は、 「Hello world！」という記事でした。 したがって、すぐに次の問題の解決に進みます。特定の文字列を表示するBrainFuckの遺伝的アルゴリズムを使用してプログラムを作成するプログラムを作成します。 Javaで実装します。
最初にBFコードインタープリターが必要です。ホイールの再発明は行わず、 BFIライブラリを使用します* Copyright©2003 Thomas Cort 。 実験のために、私は彼女に別のスレッドで実行する機能を追加しました。
プログラム記述のクラス：
class Individ implements Comparable
{
//
String data;
//
double fitness;
// .
// fitness ""
public int compareTo(Object o)
}
それでは、遺伝的アルゴリズムの作成に取りかかりましょう。 アルゴリズムの段階を図に示します：
1つは母集団の形成です。BF言語の辞書からオペランドをランダムに配置することで取得します。
再生機能は交配を担当し、ランダムな個体を2つ受け取り、2つの部分に分割し、結果の半分をペアで接着します。
3種類の突然変異が実装されています。
1）あるオペランドを別のオペランドに置き換える。
2）オペランドのランダムな位置への追加。
3）ループを追加します。
3番目の項目が導入された理由は ループは「[」と「]」で構成され、一度に1つずつ追加すると、プログラムは正しくなくなります。
最も難しい機能は、個人の適合性を計算することです。 適合値は、プログラムの結果が目的の値からどれだけ逸脱しているかを示します。
最初に思いついたのは、文字列内の文字の差の合計、たとえばabc-aaa = 3を検討することでしたが、このアプローチでは、遺伝的アルゴリズムはローカルの極値点をすばやく見つけて、サイクルを繰り返します。
例を見てみましょう。 文字列「abb」とプログラムを取得します。
+++++++ [<+++++++++++++++>-] <...
「bbb」にそのようなプログラムの適合性を表示します1.「a」を取得する最初の位置を取得するには、サイクルの後に「-」を入力する必要があります。
+++++++ [<+++++++++++++++>-]-<...
このプログラムはすでに「aaa」と表示されていますが、その適合性は2になっており、これはさらに悪く、この「個人は死にます」。
したがって、シンボルの位置に応じて、abc-aaa = | a-a |などの適合性を考慮します。 * 100 ^ 3 + | b-a | * 100 ^ 2 + | c-a | * 100 ^ 1 =100200。このアプローチのおかげで、左側のキャラクターの優先度が高くなります。
選択は、適合性の降順での単純なソートです。
そして、プログラムを取得するまで、乗算と突然変異を行います。
そして、文字列「Hello」に対するプログラムの結果は次のとおりです。
449世代
プログラムの長さ：236文字。 プログラムテキスト：+++++++++++++++++++> +++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++> ++++++++++++++> ++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++。++++++++++ ++-+++++++++++++++++++。++-++++++ .. +++。>
code.google.comのソースコード
イフォルダーミラー