3 ms·

I took a course on this stuff in uni, it was so fantastically fun to play with. Simulated annealing has less cachet than GAs (and other evolution-inspired appr

I took a course on this stuff in uni, it was so fantastically fun to play with. Simulated annealing has less cachet than GAs (and other evolution-inspired approaches) but tends to perform well enough on lots of problems that you might as well skip GAs. I haven't dug much on the linked GA, but it looks like it converges too quickly. That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems. The problem I practiced on was Ackley's Function[1]. Even in 2 dimensions it's really good at tripping up algorithms that converge too eagerly. Some GA methods actually make the parameters of the system part of the genome, but as I recall it doesn't make a huge difference overall. Fun to think about though. Mind you, the No Free Lunch Theorem means that there's a place for everyone in the heuristic computing tent. And simple random sampling (monte carlo method) and/or graphing can be very helpful for looking for the contours of a solution space. There's still room for humans too. [1] https://github.com/jchester/ruby-ackley-genetic-algorithm https://github.com/jchester/ruby-ackley-genetic-algorithm

antirez 12y ago
Totally agree one reason why it converges so fast is because independent solutions are unlikely to produce a better offspring when crossed, so basically my feeling is that it ends with a very similar population and most of the evolution happens just because of the mutations... that's why I eventually switched to SA. Another funny thing is when the improvement you get because of the algorithm is not compensated by the drop in performance: working with just a set of triangles that fit the cache can be a true boost.
- jacques_chester 12y ago
  Ah, good point about crossing. Each individual actually faces enormous local selection pressure, so once a given triangle converges closely enough, offspring just aren't going to be selected upon crossover with a (possibly very different) neighbour. So actually I think this demonstrates a kind speciation in a very sharply divided landscape. It'd probably work better on simple images with smooth gradients and the like.
chriswarbo 12y ago
> That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems. The nicest approach to exploration/exploitation I've seen for simulated annealing is to run two searches side-by-side. Their relative "temperatures" (ie. probability of accepting a worse solution) depends on their relative fitness: if both are the same fitness, both have the same temperature; if one has higher fitness than the other, its temperature lowers (so it can "focus" on that high-fitness region) whilst the other's temperature raises (so it can "spread out" to find higher-fitness regions). Also, regarding the No Free Lunch Theorems, I don't give them much thought since they don't take the computational complexity of the problem into account. They say that every search algorithm, when averaged over all problems, achieves total performance that's the same as random search. The real world doesn't contain all problems; in particular, we care more about (computationally) simple problems than unrealisitically-complex ones. Worrying about NFL for search is like worrying about adversaries with infinite computing power in crypto; yes your algorithm will be weak against such an attacker, but it's unrealistic to care about.
- jacques_chester 12y ago
  For me the two lessons of the No Free Lunch Theorem are: 1. Stop trying to prove that your solution is the "best overall" 2. Hooray, we can pick and choose our tools.

antirez 12y ago

Totally agree one reason why it converges so fast is because independent solutions are unlikely to produce a better offspring when crossed, so basically my feeling is that it ends with a very similar population and most of the evolution happens just because of the mutations... that's why I eventually switched to SA. Another funny thing is when the improvement you get because of the algorithm is not compensated by the drop in performance: working with just a set of triangles that fit the cache can be a true boost.

jacques_chester 12y ago
Ah, good point about crossing. Each individual actually faces enormous local selection pressure, so once a given triangle converges closely enough, offspring just aren't going to be selected upon crossover with a (possibly very different) neighbour. So actually I think this demonstrates a kind speciation in a very sharply divided landscape. It'd probably work better on simple images with smooth gradients and the like.

chriswarbo 12y ago

> That's a classic problem (exploration vs exploitation, aka coverage vs convergence) in optimisation problems. The nicest approach to exploration/exploitation I've seen for simulated annealing is to run two searches side-by-side. Their relative "temperatures" (ie. probability of accepting a worse solution) depends on their relative fitness: if both are the same fitness, both have the same temperature; if one has higher fitness than the other, its temperature lowers (so it can "focus" on that high-fitness region) whilst the other's temperature raises (so it can "spread out" to find higher-fitness regions). Also, regarding the No Free Lunch Theorems, I don't give them much thought since they don't take the computational complexity of the problem into account. They say that every search algorithm, when averaged over all problems, achieves total performance that's the same as random search. The real world doesn't contain all problems; in particular, we care more about (computationally) simple problems than unrealisitically-complex ones. Worrying about NFL for search is like worrying about adversaries with infinite computing power in crypto; yes your algorithm will be weak against such an attacker, but it's unrealistic to care about.

jacques_chester 12y ago
For me the two lessons of the No Free Lunch Theorem are: 1. Stop trying to prove that your solution is the "best overall" 2. Hooray, we can pick and choose our tools.