From: Robert J. Bradbury (bradbury@www.aeiveos.com)
Date: Wed Sep 08 1999 - 00:11:11 MDT
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:05:04 MST