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

Question

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

Answer 1

私は気づいていません。あなたの例で示唆している特定の方向はありそうもありません。バブルソートはほとんどの方法でクイックソートよりも悪いので、一種の逆行性フィットネス機能が必要になります。これは起こりえないことは考えられませんが、一般的によく理解されているアルゴリズムがあれば、それはすでにかなり適しています。別のアルゴリズムに行くには、おそらくいくつかの悪い選択肢を通過する必要があります。

ローカルミニマにトラップされていることは、ほとんどの検索戦略では未知の問題ではありません。

Answer 2

GPが進化できなかった理由はありません。いずれかのタイプのアルゴリズム。私はそれを進化させることを他のものに "考える"ことが本当に理にかなっているとは確信していません。 GPはあなたが定義したフィットネス機能に一層近づくプログラムを進化させます。

あなたのフィットネス機能が並べ替えの正確さだけを見ている場合（あなたのGPが使用する適切なビルディングブロックを持っていると仮定した場合）、BubbleSortとQuickSortの両方を非常によく進化させることができます。適性の尺度として効率を含めると、それがより良い解決策として決定されることに影響するかもしれません。

たとえば、次のようにGPをシードできます。クイックソート、適切なフィットネス機能を持っていれば、最終的にBubbleSortが登場することは間違いありませんが、クイックソート以外のものも考えられます。

は、今ではこの進化を行うにはGPのエンジンを取るどのくらいあなたは80年代からW.ダニエルヒリスの仕事で見たいと思うかもしれません別の質問...

Answer 3

です。彼は遺伝子プログラミングによってソートネットワークを作るのに多大な時間を費やしました。彼は一定の数のオブジェクトをソートする問題にもっと関心を持っていましたが（16オブジェクトソートネットワークは10年近くにわたり大きな学問的問題でした）、もしあなたがそうであれば彼の仕事に精通していることをお勧めします遺伝子選別アルゴリズムに本当に関心があります。

任意の長さのリストをソートするためのアルゴリズムの進化において、共進化の概念に精通したいことがあります。私は共進化システムを構築しました。その前に、一つの遺伝的アルゴリズムがソートアルゴリズムを進化させ、もう一つのGAは未整列のリストを作成することでした。ソーターの適合度は、その精度（100％正確であれば比較回数が少ないことに加えてボーナス）であり、リストジェネレーターの適合度はソートアルゴリズムがそのリストをソートする際にどれだけ多くのエラーが発生するかです。

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

GPがあるアルゴリズムを別のアルゴリズムに進化させることができるかどうかを尋ねることで、私はGPが何であるか完全に明確であるかどうか疑問に思っています。理想的には、各固有の染色体は一意のソートを定義します。 200染色体の集団は、200の異なるアルゴリズムを表す。はい、すばやく気泡がどこかにあるかもしれませんが、潜在的に無名の198のメソッドもあります。