Dans le cadre de l'optimisation multiobjectif, les métaheuristiques sont reconnues pour être des méthodes performantes mais elles ne rencontrent qu'un succès modéré dans le monde de l'industrie. Dans un milieu où seule la performance compte, l'aspect stochastique des métaheuristiques semble encore être un obstacle difficile à franchir pour les décisionnaires. Il est donc important que les chercheurs de la communauté portent un effort tout particulier sur la facilité de prise en main des algorithmes. Plus les algorithmes seront faciles d'accès pour les utilisateurs novices, plus l'utilisation de ceux-ci pourra se répandre. Parmi les améliorations possibles, la réduction du nombre de paramètres des algorithmes apparaît comme un enjeu majeur. En effet, les métaheuristiques sont fortement dépendantes de leur jeu de paramètres. Dans ce cadre se situe l'apport majeur de TRIBES, un algorithme mono-objectif d'Optimisation par Essaim Particulaire (OEP) qui fonctionne automatiquement,sans paramètres. Il a été mis au point par Maurice Clerc. En fait, le fonctionnement de l'OEP nécessite la manipulation de plusieurs paramètres. De ce fait, TRIBES évite l'effort de les régler (taille de l'essaim, vitesse maximale, facteur d'inertie, etc.).Nous proposons dans cette thèse une adaptation de TRIBES à l'optimisation multiobjectif. L'objectif est d'obtenir un algorithme d'optimisation par essaim particulaire multiobjectif sans paramètres de contrôle. Nous reprenons les principaux mécanismes de TRIBES auxquels sont ajoutés de nouveaux mécanismes destinés à traiter des problèmes multiobjectif. Après les expérimentations, nous avons constaté, que TRIBES-Multiobjectif est moins compétitif par rapport aux algorithmes de référence dans la littérature. Ceci peut être expliqué par la stagnation prématurée de l'essaim. Pour remédier à ces problèmes, nous avons proposé l'hybridation entre TRIBES-Multiobjectif et un algorithme de recherche locale, à savoir le recuit simulé et la recherche tabou. L'idée était d'améliorer la capacité d'exploitation deTRIBES-Multiobjectif. Nos algorithmes ont été finalement appliqués sur des problèmes de dimensionnement des transistors dans les circuits analogiques / Meta-heuristics are recognized to be successful to deal with multiobjective optimization problems but still with limited success in engineering fields. In an environment where only the performance counts, the stochastic aspect of meta-heuristics again seems to be a difficult obstacle to cross for the decision-makers. It is, thus, important that the researchers of the community concern a quite particular effort to ease the handling of those algorithms. The more the algorithms will be easily accessible for the novices, the more the use of these algorithms can spread. Among the possible improvements, reducing the number of parameters is considered as the most challenging one. In fact, the performance of meta-heuristics is strongly dependent on their parameters values. TRIBES presents an attempt to remedy this problem. In fact, it is a particle swarm optimization (PSO) algorithm that works in an autonomous way. It was proposed by Maurice Clerc. Indeed, like every other meta-heuristic, PSO requires many parameters to be fitted every time a new problem is considered. The major contribution of TRIBES is to avoid the effort of fitting them. We propose, in this thesis, an adaptation of TRIBES to the multiobjective optimization. Our aim is to conceive a competitive PSO algorithm free of parameters. We consider the main mechanisms of TRIBES to which are added new mechanisms intended to handle multiobjective problems. After the experimentations, we noticed that Multiobjective-TRIBESis not competitive compared to other multiobjective algorithms representative of the state of art. It can be explained by the premature stagnation of the swarm. To remedy these problems, we proposed the hybridization between Multiobjective-TRIBES and local search algorithms such as simulated annealing and tabu search. The idea behind the hybridization was to improve the capacity of exploitation of Multiobjective-TRIBES. Our algorithms were finally applied to sizing analogical circuits' problems

Orientador: Sérgio Azevedo de Oliveira / Banca: José Roberto Sanches Mantovani / Banca: Fujio Sato / Resumo: A metaheurística Busca Tabu, é uma técnica baseada em parâmetros de controle, a estrutura de vizinhança e seu próprio algoritmo com poderosas estratégias de busca. Nesta técnica, dada uma configuração, deseja-se passar ao melhor vizinho através da entrada e saída de ramos, obtendo assim a configuração incumbente. Com essa configuração que é considerada como a melhor configuração encontrada até o momento, e mesmo sendo um bom valor o sistema continua a busca procurando mais configurações até encontrar uma que seja melhor que as já encontradas até o momento. As versões paralelas dos algoritmos foram desenvolvidas a partir de um algoritmo BT serial avançado, sob o paradigma de programacão SPMD ("Single Program, Multiple Data"), e as mesmas foram testadas para sistemas testes de pequeno porte (Garver - 6 barras/15 ramos), médio porte (Sul brasileiro - 46 barras/79 ramos) e grande porte (Norte-Nordeste brasileiro - 87 barras/179 ramos) e seus resultados comparados com o resultado do algoritmo BT serial. Esta comparacão mostrou que os algoritmos propostos obtiveram um melhor desempenho, com alta eficiência. / Abstract: This paper deals with the use of Tabu Search metaheurístic applied to solving the problem of transmission system expansion planning (TSEP), analyzed on the static point of view, with the development of parallel algorithms in the environment MPI (?Message Passing Interface "). Tabu Search metaheurístic is a technique based on the control parameters, the structure of the neighborhood and its own algorithm with powerful search strategies. In this technique, given a configuration we want to progress to the best neighbor across the entrance and exit of branches, so getting the configuration incumbent. With this configuration which is regarded as the best configuration found so far, and this is a very good value, the system continuously seeking more settings to find a better than those found throughout the search. The parallel versions of the algorithms were developed from an advanced TS series algorithm on the paradigm of programming SPMD (Single Program Multiple Data), and they were tested for test systems small scale (Garver - bars 6/15 branches), medium scale (South Brazilian - 46 bars/79 branches) and large scale (North-Northeast Brazilian - 87 bars/179 branches), and their results compared with the result of the series algorithm TS. This comparison showed that the proposed algorithms obtained best performance and high efficiency. / Mestre

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2017-02-08T15:41:51Z No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) / Made available in DSpace on 2017-02-08T15:41:51Z (GMT). No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) Previous issue date: 2016-12-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste estudo, foi desenvolvida uma ferramenta computacional baseada em metaheurísticas para a otimização do sequenciamento de produção em Flow Shop permutacionais aplicados à montagem de placas eletrônicas que operam em ambientes High-Mix, Low-Volume. O ambiente High-Mix, Low-Volume exige a realização de um grande número de setups para atender à flexibilidade exigida. Esse elevado número de sucessivos setups para a produção de pequenos lotes impacta negativamente nos custos operacionais da empresa. Uma das formas de se obter vantagem ao lidar com um grande mix de produção é explorando características similares entre os produtos, de forma que, através de um sequenciamento adequado, seja possível reduzir o tempo total de parada para setup e, por consequência, reduzir também o tempo total de processamento (makespan). A literatura apresenta muitos exemplos de sucesso na aplicação de técnicas de otimização para o sequenciamento da produção como forma de ganho de vantagem competitiva. Porém, a complexidade e o grande esforço computacional exigidos na solução deste problema, por muitas vezes, inviabilizam sua aplicação na rotina das indústrias. Neste contexto, as metaheurísticas emergem como uma opção para a viabilização de ferramentas para otimização do sequenciamento de produção. Dentre as abordagens metaheurísticas existentes, destacam-se as abordagens híbridas que combinam estratégias de busca local com algoritmos evolutivos como opções para a geração, de forma rápida, de boas soluções para o problema de sequenciamento, ainda que estes métodos não possam garantir a otimalidade da solução. A ferramenta desenvolvida, baseada no uso combinado das metaheurísticas Busca Tabu e Algoritmo Genético, busca a melhor sequência possível dentro do tempo computacional disponível de forma a reduzir os tempos gastos com operações de tempo de setup, e consequentemente o makespan. O Algoritmo Hibrido foi avaliado utilizando instâncias da literatura e instâncias advindas de um caso real. Os resultados dos testes indicam a superioridade da abordagem híbrida sobre as abordagens canônicas do algoritmo Genético e Busca Tabu. Os resultados obtidos na avaliação de instâncias reais indicam a aplicabilidade da ferramenta em ambientes reais, obtendo bons resultados na otimização dos tempos de setup, mesmo para o sequenciamento de grandes quantidades de produtos diferentes. / This work proposes the development of a metaheuristics based computation tool, to solve the permutation flow shop scheduling problem (PFSSP) in the electronic manufacturing operating in High-mix, Low-volume enviroment. To operate in HMLV enviroment is demanded a large number of setup changes to comply the flexibility required. This elevated number of successive setup changes to produce little batches have negative impacts on the operation costs. One way for to obtain advantages handling a large product mix is to explore the similar features between this products. Through a proper scheduling we can reduce the total downtime to setup changes, and consequently reduces the process time (makespan). The literature brings many success examples in the production scheduling optimization as a way to obtain competitive advantages. But, the complexity and the computational effort demanded to solve this problems, sometimes, turns the practical application unfeasible in the factories routine. In this contexto emerges the metaheuristics as an option to viability this type of application. Among the mataheuristics approaches, outstands the hybrid approaches that combine local search strategies with evolutionary algorithms as a way to obtain good and fast solutions for the scheduling problems, although the optimality is not been guaranted. The tool proposed combine the metaheuristics Genetic Algorithm and Tabu Search to optimize the flow shop scheduling in the shortest possible time to allow the practical application in industry. The tool was evaluate based on quality metrics like makespan and mean setup time. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The results of the tests indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the optimization of textit setup times, also for the sequencing of large products. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The tests results indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the setup time optimization, also for the sequencing of large products.

This thesis examines the problem of the automated re-assembly of jigsaw puzzles. The objectives of this research are as follows: to provide a clear statement of the jigsaw puzzle re-assembly problem; to find out which solution technique is best suited to this problem; to determine the level of sensitivity of the proposed solution technique when solving different variations of this problem; and to explore solution methods for solving incomplete jigsaw puzzles (puzzles with missing pieces). The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. This work presents an extensive examination of the suitability and efficiency of the standard solution techniques that can be applied to this problem. A detailed comparison between different solution methods including Genetic Algorithms, Simulated Annealing, Tabu Search and Constraint Satisfaction Programming, shows that a constraint-based approach is the most efficient method of generating solutions to the jigsaw puzzle problem. The proposed re-assembly algorithm is successful. Consequently, it can be used in development of automated solution generators for other problems in the same domain, thus creating new theoretical and applied directions in this field of research. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this thesis demonstrate that the proposed algorithm being optimised to re-assemble the jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, an original heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research. The solution of this problem involves a number of procedures with significant applications in other computer-related areas such as pattern recognition, feature and shape description, boundary-matching, and heuristic modelling. It also has more practical applications in robotic vision and reconstruction of broken artefacts in archaeology.

<p>The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. </p><p>The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. </p><p>The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.</p>

There is a growing interest in investigating the high order contingency events that may result in large blackouts, which have been a great concern for power grid secure operation. The actual number of high order contingency is too huge for operators and planner to apply a brute-force enumerative analysis. This thesis presents a heuristic searching method based on particle swarm optimization (PSO) and tabu search to select severe high order contingencies. The original PSO algorithm gives an intelligent strategy to search the feasible solution space, but tends to find the best solution only. The proposed method combines the original PSO with tabu search such that a number of top candidates will be identified. This fits the need of high order contingency screening, which can be eventually the input to many other more complicate security analyses. Reordering of branches of test system based on severity of N-1 contingencies is applied as a pre-processing to increase the convergence properties and efficiency of the algorithm. With this reordering approach, many critical high order contingencies are located in a small area in the whole searching space. Therefore, the proposed algorithm tends to concentrate in searching this area such that the number of critical branch combinations searched will increase. Therefore, the speedup ratio is found to increase significantly. The proposed algorithm is tested for N-2 and N-3 contingencies using two test systems modified from the IEEE 118-bus and 30-bus systems. Variation of inertia weight, learning factors, and number of particles is tested and the range of values more suitable for this specific algorithm is suggested. Although illustrated and tested with N-2 and N-3 contingency analysis, the proposed algorithm can be extended to even higher order contingencies but visualization will be difficult because of the increase in the problem dimensions corresponding to the order of contingencies.

The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.

Abstract This dissertation presents a new algorithm by integrating evolutionary programming (EP), tabu search (TS) and quadratic programming (QP), named the evolutionary-tabu quadratic programming (ETQ) method, to solve the nonconvex economic dispatch problem (NED). This problem involves the economic dispatch with valve-point effects (EDVP), economic dispatch with piecewise quadratic cost function (EDPQ), and economic dispatch with prohibited operating zones (EDPO). EDPV, EDPQ and EDPO are similar problems when ETQ was employed. The problem was solved in two phases, the cost-curve-selection subproblem, and the typical ED solving subproblem. The first phase was resolved by using a hybrid EP and TS, and the second phase by QP. In the solving process, EP with repairing strategy was used to generate feasible solutions, TS was used to prevent prematurity, and QP was used to enhance the performance. Numerical results show that the proposed method is more effective than other previously developed evolutionary computation algorithms.

There is a growing interest in investigating the high order contingency events that may result in large blackouts, which have been a great concern for power grid secure operation. The actual number of high order contingency is too huge for operators and planner to apply a brute-force enumerative analysis. This thesis presents a heuristic searching method based on particle swarm optimization (PSO) and tabu search to select severe high order contingencies. The original PSO algorithm gives an intelligent strategy to search the feasible solution space, but tends to find the best solution only. The proposed method combines the original PSO with tabu search such that a number of top candidates will be identified. This fits the need of high order contingency screening, which can be eventually the input to many other more complicate security analyses. Reordering of branches of test system based on severity of N-1 contingencies is applied as a pre-processing to increase the convergence properties and efficiency of the algorithm. With this reordering approach, many critical high order contingencies are located in a small area in the whole searching space. Therefore, the proposed algorithm tends to concentrate in searching this area such that the number of critical branch combinations searched will increase. Therefore, the speedup ratio is found to increase significantly. The proposed algorithm is tested for N-2 and N-3 contingencies using two test systems modified from the IEEE 118-bus and 30-bus systems. Variation of inertia weight, learning factors, and number of particles is tested and the range of values more suitable for this specific algorithm is suggested. Although illustrated and tested with N-2 and N-3 contingency analysis, the proposed algorithm can be extended to even higher order contingencies but visualization will be difficult because of the increase in the problem dimensions corresponding to the order of contingencies.

No description available.