optimum finding in Genetic algorithms

Question

I am implementing my M.Sc dissertation and in theory aspect of my thesis, i have a big problem.

suppose we want to use genetic algorithms.

we have 2 kind of functions :

a) some functions that have relations like this : ||x1 - x2||>>||f(x1) - f(x2)|| for example : y=(1/10)x^2

b) some functions that have relations like this : ||x1 - x2||<<||f(x1) - f(x2)|| for example : y=x^2

my question is that which of the above kind of functions have more difficulties than other when we want to use genetic algorithms to find optimum ( never mind MINIMUM or MAXIMUM ).

Thank you a lot, Armin

• Shark: Are you trying to approximate the function using GA or ... ?
• Armin Ghasem Azar: Thank you for your attention , yes i want to do that. i find that this problem is scaling problem, i i want to know the solution for solving the problem ? is my question and this comment clear or i should declare more ?
• Shark: Hopefully. For starters you can start sharing what you tried and what language/IDE you are using. Later we can talk about what selection to use and picking the right fitness function. What are you using for genes, a binary representation of a float?
• Armin Ghasem Azar: suppose for the first function ( a ), our fitness is f(x) = (1/1000)*x and our variables are x1=1000 and x2=500 , then we have 500>>0.5 , it means the population is very sparse but the fitness function export very close solutions. and if we suppose for function ( b) , x1=5 and x2=3 and f(x)=1000*x, then we have 2<<2000 , and if your selection operator be roulette wheel you will have problem for selecting ( I mean I think we have have problem I'm not sure ! ). now my question is this , which kind of a or functions is hard to finding optimum solution(chromosome) via genetic algorithms ?\

Answer 1

I don't believe you can answer this question in general without imposing additional constraints.

It's going to depend on the particular type of genetic algorithm you're dealing with. If you use fitness proportional (roulette-wheel) selection, then altering the range of fitness values can matter a great deal. With tournament selection or rank-biased selection, as long as the ordering relations hold between individuals, there will be no effects.

Even if you can say that it does matter, it's still going to be difficult to say which version is harder for the GA. The main effect will be on selection pressure, which causes the algorithm to converge more or less quickly. Is that good or bad? It depends. For a function like f(x)=x^2, converging as fast as possible is probably great, because there's only one optimum, so find it as soon as possible. For a more complex function, slower convergence can be required to find good solutions. So for any given function, scaling and/or translating the fitness values may or may not make a difference, and if it does, the difference may or may not be helpful.

There's probably also a No Free Lunch argument that no single best choice exists over all problems and optimization algorithms.

I'd be happy to be corrected, but I don't believe you can say one way or the other without specifying much more precisely exactly what class of algorithms and problems you're focusing on.