3 ms·

> I don't think there's a local optima here. The gradient always points you directly at the solution, at all times, in all states. Well, there are no local op

> I don't think there's a local optima here. The gradient always points you directly at the solution, at all times, in all states. Well, there are no local optima but plenty of global optima other than the correct answer, I think: "Hello, World!" and "!dlroW ,olleH" have the same fitness for example. So no, the gradient won't necessarily lead you to the solution. Now, suppose we defined the fitness function instead as the number of correct characters plus the number of characters in the right place, then we'd have local optima and a better chance of getting to the optimum.

abhikshah 16y ago
The fitness function does take char location into account. In python, it'd be -1*sum(abs(x-y) for x,y in zip(chromosome,target)). The gradient here is continuous and smooth. Problems where GA is an appropriate solution have fitness landscapes that are much more pathological.
tassl 16y ago
There is only one global optima with the defined fitness function, and is the one with f=0. There are different local minimum when there is no mutation (for example, if all chromosomes on the initial population don't have the letter W, it will be impossible to create the target unless mutation is used). The other answers that you are thinking on have different fitness (the comparison is target[i] ?= guess[i]). In any case, I like this examples because they currently show the process that the GA has to converge in a way easy to see/understand. Of course, in real life it is more used when there is no information of the function to minimize (optimize), or the function is not convex in our search domain, which can lead to getting stuck in a local minimum using other search methods. I have always felt that the fancy name increased the interest on the topic.
deleted 16y ago
[deleted]
SeanLuke 16y ago
Update Looks like the guy's description of his function is different from his actual function. You're right, there is a single global optimum and no local optima.
- user24 16y ago
  Ah, you're right. Wasn't intentional. I say: > Return the sum of the differences between the chromosome and the target string. but I mean something more like: > Return the sum of the character-wise differences between the chromosome and the target string.

abhikshah 16y ago

The fitness function does take char location into account. In python, it'd be -1*sum(abs(x-y) for x,y in zip(chromosome,target)). The gradient here is continuous and smooth. Problems where GA is an appropriate solution have fitness landscapes that are much more pathological.

tassl 16y ago

There is only one global optima with the defined fitness function, and is the one with f=0. There are different local minimum when there is no mutation (for example, if all chromosomes on the initial population don't have the letter W, it will be impossible to create the target unless mutation is used). The other answers that you are thinking on have different fitness (the comparison is target[i] ?= guess[i]). In any case, I like this examples because they currently show the process that the GA has to converge in a way easy to see/understand. Of course, in real life it is more used when there is no information of the function to minimize (optimize), or the function is not convex in our search domain, which can lead to getting stuck in a local minimum using other search methods. I have always felt that the fancy name increased the interest on the topic.

deleted 16y ago

[deleted]

SeanLuke 16y ago

Update Looks like the guy's description of his function is different from his actual function. You're right, there is a single global optimum and no local optima.

user24 16y ago
Ah, you're right. Wasn't intentional. I say: > Return the sum of the differences between the chromosome and the target string. but I mean something more like: > Return the sum of the character-wise differences between the chromosome and the target string.