Made available in DSpace on 2014-06-12T15:57:08Z (GMT). No. of bitstreams: 2 arquivo3142_1.pdf: 2136149 bytes, checksum: 9584d05181d7f6e862c757ce418c8701 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / de Siqueira Teles, Fabrício; Pierre Louis Robin, Jacques. Towards Model-Driven Engineering Constraint-Based Scheduling Applications. 2008. Dissertação (Mestrado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2008.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-01-15T14:16:25Z No. of bitstreams: 1 denisemanueldacostavargas.pdf: 16589539 bytes, checksum: 44a0869db27ffd5f8254f85fb69ab78c (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-01-25T17:40:31Z (GMT) No. of bitstreams: 1 denisemanueldacostavargas.pdf: 16589539 bytes, checksum: 44a0869db27ffd5f8254f85fb69ab78c (MD5) / Made available in DSpace on 2016-01-25T17:40:31Z (GMT). No. of bitstreams: 1 denisemanueldacostavargas.pdf: 16589539 bytes, checksum: 44a0869db27ffd5f8254f85fb69ab78c (MD5) Previous issue date: 2015-11-05 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Problemas de Otimização Multiobjetivo (POMs) com restrições são frequentes em diversas áreas das ciências e engenharia, entre elas a Otimização Estrutural (OE). Apesar da Evolução Diferencial (ED) ser uma metaheurística muito atraente na resolução de problemas do mundo real, há uma carência na literatura de discussões sobre o desempenho em POMs de OE. Na sua grande maioria os problemas de OE apresentam restrições. Nesta tese utiliza-se uma técnica para o tratamento de restrições chamada de APM (Adaptive Penalty Method) que tem histórico de bons resultados quando aplicada em problemas monobjetivo de OE. Pelo potencial da ED na resolução de problemas do mundo real e da técnica APM em OE, juntamente com a escassez de trabalhos envolvendo esses elementos em POMs de OE, essa tese apresenta um estudo de um algoritmo bem conhecido de ED acoplado à técnica APM nesses problemas. Experimentos computacionais considerando cenários sem e com inserção de informações de preferência do usuário foram realizados em problemas com variáveis continuas e discretas. Os resultados foram comparados aos encontrados na literatura, além dos obtidos pelo algoritmo que representa o estado da arte. Comparou-se também os resultados obtidos pelo mesmo algoritmo de ED adotado, porém sem ser acoplado à técnica APM, objetivando investigar sua influência no desempenho da combinação proposta. As vantagens e desvantagens do algoritmo proposto em cada cenário são apresentadas nessa tese, além de sugestões para trabalhos futuros. / Multiobjective Optimization Problems (MOPs) with constraints are common in many areas of science and engineering, such as Structural Optimization (SO). In spite of Differential Evolution (DE) being a very attractive metaheuristic in real-world problems, no work was found assessing its performance in SO MOPs. Most OE problems have constraints. This thesis uses the constraint handling technique called Adaptive Penalty Method (APM) that has a history of good results when applied in monobjective problems of SO. Due to the potential of DE in solving real world problems and APM in SO problems, and also with the lack of studies involving these elements in SO MOPs, this work presents a study of a well-known DE algorithm coupled to the APM technique in these problems. Computational experiments considering scenarios with and without inclusion of user preference information were performed in problems with continuous and discrete variables. The results were compared with those in the literature, in addition to those obtained by the algorithm that represents the state of the art. They were also compared to the results obtained by the same DE algorithm adopted, but without the APM technique, aiming at investigating the influence of the APM technique in their performance. The advantages and disadvantages of the proposed algorithm in each scenario are presented in this research, as well as suggestions for future works.

On s'intéresse à l'étude d'algorithmes stochastiques pour l'optimisation numérique boîte-noire. Dans la première partie de cette thèse, on présente une méthodologie pour évaluer efficacement des stratégies d'adaptation du step-size dans le cas de l'optimisation boîte-noire sans contraintes. Le step-size est un paramètre important dans les algorithmes évolutionnaires tels que les stratégies d'évolution; il contrôle la diversité de la population et, de ce fait, joue un rôle déterminant dans la convergence de l'algorithme. On présente aussi les résultats empiriques de la comparaison de trois méthodes d'adaptation du step-size. Ces algorithmes sont testés sur le testbed BBOB (black-box optimization benchmarking) de la plateforme COCO (comparing continuous optimisers). Dans la deuxième partie de cette thèse, sont présentées nos contributions dans le domaine de l'optimisation boîte-noire avec contraintes. On analyse la convergence linéaire d'algorithmes stochastiques adaptatifs pour l'optimisation sous contraintes dans le cas de contraintes linéaires, gérées avec une approche Lagrangien augmenté adaptative. Pour ce faire, on étend l'analyse par chaines de Markov faite dans le cas d'optimisation sans contraintes au cas avec contraintes: pour chaque algorithme étudié, on exhibe une classe de fonctions pour laquelle il existe une chaine de Markov homogène telle que la stabilité de cette dernière implique la convergence linéaire de l'algorithme. La convergence linéaire est déduite en appliquant une loi des grands nombres pour les chaines de Markov, sous l'hypothèse de la stabilité. Dans notre cas, la stabilité est validée empiriquement. / We investigate various aspects of adaptive randomized (or stochastic) algorithms for both constrained and unconstrained black-box continuous optimization. The first part of this thesis focuses on step-size adaptation in unconstrained optimization. We first present a methodology for assessing efficiently a step-size adaptation mechanism that consists in testing a given algorithm on a minimal set of functions, each reflecting a particular difficulty that an efficient step-size adaptation algorithm should overcome. We then benchmark two step-size adaptation mechanisms on the well-known BBOB noiseless testbed and compare their performance to the one of the state-of-the-art evolution strategy (ES), CMA-ES, with cumulative step-size adaptation. In the second part of this thesis, we investigate linear convergence of a (1 + 1)-ES and a general step-size adaptive randomized algorithm on a linearly constrained optimization problem, where an adaptive augmented Lagrangian approach is used to handle the constraints. To that end, we extend the Markov chain approach used to analyze randomized algorithms for unconstrained optimization to the constrained case. We prove that when the augmented Lagrangian associated to the problem, centered at the optimum and the corresponding Lagrange multipliers, is positive homogeneous of degree 2, then for algorithms enjoying some invariance properties, there exists an underlying homogeneous Markov chain whose stability (typically positivity and Harris-recurrence) leads to linear convergence to both the optimum and the corresponding Lagrange multipliers. We deduce linear convergence under the aforementioned stability assumptions by applying a law of large numbers for Markov chains. We also present a general framework to design an augmented-Lagrangian-based adaptive randomized algorithm for constrained optimization, from an adaptive randomized algorithm for unconstrained optimization.

The introduction of initial margin requirements for non-cleared OTC derivatives has made it possible to optimize initial margin when considering a network of trading participants. Applying CMA-ES, this thesis has explored a new method to handle the nonlinear constraints present in the initial margin optimization problem. The idea behind the method and the research question in this thesis are centered around leveraging data created during optimization. Specifically, by creating a linear approximation of the feasible region using support vector machines and in turn applying a repair strategy based on projection. The hypothesis was that by repairing solutions an increase in convergence speed should follow. In order to answer the research question, a reference method was at first created. Here CMA-ES along with feasibility rules was used, referred to as CMA-FS. The proposed method of optimization data leveraging (ODL) was then appended to CMA-FS, referred to as CMA-ODL. Both algorithms were then applied to a single initial margin optimization problem 100 times each with different random seeds used for sampling in the optimization algorithms. The results showed that CMA-ODL converged significantly faster than CMA-FS, without affecting final objective values significantly negatively. Convergence was measured in terms of iterations and not computational time. On average a 5% increase in convergence speed was achieved with CMA-ODL. No significant difference was found between CMA-FS and CMA-ODL in terms of the percentage of infeasible solutions generated. A reason behind the lack of a reduction in violations can be due to how ODL is implemented with the CMA-ES algorithm. Specifically, ODL will lead to a greater number of feasible solutions being available during recombination in CMA-ES. Although, due to the projection, the solutions after projection are not completely reflective of the actual parameters used for that generation. The projection should also bias the algorithm towards the boundary of the feasible region. Still, the performative difference in terms of convergence speed was significant. In conclusion, the proposed boundary constraint handling method increased performance, but it is not known whether the method has any major practical applicability, due to the restriction to only considering the number of iterations and not the computational time. / Införandet av initial margin för non-cleared OTC derivatives har gjort det möjligt att optimera initial margin när ett flertal marknadsdeltagare tas till hänsyn. Denna uppsats har applicerat CMA-ES och specifikt undersökt en ny metod för hantering av de icke-linjära bivillkoren som uppstår när initial margin optimeras. Idén bakom metoden och forskningsfrågan i rapporten bygger på att utnyttja data som generas vid optimering. Detta görs specifikt genom att den icke-linjära tillåtna regionen approximeras linjärt med support vector machines. Därefter används en reparationsstrategi bestående av projicering för att reparera otillåtna lösningar. Hypotesen i uppsatsen var att genom att reparera lösningar så skulle konvergenshastigheten öka. För att svara på forskningsfrågan så togs en referensmetod fram, där CMA-ES och feasibility rules användes för att hantera icke-linjära bivillkor. Denna version av CMA-ES kallades CMA-FS. Sedan integrerades den nya metoden med CMA-FS, denna version kallades för CMA-ODL. Därefter så applicerades båda algoritmer 100 gånger på ett initial margin optimeringsproblem, där olika seeds användes för generering av lösningar i algoritmerna. Resultaten visade att CMA-ODL konvergerade signifikant snabbare än CMA-FS utan att påverka optimeringsresultatet negativt. Med CMA-ODL så ökade konvergenshastigheten med ungefär 5%. Konvergens mättes genom antal iterationer och inte beräkningstid. Ingen signifikant skillnad mellan CMA-ODL och CMA-FS observerades när de jämfördes med avseende på mängden icke-tillåtna lösningar genererade. En anledning varför ingen skillnad observerades är hur den nya metoden var integrerad med CMA-ES algoritmen. Den tilltänkta metoden leder till att fler tillåtna lösningar är tillgängliga när CMA-ES ska bilda nästa generation men eftersom lösningar projiceras så kommer dom inte att reflektera dom parametrar som användes för att faktiskt generera dom. Projiceringen leder också till att fler lösningar på randen av det tillåtna området kommer att genereras. Sammanfattningsvis så observerades fortfarande en signifikant ökning i konvergenshastighet för CMA-ODL men det är oklart om algoritmen är praktiskt användbar p.g.a. restriktionen att enbart betrakta antalet iterationer och inte total beräkningstid.