On Tue, 7 Sep 1999, Matt Gingell wrote:
>
> I don’t think there can be any general solution to the problem of local
> optima. There are lots of different useful techniques, but any
> hill-climbing algorithm can potentially get stuck. It's a question of
> the topology of the search space, which can be arbitrarily complex
Many years ago (my first programming experience actually), we worked on a program to solve a set of differential equations that used the SIMPLEX [sp?] algorithm. This in my interpretation was a hill-climbing algorithm and did suffer from the problem of getting stuck at local optima.
A number of years later (mid-80s?), I was quite suprised to hear that a mathematician, I believe Bell Labs, had solved this problem. His solution interestingly enough turned out to be geometric. If you move a "plane" upward through the entire search space of "hills", then its last point of intersecting will be the optima of the entire landscape.
Does anyone have any more details on this? More importantly, does this approach solve the problem of getting stuck
If it does, then it would suggest that the best way to find an optima is to apply methods that are outside of the realm which is being optimized.
> For instance, organisms in a genetic search might contain a block of
> data representing a mutation function, which you hope will be
> optimized along with the fitness function.
Organisms do contain a bi-modal mutation function. If the organism is doing fairly well, it mutates at a level that is probably optimal for normal survival & reproduction, but if it gets really stressed it goes into hypermutation mode -- though most of the organisms will die, a few might survive and prosper (as "new" organisms).
>
> I think it’s interesting to ask why evolution didn't get stuck, and
> whether free market economics can be modeled as a hill-climb optimizing
> wealth and, if so, are there local optima?
>
Evolution is *very* stuck in many places. Why is 98% of the genome
junk? Because making extra DNA is easy while cleaning it up without
doing more harm than good is difficult. Why do we grow so slowly?
Because developing active transport systems that can quicky and
efficiently deliver proteins to the desired location in cells is
difficult. Why are there strange protein "complexes" required
for translation and transcription? Because you evolution almost always
operates in "add-onto" mode. I could go on for hours.
Free-market economics is *clearly* suboptimal for wealth optimization. Game theory says that the best solution is when the maximum degree of trust and cooperation is possible. Do we need 3 big car manufacturers? No. One car manufacturer could make all of the models the 3 currently do, spend much less on advertising, have greater efficiencies of scale, etc. BUT only if it functioned in a "non-profit" mode and were able to highly motivate the workers to be as productive as competition between the big-3 currently does. The *interesting* thing about where we are going is that computers, and in theory most software can be made completely trustable -- Error Correcting Codes and program proofs become the lawyers of info/cyberspace -- and motivating computers (like your immune system or heart) is a completely unrequired. So in theory, these things allow significant increases in productivity and wealth. Free-market economics is required because competition drives us to innovate. If I can "prove" I have the most efficient way of doing something (e.g. diamond as a building material), then I have completed an examination of the search space and should waste no more energy on competition to optimize things.
Robert