遺伝的アルゴリズムはクヌース問題のような問題に適していますか？
遺伝的アルゴリズムが最適またはほぼ最適なソリューションを提供できることは誰もが知っています。したがって、NP困難な問題のようないくつかの問題では、時間と最適解の間のトレードオフがあり、ほぼ最適解で十分です。
最適解を見つける保証はないので、GAはクヌース問題を解くための良い選択であると考えられていますか？
人工知能によると：現代のアプローチ（第3版）、セクション3.2（p。73）：
クヌースは、4から始まり、階乗、平方根、およびフロア演算のシーケンスが任意の正の整数に達すると推測しました。
たとえば、4から5に到達できます。
floor（sqrt（sqrt（sqrt（sqrt（sqrt（（4！）！）））））））
したがって、数（5）があり、指定された数に到達するために言及された3つの操作のシーケンスを知りたい場合、染色体の各遺伝子は、特定の操作を表す番号になります。 （操作なし）および適応度関数は、指定された数と、各染色体に特定の順序で操作を適用して得られる数（最小）との絶対差になります。反復（世代）の数が最適解なしで行われ、最も近い数が4（フィットネス1の場合）であると考えてみましょう。問題は、4に操作を適用しないことで4を取得できるのに対し、5の場合は必要です。多くの操作があるため、ほぼ最適なソリューションはソリューションにさえ近くありません。
では、GAはこの種の問題には適していませんか？または、提案された染色体表現と適応度関数は十分ではありませんか？
回答
あなたの質問にもっと直接的に答えようとする前に、私に何かを明確にさせてください。
人々はしばしば遺伝的アルゴリズム（GA）という用語を使用しますが、多くの場合、実際に意味するのは進化的アルゴリズム（EA）です。これは、人口ベースの（つまり、複数のソリューションが同時に維持される）最適化アルゴリズムとダーウィニズムと適者生存に触発されたアプローチ。 GAはこれらのアプローチの1つであり、染色体はバイナリであり、突然変異とクロスオーバー操作の両方があります。進化戦略や遺伝的プログラミングなど、他のアプローチもあります。
またお気づきのように、EAはメタヒューリスティックであり、収束特性に関するいくつかの研究がありますが[ 1 ]、実際には収束しない可能性があります。ただし、他の潜在的なアプローチが失敗した場合、EAは間違いなく役立ちます。
あなたの場合、問題は実際には、他の小さな関数で構成される関数の閉じた形（または分析）の式を見つけることです。これは本当に遺伝的プログラミング（特にツリーベースのGP）が作成された目的です。実際、クヌース問題は、GPが適用される典型的な問題であるシンボリック回帰問題の特定のインスタンスです。したがって、GPはおそらくあなたが試すべき最初のアプローチです。
Meanwhile, I have implemented a simple program in DEAP that tries to solve the Knuth problem. Check it here. The fitness of the best solution that it has found so far (with some seed) is 4 and the solution is floor(sqrt(float(sqrt(4)))) (here float just converts the input to a floating-point number, to ensure type safety). I used the difference as the fitness function and ran the GP algorithm for 100 generations with 100 individuals for each generation (which is not a lot!). I didn't tweak much the hyper-parameters, so, maybe, with the right seed and hyper-parameters, you can find the right solution.
To address your concerns, in principle, you could use that encoding, but, as you note, the GA could indeed return $4$ as the best solution (which isn't actually that far away from $5$）、これは、すべての世代で、その価値だけを持っている個人を殺すことを避けることができます。
私は自分の実装とこの問題について考えることにあまり時間をかけませんでしたが、上で述べたように、遺伝子プログラミングとKnuthの操作のみを使用しても、それは局所的な最適点で立ち往生する可能性があります。乗算や加算などの他の操作で私の（またはあなたの）実装を拡張して、何かが改善されるかどうかを確認することができます。