La planification automatique est un domaine de recherche de l’Intelligence Artificielle qui vise à calculer automatiquement une séquence d’actions menant d’un état initial donné à un but souhaité. Cependant, résoudre des problèmes réalistes est généralement difficile car trouver un chemin solution peut demander d’explorer un nombre d’états croissant exponentiellement avec le nombre de variables. Pour faire face à cette explosion combinatoire, les algorithmes performants ont recours aux heuristiques ou à des solutions hiérarchiques, décomposant le problème en sous-problèmes plus petits et plus simples. Dans une grande majorité des cas, le planificateur doit prendre en compte un certain nombre de contraintes telles que des phases d’actions prédéfinies ou des protocoles. Ces contraintes aident à résoudre le problème en élaguant un grand nombre de branches de l’arbre de recherche. Nous proposons alors une nouvelle méthode pour modéliser et résoudre des problèmes de planification déterministe en se basant sur une approche hiérarchique et heuristique. Nous nous sommes inspirés des formalismes de programmation structurée afin de fournir à l’utilisateur un cadre de travail plus intuitif pour la modélisation des domaines de planification hiérarchique. D’autre part, nous avons proposé un algorithme de planification capable d’exploiter ce formalisme et composer des stratégies à différents niveaux de granularité, ce qui lui permet de planifier rapidement une stratégie globale, tout en étant en mesure de pallier aux difficultés rencontrées à plus bas niveau. Cet algorithme a fait ses preuves face au principal planificateur HTN, SHOP2, sur des problèmes de planification classique. / Automated planning is a field of Artificial Intelligence which aims at automatically computing a sequence of actions that lead to some goals from a given initial state. However, solving realistic problems is challenging because finding a solution path may require to explore an exponential number of states with regard to the number of state variables. To cope with this combinatorial explosion, efficient algorithms use heuristics, which guide the search towards optimistic or approximate solutions. Remarkably, hierarchical methods iteratively decompose the planning problem into smaller and much simpler ones. In a vast majority of problems, the planner must deal with constraints, such as multiple predefined phases or protocols. Such constraints generally help solving the planning problem, because they prune lots of search paths where these constraints do not hold. In this thesis, we assume that these constraints are known and given to the planner. We thus propose a new method to model and solve a deterministic planning problem, based on a hierarchical and heuristic approach and taking advantage of these constraints. We inspired ourselves from structured programming formalisms in order to offer a more intuitive modeling framework in the domain of hierarchical planning to the user. We also proposed a planning algorithm able to exploit this formalism and build strategies at various levels of granularity, thus allowing to plan quickly a global strategy, while still being able to overcome the difficulties at lower level. This algorithm showed its performances compared with the main HTN planner, SHOP2, on classical planning problems.

Seismic inversion using a global optimization algorithm is a non-linear, model-driven process. It yields an optimal solution of the cost function – reflectivity/acoustic impedance, when prior information is sparse. The inversion result offers detailed interpretations of thin layers, internal stratigraphy, and lateral continuity and connectivity of sand bodies. This study compared two stable and robust global optimization techniques, Simulated Annealing (SA) and Basis Pursuit Inversion (BPI) as applied to post-stack seismic data from the Gulf of Mexico. Both methods use different routines and constraints to search for the minimum error energy function. Estimation of inversion parameters in SA is rigorous and more reliable because it depends on prior knowledge of subsurface geology. The BPI algorithm is a more robust deterministic process. It was developed as an alternative method to incorporating a priori information. Results for the Gulf of Mexico show that BPI gives a better stratigraphic and structural actualization due to its capacity to delineate layers thinner than the tuning thickness. The SA algorithm generates both absolute and relative impedances, which provide both qualitative and quantitative characterization of thin-bed reservoirs.

O Serviço de Gerenciamento de Fluxo de Tráfego Aéreo (ATFM) estabelece um controle de fluxo seguro, ordenado e eficiente de acordo com a capacidade da infraestrutura e dos serviços de controle. O Gerenciamento ´e realizado com o auxílio de sistemas automatizados. Tais sistemas implementam programas que ajustam a demanda de voos à capacidade do espaço aéreo. Algoritmos simples podem sugerir medidas ATFM para solucionar a saturação em um conjunto restrito de elementos regulados (aeródromos, regiões do espaço aéreo, fixos ou aerovias). A natureza interconectada dos elementos regulados, que compõem o fluxo de tráfego aéreo, demanda uma abordagem mais abrangente para atingir o uso ótimo desses recursos, uma vez que outros problemas podem surgir quando a otimização local é aplicada a um elemento sem levar em conta seus elementos relacionados. Nem sempre há a necessidade do planejamento estratégico ser um ótimo global, uma vez que cenários viáveis e sub-ótimos encontrados com menor custo computacional podem representar soluções satisfatórias. O aumento da demanda do tráfego aéreo, no entanto, tem fomentado a aplicação de programas de geração de medidas ATFM mais complexos. Esta pesquisa implementou um programa de otimização global para a geração de medidas ATFM em cenários de larga escala do mundo real. O problema ´e modelado como um problema de programa¸c~ao inteira e o modelo adotado ´e abrangente, pois prevê atraso em solo, em voo, alteração de velocidade e rerroteamento. O programa é capaz de balancear o fluxo atendendo restrições de capacidade dos aeródromos e dos setores. Além disso, foi desenvolvida uma interface de visualização e edição de dados para os cenários estudados. Dados de voos no espaço aéreo brasileiro foram processados e utilizados para testar a solução implementada e mostraram a viabilidade do método. A utilização de um programa de otimização que leva em conta mais restrições potencialmente irá contribuir com o aumento de eficiência no uso da infraestrutura e do espaço aéreo de forma segura. / The Air Traffic Flow Management Service (ATFM) establishes a secure, orderly and efficient flow control according to the capacity of the infrastructure and control services. The Management is performed with the aid of automated systems. Such systems implement programs that adjust the flight demand to the airspace capacity. Simple algorithms might suggest ATFM measures to resolve saturation in a restricted set of regulated elements (aerodromes, airspace regions, fixes or airways). The interconnected nature of the regulated elements that make up the air traffic flow requires a more comprehensive approach to achieve optimum use of these resources, since other problems can arise when local optimization is applied to an element without regard to its related elements. There is not always a need for strategic planning to be a global optimum, since feasible and sub-optimal scenarios encountered at lower computational cost might represent satisfactory solutions. The increase in air traffic demand, however, has encouraged the application of programs to generate more complex ATFM measures. This research implemented a global optimization program for the generation of ATFM measures in large-scale real-world scenarios. The problem is modeled as an integer programming problem and the adopted model is comprehensive, since it provides ground and airborne delays, change of speed and re-routing. The program is able to balance the flow by meeting capacity constraints of the aerodromes and sectors. In addition, a visualization and data editing interface was developed for the studied scenarios. Flight data in Brazilian airspace were processed and used to test the implemented solution and the viability of the method was shown. The use of an optimization program that takes into account more constraints will potentially contribute to increase the efficiency in use of infrastructure and airspace in a secure manner.

Dans les situations convexes, le problème d'optimisation globale peut être abordé par un ensemble de méthodes classiques, telles, par exemple, celles basées sur le gradient, qui ont montré leur efficacité en ce domaine. Lorsque la situation n'est pas convexe, ces méthodes peuvent être mises en défaut et ne pas trouver un optimum global. La contribution de cette thèse est une méthodologie pour la détermination de l'optimum global d'une fonction non convexe, en utilisant des algorithmes hybrides basés sur un couplage entre des algorithmes stochastiques issus de familles connues, telles, par exemple, celle des algorithmes génétiques ou celle du recuit simulé et des algorithmes déterministes perturbés aléatoirement de façon convenable. D'une part, les familles d'algorithmes stochastiques considérées ont fait preuve d'efficacité pour certaines classes de problèmes et, d'autre part, l'adjonction de perturbations aléatoires permet de construire des méthodes qui sont en théorie convergents vers un optimum global. En pratique, chacune de ces approches a ses limitations et insuffisantes, de manière que le couplage envisagé dans cette thèse est une alternative susceptible d'augmenter l'efficacité numérique. Nous examinons dans cette thèse quelques unes de ces possibilités de couplage. Pour établir leur efficacité, nous les appliquons à des situations test classiques et à un problème de nature stochastique du domaine des transports. / This thesis concerns the global optimization of a non convex function under non linear restrictions, this problem cannot be solved using the classic deterministic methods like the projected gradient algorithm and the sqp method because they can solve only the convex problems. The stochastic algorithms like the genetic algorithm and the simulated annealing algorithm are also inefficients for solving this type of problems. For solving this kind of problems, we try to perturb stocasicly the deterministic classic method and to combine this perturbation with genetic algorithm and the simulated annealing. So we do the combination between the perturbed projected gradient and the genetic algorithm, the perturbed sqp method and the genetic algorithm, the perturbed projected gradient and the simulated annealing, the Piyavskii algorithm and the genetic algorithm. We applicate the coupled algorithms to different classic examples for concretited the thesis. For illustration in the real life, we applicate the coupled perturbed projected gradient end the genetic algorithm to logistic problem eventuelly transport. In this view, we sold the efficient practices.

The research is a study of the efficiency and robustness of genetic algorithm to instances of both discrete and continuous global optimization problems. We developed genetic algorithm based heuristics to find the global minimum to problem instances considered. In the discrete category, we considered two instances of real-world space allocation problems that arose from an academic environment in a developing country. These are the university timetabling problem and hostel space allocation problem. University timetabling represents a difficult optimization problem and finding a high quality solution is a challenging task. Many approaches, based on instances from developed countries, have been reported in the literature. However, most developing countries are yet to appreciate the deployment of heuristics and metaheuristics in handling the timetabling problem. We therefore worked on an instance from a university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling problem. We adopt a simplified bottom up approach in which timetable are build around departments. Thus a small portion of real data was used for experimental testing purposes. As with similar baseline studies in literature, we employ genetic algorithm to solve this instance and show that efficient solutions that meet stated constraints can be obtained with the metaheuristics. This thesis further focuses on an instance of university space allocation problem, namely the hostel space allocation problem. This is a new instance of the space allocation problems that has not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at the allocation of categories of students into available hostel space. This must be done without violating any hard constraints but satisfying as many soft constraints as possible and ensuring optimum space utilization. We identified some issues in the problem that helped to adapt metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first highlight an initial investigation based on genetic algorithm adapted to find a good solution within the search space of the hostel space allocation problem. Some ideas are introduced to increase the overall performance of initial results based on instance of the problem from our case study. Computational results obtained are reported to demonstrate the effectiveness of the solution approaches employed. Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to determine the best parameter values that consistently give good solutions. We noted that the genetic algorithms perform well specially, when repair strategies are incorporated. This thesis pioneers the application of metaheuristics to solve the hostel space allocation problem. It provides a baseline study of the problem based on genetic algorithms with associated test data sets. We report the best known results for the test instances. It is a known fact that many real-life problems are formulated as global optimization problems with continuous variables. On the continuous global optimization category therefore, we focus on improving the efficiency and reliability of real coded genetic algorithm for solving unconstrained global optimization, mainly through hybridization with exploratory features. Hybridization has widely been recognized as one of the most attractive approach to solving unconstrained global optimization. Literatures have shown that hybridization helps component heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We therefore derived three modified forms of real coded genetic algorithm by hybridizing the standard real-coded genetic algorithm with pattern search and vector projection. These are combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The hybridization strategy used and results obtained are reported and compared with the standard real-coded genetic algorithm. Experimental studies show that all the modified algorithms perform better than the original algorithm.

Vários problemas do mundo real podem ser modelados como problemas de otimização global, os quais são comuns em diversos campos da Engenharia e Ciência. Em geral, problemas complexos e de larga-escala não podem ser resolvidos de forma eficiente por técnicas determinísticas. Desse modo, algoritmos probabilísticos, como as metaheurísticas, têm sido amplamente empregados para otimização global. Duas das principais dificuldades nesses problemas são escapar de regiões sub-ótimas e evitar convergência prematura do algoritmo. À medida que a complexidade do problema aumenta, devido a um grande número de variáveis ou de regiões sub-ótimas, o tempo computacional torna-se grande e a possibilidade de que o algoritmo encontre o ótimo global diminui consideravelmente. Para solucionar esses problemas, propõe-se o uso de técnicas de aumento ou melhoria de eficiência. Com essas técnicas, buscase desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização global, ao invés de criar um novo algoritmo de otimização ou um algoritmo híbrido. No contexto de problemas contínuos, foram desenvolvidas técnicas para determinação de uma ou mais regiões promissoras do espaço de busca, que contenham uma grande quantidade de soluções de alta qualidade, com maior chance de conterem o ótimo global. Duas das principais técnicas propostas, o Algoritmo de Otimização de Domínio (DOA) e a arquitetura de Amostragem Inteligente (SS), foram testadas com sucesso significativo em vários problemas de otimização global utilizados para benchmark na literatura. A aplicação do DOA para metaheurísticas produziu melhoria de desempenho em 50% dos problemas testados. Por outro lado, a aplicação da SS produziu reduções de 80% da quantidade de avaliações da função objetivo, bem como aumentou a taxa de sucesso em encontrar o ótimo global. Em relação a problemas discretos (binários), foram abordados problemas nos quais existem correlações entre as variáveis, que devem ser identificadas por um modelo probabilístico. Das duas técnicas de aumento de eficiência propostas para esses problemas, a técnica denominada Gerenciamento do Tamanho da População (PSM) possibilita a construção de modelos probabilísticos mais representativos. Com o PSM foi possível atingir uma redução de cerca de 50% na quantidade de avaliações, mantendo a taxa de sucesso em 100%. Em resumo, as técnicas de aumento de eficiência propostas mostramse capazes de aumentar significativamente o desempenho de metaheurísticas, tanto para problemas contínuos quanto para discretos / Several real-world problems from various fields of Science and Engineering can be modeled as global optimization problems. In general, complex and large-scale problems can not be solved eficiently by exact techniques. In this context, Probabilistic algorithms, such as metaheuristics, have shown relevant results. Nevertheless, as the complexity of the problem increases, due to a large number of variables or several regions of the search space with sub-optimal solutions, the running time augments and the probability that the metaheuristics will find the global optimum is significantly reduced. To improve the performance of metaheuristics applied to these problems, new eficiency-enhancement techniques (EETs) are proposed in this thesis. These EETs can be applied to different types of global optimization algorithms, rather than creating a new or a hybrid optimization algorithm. For continuous problems, the proposed EETs are the Domain Optimization Algorithm (DOA) and the Smart Sampling (SS) architecture. In fact, they are pre-processing algorithms that determine one or more promising regions of the search-space, containing a large amount of high-quality solutions, with higher chance of containing the global optimum. The DOA and SS were tested with signicant success in several global optimization problems used as benchmark in the literature. The application of DOA to metaheuristics produced a performance improvement in 50% of problems tested. On the other hand, the application of SS have produced reductions of 80% of the evaluations of the objective function, as well as increased the success rate of finding the global optimum. For discrete problems (binary), we focused on metaheuristics that use probabilistic models to identify correlations among variables that are frequent in complex problems. The main EET proposed for discrete problems is called Population Size Management (PSM), which improves the probabilistic models constructed by such algorithms. The PSM produced a reduction of 50% of function evaluations maintaining the success rate of 100%. In summary, the results show that the proposed EETs can significantly increase the performance of metaheuristics for both discrete and continuous problems

This manuscrit is a compact presentation of my research done between 1993 and 2008 and which concerns the global optimization of mechanical systems. General and specialized global optimization algorithms are presented. With respect to previously published work, an updated presentation of my work on composite optimization is given.

<p>Antimicrobial peptides (AMPs) play a key role in the innate immune response. They can be ubiquitously found in a wide range of eukaryotes including mammals, amphibians, insects, plants, and protozoa. In lower organisms, AMPs function merely as antibiotics by permeabilizing cell membranes and lysing invading microbes. Prediction of antimicrobial peptides is important because experimental methods used in characterizing AMPs are costly, time consuming and resource intensive and identification of AMPs in insects can serve as a template for the design of novel antibiotic. In order to fulfil this, firstly, data on antimicrobial peptides is extracted from UniProt, manually curated and stored into a centralized database called dragon antimicrobial peptide database (DAMPD). Secondly, based on the curated data, models to predict antimicrobial peptides are created using support vector machine with optimized hyperparameters. In particular, global optimization methods such as grid search, pattern search and derivative-free methods are utilised to optimize the SVM hyperparameters. These models are useful in characterizing unknown antimicrobial peptides. Finally, a webserver is created that will be used to predict antimicrobial peptides in haemotophagous insects such as Glossina morsitan and Anopheles gambiae.</p>

A unique mathematical tool is developed to deal with global optimization of a set of engineering problems. These include image processing, mechanical topology optimization, and optimal path planning in a variational framework, as well as some benchmark problems in parameter optimization. The optimization tool in these applications is based on the level set theory by which an evolving contour converges toward the optimum solution. Depending upon the application, the objective function is defined, and then the level set theory is used for optimization. Level set theory, as a member of active contour methods, is an extension of the steepest descent method in conventional parameter optimization to the variational framework. It intrinsically suffers from trapping in local solutions, a common drawback of gradient based optimization methods. In this thesis, methods are developed to deal with this drawbacks of the level set approach. By investigating the current global optimization methods, one can conclude that these methods usually cannot be extended to the variational framework; or if they can, the computational costs become drastically expensive. To cope with this complexity, a global optimization algorithm is first developed in parameter space and compared with the existing methods. This method is called "Spiral Bacterial Foraging Optimization" (SBFO) method because it is inspired by the aggregation process of a particular bacterium called, Dictyostelium Discoideum. Regardless of the real phenomenon behind the SBFO, it leads to new ideas in developing global optimization methods. According to these ideas, an effective global optimization method should have i) a stochastic operator, and/or ii) a multi-agent structure. These two properties are very common in the existing global optimization methods. To improve the computational time and costs, the algorithm may include gradient-based approaches to increase the convergence speed. This property is particularly available in SBFO and it is the basis on which SBFO can be extended to variational framework. To mitigate the computational costs of the algorithm, use of the gradient based approaches can be helpful. Therefore, SBFO as a multi-agent stochastic gradient based structure can be extended to multi-agent stochastic level set method. In three steps, the variational set up is formulated: i) A single stochastic level set method, called "Active Contours with Stochastic Fronts" (ACSF), ii) Multi-agent stochastic level set method (MSLSM), and iii) Stochastic level set method without gradient such as E-ARC algorithm. For image processing applications, the first two steps have been implemented and show significant improvement in the results. As expected, a multi agent structure is more accurate in terms of ability to find the global solution but it is much more computationally expensive. According to the results, if one uses an initial level set with enough holes in its topology, a single stochastic level set method can achieve almost the same level of accuracy as a multi-agent structure can obtain. Therefore, for a topology optimization problem for which a high level of calculations (at each iteration a finite element model should be solved) is required, only ACSF with initial guess with multiple holes is implemented. In some applications, such as optimal path planning, objective functions are usually very complicated; finding a closed-form equation for the objective function and its gradient is therefore impossible or sometimes very computationally expensive. In these situations, the level set theory and its extensions cannot be directly employed. As a result, the Evolving Arc algorithm that is inspired by "Electric Arc" in nature, is proposed. The results show that it can be a good solution for either unconstrained or constrained problems. Finally, a rigorous convergence analysis for SBFO and ACSF is presented that is new amongst global optimization methods in both parameter and variational framework.

Monotonic optimization consists of minimizing or maximizing a monotonic objective function over a set of constraints defined by monotonic functions. Many optimization problems in economics and engineering often have monotonicity while lacking other useful properties, such as convexity. This thesis is concerned with the development and application of global optimization algorithms for monotonic optimization problems. First, we propose enhancements to an existing outer-approximation algorithm | called the Polyblock Algorithm | for monotonic optimization problems. The enhancements are shown to significantly improve the computational performance of the algorithm while retaining the convergence properties. Next, we develop a generic branch-and-bound algorithm for monotonic optimization problems. A computational study is carried out for comparing the performance of the Polyblock Algorithm and variants of the proposed branch-and-bound scheme on a family of separable polynomial programming problems. Finally, we study an important class of monotonic optimization problems | probabilistically constrained linear programs. We develop a branch-and-bound algorithm that searches for a global solution to the problem. The basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partitions and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires the solution of only linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.