Re:Evolutionary Algorithm: Evolving "Hello, World"
by sparky on Wednesday September 28, 2011 @03:30PM
(#3049497)
Err.. I would argue that (+1)^2+(-1)^2 would not yield a false positive.
You are right that the explanation is incomplete, though. The squaring provides an 'absolute value' effect as well as disproportionately weighting larger alphabetical distances.
Re:Evolutionary Algorithm: Evolving "Hello, World"
by mahcuz on Thursday September 29, 2011 @03:53AM
(#3051548)
Regarding the squaring - would it be enough to take the absolute value of the distance? (abs -5) + (abs 5) = 10.
Re:Evolutionary Algorithm: Evolving "Hello, World"
by jessedhillon on Thursday September 29, 2011 @07:00PM
(#3054697)
It's still a problematic way to quantify distance between strings. It says that "Rello World" is as close to the target as "Ifmkn Vpqkc"
Levenshtein would quantify those differently, and I'd argue, more correctly. It would say the first is much closer than the second.
Squaring is a dumb way to avoid that problem. You can still have false positives: for example if a string differs from the target by two letters, who distances are +1 and -1, then squaring will not mitigate the issue.
EDIT: I realize now that -1^2 is a positive number...
I'm very surprised that the author doesn't know about the Levenshtein distance metric http://en.wikipedia.org/wiki/Levenshtein_distance
That seems like it would be the perfect utility function for this case.