Steel has become widespread and now it can be accepted as the candidate of being main material for the structural systems with its excellent properties. Its high quality, durability, stability, low maintenance costs and opportunity of fast construction are the advantages of steel. The correct use of the material is important for steel&rsquo / s bright prospects. The need for weight optimization becomes important at this point. Available sources are used economically through optimization. Optimization brings material savings and at last economy. Optimization can be achieved with different ways. This thesis investigates the effect of the appropriate choice of column orientation on minimum weight design of steel frames. Evolution strategies (ESs) method, which is one of the three mainstreams of evolutionary algorithms, is used as the optimizer in this study to deal with the current problem of interest. A new evolution strategy (ES) algorithm is proposed, where design variables are considered simultaneously as cross-sectional dimensions (size variables) and orientation of column members (orientation variables). The resulting algorithm is computerized in a design optimization software called OFES. This software has many capabilities addressing to issues encountered in practical applications, such as producing designs according to TS-648 and ASD-AISC design provisions. The effect of column orientations is numerically studied using six examples with practical design considerations. In these examples, first steel structures are sized for minimum weight considering the size variables only, where orientations of the column members are initially assigned and kept constant during optimization process. Next, the weight optimum design of structures are implemented using both size and orientation design variables. It is shown that the inclusion of column orientations produces designs which are generally 4 to 8 % lesser in weight than the cases where only size variables are employed.

協同規劃、預測與補貨（Collaborative Planning, Forecasting and Replenishment; CPFR）是協同商務中一個新發展的應用實務，主要強調供應鏈上買賣雙方協同合作流程的概念，以提升供應鏈上流程的處理效率。企業需要利用協同合作所獲得之即時資訊來進行預測，減少不確定性因素之影響，提高預測之準確性。CPFR流程下協同預測階段分為銷售預測與訂單預測，兩者之預測項目與目的並不相同且所需要之資訊亦有所差異。銷售預測著重在市場需求部份的預測；訂單預測則是依據銷售預測、存貨狀況與生產面因素來做實際訂單之預測。由於訂單預測作為下個階段之實際補貨的參考，其預測準確性的要求就格外重要。然而研究文獻多偏向CPFR流程架構與導入效益等管理議題，雖有少數針對預測模型之研究，但亦以企業內部銷售預測為主，並未有文獻提出跨企業之協同訂單預測模型，故CPFR流程下訂單預測方法之研究探討有其必要性。本研究以CPFR流程中接續銷售預測之訂單預測階段為研究主題，蒐集近年來國內外研究CPFR與訂單預測之相關文獻為基礎，歸納出協同合作下訂單預測所須具備之屬性與影響因素，並作為模型解釋變數，透過時間序列、多元迴歸與演化策略法（Evolution Strategies）的結合，建構一個統整供應鏈上、下游協同資訊與符合CPFR流程下訂單預測特性之預測模型。最後以國內某製造業公司與其顧客（一國際大型零售商）之訂單資料進行模型驗證，與單純使用時間序列方法或統計迴歸分析的預測結果作績效評比，實驗顯示本研究所提出之訂單預測方法較傳統使用單一時間序列或統計回歸方法之預測結果佳。 / Collaborative Planning, Forecasting and Replenishment (CPFR) is nowadays a practice of collaborative commerce, emphasizing buyers and sellers’ coordination for the efficiency of the process in supply chain. Enterprises utilize instant information obtained from coordinate processes to forecast in order to reduce the influence of the uncertain factor and improve forecasting accuracy. The stage of the collaborative forecasting in CPFR process is divided into sales forecasting and order forecasting which make differences on forecasting objective, subject, and information needed. Sales forecasting focuses on the prediction of the market demand; order forecasting is the prediction of the real orders according to sales forecasting, stock state and productive factor. The accuracy of order forecasting is extremely important because it is regarded as the reference of the replenishment at next stag. The literatures about CPFR mostly probe into manage topics like benefits of implementation or process structures though there are some researches on the forecasting model which mainly discuss sales forecasting inside enterprises. Therefore, it is necessary to investigate into the coordinative order forecasting model under CPFR process. This paper regards order forecasting following sales forecasting in CPFR as the theme. Besides generalizing the necessary parameter of order forecasting based on literatures review, the research presents a hybrid forecasting model which considers coordinative information and order forecasting requirements. It integrates the time series model, regression model, and use evolution strategies to determine its coefficients efficiently. The validity of the forecasting model is verified by experiment on order datum from one manufacturer in Taiwan and its international retailer. The results show that the order forecasting model has better forecasting performance than not only the time series model but also the ordinary regression model.

Názov práce: Evoluční algoritmy a aktivní učení Autor: Jakub Repický Katedra: Katedra teoretické informatiky a matematické logiky Vedúci diplomovej práce: doc. RNDr. Ing. Martin Holeňa, CSc., Ústav informa- tiky, Akademie věd České republiky Abstrakt: Vyhodnotenie ciel'ovej funkcie v úlohách spojitej optimalizácie často do- minuje výpočtovej náročnosti algoritmu. Platí to najmä v prípade black-box fun- kcií, t. j. funkcií, ktorých analytický popis nie je známy a ktoré sú vyhodnocované empiricky. Témou urýchl'ovania black-box optimalizácie s pomocou náhradných modelov ciel'ovej funkcie sa zaoberá vel'a autorov a autoriek. Ciel'om tejto dip- lomovej práce je vyhodnotit' niekol'ko metód, ktoré prepájajú náhradné modely založené na Gaussovských procesoch (GP) s Evolučnou stratégiou adaptácie ko- variančnej matice (CMA-ES). Gaussovské procesy umožňujú aktívne učenie, pri ktorom sú body pre vyhodnotenie vyberané s ciel'om zlepšit' presnost' modelu. Tradičné náhradné modely založené na GP zah'rňajú Metamodelom asistovanú evolučnú stratégiu (MA-ES) a Optimalizačnú procedúru pomocou Gaussovských procesov (GPOP). Pre účely tejto práce boli oba prístupy znovu implementované a po prvý krát vyhodnotené na frameworku Black-Box...

協同規劃、預測與補貨﹙Collaborative Planning, Forecasting and Replenishment; CPFR﹚是協同商務中的一個應用實務，主要強調供應鏈上買賣雙方協同合作流程的概念，以提升供應鏈上流程的處理效率。未來企業的競爭將是產品背後整體供應鏈的激烈競爭，能對於不斷變化的市場需求作出有效預測，進而快速反應的企業將脫穎而出。對於庫存與補貨的掌控能力更將是企業決勝的關鍵因素之一。 CPFR 中的補貨模型是根據銷售預測、訂單預測、存貨策略與供給面資訊來做實際訂單，以作為補貨之用。補貨模式的準確性可以使賣方針對不同的需求來有效分配未來訂單預測的需求量，並降低安全庫存；買方則可根據訂單預測來調整庫存策略與採購數量。 現今廣用的供應商管理存貨（Vendor Managed Inventory, VMI）並沒有像CPFR加入更多的協同項目與精神，因此比較VMI與CPFR的補貨流程的差異性與優劣性，進而提供企業導入CPFR的補貨流程是相當重要的。 本研究以補貨階段為主題，除了探討協同補貨模式所需具備的屬性與輸入變數外，更將建構一個整合供應鏈上、下游協同資訊與符合協同訂單預測特性之預測模型，以提升補貨準確度，進而堆砌出整個CPFR 協同補貨模式，並加以與現今企業廣為採用的供應商管理存貨（Vendor Managed Inventory, VMI）的補貨模式進行比較，證明CPFR優於VMI，進而可供欲導入CPFR 流程下協同補貨模式或一般補貨模式的相關人員之參考。 / CPFR (Collaborative Planning, Forecasting, and Replenishment) is one of the applications of collaborative business. The stressed concept is the cooperation process of sellers and buyers on the supply chain in order to increase the handling efficiency. In the future, the industries would compete on the whole supply chains behind products—only the industry that is capable of making accurate predictions according to the constantly changing market and reacts immediately has the chance of winning. Being able to control the inventory and supply effectively would be one of the key factors leading to an industry’s success. The replenishment model of CPFR is to fill out the order according to the sales prediction, order prediction, inventory strategy, and supply information. The precision of the replenishment model could affect both suppliers and customers. The former can distribute products properly and meet the different demands from the upcoming orders so as to reduce inventory; the latter are able to revise the inventory strategy and amount of order according to the order prediction. A few research papers aimed at the replenishment model, though, most still focus on the management issues like the process framework of CPFR and the implementation benefit. Hence, establishing both an information system that coordinates customer demand with suppliers and a collaborative replenishment model that increases the accuracy of predictions is fairly important. The phase of replenishment, as the subject of this study, will approach on parameters the collaborative replenishment model needs to input and combine evolution strategies with tabu search to establish a replenishment model under the process of CPFR.

[pt] Através das técnicas utilizadas em Identificação de Sistemas é possível obter um modelo matemático para um sistema dinâmico somente a partir de dados medidos de suas entradas e saídas. Por possuírem comportamento naturalmente dinâmico e um procedimento de treinamento simples e rápido, o uso de redes neurais do tipo Echo State Networks (ESNs) é vantajoso nesta área. Entretanto, as ESNs possuem hiperparâmetros que devem ser ajustados para que obtenham um bom desempenho em uma dada tarefa, além do fato de que a inicialização aleatória de pesos da camada interna destas redes (reservatório) nem sempre ser a ideal em termos de desempenho. Por teoricamente conseguirem obter boas soluções com poucas avaliações, o AEIQ-R (Algoritmo Evolutivo com Inspiração Quântica e Representação Real) e a estratégia evolucionária com adaptação da matriz de covariâncias (CMA-ES) representam alternativas de algoritmos evolutivos que permitem lidar de maneira eficiente com a otimização de hiperparâmetros e/ou pesos desta rede. Sendo assim, este trabalho propõe um modelo neuroevolucionário que define automaticamente uma ESN para aplicações de Identificação de Sistemas. O modelo inicialmente foca na otimização dos hiperparâmetros da ESN utilizando o AEIQ-R ou o CMA-ES, e, num segundo momento, seleciona o reservatório mais adequado para esta rede, o que pode ser feito através de uma segunda otimização focada no ajuste de alguns pesos do reservatório ou por uma escolha simples baseando-se em redes com reservatórios aleatórios. O método proposto foi aplicado a 9 problemas benchmark da área de Identificação de Sistemas, apresentando bons resultados quando comparados com modelos tradicionais. / [en] Through System Identification techniques is possible to obtain a mathematical model for a dynamic system from its input/output data. Due to their intrinsic dynamic behavior and simple and fast training procedure, the use of Echo State Networks, which are a kind of neural networks, for System Identification is advantageous. However, ESNs have global parameters that should be tuned in order to improve their performance in a determined task. Besides, a random reservoir may not be ideal in terms of performance. Due to their theoretical ability of obtaining good solutions with few evaluations, the Real Coded Quantum-Inspired Evolutionary Algorithm (QIEA-R) and the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) represent efficient alternatives of evolutionary algorithms for optimizing ESN global parameters and/or weights. Thus, this work proposes a neuro-evolutionary method that automatically defines an ESN for System Identification problems. The method initially focuses in finding the best ESN global parameters by using the QIEA-R or the CMA-ES, then, in a second moment, in selecting its best reservoir, which can be done by a second optimization focused on some reservoir weights or by doing a simple choice based on networks with random reservoirs. The method was applied to 9 benchmark problems in System Identification, showing good results when compared to traditional methods.

Au cours des dernières années, s’est développé un intérêt tout particulier pour l’optimisation sans dérivée. Ce domaine de recherche se divise en deux catégories: une déterministe et l’autre stochastique. Bien qu’il s’agisse du même domaine, peu de liens ont déjà été établis entre ces deux branches. Cette thèse a pour objectif de combler cette lacune, en montrant comment les techniques issues de l’optimisation déterministe peuvent améliorer la performance des stratégies évolutionnaires, qui font partie des meilleures méthodes en optimisation stochastique. Sous certaines hypothèses, les modifications réalisées assurent une forme de convergence globale, c’est-à-dire une convergence vers un point stationnaire de premier ordre indépendamment du point de départ choisi. On propose ensuite d’adapter notre algorithme afin qu’il puisse traiter des problèmes avec des contraintes générales. On montrera également comment améliorer les performances numériques des stratégies évolutionnaires en incorporant un pas de recherche au début de chaque itération, dans laquelle on construira alors un modèle quadratique utilisant les points où la fonction coût a déjà été évaluée. Grâce aux récents progrès techniques dans le domaine du calcul parallèle, et à la nature parallélisable des stratégies évolutionnaires, on propose d’appliquer notre algorithme pour résoudre un problème inverse d’imagerie sismique. Les résultats obtenus ont permis d’améliorer la résolution de ce problème. / In recent years, there has been significant and growing interest in Derivative-Free Optimization (DFO). This field can be divided into two categories: deterministic and stochastic. Despite addressing the same problem domain, only few interactions between the two DFO categories were established in the existing literature. In this thesis, we attempt to bridge this gap by showing how ideas from deterministic DFO can improve the efficiency and the rigorousness of one of the most successful class of stochastic algorithms, known as Evolution Strategies (ES’s). We propose to equip a class of ES’s with known techniques from deterministic DFO. The modified ES’s achieve rigorously a form of global convergence under reasonable assumptions. By global convergence, we mean convergence to first-order stationary points independently of the starting point. The modified ES’s are extended to handle general constrained optimization problems. Furthermore, we show how to significantly improve the numerical performance of ES’s by incorporating a search step at the beginning of each iteration. In this step, we build a quadratic model using the points where the objective function has been previously evaluated. Motivated by the recent growth of high performance computing resources and the parallel nature of ES’s, an application of our modified ES’s to Earth imaging Geophysics problem is proposed. The obtained results provide a great improvement for the problem resolution.

Submitted by (ana.araujo@ufrpe.br) on 2016-06-28T16:05:18Z No. of bitstreams: 1 David Augusto Silva.pdf: 1453777 bytes, checksum: 4516b869e7e749b770a803eb7e91a084 (MD5) / Made available in DSpace on 2016-06-28T16:05:18Z (GMT). No. of bitstreams: 1 David Augusto Silva.pdf: 1453777 bytes, checksum: 4516b869e7e749b770a803eb7e91a084 (MD5) Previous issue date: 2011-07-01 / The techniques for Time Series Analysis and Forecasting have great presence on the literature over the years. The computational resources combined with statistical techniques are improving the predictive results, and these results have been become increasingly accurate. Computational methods base on Artificial Neural Networks (ANN) and Evolutionary Computing (EC) are presenting a new approach to solve the Time Series Analysis and Forecasting problem. These computational methods are contained in the branch of Artificial Intelligence (AI), and they are biologically inspired, where the ANN models are based on the neural structure of intelligent organism, and the EC uses the concept of nature selection of Charles Darwin. Both methods acquire experience from prior knowledge and example of the given problem. In particular, for the Time Series Forecasting Problem, the objective is to find the predictive model with highest forecast perfomance, where the performance measure are statistical errors. However, there is no universal criterion to identify the best performance measure. Since the ANNs are the predictive models, the EC will constantly evaluate the forecast performance of the ANNs, using a fitness functions to guide the predictive model for an optimal solution. The Data Envelopment Analysis (DEA) was employed to predictive determine the best combination of variables based on the relative efficiency of the best models. Therefore, this work to study the optimization Fitness Function process with Data Envelopment Analysis applied the Intelligence Hybrid System for time series forecasting problem. The data analyzed are composed by financial data series, agribusiness and natural phenomena. The C language program was employed for implementation of the hybrid intelligent system and the R Environment version 2.12 for analysis of DEA models. In general, the perspective of using DEA procedure to evaluate the fitness functions were satisfactory and serves as an additional resource in the branch of time series forecasting. Researchers need to compute the results under different perspectives, whether in the matter of the computational cost of implementing a particular function or which function was more efficient in the aspect of assessing which combinations are unwanted saving time and resources. / As técnicas de análise e previsão de séries temporais alcançaram uma posição de distinção na literatura ao longo dos anos. A utilização de recursos computacionais, combinada com técnicas estatísticas, apresenta resultados mais precisos quando comparados com os recursos separadamente. Em particular, técnicas que usam Redes Neurais Artificiais (RNA) e Computação Evolutiva (CE), apresenta uma posição de destaque na resolução de problemas de previsão na análise de séries temporais. Estas técnicas de Inteligência Artificial (AI) são inspiradas biologicamente, no qual o modelo de RNA é baseado na estrutura neural de organismos inteligentes, que adquirem conhecimento através da experiência. Para o problema de previsão em séries temporais, um fator importante para o maior desempenho na previsão é encontrar um método preditivo com a melhor acurácia possível, tanto quanto possível, no qual o desempenho do método pode ser analisado através de erros de previsão. Entretanto, não existe um critério universal para identificar qual a melhor medida de desempenho a ser utilizada para a caracterização da previsão. Uma vez que as RNAs são os modelos de previsão, a CE constantemente avaliará o desempenho de previsão das RNAs, usando uma função de fitness para guiar o modelo preditivo para uma solução ótima. Desejando verificar quais critérios seriam mais eficientes no momento de escolher o melhor modelo preditivo, a Análise Envoltória de Dados (DEA) é aplicada para fornecer a melhor combinação de variáveis visando a otimização do modelo. Portanto, nesta dissertação, foi estudado o processo de otimização de Funções de Fitness através do uso da Análise Envoltória de Dados utilizando-se de técnicas hibridas de Inteligência Artificial aplicadas a área de previsão de séries temporais. O banco de dados utilizado foi obtido de séries históricas econômico- financeiras, fenômenos naturais e agronegócios obtidos em diferentes órgãos específicos de cada área. Quanto à parte operacional, utilizou-se a linguagem de programação C para implementação do sistema híbrido inteligente e o ambiente R versão 2.12 para a análise dos modelos DEA. Em geral, a perspectiva do uso da DEA para avaliar as Funções de Fitness foi satisfatório e serve como recurso adicional na área de previsão de séries temporais. Cabe ao pesquisador, avaliar os resultados sob diferentes óticas, quer seja sob a questão do custo computacional de implementar uma determinada Função que foi mais eficiente ou sob o aspecto de avaliar quais combinações não são desejadas poupando tempo e recursos.

Made available in DSpace on 2016-08-17T14:52:49Z (GMT). No. of bitstreams: 1 Aniceto_de_Deus_Pereira_Neto.pdf: 1168768 bytes, checksum: adc4488efe00f3201345ff8a783ac6bb (MD5) Previous issue date: 2008-07-25 / The restructuring and deregulation of electricity markets has caused signi¯cant changes in electrical power systems in several countries. This process has result in a market-based competition by creating an open market environment. In this new environment each generation company runs the Unit Commitment to maximize their pro¯ts, and have no obligation to meet the energy and spinning reserve demands, as happened in the past. With this new structure, the Unit Commitment problem has received special attention, since generation companies in actual model always seek the maximum pro¯t without concern to serve all demands. On the other hand, there is the system operator, which always seeks to optimize overall system at the lowest cost. So, there are two di®erent situations into this competitive market environment: generators seeking the maximum bene¯t without concern to the system security operating, and independent system operator seeking always operate the system safely and at less cost. This work presents the mathematical models and the solution Unit Commitment problem, which was implemented considering two view points: the generation companies and the system independent operator views. Moreover, an auction model is extended to PRD in a horizon of 24 hours. This auction model simulates the interaction between generators and system operator to meet demands and security of the system. The idea is to stimulate the players to o®er products to energy (primary) and reserve (Ancilar Service) markets using only prices o®ered by market operator for each product. This iterative process is ¯nalized when generators supply su±cient to meet demand, and not cause any violation on °ow limits in transmission lines. The solution method proposed for Unit Commitment is based on evolution strategies and Lagrange Relaxation, resulting in a robust hybrid algorithm. The method have been validated in a test system composed of 6 buses, 7 transmission lines and 10 generating units. The results showed the e±ciency of the hybrid model proposed, which was able to solve the unit commitment problem in its various models considered here. / A reestruturação dos mercados de energia elétrica provocou mudanças significativas nos sistemas elétricos de potência de diversos países. Neste novo ambiente, cada empresa de geração executa individualmente o Pré-Despacho para maximizar seus benefícios financeiros, e não têm a obrigação em atender suas demandas de potência e reserva girante, como acontecia no modelo tradicional. Por outro lado existe o operador do sistema, o qual sempre busca a otimização global do sistema ao menor custo. Assim, têm-se duas situações distintas neste ambiente competitivo: os geradores buscando o máximo benefício sem preocupação com a segurança operativa do sistema, e o operador independente buscando sempre operar o sistema de forma segura e ao menor custo. Este trabalho apresenta as modelagens matemáticas e a solução do Pré- Despacho executado sob os dois pontos de vista: dos agentes de geração e do operador independente do sistema. Além do mais, um modelo de leilão é estendido para o PRD num horizonte de 24 horas. Este modelo simula a interação entre os agentes de geração e o operador do sistema na busca por uma solução única que concilie o interesse de ambos. A idéia é estimular os agentes geradores a ofertarem os produtos para os mercados de energia (primário) e de reserva (Serviço Ancilar) mediante oferta de preços pelo operador do mercado para os respectivos produtos. Esse procedimento iterativo é finalizado quando a oferta dos geradores for suficiente para atender completamente a demanda e, não provocar violações em nenhum limite de fuxos na malha de transmissão. O método de solução proposto para o Pré-Despacho é baseado em estratégias evolutivas e Relaxação de Lagrange, resultando em um modelo híbrido robusto. Os modelos e técnicas foram validados em um sistema teste composto por 6 barras, 7 linhas de transmissão e 10 unidades geradoras. Os resultados obtidos demonstraram a eficiência do método de solução, o qual se mostrou capaz de resolver o problema de Pré-Despacho nas suas diversas modelagens utilizadas.

Dans ce manuscrit de thèse, mes travaux portent sur la combinaison de méthodes pour la prise de décision séquentielle (plusieurs étapes de décision corrélées) dans des environnements complexes et incertains. Les méthodes mises au point sont essentiellement appliquées à des problèmes de gestion et de production d'électricité tels que l'optimisation de la gestion des stocks d'énergie dans un parc de production pour anticiper au mieux la fluctuation de la consommation des clients.Le manuscrit comporte 7 chapitres regroupés en 4 parties : Partie I, « Introduction générale », Partie II, « État de l'art », Partie III, « Contributions » et Partie IV, « Conclusion générale ».Le premier chapitre (Partie I) introduit le contexte et les motivations de mes travaux, à savoir la résolution de problèmes d' « Unit commitment », c'est à dire l'optimisation des stratégies de gestion de stocks d'énergie dans les parcs de production d'énergie. Les particularités et les difficultés sous-jacentes à ces problèmes sont décrites ainsi que le cadre de travail et les notations utilisées dans la suite du manuscrit.Le second chapitre (Partie II) dresse un état de l'art des méthodes les plus classiques utilisées pour la résolution de problèmes de prise de décision séquentielle dans des environnements incertains. Ce chapitre introduit des concepts nécessaires à la bonne compréhension des chapitres suivants (notamment le chapitre 4). Les méthodes de programmation dynamique classiques et les méthodes de recherche de politique directe y sont présentées.Le 3e chapitre (Partie II) prolonge le précédent en dressant un état de l'art des principales méthodes d’optimisation spécifiquement adaptées à la gestion des parcs de production d'énergie et à leurs subtilités. Ce chapitre présente entre autre les méthodes MPC (Model Predictive Control), SDP (Stochastic Dynamic Programming) et SDDP (Stochastic Dual Dynamic Programming) avec pour chacune leurs particularités, leurs avantages et leurs limites. Ce chapitre complète le précédent en introduisant d'autres concepts nécessaires à la bonne compréhension de la suite du manuscrit.Le 4e chapitre (Partie III) contient la principale contribution de ma thèse : un nouvel algorithme appelé « Direct Value Search » (DVS) créé pour résoudre des problèmes de prise de décision séquentielle de grande échelle en milieu incertain avec une application directe aux problèmes d' « Unit commitment ». Ce chapitre décrit en quoi ce nouvel algorithme dépasse les méthodes classiques présentées dans le 3e chapitre. Cet algorithme innove notamment par sa capacité à traiter des grands espaces d'actions contraints dans un cadre non-linéaire, avec un grand nombre de variables d'état et sans hypothèse particulière quant aux aléas du système optimisé (c'est à dire applicable sur des problèmes où les aléas ne sont pas nécessairement Markovien).Le 5e chapitre (Partie III) est consacré à un concept clé de DVS : l'optimisation bruitée. Ce chapitre expose une nouvelle borne théorique sur la vitesse de convergence des algorithmes d'optimisation appliqués à des problèmes bruités vérifiant certaines hypothèses données. Des méthodes de réduction de variance sont également étudiées et appliquées à DVS pour accélérer sensiblement sa vitesse de convergence.Le 6e chapitre (Partie III) décrit un résultat mathématique sur la vitesse de convergence linéaire d’un algorithme évolutionnaire appliqué à une famille de fonctions non quasi-convexes. Dans ce chapitres, il est prouvé que sous certaines hypothèses peu restrictives sur la famille de fonctions considérée, l'algorithme présenté atteint une vitesse de convergence linéaire.Le 7e chapitre (Partie IV) conclut ce manuscrit en résumant mes contributions et en dressant quelques pistes de recherche intéressantes à explorer. / This thesis is dedicated to sequential decision making (also known as multistage optimization) in uncertain complex environments. Studied algorithms are essentially applied to electricity production ("Unit Commitment" problems) and energy stock management (hydropower), in front of stochastic demand and water inflows. The manuscript is divided in 7 chapters and 4 parts: Part I, "General Introduction", Part II, "Background Review", Part III, "Contributions" and Part IV, "General Conclusion". This first chapter (Part I) introduces the context and motivation of our work, namely energy stock management. "Unit Commitment" (UC) problems are a classical example of "Sequential Decision Making" problem (SDM) applied to energy stock management. They are the central application of our work and in this chapter we explain main challenges arising with them (e.g. stochasticity, constraints, curse of dimensionality, ...). Classical frameworks for SDM problems are also introduced and common mistakes arising with them are be discussed. We also emphasize the consequences of these - too often neglected - mistakes and the importance of not underestimating their effects. Along this chapter, fundamental definitions commonly used with SDM problems are described. An overview of our main contributions concludes this first chapter. The second chapter (Part II) is a background review of the most classical algorithms used to solve SDM problems. Since the applications we try to solve are stochastic, we there focus on resolution methods for stochastic problems. We begin our study with classical Dynamic Programming methods to solve "Markov Decision Processes" (a special kind of SDM problems with Markovian random processes). We then introduce "Direct Policy Search", a widely used method in the Reinforcement Learning community. A distinction is be made between "Value Based" and "Policy Based" exploration methods. The third chapter (Part II) extends the previous one by covering the most classical algorithms used to solve UC's subtleties. It contains a state of the art of algorithms commonly used for energy stock management, mainly "Model Predictive Control", "Stochastic Dynamic Programming" and "Stochastic Dual Dynamic Programming". We briefly overview distinctive features and limitations of these methods. The fourth chapter (Part III) presents our main contribution: a new algorithm named "Direct Value Search" (DVS), designed to solve large scale unit commitment problems. We describe how it outperforms classical methods presented in the third chapter. We show that DVS is an "anytime" algorithm (users immediately get approximate results) which can handle large state spaces and large action spaces with non convexity constraints, and without assumption on the random process. Moreover, we explain how DVS can reduce modelling errors and can tackle challenges described in the first chapter, working on the "real" detailed problem without "cast" into a simplified model. Noisy optimisation is a key component of DVS algorithm; the fifth chapter (Part III) is dedicated to it. In this chapter, some theoretical convergence rate are studied and new convergence bounds are proved - under some assumptions and for given families of objective functions. Some variance reduction techniques aimed at improving the convergence rate of graybox noisy optimization problems are studied too in the last part of this chapter. Chapter sixth (Part III) is devoted to non-quasi-convex optimization. We prove that a variant of evolution strategy can reach a log-linear convergence rate with non-quasi-convex objective functions. Finally, the seventh chapter (Part IV) concludes and suggests some directions for future work.

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.