So essentially you have a number s and you want to find a subset of numbers that add up to s. This is described as the subset sum problem which is a special case of the knapsack problem.
I think your expactations regarding the application of genetic algorithms are wrong. To visualize the number of possible solutions that have to be considered to select 500 items out of a set of 1000 items, please read the following number [the binomial coefficient for "1000 over 500"]:
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320
(source).
Le me clarify first: Genetic algorithms and related methods are metaheuristics, which means they are not suited to find the optimal solution, but a "good" solution in a very short time. To find the optimum solution in a problem that is NP hard you would have to try every single possible combination in the worst case. There are methods for exact optimization that intelligently partition the search space and evaluate only a smaller number of solutions, still it can take weeks to come up with the optimal answer.
If you are required to find this exact optimum I would suggest you look for exact methods such as e.g. branch and bound. You could use for example the well-known CPLEX optimizer to describe your problem as an integer program. Look for example at the ILP formulation of the TSP to see how this can be achieved and translate that to your problem.
If you are not required to find the exact optimum there are several things that you can monitor in your genetic algorithm to improve its output:
- Use a large enough population size and according selection pressure. You want to avoid the effect of genetic drift, still achieve convergence.
- Monitor the variance (diversity) in your population. Is it decreasing quickly? If all solutions in your population are essentially the same then the algorithm has converged. Once it has converged you would need to restart it, or introduce new genetic information to revive the evoluationary process.
- Vary the strength of the mutation. Flip multiple bits at the beginning of the search and reduce to flip only few bits at the end of the search.
- Use multiple crossover points (I assume you're using single-point crossover). For such a long string maybe you want to use 10 crossover points.