global_optimization

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

— |
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 | ||

+ | 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.txt · Last modified: 2015/03/06 09:46 (external edit)