Les problèmes de partitionnement de graphique sont une classe bien connue des problèmes d'optimisation combinatoire NP-difficiles avec un large éventail d'applications, telles que la conception de plans VLSI, la physique statistique, la planification d'une équipe sportive, la segmentation d'images et la structuration de protéines. En raison de la grande complexité de ces problèmes, les approches heuristiques et métaheuristiques sont couramment utilisées pour aborder les problèmes difficiles. Cette thèse considère trois problèmes représentatifs de cette famille, incluant le problème "max-k-cut", le problème "max-bisection" et le problème de séparation de sommets (VSP). Elle vise à élaborer des algorithmes heuristiques efficaces basés sur une ensemble d'opérateurs de recherche complémentaires. Plus précisément, nous développons une heuristique à opérateur multiple (MOH) pour "max-k-cut", un algorithme de recherche Tabu itérée (ITS) pour "max-bisection" et un algorithme "path relinking" (PR-VSP) pour VSP. Des résultats expérimentaux sur des jeux de test standard démontrent que les algorithmes proposés rivalisent favorablement avec les approches existantes de la littérature. L'utilisation combinée de plusieurs opérateurs de recherche est analysée afin de mettre en évidence l'influence de ces opérateurs sur la performance des algorithmes. / Graph partitioning problems are a class of well-known NP-hard combinatorial optimization problems with a wide range of applications, such as VLSI layout design, statistical physics, sports team scheduling, image segmentation, and protein conformation for instances. This thesis considers three representative problems in this family, including the max-k-cut problem, the max-bisection problem and the vertex separator problem (VSP). Due to high computational complexity, heuristic and metaheuristic approaches are commonly used for approximating the challenging problems. This thesis is devoted to developing efficient metaheuristic algorithms based on a collection of complementary search operators. Specifically, we develop a multiple operator heuristic (MOH) for max-k-cut, an iterated tabu search (ITS) algorithm for max-bisection and a path relinking (PR-VSP) algorithm for VSP. Extensive computational experiments and comparisons demonstrate that the proposed algorithms compete favorably with state-of-the-art approaches in the literature. The combined use of multiple search operators is analyzed to shed lights on the influence over the performance of the algorithms.

Nous vivons dans un monde où le besoin d’efficacité s’impose de plus en plus. Ce besoin s’exprime dans différents domaines, allant de l’industrie à la médecine en passant par la surveillance environnementale. Engendrées par cette demande, de nombreuses méthodes d’optimisation « modernes » également appelées « métaheuristiques » sont apparues ces quarante dernières années. Ces méthodes se basent sur des raisonnements probabilistes et aléatoires et permettent la résolution de problèmes pour lesquels les méthodes d’optimisation « classiques » également appelées « méthodes déterministes » ne permettent pas l’obtention de résultats dans des temps raisonnables. Victimes du succès de ces méthodes, leurs concepteurs doivent aujourd’hui plus que jamais répondre à de nombreuses problématiques qui restent en suspens : « Comment évaluer de manière fiable et rapide les solutions proposées ? », « Quelle(s) méthode(s) choisir pour le problème étudié ? », « Comment paramétrer la méthode utilisée ? », « Comment utiliser une même méthode sur différents problèmes sans avoir à la modifier ? ». Pour répondre à ces différentes questions, nous avons développé un ensemble de concepts et outils. Ceux-ci ont été réalisés dans le cadre de la modélisation et la simulation de systèmes à évènements discrets avec le formalisme DEVS. Ce choix a été motivé par deux objectifs : permettre l’optimisation temporelle et spatiale de modèles DEVS existants et améliorer les performances du processus d’optimisation (qualité des solutions proposées, temps de calcul). La modélisation et la simulation de l’optimisation permettent de générer directement des propositions de paramètres sur les entrées du modèle à optimiser. Ce modèle, quant à lui, génère des résultats utiles à la progression de l’optimisation. Pour réaliser ce couplage entre optimisation et simulation, nous proposons l’intégration des méthodes d’optimisation sous la forme de modèles simulables et facilement interconnectables. Notre intégration se concentre donc sur la cohérence des échanges entre les modèles dédiés à l’optimisation et les modèles dédiés à la représentation du problème. Elle permet également l’arrêt anticipé de certaines simulations inutiles afin de réduire au maximum la durée de l’optimisation. La représentation des méthodes d’optimisation sous formes de modèles simulables apporte également un élément de réponse dans le choix et le paramétrage des algorithmes. Grace à l’usage de la simulation, différents algorithmes et paramètres peuvent être utilisés pour un même processus d’optimisation. Ces changements sont également influencés par les résultats observés et permettent une adaptation automatique de l’optimisation aux spécificités connues et/ou cachées du problème étudié ainsi qu’à ses différentes étapes de résolution. L’architecture de modèle que nous proposons a été validée sur trois problèmes distincts : l’optimisation de paramètres pour des fonctions mathématiques, l’optimisation spatialisée d’un déploiement de réseau de capteurs sans fil, l’optimisation temporisée de traitements médicaux. La généricité de nos concepts et la modularité de nos modèles ont permis de mettre en avant la facilité d’utilisation de notre outil. Au niveau des performances, l’interruption de certaines simulations ainsi que le dynamisme de l’optimisation ont permis l’obtention de solutions de qualité supérieure dans des temps inférieurs. / In the world in witch we live the efficient needs are increasing in various fields like industry medecine and environnemtale monitoring. To meet this needs, many optimization methods nammed « metaheuristics » have been created over the last forty years. They are based on probabilistic and random reasoning and allow user to solve problems for witch conventional methods can not be used in acceptable computing times. Victim of their methods succes, the developers of the methods have to answer to several questions : « How can the fitness of solutions be assessed ? », « How to use the same method for several projects without change the code? », « What method will we choose for a specific problem ? », « How to parametrize algorithms ? ». To deal with this problem, we have developed a set of concepts and tools. They have been developed in the context of modeling and simulation of discrete event systems with DEVS formalism. The aims pursued are : allow temporized and spacialized optimization of existing DEVS models, improve the optimization process efficiency (quality of solutions, computing time). Modeling and simulation are used to propose parameters toward the input of problem to optimize. This one generate results used to improve the next proposed solutions. In order to combine optimization and simulation, we propose to represent the optimization method as models which can be easily interconnected and simulated. We focus on consistency of exchanges between optimization models and problem models. Our approach allows early stopping of useless simulations and reduce the computing time as a result. Modeling optimization methods in DEVS formalism also allows to autimatically choose the optimization algorithm and its parameters. Various algorithms and parameters can be used for the same problem during optimization process at different steps. This changes are influenced by collected results of problem simulation. They lead on a self adaptation to the visible or/and hidden features of the studied problem. Our models architecture has been tested on three different problems : parametric optimization of mathematical functions, spacialized optimization of a sensor network deployment, temporized optimization of a medical treatment. Genericity of our concepts and scalability of our models underline the usabily of proposed tool. Concerning performance, simulation breaks and dynamic optimization have obtained higher quality solutions in a short time.

Routing problems are ones of the most famous members of the group of the classical optimalization combinatorial problems. Travelling salesman problem and problems derived from it have been attracting mathematics and analysts, since they were firstly formulated, and accelerating a development of new methods and approaches that can be used for a wide range of another real-life problems. This thesis aims to demonstrate an usefulness and a flexibility of shown metaheristic methods. Results are compared with outputs of alternative algorithms or known optimal solutions where it is possible. To fulfill this goal the VBA application has been developed. The results of experiments are presented and the application is decribed in a second part of this thesis. A reader should be sufficiently instructed which way he could choose to solve similar types of problems

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T10:35:24Z (GMT). No. of bitstreams: 1 Goncalves_AndreRicardo_M.pdf: 2010410 bytes, checksum: d89f7061364f054a7b11d52cc61d27a4 (MD5) Previous issue date: 2011 / Resumo: O dinamismo do mundo moderno traz consigo grandes desafios científicos e tecnológicos, particularmente junto a problemas de otimização. Problemas antes tratados de forma estática estão sendo reformulados para incorporar esse dinamismo, exigindo com isso novas estratégias de solução. Meta-heurísticas populacionais para otimização surgem então como abordagens promissoras, visto que favorecem a exploração do espaço de busca e contribuem para a adaptação ao dinamismo do ambiente. Foram tratados aqui algoritmos de estimação de distribuição (AEDs), os quais empregam modelos probabilísticos para identificar regiões promissoras do espaço de busca. Pelo fato de serem raras e limitadas as propostas de AEDs para problemas dinâmicos, principalmente em espaços de busca contínuos, foram concebidos AEDs baseados em modelos de mistura gaussianos flexíveis, auto-controláveis e com baixo custo computacional, incluindo ainda operadores de manutenção de diversidade e de controle de convergência. Uma extensa comparação com métodos alternativos de otimização para ambientes dinâmicos foi realizada e, em várias situações, a proposta deste trabalho superou o desempenho de métodos considerados estado-da-arte / Abstract: The dynamism of the modern world gives rise to huge scientific and technological challenges. Problems until recently being treated as static are now being reformulated to incorporate that dynamism, thus requiring novel solution strategies. Population-based metaheuristics devoted to optimization emerge as promising approaches, given that they promote an effective exploration of the search space and contribute to the adaptation to the dynamism of the environment. Estimation of distribution algorithms (EDAs) were considered here, which make use of probabilistic models to identify promising regions of the search space. Due to the fact that the proposals of EDAs for dynamic problems are rare and limited, mainly in real-parameter search spaces, EDAs were conceived based on flexible Gaussian mixture models, self-controlable and computationally inexpensive steps, including diversity maintenance and convergence control mechanisms. An extensive comparison with alternative optimization methods for dynamic environments was accomplished and, in many situations, the proposed technique overcame the performance produced by state-of-the-art methods / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

O presente trabalho tem como objetivo comparar o desempenho de diferentes metaheurísticas bio-inspiradas aplicadas à resolução de problemas de otimização multiobjetivo do controle de tensão e reativos, ou controle Volt/VAr, em redes elétricas inteligentes. Entre os algoritmos implementados estão o algoritmo genético, o algoritmo memético, a otimização por colônia de formigas, a otimização por enxame de partículas e o strength pareto evolutionary algorithm (SPEA2). Aplicações dos algoritmos à resolução de problemas de otimização do controle Volt/VAr, em redes de distribuição de energia elétrica com dimensões reais, são utilizadas para comparação de seus indicadores de desempenho. A avaliação é feita tanto em relação à velocidade de busca quanto em relação à qualidade da solução encontrada. Os algoritmos mostraram resultados promissores para aplicação a redes de distribuição com dimensões reais, encontrando soluções de qualidade em tempos de busca aceitáveis. Parte deste desempenho se dá pelos métodos meta-heurísticos, parte por conta da modelagem adotada no processo de otimização. / The present work aims at comparing the performance of different bio-inspired metaheuristics applied to the Volt/VAr control multiobjective optimization problem in smart grids. Among the algorithms implemented are the genetic algorithm, the memetic algorithm, ant colony optimization, particle swarm optimization and the strength pareto evolutionary algorithm (SPEA2). Applications of the algorithms to solve Volt/VAr control optimization problems in distribution networks with real dimensions are used to compare their performance indicators. The evaluation is done both in relation to the search speed and in relation to the quality of the solution found. The promising results show that the algorithms are applicable to distribution networks with real dimensions, finding quality solutions in acceptable search times. This performance is obtained due to both the metaheuristic methods, and the modeling adopted in the optimization process.

Due to the current trends in business as the necessity to have a large catalogue of products, orders that increase in frequency but not in size, globalisation and a market that is increasingly competitive, the production sector faces an ever harder economical environment. All this raises the need for production scheduling with maximum efficiency and effectiveness. The first scientific publications on production scheduling appeared more than half a century ago. However, many authors have recognised a gap between the literature and the industrial problems. Most of the research concentrates on optimisation problems that are actually a very simplified version of reality. This allows for the use of sophisticated approaches and guarantees in many cases that optimal solutions are obtained. Yet, the exclusion of real-world restrictions harms the applicability of those methods. What the industry needs are systems for optimised production scheduling that adjust exactly to the conditions in the production plant and that generates good solutions in very little time. This is exactly the objective in this thesis, that is, to treat more realistic scheduling problems and to help closing the gap between the literature and practice. The considered scheduling problem is called the hybrid flowshop problem, which consists in a set of jobs that flow through a number of production stages. At each of the stages, one of the machines that belong to the stage is visited. A series of restriction is considered that include the possibility to skip stages, non-eligible machines, precedence constraints, positive and negative time lags and sequence dependent setup times. In the literature, such a large number of restrictions has not been considered simultaneously before. Briefly, in this thesis a very realistic production scheduling problem is studied. Various optimisation methods are presented for the described scheduling problem. A mixed integer programming model is proposed, in order to obtai / Urlings ., T. (2010). Heuristics and metaheuristics for heavily constrained hybrid flowshop problems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8439

[pt] O problema de Districting-and-routing é um problema estratégico no qual porções geográficas devem ser agregadas em regiões de entrega, e cada região de entrega possui um custo de roteamento estimado. Seu objetivo é de minimizar esses custos, além de garantir a divisão da região em distritos. A simulação para obter uma boa aproximação é muito custosa computacionalmente, enquanto mecanismos como buscas locais exigem que esse cálculo seja feito de forma muito eficiente, tornando essa estratégia de aproximação inviável para uma solução metaheurística. Grande parte das soluções existentes para esse problema utilizam de formulas de aproximação contínua para mensurar os custos de roteamento, funções essas que são rápidas de serem calculadas porém cometem erros significativos. Em contraste, propomos uma Rede Neural em Grafo (Graph Neural Network - GNN) que é usada como oráculo por um algoritmo de otimização. Nossos experimentos computacionais executados com dados de cidades do Reino Unido mostram que a GNN é capaz de produzir previsões de custos mais precisas em tempo computacional aceitável. O uso desse estimator na busca local impacta positivamente a qualidade das soluções, levando a uma economia de 10,35 por cento no custo de entrega estimado em relação a função Beardwood, que é comumente usada nesse cenários, e ganhos similares em comparação com outros métodos de aproximação. / [en] The districting-and-routing problem is a strategic problem in which basic geographical units (e.g., zip codes) should be aggregated into delivery regions, and each delivery region is characterized by a routing cost estimated over an extended planning horizon. The objective is to minimize the expected routing costs while ensuring regional separability through the definition of the districts. Repeatedly simulating routing costs on a set of scenarios while searching for good districts can be computationally intensive, so existing solution approaches for this problem rely on approximation functions. In contrast, we propose to rely on a graph neural network (GNN) trained on a set of demand scenarios, which is then used within an optimization approach to infer routing costs while solving the districting problem. Our computational experiments on various metropolitan areas show that the GNN produces accurate cost predictions. Moreover, using this better estimator during the search positively impacts the quality of the districting solutions and leads to 10.35 percent delivery-cost savings over the commonly-used Beardwood estimator and similar gains compared to other approximation methods.

Les travaux de cette thèse concernent la conception et l’optimisation de lignes de transfert reconfigurables. L’objectif principal est de concevoir une ligne d’usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d’optimisation correspondant est un problème d’équilibrage de lignes d’usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d’installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d’inclusion et d’exclusion, nous avons dû considérer des contraintes d’accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d’usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l’utilisation d’une tête d’usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d’outils qui dépendent de la séquence d’opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l’aide d’un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu’une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d’équilibrage plus difficile que dans le cas des lignes dédiées, et l’approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d’optimisation combinatoire. / This work concerns the design and the optimization of reconfigurable transfer lines. The principle objective is to design a machining line with less cost while respecting the technological and economic constraints of the problem. The corresponding optimization problem is a transfer lines balancing problem subject to specific constraints. It consists to affect operations to workstations minimizing the installations cost. In addition to the habitual constraints of the transfer balancing problem, i.e. precedence, inclusion and exclusion constraints, we consider accessibility constraints. In addition, the principal specificity of reconfigurable lines compared to the dedicated transfer lines, comes from the sequential execution of operations. This often makes it necessary to set up stations with several machining centers working in parallel to achieve desired production volumes. Finally, the utilization of mono-spindle head machining center induces the inclusion of setup times between operations. This setup time is due to the time of displacement and change of tools which it depends of the operational sequence. We proposed firstly a mathematical formalization of the problem using a mixed integer program. We developed also several methods to calculate lower bounds and a pretreatment procedure. However, the additional constraints make the resolution of the considered balancing problem very difficult and the proposed approach generally does not solve instances of industrial size. To meet this need, we have developed several approximate resolution methods of the problem taking inspiration from effective Metaheuristics on combinatorial optimization problems.

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique. / Metaheuristics are a useful tool within the field of discrete optimization that allow for large, complex, and difficult optimization problems to achieve a solution with a good quality in a reasonable amount of time. Often metaheuristics have many parameters that require a user to manually define and tune for a given problem. An adaptive metaheuristic aims to remove some parameters from being tuned or defined by the end user by allowing the method to specify and/or adapt a parameter or set of parameters based on the problem. The adaptive metaheuristic, using advancements in understanding of the problem being solved, machine learning, and related fields, aims to provide this more generalized and automatic toolkit for solving problems. Global optimization of mining complexes aims to schedule material movement in mines and processing streams to maximize the economic value of the system. Often due to the large number of integer variables within the model, complicated constraints, and non-linear constraints, it becomes prohibitive to solve these models using commercially available optimizers. Therefore, metaheuristics are often employed in solving mining complexes. This thesis builds upon a simulated annealing method developed by Goodfellow & Dimitrakopoulos (2016) to optimize the stochastic global mining complex. The method outlined by the authors requires many parameters to be defined to operate. One of these is how the simulated annealing algorithm searches the local neighborhood of solutions. This thesis illustrates and implements an adaptive way of searching the neighborhood for increasing the quality of a solution. Numerical results show up to a 10% increase in objective function value.