文法進化と簡単な実装とは

ごく最近、私は説明なしで文法進化法が何ができるかを示した記事を書きました 。 私はこれができないことに完全に同意しますが、興味深い方法の結果を示したかったのです。 「何が良いのか：ソースを翻訳するか、あなた自身の説明をする」と思った。 怠azineが勝った。

誰かが進化論的手法とシンボリック回帰のタスク（だけでなく）に興味があるなら、読んでください。

バクスナウア形

最初に、コンテキスト非依存の文法がBakus-Naur（BNFと略される）の形式であるかどうかを言わなければなりません。 Habréの正式な言語と文法については、すでにかなり興味深い記事があります。 読むことを強くお勧めします。 しかし、私たちの目標は、BPFとは何かを理解し、このフォームの使用方法を学ぶことです。

ウィキペディアは完全に適切な定義を提供します。

BNFは、いくつかの構文カテゴリが他のカテゴリを通じて順番に定義される正式な構文記述システムです。 BNFは、文脈自由形式文法を記述するために使用されます。

BNFには終端記号と非終端記号があります。 端末は定数です。 それらを設定しましたが、それで終わりですが、非終端記号を使用すると、すべてがはるかに興味深いものになります。ルールに従って相互に置き換えることができます。

例を考えてみましょう。 文脈自由文法の構文を記述するための次の正式なシステムがあります。





この例では、多くの非終端文字


多くの終端記号は次のように表されます


セットSには1つの要素が含まれます。


この要素は、ルールを構築および操作するためのエントリポイントになります。

これで、1つの非終端要素を使用して、文法に対応する構造を作成できます。

チェーンを追跡する

1）<sntnce> => <副詞> <動詞> =>すばやく<動詞> =>すぐに実行

2）<sntnce> => <名詞> <動詞> => Peter <動詞> => Peter fall

問題が発生します。これらの置換はどのような基準で発生しますか？ この質問には少し後で答えます。

遺伝的アルゴリズム

このアルゴリズムは、進化論の分野では標準的であるように思えます。 実装は簡単で、うまく機能します。 文法進化の方法における「エンジン」としてどのようなメカニズムになるかを理解するには、このアルゴリズムの検討が必要です。 しかし、（!!）の代わりに、あなたにとって便利な他の進化的アルゴリズムを使用できます。

したがって、GAは自然の振る舞いを使用します。 実際、新しいものは何も発明されていません。 このアルゴリズムは何百万年も実行されています。 彼に感謝します。 結局のところ、彼のためでなければ、私たちはそうではなかったでしょう。

GAはいくつかの段階で構成されています。

（1）初期集団の作成（個人ごとに染色体を作成）

（2）各個人のフィットネス関数の計算（この母集団に最適なのは誰であるかを示すのは彼女です）

（3）さらなる子孫の形成のための最良の代表者の選択

（4）クロスオーバー

（5）突然変異

（6）（4）の後、子供を取得し、その一部は（5）を通過します。 出力は子孫です

（7）新世代の父親と子供の選択

（8）子供が与える値が私たちに合わない場合、ステップ（2）に戻る

染色体は、必要な情報のエンコードされた表現です。 プライマリソースはバイナリ表現を使用します。 つまり 4つのパラメーター（それぞれが0から15の範囲）を見つける必要がある場合、パラメーターごとに4ビット（ゼロまたは1）が必要です。 そして、染色体自体の長さは16になります。すべてが原始的です。

重要 ：10進表現を使用できます。 文法の進化のためにそうします。

次に、GAの演算子とあらゆる種類のフィットネス関数について少し説明します。

フィットネス機能 -最適化する必要がある機能。 タスクごとに異なります。 機能を最小化するという質問がある場合、選択にはフィットネス機能をできるだけ持たない親が必要です。

クロスオーバーはクールなものです。 ちなみに、遺伝的プログラミングでは、この演算子は、最高品質の子孫を取得するためのほぼ唯一の演算子です。 一番下の行は、2人の親（またはその遺伝子型）を取得することです。 半分に分けます。 そしてスワップ。 今からお見せします。

次の2つのリストがあります。






これはポイントクロスオーバーの例です。 このテーマには他にもバリエーションがありますが、それらについては説明しません。

突然変異は、特定の遺伝子を誤って置き換えるプロセスです。



新世代で頻繁に使用される選択方法はエリート主義です。 私たちは、子供と親のリストから最高のn人を選びます。 そして、人口をランダムに適切な量まで補充します。

重要：染色体のサイズは固定でも任意でもかまいません。 人口規模についても同じことが言えます。

文法進化

そして今、最も重要なことについて。 これはどのような方法で、何と一緒に食べますか。
一番下の行は、あなたが解決すべき問題があるということです。 Bakus-Naurの形式で文法を構築しています。 各個体が独自の染色体を持つ初期集団を作成します。この染色体には、いつ、どこで、いつ置換するかを規定します。 重要なのは、これらのルールのおかげで、計算に使用できる関数を取得できることです。 定義済み（または未定義）のパラメーターが定義されたこの関数の値は、関数（フィットネス関数）として機能できます。 機能が良くなればなるほど、機能も良くなり、そのため染色体を持つ個人も良くなります。

染色体についての詳細。

次の文法を持ちましょう

<e> :: = <e> <op> <e> | <val>

<val> :: = x | 3 | 2

<op> :: = + | -| * | /

次に、このような染色体があります


最初に、関数のシンボリック表現には1つの非終端記号が含まれます：H = <e>（原則として）。

chromoから最初の要素を取得します。2. <e>への変換にいくつのルールがあるかを検討します。2. 2％2（modulo !!）= 0で除算します。 したがって、H = <e> <op> <e>です。 クロモからデュースを捨てます。 彼女はもう必要ありません。

次の行は1です。 もう一度<e>を見てください。 1％2（置換ルールの数）=1。したがって、<e>の代わりに<val>を置換します。 H = <val> <op> <e>を取得します。

これらの簡単な操作をさらに行うと、このようなチェーンが得られます






次に、この関数を使用して機能を計算し、特定の表現型（関数が呼び出されるとき）と遺伝子型（染色体）で個人がどれだけ適しているかを判断します。

以上です。 はい、いくつかの代替オプションがあります：深さ（考慮）、幅、いわゆる -置換。 しかし、これは別の記事の資料です。

そして今、例。

時間間隔があります 。 機能があります 。 この問題の関数である最小二次誤差を与える関数を見つける必要があります。

コードを見てみましょう

メインモジュール

# -*- coding: utf-8 -*- import GE def foo(x): return 1+x+x**2+x**3 interval = [-5, 5] values =[foo(e) for e in range(interval[0], interval[1])] if __name__ == "__main__": result = GE.GA( chromo_len=12, pop_len=100, count=20 )[0] print(result) 

foo関数は、各個人が作成した関数から取得される値と比較する値を生成します。

染色体の長さ= 15;

人口の長さ= 100;

反復数（進化）= 20;

パーサーモジュール

 # -*- coding: utf-8 -*- import random import re def rand(num): return int(random.random()*num) def parse(chromo): l = len(chromo) j = 0 h = "<expr>" grammar = { "<expr>": ["<expr><op><expr>", "<val>"], "<op>": ["+", "-", "*", "/"], "<val>": ["x", "1"] } s = r"<+["+('|'.join(list(map(lambda x: x[1:-1], grammar.keys()))))+"]+>" pattern = re.compile(s) while j < l: elems = pattern.findall(h) if not elems: break el = elems[0] h = h.replace(el, grammar[el][(chromo[j] % int(len(grammar[el])))], 1) j += 1 while True: elems = pattern.findall(h) if elems: for elem in elems: el = elem if elem == "<expr>": el = "<val>" h = h.replace(elem, grammar[el][rand(len(grammar[el]))], 1) else: break return h 

文法辞書には、文法の規則が含まれています。 さらに、上で説明した置換アルゴリズム。 ブロックを終了した後は、機能を完了するために必要です。 染色体が終了する場合もありますが、非終端記号が残ります。 これが最後のサイクルであり、すべての非ターミナルをターミナルに置き換えるために必要です。
重要 ：最終的な関数がセマンティクスの観点から有効であることは事実ではありません（ゼロで割ることができます）。


GEモジュール

 # -*- coding: utf-8 -*- import random import math from parser import parse def rand(num): return int(random.random() * num) class Individ: def __init__(self, genotype): self.genotype = genotype self.phenotype = self.get_phenotype() self.fitness = self.get_mistake() def __eq__(self, other): return self.fitness == other.fitness def __ne__(self, other): return not self.__eq__(other) def __lt__(self, other): return self.fitness < other.fitness def __ge__(self, other): return not self.__lt__(other) def __str__(self): return "chromosome : {0}\nphenotype = {2}\nfitness = {1}\n".format(self.genotype, self.fitness, self.phenotype) def get_phenotype(self): return parse(self.genotype) def get_mistake(self): import main intr = main.interval vals = main.values f = eval("lambda x: {0}".format(self.phenotype)) f_vals = [] for i in range(intr[0], intr[1]): try: f_vals.append(f(i)) except: return 10000 return sum(list(map(lambda e: (e[0] - e[1]) ** 2, list(zip(vals, f_vals))))) def GA(chromo_len, pop_len, count): population = get_population(pop_len, chromo_len) while count > 0: childrn_chromos = get_children_chromose(population) mutation(childrn_chromos, 0.8) children = get_children(childrn_chromos) population = get_new_population(population, children) count -= 1 return population def get_genotype(gen_length): return [rand(200) for _ in range(gen_length)] def get_population(length, chromo_len): return [Individ(get_genotype(chromo_len)) for _ in range(length)] def get_children_chromose(parents): def tournament(): return [min([parents[rand(len(parents)-1)] for _1 in range(7)]) for _2 in range(2)] children_chromo = [] for _3 in range(int(len(parents)/2)): children_chromo += crossover(tournament()) return children_chromo def get_children(childrn_chromos): return [Individ(childrn_chromos[i]) for i in range(len(childrn_chromos))] def crossover(pair): p1 = pair[0] p2 = pair[1] d = random.randint(1, len(p1.genotype) - 2) return [p1.genotype[:d] + p2.genotype[d:], p2.genotype[:d] + p1.genotype[d:]] def mutation(chldrn_chromo, p): for j in range(len(chldrn_chromo)): if p > random.random(): i = random.randint(1, len(chldrn_chromo[j]) - 1) chldrn_chromo[j][i] = rand(200) return chldrn_chromo def get_new_population(population, children): l = len(population) buf = population+children buf.sort() c = math.trunc(0.2*l) new_population = buf[:c] tmp = buf[c:] ll = len(tmp) new_population += [tmp[random.randint(1, ll - 1)] for _ in range(c, l)] return new_population 

遺伝的アルゴリズムの通常の実装。

GA関数は、進化のサイクルへの入り口です。

一般に、関数はそれ自体を語っており、各関数の実装はそれほど長くありません。 クロスオーバーの選択は標準ではないことに注意してください。 私は両親を悩ませ、混合パイルの前半を選択します。 これはこのタスクにとってそれほど有害ではありませんが、そうしない方が良いです。 クロスオーバーの最適な候補を選択できるようにするためのメソッドは12個（またはそれ以上）あります。

各個人には、遺伝子型、表現型、フィットネス関数値の3つのフィールドがあります。

最後に

関数を取得する



同じです



最適な文法を作成するのは簡単ではなく、非常に重要なタスクです。

この方法がどのような「文法的進化」であり、問​​題を解決するためにどのようにそれを使用するかが明らかになったことを願っています。 興味深い事実は、シンボリック回帰が関数だけでなく適用可能であることです。 ロボット用の命令を作成したり、ニューラルネットワークの構造を構築したり、その中にパラメーターを構成したりできます。 ネットワークをトレーニングするためのエラーの逆伝播の方法はもう必要ありません。 それと一緒に、連続一次導関数を使用して活性化関数を放棄することもできます。 これは、いわゆる「神経進化プログラミング」です。

もう一度、 ソースへのリンクを提供します 。 誰もがメソッドをより深く理解したい場合。