The pattern reduction (PR) algorithm we proposed previously, which works by eliminating patterns that are unlikely to change their membership during the convergence process, is obviously one of the most efficient methods for reducing the computation time of clustering algorithms. However, it is limited to problems with solutions that can be binary or integer encoded, such as combinatorial optimization problems. As such, this study is aimed at developing a new pattern reduction algorithm, called pattern reduction over continuous space, to get rid of this limitation. Like the PR, the proposed algorithm consists of two operators: detection and compression. Unlike the PR, the detection operator is divided into two steps. The first step is aimed at finding out subsolutions that can be considered as the candidate subsolutions for compression. The second step is performed to ensure that the candidate subsolutions have reached the final state so that any further computation is eventually a waste and thus can be compressed. To evaluate the performance of the proposed algorithm, we apply it to metaheuristics for clustering.

We propose a large neighborhood search (LNS) algorithm to solve the periodic location routing problem (PLRP). The PLRP combines location and routing decisions over a planning horizon in which customers require visits according to a given frequency and the specific visit days can be chosen. We use parallelization strategies that can exploit the availability of multiple processors. The computational results show that the algorithms obtain better results than previous solution methods on a set of standard benchmark instances from the literature.

Orientador: Fernando Antônio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T11:42:14Z (GMT). No. of bitstreams: 1 Marques_VitorHugoAlmeida_M.pdf: 2517224 bytes, checksum: e0259e1018ac57ec9a5cb95e0d65284b (MD5) Previous issue date: 2011 / Resumo: Esta dissertação introduz um sistema nebuloso genético (SNG) para adaptação de parâmetros em meta-heurísticas. Duas meta-heurísticas entre as mais usadas foram consideradas como exemplos, algoritmo genético e busca tabu. Os parâmetros trabalhados na busca tabu são relacionados às memórias, de curto prazo e de longo prazo. Já os parâmetros do algoritmo genético a sofrer adaptação são as taxas de reprodução e mutação. Sistemas baseados em regras nebulosas oferecem um mecanismo natural para descrever comportamentos globais como combinação de regras de controle. Eles também herdam um meio de gradualmente alternar entre regras que conjuntamente definem uma estratégia de controle. Dessa forma, esses sistemas são candidatos naturais para construir estratégias de controle de parâmetro porque eles proveem um maneira de desenvolver mecanismos baseados na natureza específica de uma região de busca e as transições entre suas fronteiras. Uma aplicação usando o problema clássico de roteamento de veículos com janela de tempo foi incluído para avaliar o desempenho do sistema nebuloso genético. Resultados experimentais mostram que meta-heurísticas com o mecanismo de adaptação com SNG melhoram o comportamento da busca e a qualidade das soluções quando comparado à versões padrões ( sem SNG ) e com parâmetros constantes dos algoritmos genético e busca tabu. Eles também geram boas soluções sub-ótimas mais rápidas que métodos exatos desenvolvidos para o problema e que são reportados na literatura / Abstract: This dissertation introduces a genetic fuzzy system for parameter adaptation of metaheuristics. Two metaheuristics, among the most used ones, have been considered as examples, genetic algorithm and tabu search. The considered parameters of the tabu search are related to the short and long term memories. Parameters of the genetic algorithm under adaptation are the mutation and reproduction rates. Fuzzy rule-based models offer a natural mechanism to describe global behavior as a combination of control rules. They also inherit a means to gradually shift between control rules which jointly defines a control strategy. They are a natural candidate to construct parameter control strategies because they provide a way to develop decision mechanisms based on the specific nature of search regions and transitions between their boundaries. An application using the classic vehicle routing problem with time windows is included to evaluate the genetic fuzzy system performance. Experimental results show that metaheuristics with GFS improve search behavior and solution quality when compared against standard, constant parameters genetic and tabu search approaches. It also provides reasonably good suboptimal solutions faster than specially tailored exact methods reported in the literature / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

- / The main topic of this thesis is the combination of metaheuristics and other methods for solving combinatorial optimization problems (COPs). In particular, focus is given in a special category of COPs known as timetabling problems. Timetabling problems belong in general to the class of NP-hard problems meaning that exact methods are usually unable to solve problem instances with sizes of practical importance. In the first three chapters optimization problems are analyzed and four major disciplines regarding optimization approaches are examined: Mathematical Programming, Artificial Intelligence, Computational Intelligence and Metaheuristics. Borders are not always clear between them while a recent trend is to hybridize approaches originating from the same or different disciplines. Even with the progress in optimization that occurred during the last decades programming successful optimization application still is an intricate mission. Nevertheless, software developing techniques, open source software and exploitation of the processing power of modern hardware can assist in constructing applications that are expected to be of much benefit for their users. Key ideas of achieving this are described in Chapter 4. The first application, presented in Chapter 5, is a pump scheduling system for a water distribution network. The objective is to achieve a way of operation for the pumps of each reservoir that results in diminished electricity cost. A model of the problem was constructed and the metaheuristic technique of genetic algorithms with the addition of several heuristics solved the problem. The second application, presented in Chapter 6, is the examination timetabling problem for Universities. Educational timetabling problems in general attract much interest from the scientific community. Our approach targeted various models of the examination timetabling problem and constituted by two major phases: construction and improvement. A number of metaheuristics were hybridized (Simulated Annealing, GRASP, VNS, Taboo Search and others) while certain sub-problems were solved using exact methods (Integer Programming). The results that we achieved in known datasets for evaluating the performance of such methods were most promising. In particular, for the publicly available datasets of the second International Timetabling Competition our approach achieved the best published score for 6 out of 8 datasets. The third application, presented in Chapter 7, is the construction of timetables for Greek high schools. A model of the problem that had publicly available problem instances and published results was used. Better results were able to be obtained by reformulating the problem and subsequently using a branch and cut approach implemented using entirely open source software. In summary, successful results of our approaches suggest that metaheuristics and hybridized metaheuristics with other metaheuristic or exact methods appears to be a promising research direction for handling complex combinatorial optimization problems.

Many real-world optimisation problems are discrete in nature. Although recent rapid developments in computer technologies are steadily increasing the speed of computations, the size of an instance of a hard discrete optimisation problem solvable in prescribed time does not increase linearly with the computer speed. This calls for the development of new solution methodologies for solving larger instances in shorter time. Furthermore, large instances of discrete optimisation problems are normally impossible to solve to optimality within a reasonable computational time/space and can only be tackled with a heuristic approach. In this thesis the development of so called matheuristics, the heuristics which are based on the mathematical formulation of the problem, is studied and employed within the variable neighbourhood search framework. Some new variants of the variable neighbourhood searchmetaheuristic itself are suggested, which naturally emerge from exploiting the information from the mathematical programming formulation of the problem. However, those variants may also be applied to problems described by the combinatorial formulation. A unifying perspective on modern advances in local search-based metaheuristics, a so called hyper-reactive approach, is also proposed. Two NP-hard discrete optimisation problems are considered: 0-1 mixed integer programming and clustering with application to colour image quantisation. Several new heuristics for 0-1 mixed integer programming problem are developed, based on the principle of variable neighbourhood search. One set of proposed heuristics consists of improvement heuristics, which attempt to find high-quality near-optimal solutions starting from a given feasible solution. Another set consists of constructive heuristics, which attempt to find initial feasible solutions for 0-1 mixed integer programs. Finally, some variable neighbourhood search based clustering techniques are applied for solving the colour image quantisation problem. All new methods presented are compared to other algorithms recommended in literature and a comprehensive performance analysis is provided. Computational results show that the methods proposed either outperform the existing state-of-the-art methods for the problems observed, or provide comparable results. The theory and algorithms presented in this thesis indicate that hybridisation of the CPLEX MIP solver and the VNS metaheuristic can be very effective for solving large instances of the 0-1 mixed integer programming problem. More generally, the results presented in this thesis suggest that hybridisation of exact (commercial) integer programming solvers and some metaheuristic methods is of high interest and such combinations deserve further practical and theoretical investigation. Results also show that VNS can be successfully applied to solving a colour image quantisation problem.

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization. * A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. * The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier. * Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception. * ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem. * ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.

Planning for emergency evacuation, and, more generally, for emergency movement involving both evacuation (egress) of occupants and ingress of first responders, presents important and challenging problems. A number of the current issues that arise during emergency incidents are due to the uncertainty and transiency of environmental conditions. In general, movement plans are formulated at building design-time, and those involved, such as building occupants and emergency responders, are left to adapt routing plans to actual events as they unfold. In the context of next-generation emergency response systems, it has been proposed to dynamically plan and route individuals during an emergency event, replanning to take account of changes in the environment. In this work, an emergency movement problem, the Maximal Safest Escape (MSE) problem, is formulated in terms that model the uncertain and transient environmental conditions as a flow problem in time-dependent networks with time-varying and stochastic edge travel-times and capacities (STV Networks). The objective of the MSE problem is to find flow patterns with the a priori maximal probability of successfully conveying all supply from the source to the sink in some given STV Network. The MSE and its deterministic counterpart are proved to be NP-hard. Furthermore, due to inherent complexity in evaluating the exact quality of candidate solutions, a simulation approximation method is presented based on well-known Monte-Carlo sampling methods. Given the complexity of the problem, and using the approximation method for evaluating solutions, it is proposed to tackle the MSE problem using a metaheuristic approach based on an existing framework that integrates Evolutionary Algorithms (EA) with a state-of-the-art statistical ranking and selection method, the Optimal Computing Budget Allocation (OCBA). Several improvements are proposed for the framework to reduce the computational demand of the ranking method. Empirically, the approach is compared with a simple fitness averaging approach and conditions under which the integrated framework is more efficient are investigated. The performance of the EA is compared against upper and lower bounds on optimal solutions. An upper bound is established through the “wait-and-see” bound, and a lower bound by a naıve random search algorithm (RSA). An experimental design is presented that allows for a fair comparison between the EA and the RSA. While there is no guarantee that the EA will find optimal solutions, this work demonstrates that the EA can still find useful solutions; useful solutions are those that are at least better than some baseline, here the lower bound, in terms of solution quality and computational effort. Experimentally, it is demonstrated that the EA performs significantly better than the baseline. Also, the EA finds solutions relatively close to the upper bound; however, it is difficult to establish how optimistic the upper bounds. The main approach is also compared against an existing approach developed for solving a related problem wrapped in a heuristic procedure in order to apply the approach to the MSE. Empirical results show that the heuristic approach requires significantly less computation time, but finds solutions of significantly lower quality. Overall, this work introduces and empirically verifies the efficacy of a metaheuristic based on a framework integrating EAs with a state-of-the-art statistical ranking and selection technique, the OCBA, for a novel flow problem in STV Networks. It is suggested that the lessons learned during the course of this work, along with the specific techniques developed, may be relevant for addressing other flow problems of similar complexity.

L’optimisation offre la possibilité, dans de nombreux domaines, d’améliorer les performances d’unsystème donné, qu’il soit physique ou mathématique. Depuis quelques décennies, les méthodesd’optimisation metaheuristiques ont fait leurs preuves, notamment dans le domaine de la mécanique.Du grec meta signifiant "un niveau au dessus", les metaheuristiques permettent de s’affranchir ducalcul des sensibilités souvent problématique quant à la résolution de problèmes d’optimisationcomplexes et/ou NP difficiles. En outre, elles ont la capacité à analyser simultanément l’ensemble dudomaine des solutions, ce qui leur permet converger efficacement vers l’optimum global de la fonctionobjectif considérée. Notre travail propose le développement d’une nouvelle méthode metaheuristiqueintelligente, basée conjointement sur l’algorithme d’optimisation par essaim particulaire PSO, etl’algorithme PageRank développé par MM. Brin et Page, et utilisé par le moteur de rechercheGoogle. Cet algorithme, appelé Inverse-PageRank-PSO (I-PR-PSO), a été validé sur un benchmarkde fonctions mathématiques, puis en optimisation contrainte sur des treillis mécaniques. Interfacéeavec l’algorithme Evolutionary Structural Optimization (ESO), elle a été adaptée à l’optimisationtopologique et a permis de trouver des résultats dont les topologies sont régulières et les temps decalcul minimisés. Dans le domaine des metamatériaux, nous avons développé une cape d’invisibilitéélectromagnétique fréquentielle, c’est à dire un metamatériau dont les parties réelle et imaginaire dela perméabilité effective sont négatives. En appliquant notre algorithme I-PR-PSO aux metamatériauxmécaniques, nous avons montré qu’il est possible de développer un metamatériau constitué d’acierqui présente des grandes déformations à l’échelle macroscopique, dues notamment aux grandsdéplacements présents dans le Volume Elémentaire Représentatif à l’échelle microscopique. / Based on a recent research concerning the PageRank algorithm used by the famous search engineGoogle, a new Inverse-PageRank-Particle Swarm Optimizer (I-PR-PSO) is developed, in order toimprove the performances of classic PSO. After having been tested and validated on a benchmarkof classical mathematical functions, this algorithm has been validated on constrained optimization,applied on classical trusses of the literature. Interfaced with the Evolutionary Structural Optimizationalgorithm, this algorithm has shown its performances on topology optimization, applied to structuralmechanics. Finally, using the performances of our newly developed algorithm, we have developedmetamaterials. In electromagnetics, a frequantial cloaking device has been developed, minimizingthe effective permeability of the considered Representative Volume Element. In mechanics, we havedeveloped a metamaterial made of steel which exhibits hyper-elastic - or, at least, non linear -mechanical behaviour. Combining great displacements and rotations at microscale, the developedmetamaterial exhibits great deformations at the macroscale as well.

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <br> To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <br> To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation. <br> Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <br> In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: 1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; 2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art.

Recent years have witnessed increasing interest in using metaheuristics to solve the codebook generation problem (CGP) of vector quantization as well as increasing interest in reducing the computation time of metaheuristics. One of the recently proposed methods aimed at reducing the computation time of metaheuristics is based on the notion of pattern reduction (PR). The problem with PR is in that it may compress and remove patterns that are not supposed to be compressed and removed, thus decreasing the quality of the solution. In this thesis, we proposed a fuzzy version of PR called fuzzy pattern reduction (FPR) to reduce the possibility of compressing and removing patterns that are not supposed to be compressed and removed. To evaluate the performance of the proposed algorithm, we apply it to the following four metaheuristics: generalized Lloyd algorithm, code displacement, genetic k-means algorithm, and particle swarm optimization and use them to solve the CGP. Our experimental results show that the proposed algorithm can not only significantly reduce the computation time but also improve the quality of all the metaheuristics evaluated.