User Tools

Site Tools


global_optimization

Differences

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

Link to this comparison view

global_optimization [2015/02/11 16:58]
guest created
global_optimization [2015/03/06 09:46] (current)
Line 1: Line 1:
-blah+====== 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 
 +separation. 
 + 
 +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 
 +beforehand. 
 + 
 + 
 +{{: intergriewank.gif?​600| }} 
global_optimization.1423670281.txt.gz · Last modified: 2015/03/06 09:46 (external edit)