3

I'm trying to design a nonlinear fitness function where I maximize variable A and minimize the variable B. The issue is that maximizing A is much more important at single digit values, almost logarithmic. B needs to be minimized and in contrast to A, it becomes less important when small (less than one) and more important when it's larger (>1), so exponential decay.

The main goal is to optimize A, so I guess an analog is A=profits, B=costs

Should I aim to keep everything positive so that the I can use a roulette wheel selection, or would it be better to use a rank/torunament kind of system? The purpose of my algorithm is shape optimization.

Thanks

randomafk
  • 783
  • 1
  • 8
  • 13
  • Your description of your fitness function seems incomplete. Have you derived a mathematical formula for it? – ThomasMcLeod Jul 18 '11 at 07:14
  • Look over this topic http://stackoverflow.com/questions/6589146/need-help-on-like-dislike-voting-system - maybe it helps you to construct right fitness function. – stemm Jul 18 '11 at 23:12
  • Are you concerned about local minima and maxima? Otherwise I would look into implementing a more simple Hill Climbing Search: http://en.wikipedia.org/wiki/Hill_climbing – Patrick Jul 21 '11 at 13:11

2 Answers2

4

When considering a multi-objective problem the goal is usually to identify all solutions that lie on the Pareto curve - the Pareto optimal set. Have a look here for a 2-dimensional visual example. When the algorithm completes you want a set of solutions that are not dominated by any other solution. You therefore need to define a pareto ranking mechanism to take into account both objectives - for a more in depth explanation, as well as links to even more reading, go here

With this in mind, in order to effectively explore all solutions along the pareto front you do not want an implementation that encourages premature convergence, otherwise your algorithm will only explore the search space in one specific area of the Pareto curve. I would implement a selection operator that keeps all members of each iteration's optimal set of solutions, that is all solutions which are not dominated by another + plus a parameter controlled percentage of other solutions. This way you encourage exploration all along the Pareto curve.

You also need to ensure your mutation and crossover operators are tuned correctly too. With any novel application of Evolutionary Algorithms, part of the problem is trying to identify an optimal parameter set for the problem domain... this is where it gets really interesting!!

GordyD
  • 5,063
  • 25
  • 29
  • My fitness function right now is something like (x+1)/sqrt(1+y^2/2^2) o that a value of y being 1.3 vs .8 is not matter too much, but a value of 3.0 does. My understanding with pareto ranking is that I need a larger population size of around 100 which is the main reason why I opted for a fitness funciton instead. I should be able to try implementing pareto ranking as well though. – randomafk Jul 21 '11 at 14:22
0

The description is very vague, but assuming that you actually have an idea of what the function should look like and you're just wondering whether you need to modify it so that proportional selection can be used easily, then no. Regardless of fitness function, you should probably default to using something like tournament selection. Controlling selection pressure is one of the most important things you have to do in order to get consistently good results, and roulette wheel selection doesn't allow you that control. You typically get enormous pressure very early, which drives premature convergence. That might be preferable in a few cases, but it's not where I'd start my investigations.

deong
  • 3,820
  • 21
  • 18