Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Antonio Padilha Feltrin / Banca: Luiz Carlos Pereira da Silva / Banca: Eduardo Nobuhiro Asada / Resumo: O Problema de Planejamento da Expansão de Sistemas de Transmissão de Energia Elétrica consiste em se escolher, entre um conjunto pré-definido de circuitos candidatos, aqueles que devem ser incorporados ao sistema de forma a minimizar os custos de investimento e operação ao e atender a demanda de energia futura ao longo de um horizonte de planejamento com confiabilidade, assumindo como conhecido o plano de geração. É considerado um problema muito complexo e difícil por se tratar de um problema não linear inteiro misto, não convexo, multimodal e altamente combinatório. Este problema tem sido solucionado usando técnicas clássicas como Decomposição ao de Benders e Branch and Bound, assim como também algoritmos heurísticos e metaheurísticas obtendo diversos resultados, mais com uma série de problemas como, por exemplo, alto esforço computacional e problemas de convergência. Neste trabalho apresentam-se duas novas técnicas de solução para o problema, a saber, as metaheurísticas Busca em Vizinhança Variável e a Busca Dispersa. A Busca em Vizinhança Variável é uma técnica baseada em trocas de estruturas de vizinhança dentro de um algoritmo de busca local, e a metaheurística Busca Dispersa, um método evolutivo que combina sistematicamente conjuntos de soluções para se obter solucões melhores. Essas técnicas de solução oferecem novas alternativas de solução que oferecem solução aos problemas encontrados com outros métodos, como é um baixo esforço computacional é uma melhor convergência, sendo este o principal aporte do trabalho. Os algoritmos são apresentados sistematicamente, explicando os seus algoritmos e a forma como são adaptados para resolver o problema do planejamento da expansão de sistemas de transmissão considerando-se a modelagem matemática conhecida com o modelo de transporte e o modelo DC. São realizados testes com os sistemas... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Electric Energy Transmission Network Expansion Problem consist in choose among a set of pre-defined circuits candidates, who must be incorporated into the system so as to minimize the investment costs and operation and meet the future energy demand over a planning horizon with reliability, assuming the generation plan is known. It is a very complex and difficult problem because it is non linear, non convex, multimodal and highly combinatorial. This problem has been solved using traditional techniques such as Benders decomposition and Branch and Bound, as well as heuristic algorithms and metaheuristics getting different results, but with a series of problems such as high computational effort and convergence problems. This paper tests out two new techniques for solving the problem as are the metaheuristics Variable Neighborhood Search and Scatter Search. The Variable Neighborhood Search is a technique based on trading structures within a neighborhood of a local search algorithm, and the Scatter Search metaheuristic is a method which combines systematically sets of solutions in an evolutionary way to achieve better solutions. These solution techniques offer new alternatives to solve the problems encountered with other methods, such as a low computational effort and better convergence, which is the main contribution of this work. The techniques are presented systematically, explaining their algorithms and the way they are adapted to solve the network expansion planning problem based on the mathematical model known as the transportation model and the DC model. They are tested with the systems Southern Brazilian with 46 buses and the IEEE 24 buses system, results are compared with those obtained with other metaheuristics, obtaining excellent results with a best performance both in processing speed as in computational effort. / Doutor

<p>The GSM network technology has been developed and improved during several years which have led to an increased complexity. The complexity results in more network parameters and together with different scenarios and situations they form a complex set of configurations. The definition of the network parameters is generally a manual process using static values during test execution. This practice can be costly, difficult and laborious and as the network complexity continues to increase, this problem will continue to grow.This thesis presents an implementation of an automated performance optimization algorithm that utilizes genetic algorithms for optimizing the network parameters. The implementation has been used for proving that the concept of automated optimization is working and most of the work has been carried out in order to use it in practice. The implementation has been applied to the Link Quality Control algorithm and the Improved ACK/NACK feature, which is an apart of GSM EDGE Evolution.</p> / <p>GSM-nätsteknologin har utvecklats och förbättrats under lång tid, vilket har lett till en ökad komplexitet. Denna ökade komplexitet har resulterat i fler nätverksparameterar, tillstånd och standarder. Tillsammans utgör de en komplex uppsättning av olika konfigurationer. Dessa nätverksparameterar har hittills huvudsakligen bestämts med hjälp av en manuell optimeringsprocess. Detta tillvägagångssätt är både dyrt, svårt och tidskrävande och allt eftersom komplexiteten av GSM-näten ökar kommer problemet att bli större.Detta examensarbete presenterar en implementering av en algoritm för automatiserad optimering av prestanda som huvudsakligen använder sig av genetiska algoritmer för att optimera värdet av nätverksparametrarna. Implementeringen har använts för att påvisa att konceptet med en automatiserad optimering fungerar och det mesta av arbetet har utförts för att kunna använda detta i praktiken. Implementeringen har tillämpats på Link Quality Control-algoritmen och Improved ACK/NACK-funktionaliteten, vilket är en del av GSM EDGE Evolution.</p>

<p>In the field of systems biology the task of finding optimal model parameters is a common procedure. The optimization problems encountered are often multi-modal, i.e., with several local optima. In this thesis, a class of algorithms for multi-modal problems called metaheuristics are studied. A downside of metaheuristic algorithms is that they are dependent on algorithm settings in order to yield ideal performance.This thesis studies an approach to tune these algorithm settings using user constructed test functions which are faster to evaluate than an actual biological model. A statistical procedure is constructed in order to distinguish differences in performance between different configurations. Three optimization algorithms are examined closer, namely, scatter search, particle swarm optimization, and simulated annealing. However, the statistical procedure used can be applied to any algorithm that has configurable options.The results are inconclusive in the sense that performance advantages between configurations in the test functions are not necessarily transferred onto real biological models. However, of the algorithms studied a scatter search implementation was the clear top performer in general. The set of test functions used must be studied if any further work is to be made following this thesis.In the field of systems biology the task of finding optimal model parameters is a common procedure. The optimization problems encountered are often multi-modal, i.e., with several local optima. In this thesis, a class of algorithms for multi-modal problems called metaheuristics are studied. A downside of metaheuristic algorithms is that they are dependent on algorithm settings in order to yield ideal performance.</p><p>This thesis studies an approach to tune these algorithm settings using user constructed test functions which are faster to evaluate than an actual biological model. A statistical procedure is constructed in order to distinguish differences in performance between different configurations. Three optimization algorithms are examined closer, namely, scatter search, particle swarm optimization, and simulated annealing. However, the statistical procedure used can be applied to any algorithm that has configurable options.</p><p>The results are inconclusive in the sense that performance advantages between configurations in the test functions are not necessarily transferred onto real biological models. However, of the algorithms studied a scatter search implementation was the clear top performer in general. The set of test functions used must be studied if any further work is to be made following this thesis.</p>

The GSM network technology has been developed and improved during several years which have led to an increased complexity. The complexity results in more network parameters and together with different scenarios and situations they form a complex set of configurations. The definition of the network parameters is generally a manual process using static values during test execution. This practice can be costly, difficult and laborious and as the network complexity continues to increase, this problem will continue to grow.This thesis presents an implementation of an automated performance optimization algorithm that utilizes genetic algorithms for optimizing the network parameters. The implementation has been used for proving that the concept of automated optimization is working and most of the work has been carried out in order to use it in practice. The implementation has been applied to the Link Quality Control algorithm and the Improved ACK/NACK feature, which is an apart of GSM EDGE Evolution. / GSM-nätsteknologin har utvecklats och förbättrats under lång tid, vilket har lett till en ökad komplexitet. Denna ökade komplexitet har resulterat i fler nätverksparameterar, tillstånd och standarder. Tillsammans utgör de en komplex uppsättning av olika konfigurationer. Dessa nätverksparameterar har hittills huvudsakligen bestämts med hjälp av en manuell optimeringsprocess. Detta tillvägagångssätt är både dyrt, svårt och tidskrävande och allt eftersom komplexiteten av GSM-näten ökar kommer problemet att bli större.Detta examensarbete presenterar en implementering av en algoritm för automatiserad optimering av prestanda som huvudsakligen använder sig av genetiska algoritmer för att optimera värdet av nätverksparametrarna. Implementeringen har använts för att påvisa att konceptet med en automatiserad optimering fungerar och det mesta av arbetet har utförts för att kunna använda detta i praktiken. Implementeringen har tillämpats på Link Quality Control-algoritmen och Improved ACK/NACK-funktionaliteten, vilket är en del av GSM EDGE Evolution.

In the field of systems biology the task of finding optimal model parameters is a common procedure. The optimization problems encountered are often multi-modal, i.e., with several local optima. In this thesis, a class of algorithms for multi-modal problems called metaheuristics are studied. A downside of metaheuristic algorithms is that they are dependent on algorithm settings in order to yield ideal performance.This thesis studies an approach to tune these algorithm settings using user constructed test functions which are faster to evaluate than an actual biological model. A statistical procedure is constructed in order to distinguish differences in performance between different configurations. Three optimization algorithms are examined closer, namely, scatter search, particle swarm optimization, and simulated annealing. However, the statistical procedure used can be applied to any algorithm that has configurable options.The results are inconclusive in the sense that performance advantages between configurations in the test functions are not necessarily transferred onto real biological models. However, of the algorithms studied a scatter search implementation was the clear top performer in general. The set of test functions used must be studied if any further work is to be made following this thesis.In the field of systems biology the task of finding optimal model parameters is a common procedure. The optimization problems encountered are often multi-modal, i.e., with several local optima. In this thesis, a class of algorithms for multi-modal problems called metaheuristics are studied. A downside of metaheuristic algorithms is that they are dependent on algorithm settings in order to yield ideal performance. This thesis studies an approach to tune these algorithm settings using user constructed test functions which are faster to evaluate than an actual biological model. A statistical procedure is constructed in order to distinguish differences in performance between different configurations. Three optimization algorithms are examined closer, namely, scatter search, particle swarm optimization, and simulated annealing. However, the statistical procedure used can be applied to any algorithm that has configurable options. The results are inconclusive in the sense that performance advantages between configurations in the test functions are not necessarily transferred onto real biological models. However, of the algorithms studied a scatter search implementation was the clear top performer in general. The set of test functions used must be studied if any further work is to be made following this thesis.

Many important applications in the real world that can be modelled as combinatorial optimization problems are actually dynamic in nature. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. Moreover, dynamic combinatorial problems, when addressed, are typically tackled within an application context. <br /><br /> In this thesis, dynamic combinatorial problems are addressed collectively by adopting an evolutionary based algorithmic approach. On the plus side, their ability to manipulate several solutions at a time, their robustness and their potential for adaptability make evolutionary algorithms a good choice for solving dynamic problems. However, their tendency to converge prematurely, the difficulty in fine-tuning their search and their lack of diversity in tracking optima that shift in dynamic environments are drawbacks in this regard. <br /><br /> Developing general methodologies to tackle these conflicting issues constitutes the main theme of this thesis. First, definitions and measures of algorithm performance are reviewed. Second, methods of benchmark generation are developed under a generalized framework. Finally, methods to improve the ability of evolutionary algorithms to efficiently track optima shifting due to environmental changes are investigated. These methods include adapting genetic parameters to population diversity and environmental changes, the use of multi-populations as an additional means to control diversity, and the incorporation of local search heuristics to fine-tune the search process efficiently. <br /><br /> The methodologies developed for algorithm enhancement and benchmark generation are used to build and test evolutionary models for dynamic versions of the travelling salesman problem and the flexible manufacturing system. Results of experimentation demonstrate that the methods are effective on both problems and hence have a great potential for other dynamic combinatorial problems as well.

Coordinated lot sizing problems, which assume a joint setup is shared by a product family, are commonly encountered in supply chain contexts. Total system costs include a joint set-up charge each time period any item in the product family is replenished, an item set-up cost for each item replenished in each time period, and inventory holding costs. Silver (1979) and subsequent researchers note the occurrence of coordinated replenishment problems within manufacturing, procurement, and transportation contexts. Due to their mathematical complexity and importance in industry, coordinated lot-size problems are frequently studied in the operations management literature. In this research, we address both uncapacitated and capacitated variants of the problem. For each variant we propose new problem formulations, one or more construction heuristics, and a simulated annealing metaheuristic (SAM). We first propose new tight mathematical formulations for the uncapacitated problem and document their improved computational efficiency over earlier models. We then develop two forward-pass heuristics, a two-phase heuristic, and SAM to solve the uncapacitated version of the problem. The two-phase and SAM find solutions with an average optimality gap of 0.56% and 0.2% respectively. The corresponding average computational requirements are less than 0.05 and 0.18 CPU seconds. Next, we propose tight mathematical formulations for the capacitated problem and evaluate their performance against existing approaches. We then extend the two-phase heuristic to solve this more general capacitated version. We further embed the six-phase heuristic in a SAM framework, which improves heuristic performance at minimal additional computational expense. The metaheuristic finds solutions with an average optimality gap of 0.43% and within an average time of 0.25 CPU seconds. This represents an improvement over those reported in the literature. Overall the heuristics provide a general approach to the dynamic demand lot-size problem that is capable of being applied as a stand-alone solver, an algorithm embedded with supply chain planning software, or as an upper-bounding procedure within an optimization based algorithm. Finally, this research investigates the performance of alternative coordinated lotsizing procedures when implemented in a rolling schedule environment. We find the perturbation metaheuristic to be the most suitable heuristic for implementation in rolling schedules.

We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect different underlying structures in different data sets with clusters having arbitrary shapes and density variations. Thus, the current trend in the clustering literature is growing into the use of multiple objectives as the inadequacy of using a single objective is understood better. The problem is also difficult because the optimal solution is not well defined. To the best of our knowledge, all the multiobjective evolutionary algorithms for the clustering problem try to generate the whole Pareto optimal set. This may not be very useful since majority of the solutions in this set may be uninteresting when presented to the decision maker. In this study, we incorporate the preferences of the decision maker into a well known multiobjective evolutionary algorithm, namely SPEA-2, in the optimization process using reference points and achievement scalarizing functions to find the target clusters.

This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost. The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading. The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives. / text

Multi-objective optimization metaheuristics (MOMs) are powerful methods for solving complex optimization problems but can require a large number of function evaluations to find optimal solutions. Thus, an efficient multi-objective optimization method should generate accurate and diverse solutions in a timely manner. Improving MOMs convergence speed is an important and challenging research problem which is the scope of this thesis. This thesis conducted the most comprehensive comparative study ever in MOMs. Based on the results, multi-objective (MO) versions of particle swarm optimization (PSO) and differential evolution (DE) algorithms achieved the highest performances; therefore, these two MOMs have been selected as bases for further acceleration in this thesis. To accelerate the selected MOMs, this work focuses on the incorporation of leadership concept to MO variants of DE and PSO algorithms. Two complex case studies of MO design of renewable energy systems are proposed to demonstrate the efficiency of the proposed MOMs. This thesis proposes three new MOMs, namely, leader and speed constraint multi-objective PSO (LSMPSO), opposition-based third evolution step of generalized DE (OGDE3), and multi-objective DE with leadership enhancement (MODEL) which are compared with seven state-of-the-art MOMS using various benchmark problems. LSMPSO was found to be the fastest MOM for the problem undertaken. Further, LSMPSO achieved the highest solutions accuracy for optimal design of a photovoltaic farm in Toronto area. OGDE3 is the first successful application of OBL to a MOM with single population (no-coevolution) using leadership and self-adaptive concepts; the convergence speed of OGDE3 outperformed the other MOMs for the problems solved. MODEL embodies leadership concept into mutation operator of GDE3 algorithm. MODEL achieved the highest accuracy for the 30 studied benchmark problems. Furthermore, MODEL achieved the highest solution accuracy for a MO optimization problem of hydrogen infrastructures design across the province Ontario between 2008 and 2025 considering electricity infrastructure constraints.