# Algorithmes Parallèles et Optimisation

### Content

#### Internships/Stages

global_optimization

# 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.

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.

### 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.