GAs are not the best approach even for randomized heuristic approximations. Mostly they are cute, biologically intriguing programming exercises for people that don't care about sitting down and formally working out the specifications of a serious optimization problem. Often they end up throwing many CPU-hours at a relatively simple problem that they weren't even looking to solve, and get a sub-optimal solution because they didn't even bother to optimize the learning/mutation schedule, which would speed it up by an order of magnitude, but that would require maths and thinking, instead of just throwing more randomness against the wall because "it's evolution".
Genetic Algorithms aren't even easier to implement than other randomized heuristic approximations. For instance, Simulated Annealing is basically (but not quite) a GA with a population of one, so you don't need selection or crossover (do you use tournament selection or roulette selection? does it matter? will you try both? what will be your population size?). Simulated Annealing is much easier to implement and has fewer variables to optimize (such as the cooling/learning schedule). Of course it's not nearly as "sexy" as the biologically inspired genetic algorithm.
Most importantly however, a GA does not solve P?=NP, so it is not sufficient for the premise to this movie, which is about the consequences of solving P?=NP, not about arriving at suboptimal but perhaps sufficient solution in almost reasonable time to a TSP problem that doesn't actually have a practical use.
Sufficient for any practical use is not "solved" in the mathematical sense.
Also, AFAIK, a general solution to P=NP could still be very time consuming to calculate (even if you prove polynomial time solutions, that could still be a very high order polynomial). That is, your general solution to the problem could be only slightly better than O(n!) and satisfy.
tripzilch|13 years ago
GAs are not the best approach even for randomized heuristic approximations. Mostly they are cute, biologically intriguing programming exercises for people that don't care about sitting down and formally working out the specifications of a serious optimization problem. Often they end up throwing many CPU-hours at a relatively simple problem that they weren't even looking to solve, and get a sub-optimal solution because they didn't even bother to optimize the learning/mutation schedule, which would speed it up by an order of magnitude, but that would require maths and thinking, instead of just throwing more randomness against the wall because "it's evolution".
Genetic Algorithms aren't even easier to implement than other randomized heuristic approximations. For instance, Simulated Annealing is basically (but not quite) a GA with a population of one, so you don't need selection or crossover (do you use tournament selection or roulette selection? does it matter? will you try both? what will be your population size?). Simulated Annealing is much easier to implement and has fewer variables to optimize (such as the cooling/learning schedule). Of course it's not nearly as "sexy" as the biologically inspired genetic algorithm.
Most importantly however, a GA does not solve P?=NP, so it is not sufficient for the premise to this movie, which is about the consequences of solving P?=NP, not about arriving at suboptimal but perhaps sufficient solution in almost reasonable time to a TSP problem that doesn't actually have a practical use.
pfarrell|13 years ago
Also, AFAIK, a general solution to P=NP could still be very time consuming to calculate (even if you prove polynomial time solutions, that could still be a very high order polynomial). That is, your general solution to the problem could be only slightly better than O(n!) and satisfy.
unknown|13 years ago
[deleted]