遺伝Algortihm - 可変長最適化の戦略

Question

私は遺伝子アルゴリズム（GA）を使用して解決したい問題があります。あなたは次のような問題にそれを簡略化することができます。

私は意味会社のカープール、車と車種の数を最適化します。私はすでにビジネスカー、トランスポーター、またはビジネスカー、ビジネスカー、トランスポーターのような設定を評価するフィットネス機能calcFitness(carList)を持っています。問題は、GAを使用してこの可変長問題を解決する方法です。

私はあなたが一般的にこれらの問題に取り組むことができる方法4つのアイデアを持っている：（？可能な場合はわからない）多分何とかGAできる可変長染色体を実装し、単一の実行で問題を解決

1. を
2. 見積り可能な最大台数（例えば20台）と、1から20までの各スロット番号の固定長GAを実行し、20個の結果を比較してください。
3. ＃2と同様ですが、上限はありません。 1台の車を増やして、スロット数を増やして、増分した数の最適解が前のs olution（勾配ベースのアプローチ）
4. 積層された2つの固定長ガス：親GAは、単にこれらのスロットのassignementを最適化する別のGA車スロットとその適応度関数の数を最適化するための責任と呼ばれている

これらの一般的なアプローチについてどう思いますか？これらの可変長のケースについては、他のアイデアやGAの代わりになるでしょうか？

Answer 1

可変長が確かに可能で、この問題の最も自然な表現です。なぜそれが問題になるのでしょうか？唯一の実質的な違いは、クロスオーバー操作にあります。一点は簡単ですが（a内の点を1点とし、b以内の点を選択し、自動的に可変長の子孫を取得します）、可変長の直感を必要とする連続的な交差を持つ方がよい場合がよくあります。しかし、それは後で徹底した別のテストの後に実装することができます。

あなたのアルゴリズムは、染色体が良好であれば、（状況の組み合わせによって）より良い結果が得られることがわかるかもしれません。遺伝的プログラミング（遺伝子型は線形配列ではなく木である）のように指数関数的に膨らむことはありませんが、依然として染色体の長さは不快に成長し始める可能性があります。フィットネス機能でそれを考慮する必要があるかもしれません。あるいは、いくつかの制限をすぐに上回る候補を拒絶することによって、＃2のようなソリューションをモデル化することができます。