No description available.

Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1 PauloHAS_TESE.pdf: 9268945 bytes, checksum: 08c0c5f93ed7b964b99c6df2ee26ab1b (MD5) Previous issue date: 2011-12-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset / O Problema do Caixeiro Alugador (CaRS) ? uma variante ainda n?o descrita na literatura do cl?ssico Problema do Caixeiro Viajante onde o tradicional tour de visitas do caixeiro pode ser decomposto em caminhos cont?guos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final m?nimo, considerando o custo da rota adicionado ao custo de uma prov?vel penaliza??o paga em cada troca de ve?culos na rota, penaliza??o devida ao retorno do carro descartado at? a sua cidade base. Sem perda para a generalidade do caso, os custos do aluguel do carro podem ser considerados embutidos nos custos da rota do carro. O presente trabalho introduz o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma an?lise geral da complexidade desse problema combinat?rio ? descrita, visando justificar sua classifica??o na classe NP-dif?cil. Um banco de inst?ncias para o problema ? apresentado, descrevendo-se a metodologia de sua constitui??o. O problema proposto tamb?m ? objeto de um estudo algor?tmico experimental baseado na aplica??o de seis metaheur?sticas de solu??o, representando adapta??es do melhor do estado da arte em programa??o heur?stica. Novas vizinhan?as, procedimentos construtivos, operadores de busca, agentes evolucion?rios, coopera??o por multiferom?nios, s?o criados para o caso. Experimentos computacionais comparativos e testes de desempenho s?o realizados sobre uma amostra de 60 inst?ncias, visando oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se pela vantagem do algoritmo transgen?tico em todos os conjuntos de inst?ncias

Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1 LauraEASS_TESE.pdf: 2447411 bytes, checksum: 3e442431965058383423623bc7751de0 (MD5) Previous issue date: 2012-02-02 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Traditional applications of feature selection in areas such as data mining, machine learning and pattern recognition aim to improve the accuracy and to reduce the computational cost of the model. It is done through the removal of redundant, irrelevant or noisy data, finding a representative subset of data that reduces its dimensionality without loss of performance. With the development of research in ensemble of classifiers and the verification that this type of model has better performance than the individual models, if the base classifiers are diverse, comes a new field of application to the research of feature selection. In this new field, it is desired to find diverse subsets of features for the construction of base classifiers for the ensemble systems. This work proposes an approach that maximizes the diversity of the ensembles by selecting subsets of features using a model independent of the learning algorithm and with low computational cost. This is done using bio-inspired metaheuristics with evaluation filter-based criteria / A aplica??o tradicional da sele??o de atributos em diversas ?reas como minera??o de dados, aprendizado de m?quina e reconhecimento de padr?es visa melhorar a acur?cia dos modelos constru?dos com a base de dados, ao retirar dados ruidosos, redundantes ou irrelevantes, e diminuir o custo computacional do modelo, ao encontrar um subconjunto representativo dos dados que diminua sua dimensionalidade sem perda de desempenho. Com o desenvolvimento das pesquisas com comit?s de classificadores e a verifica??o de que esse tipo de modelo possui melhor desempenho que os modelos individuais, dado que os classificadores base sejam diversos, surge uma nova aplica??o ?s pesquisas com sele??o de atributos, que ? a de encontrar subconjuntos diversos de atributos para a constru??o dos classificadores base de comit?s de classificadores. O presente trabalho prop?e uma abordagem que maximiza a diversidade de comit?s de classificadores atrav?s da sele??o de subconjuntos de atributos utilizando um modelo independente do algoritmo de aprendizagem e de baixo custo computacional. Isso ? feito utilizando metaheur?sticas bioinspiradas com crit?rios de avalia??o baseados em filtro

Water distribution networks are a fundamental part of any modern city and their daily operations constitute a significant expenditure in terms of energy and maintenance costs. Careful scheduling of pump operations may lead to significant energy savings and prevent wear and tear. By means of computer simulation, an optimal schedule of pumps can be found by an optimisation algorithm. The subject of this thesis is the study of pump scheduling as an optimisation problem. New representations of pump schedules are investigated for restricting the number of potential schedules. Recombination and mutation operators are proposed, in order to use the new representations in evolutionary algorithms. These new representations are empirically compared to traditional representations using different network instances, one of them being a large and complex network from UK. By means of the new representations, the evolutionary algorithm developed during this thesis finds new best-known solutions for both networks. Pump scheduling as the multi-objective problem of minimising energy and maintenance costs in terms of Pareto optimality is also investigated in this thesis. Two alternative surrogate measures of maintenance cost are considered: the minimisation of the number of pump switches and the maximisation of the shortest idle time. A single run of the multi-objective evolutionary algorithm obtains pump schedules with lower electrical cost and lower number of pump switches than those found in the literature. Alternatively, schedules with very long idle times may be found with slightly higher electrical cost. Finally, ant colony optimisation is also adapted to the pump scheduling problem. Both Ant System and Max-Min Ant System are tested. Max-Min Ant System, in particular, outperforms all other algorithms in the large real-world network instance and obtains competitive results in the smallest test network. Computation time is further reduced by parallel simulation of pump schedules.

This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.

This paper deals with various approaches to solving optimization tasks. In prolog some examples from real life that show the application of optimization methods are given. Then term optimization task is defined and introducing of term fitness function which is common to all optimization methods follows. After that approaches by particle swarm optimization, ant colony optimization, simulated annealing, genetic algorithms and reinforcement learning are theoretically discussed. For testing we are using two discrete (multiple knapsack problem and set cover problem) and two continuous tasks (searching for global minimum of Ackley's and Rastrigin's function) which are presented in next chapter. Description of implementation details follows. For example description of solution representation or how current solutions are changed. Finally, results of measurements are presented. They show optimal settings for parameters of given optimization methods considering test tasks. In the end are given test tasks, which will be used for finding optimal settings of given approaches.

This doctoral thesis is focused on metrics and the criteria for socio-technical system diagnostics, which is a high profile topic for companies wanting to ensure the best in product quality. More and more customers are requiring suppliers to prove reliability in the production and supply quality of products according to given specifications. Consequently the ability to produce quality goods corresponding to customer requirements has become a fundamental condition in order to remain competitive. The thesis firstly lays out the basic strategies and rules which are prerequisite for a successful working company in order to ensure provision of quality goods at competitive costs. Next, methods and tools for planning are discussed. Planning is important in its impact on budget, time schedules, and necessary sourcing quantification. Risk analysis is also included to help define preventative actions, and reduce the probability of error and potential breakdown of the entire company. The next part of the thesis deals with optimisation problems, which are solved by Swarm based optimisation. Algorithms and their utilisation in industry are described, in particular the Vehicle routing problem and Travelling salesman problem, used as tools for solving specialist problems within manufacturing corporations. The final part of the thesis deals with Qualitative modelling, where solutions can be achieved with less exact quantitative information of the surveyed model. The text includes qualitative algebra descriptions, which discern only three possible values – positive, constant and negative, which are sufficient in the demonstration of trends. The results can also be conveniently represented using graph theory tools.

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.