Spelling suggestions: "subject:"constrained aglobal aptimization"" "subject:"constrained aglobal foptimization""
1 |
Differential evolution algorithms for constrained global optimizationKajee-Bagdadi, Zaakirah 04 April 2008 (has links)
In this thesis we propose four new methods for solving constrained global optimization problems.
The first proposed algorithm is a differential evolution (DE) algorithm using penalty
functions for constraint handling. The second algorithm is based on the first DE algorithm
but also incorporates a filter set as a diversification mechanism. The third algorithm is also
based on DE but includes an additional local refinement process in the form of the pattern
search (PS) technique. The last algorithm incorporates both the filter set and PS into the DE
algorithm for constrained global optimization. The superiority of feasible points (SFP) and
the parameter free penalty (PFP) schemes are used as constraint handling mechanisms.
The new algorithms were numerically tested using two sets of test problems and the
results where compared with those of the genetic algorithm (GA). The comparison shows
that the new algorithms outperformed GA. When the new methods are compared to each
other, the last three methods performed better than the first method i.e. the DE algorithm.
The new algorithms show promising results with potential for further research.
Keywords: constrained global optimization, differential evolution, pattern search, filter
method, penalty function, superiority of feasible points, parameter free penalty.
ii
|
2 |
Méthodes à intervalles et stratégies de parcours d'arbre pour l'optimisation globale / Interval methods and node selection strategies for constrained global optimisationSans, Olivier 19 November 2018 (has links)
Depuis quelques années, la méthode de séparation et évaluation par intervalles (Interval Branch and Bound) est de plus en plus utilisée pour résoudre les problèmes d’optimisation globale sous contraintes (Constrained Global Optimisation), notamment ceux qui sont non convexes. Contrairement à un grand nombre de ses concurrents, cette méthode permet de prouver l’optimalité d’une solution avec un niveau de précision donné. En revanche, son processus d’exploration arborescent implique une complexité exponentielle en temps et en mémoire dans le pire cas. De ce fait, le développement de techniques permettant d’accélérer la convergence de cette méthode définit un pan de recherche important.Une première contribution concerne les méthodes de contraction destinées à réduire l’espace de recherche. Nous proposons une nouvelle méthode de contraction, nommée TEC, qui généralise à plusieurs dimensions le principe de la disjonction constructive utilisée par la méthode de contraction CID. TEC construit un sous- arbre d’exploration par un processus de bissection et de contraction avant d’effectuer l’union des espaces de recherche associés aux feuilles de ce sous-arbre. Nous proposons deux variantes de TEC exploitant sa structure arborescente. La première, nommée Graham-TEC, permet d’apprendre des contraintes linéaires implicites utilisées pour améliorer la contraction. La seconde, nommée TEC-UB, permet d’apporter une amélioration à la recherche de solutions en faisant appel à une heuristique de recherche de solutions sur les feuilles du sous-arbre.Une deuxième contribution concerne les stratégies de parcours de l’arbre d’exploration. Nous étudions une stratégie récente qui fait un compromis entre un parcours en meilleur d’abord et un parcours en profondeur d’abord. Nous proposons des variantes de cet algorithme qui privilégient l’exploration des régions faisables.Les algorithmes proposés, testés sur un banc d’essai reconnu par la communauté, obtiennent des temps comparables à l’état de l’art. / In recent years, the Interval Branch and Bound method has been used more and more to solve constraint global optimization problems, especially those which are non-convex. Unlike many of its competitors, this method makes it possible to prove the optimality of a solution with a given level of accuracy. On the other hand, its tree exploration process implies an exponential complexity in time and memory in the worst case. That is why, the development of acceleration techniques defines an important piece of research.A first contribution concerns the interval filtering operators designed to reduce the search space. We propose a new interval filtering operator, named TEC, that generalizes to several dimensions the constructive disjunction principle used by the existing CID operator. TEC constructs a bounded subtree using a branch and contract process and returns the parallel-to-axes hull of the leaf domains/boxes. We propose two variants of TEC exploiting its tree structure. The first variant, named Graham-TEC, learns implicit linear constraints, used for improving the contraction. The second one, named TEC-UB, searches for a good feasible point inside a leaf box of the TEC subtree.A second contribution concerns the node selection strategies. We have studied a recent strategy that makes a compromise between a best-first search and a depth-first search and have proposed variants of this algorithm that favor the exploration of feasible regions.
|
Page generated in 0.1366 seconds