algorithm - 遺伝的プログラミングと検索アルゴリズム

Question

遺伝的プログラミングは現在、あるタイプの検索アルゴリズムを別のタイプに進化させることができますか? たとえば、これまでに QuickSort から BubbleSort を繁殖/変異させた実験はありますか ( http://en.wikipedia.org/wiki/Sorting_algorithmを参照) 。

Answer 1

80 年代の W. ダニエル ヒリスの作品をご覧になることをお勧めします。彼は、遺伝的プログラミングによるソーティング ネットワークの作成に多くの時間を費やしました。彼は、一定数のオブジェクトをソートする問題 (16 個のオブジェクトをソートするネットワークは、ほぼ 10 年間、主要な学術問題でした) の解決に関心を持っていましたが、もしあなたが遺伝的ソートアルゴリズムに非常に興味があります。

任意の長さのリストをソートするためのアルゴリズムの進化において、共進化の概念にも精通している必要があるかもしれません。1 つの遺伝的アルゴリズムがソート アルゴリズムを進化させ、別の GA がソートされていない数のリストを開発するという点がポイントになる前に、共進化システムを構築しました。ソーターの適合度はその精度 (さらに 100% 正確である場合は、比較が少なくなるためのボーナス) であり、リスト ジェネレーターの適合度は、ソート アルゴリズムがそのリストをソートする際に発生するエラーの数です。

バブルがクイックから進化したことがあるかどうかという特定の質問に答えるには、プログラマーのフィットネス機能が非常に具体的で不適切でない限り、私はそれを真剣に疑うだろうと言わざるを得ません. はい、バブルは非常に単純なので、フィットネス関数が精度とプログラムのサイズである GP は、最終的にバブルを見つけるでしょう。しかし、ランタイムを決定するのは後者であるのに、なぜプログラマーは適合度関数として比較の数ではなくサイズを選択するのでしょうか?

GP があるアルゴリズムを別のアルゴリズムに進化させることができるかどうかを尋ねることで、GP とは何かを完全に理解しているかどうか疑問に思っています。理想的には、それぞれの固有の染色体が固有のソートを定義します。200 の染色体の集団は、200 の異なるアルゴリズムを表します。はい、クイックとバブルがどこかにあるかもしれませんが、名前のない可能性のある198の他のメソッドもそうです。

Answer 2

どちらのタイプのアルゴリズムでも、GP が進化できない理由はありません。一方を他方に「進化させる」ことを考えることが本当に意味があるかどうかはわかりません。GP は、定義したフィットネス関数にさらに近づくプログラムを単純に進化させます。

フィットネス関数が並べ替えの正確さのみを調べる場合 (GP が使用する適切な構成要素があると仮定すると)、BubbleSort と QuickSort の両方を非常にうまく進化させることができます。フィットネスの尺度として効率も含めると、これらのどれがより良いソリューションとして決定されるかに影響する可能性があります。

たとえば QuickSort を使用して GP をシードすることができます。適切なフィットネス関数があれば、最終的には BubbleSort を思いつくことができますが、QuickSort よりも適したものを思いつくこともできます。

さて、GPエンジンがこの進化を遂げるのにどれくらいの時間がかかるかは別の問題です...

Answer 3

私はそれを認識していません。あなたの例であなたが示唆している特定の方向性はありそうにないようです。ほとんどの場合、バブル ソートはクイック ソートよりも悪いため、一種のひねくれたフィットネス関数が必要になります。これが起こる可能性は考えられないことではありませんが、一般的に、アルゴリズムを十分に理解すれば、それはすでにかなり適合しています。

極小値に閉じ込められることは、ほとんどの検索戦略にとって未知の問題ではありません。