User Tools

Site Tools



This shows you the differences between two versions of the page.

Link to this comparison view

global_optimization [2015/03/06 09:46] (current)
Line 1: Line 1:
 +====== Global Optimization ======
 +==== Stochastic Optimization ====
 +In the context of stochastic optimization,​ the APO team has acquired a
 +solid expertise on evolutionary algorithms and some of its members
 +have introduced these methods in France at the beginning of the 90's.
 +Evolutionary algorithms are inspired by the theory of evolution used
 +to solve problems of different nature. They are based on the idea of
 +building a family of tentative solutions to a given problem and make
 +it evolve towards more accurate results. They are stochastic
 +algorithms because they iteratively use random processes. ​
 +{{: aggriewank.gif?​600| }}
 +Specifically,​ the APO team has worked on problems from air traffic
 +control which can be extremely complex and of very large size (roughly
 +30000 aircraft fly over Europe every day); these problems, moreover,
 +commonly combine, in an environment characterized by uncertainties,​
 +entirely automated tasks with "​hand-made"​ ones such has aircraft
 +Classical approaches are used as much as possible: runway sequences
 +are optimized using a branch-and-bound algorithm, a neural network
 +allows us to learn techniques for opening traffic control sectors,
 +learning methods are tested to improve the prediction of aircraft
 +trajectories. In other cases, only stochastic techniques can prove
 +effective: this is the case of route network optimization,​ of the
 +optimization of the grouping of control sectors into qualification
 +zones, of the optimization of taxiways traffic, or of air traffic
 +conflicts resolution.
 +{{: 6.gif?600| }}
 +==== Exact Global Optimization ====
 +In exact global optimization,​ algorithms are based on sol-called
 +Branch and Bound techniques based on the idea of decomposing the
 +search space into smaller and smaller subdomains and of discarding
 +those subdomains that cannot produce a better solution that the one
 +found so far. Discarding subdomains requires computing solution bounds
 +which is achieved by means of interval arithmetic (based on a
 +redefinition of classical operators and unary functions). These
 +methods are general and only require few hypotheses on the considered
 +functions (they have to be explicitly known). Because of the NP-hard
 +nature of the considered problems, this class of algorithms, known as
 +Interval Branch and Bound, has exponential complexity. Nevertheless,​
 +numerous technical improvement allowed us to solve in an exact way
 +more and more complex problems that were considered unfeasible
 +{{: intergriewank.gif?​600| }}
global_optimization.txt · Last modified: 2015/03/06 09:46 (external edit)