2
$\begingroup$

I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function.

f(x_1...x_n) = M - (x_1 - a_1)^2 - (x_2 - a_2)^2 - ... - (x_n - a_n)^2

M a_i are constants. I have to find x_i such that f(x_i) = max(f) = M

My selection method is truncation (I select the top 100 fittest of a population of 500). My crossover method is average. there is a 80% chance for crossover, other wise one of the parents is passed on. My elite count is 5 (1% of the population) There is a 3% chance for a mutation for an individual, the range of the mutation is [-0.3, 0.3]

My fitness function is f it self and my stopping condition is ABS(previous best fitness - current best fitness) <= 10^(-21)

You can find the code I wrote here.

The problem is that it converges before it reaches even an approximate solution.

What can I change in the solution approach so that the algorithm would converge on the maximum(f)? (This is not my algorithm, it's a reduction of a problem I have at work.)

$\endgroup$

closed as unclear what you're asking by Raphael Feb 18 '14 at 21:38

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is the question? Note that there is Code Review for checking your code; what we can do is help you with the algorithmics. So what are you trying to accomplish? Have you tried many runs and different parameters? Any GA may get stuck in local optima. $\endgroup$ – Raphael Feb 18 '14 at 21:38
2
$\begingroup$

I haven't looked at your code, but a few observations.

  • Your selection method is very strong. If you generate 500 individuals at random and choose the best 100, within just a few generations you're going to have a population dominated by descendants of that initial 100 winners. In effect, you're very quickly focusing your search on the best 20% of a random sample. You probably need something like tournament or rank-biased selection instead -- something dramatically weaker than what you have.

  • The elite count is maybe a tad high as well. 5 might be OK, but certainly combined with your selection method, you have an algorithm that's basically designed to converge too quickly.

  • Averaging in crossover may or may not be harmful. It depends on where the optimal values of your parameters lie. Take a problem like "minimize f(x)=x^2 for x in [0, 100]". The optimal value of x in that problem is at 0, and averaging two parents will in this case always result in worse offspring than one of the parents you started with. For other problems, this may be helpful instead though. If you want to try something else, Simulated Binary Crossover (SBX) is often used for real-valued optimization problems. Alternately, one approach is to reduce the crossover rate and increase the mutation rate to provide a wider search of the parameter space.

$\endgroup$
  • $\begingroup$ This test is a reduction of the GA used in the MUSE trainer cs.bgu.ac.il/~litvakm/papers/PAPER-IR.pdf pages 13-14. I'll check your suggestions (now) hope it'll help me to find a solution because I'm fighting with the MUSE trainer for 2 months now... $\endgroup$ – Eugene Krapivin Feb 18 '14 at 17:17
  • $\begingroup$ Update: Tournament selection didn't change much, and putting less elites changed nothing at all. However on an other lead - normalize the Xs to sum to 1 and the Coef arr to sum to 1 did the trick. thank you! $\endgroup$ – Eugene Krapivin Feb 18 '14 at 18:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.