したがって、基本的には s という数値があり、合計が s になる数値のサブセットを見つけたいとします。これは、ナップザック問題の特殊なケースである部分集合和問題として記述されます。
遺伝的アルゴリズムの適用に関するあなたの予想は間違っていると思います。1000 個のアイテムのセットから 500 個のアイテムを選択するために考慮しなければならない可能性のある解の数を視覚化するには、次の数 [「1000 が 500 を超える」の二項係数] を読んでください。
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320（ソース）。
最初に明確にしましょう: 遺伝的アルゴリズムと関連する方法はメタヒューリスティックです。つまり、それらは最適解を見つけるのには適していませんが、非常に短時間で「良い」解を見つけることができます。NP 困難な問題で最適な解を見つけるには、最悪の場合に考えられるすべての組み合わせを試す必要があります。検索空間をインテリジェントに分割し、少数のソリューションのみを評価する正確な最適化の方法がありますが、それでも最適な答えを見つけるまでに数週間かかる場合があります。
この正確な最適値を見つける必要がある場合は、たとえばbranch と boundなどの正確な方法を探すことをお勧めします。たとえば、よく知られたCPLEXオプティマイザーを使用して、問題を整数プログラムとして記述することができます。たとえば、TSP の ILP 形式を見て、これをどのように達成できるかを確認し、それを問題に変換します。
正確な最適値を見つける必要がない場合は、遺伝的アルゴリズムで監視して出力を改善できることがいくつかあります。
- 十分な大きさの母集団サイズを使用し、それに応じて選択圧力を調整します。遺伝的浮動の影響を回避したいが、それでも収束を達成したい.
- 母集団の分散 (多様性) を監視します。減りが早い？母集団のすべての解が本質的に同じである場合、アルゴリズムは収束しています。収束したら、それを再開するか、新しい遺伝情報を導入して進化プロセスを復活させる必要があります。
- 変異の強さを変化させます。検索の開始時に複数のビットを反転し、検索の最後に少数のビットのみを反転するように削減します。
- 複数のクロスオーバー ポイントを使用します (シングル ポイント クロスオーバーを使用していると仮定します)。このような長いストリングの場合、10 個のクロスオーバー ポイントを使用することをお勧めします。