Techniques d'optimisation stochastique appliquées à certains problèmes du trafic aérien
In a forest a fox bumps into a little rabbit, and says, ``Hi,
junior, what are you up to?''
``I'm writing a dissertation on how rabbits eat foxes,'' said the
``Come now, friend rabbit, you know that's impossible!''
``Well, follow me and I'll show you.'' They both go into the
rabbit's dwelling and after a while the rabbit emerges with a satisfied
expression on his face.
Comes along a wolf. ``Hello, what are we doing these days?''
``I'm writing the second chapter of my thesis, on how rabbits
``Are you crazy? Where is your academic honesty?''
``Come with me and I'll show you.'' As before, the rabbit comes
out with a satisfied look on his face and a diploma in his paw.
Finally, the camera pans into the rabbit's cave and, as everybody
should have guessed by now, we see a mean-looking, huge lion sitting
next to some bloody and furry remnants of the wolf and the fox.
The moral: It's not the contents of your thesis that are important ---
it's your PhD advisor that really counts.
Numerical optimization can
be likened to a kangaroo searching for the top of Mt. Everest.
Everest is the global optimum, but the top of any other really high
mountain such as K2 would be nearly as good.
When training a neural network, initial weights are usually chosen
randomly, which means that the
kangaroo may start out anywhere in Asia. If you know something about
the scales of the inputs, you may be able to get the kangaroo to start
near the Himalayas. However, if you make a really stupid choice of
distributions for the random initial weights, or if you have really
bad luck, the kangaroo may start in South America.
In standard backprop or stochastic approximation, the kangaroo is
blind and has to feel around on the ground to make a guess about which
way is up. He may be fooled by rough terrain unless you use batch
training. If the kangaroo ever gets near the peak, he may jump back
and forth across the peak without ever landing on the peak. If you use
a decaying step size, the kangaroo gets tired and makes smaller and
smaller hops, so if he ever gets near the peak he has a better chance
of actually landing on it before the Himalayas erode away. In backprop
with momentum, the kangaroo has poor traction and can't make sharp
With Newton-type (2nd order) algorithms, the Himalayas are covered
with a dense fog, and the kangaroo can only see a little way around
his location. Judging from the local terrain, the kangaroo make a guess
about where the top of the mountain is, and tries to jump all the way
there. In a stabilized Newton algorithm, the kangaroo has an altimeter,
and if the jump takes him to a lower point, he backs up to where he
was and takes a shorter jump. If the algorithm isn't stabilized, the
kangaroo may mistakenly jump to Shanghai and get served for dinner in
a Chinese restaurant. (I never claimed this analogy was realistic.)
In steepest ascent with line search, the fog is very dense, and the
kangaroo can only tell which direction leads up. The kangaroo hops
in this direction until the terrain starts going down again, then
chooses another direction.
Notice that in all the methods discussed so far, the kangaroo can hope
at best to find the top of a mountain close to where he starts. There's
no guarantee that this mountain will be Everest, or even a very high
In simulated annealing, the kangaroo is drunk and hops around randomly
for a long time. However, he gradually sobers up and tends to hop
In genetic algorithms, there are lots of kangaroos that are parachuted
into the Himalayas (if the pilot didn't get lost) at random places.
These kangaroos do not know that they are supposed to be looking for
the top of Mt. Everest. However, every few years, you shoot the
kangaroos at low altitudes and hope the ones that are left will be
fruitful and multiply.
From all this we can conclude that the best methods to find the Mount
Everest are (in order):
and even if you have to send a kangaroo, it is useful if you know
- to know where it is
- to have a map on which you can find it
- to know someone who knows where it is or who has a map
- to send (a) kangaroo(s) to search for it
- where the mountain range is in which the Mount Everest may be and
- how to bring your kangaroo to that mountain range.
comfortably cruising in an airliner, sipping a glass of cold champagne
and looking out of the window into the endless blue sky, you hardly
ever see another man-made flying object. At the same time, the
aviation paper that you are reading speaks about the capacity crisis
in ATC. So, there seems to be a contradiction : the skies are empty,
but the ATC radar screens are full.[...] In aviation, the introduction
of new technologies in the air and on the ground have progressed out
Applications aux problèmes du trafic aérien
5.0cm Carlos Garcia-Avello et Sip Swierstra
This document was translated from LATEX by HEVEA.
This document was cut into pieces by