Dissertations / Theses on the topic 'Hill-climbing optimization'

Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested.
Ph. D.

Generalized hill climbing (GHC) algorithms provide a framework for using local search algorithms to address intractable discrete optimization problems. Many well-known local search algorithms can be formulated as GHC algorithms, including simulated annealing, threshold accepting, Monte Carlo search, and pure local search (among others). This dissertation develops a mathematical framework for simultaneously addressing a set of related discrete optimization problems using GHC algorithms. The resulting algorithms, termed simultaneous generalized hill climbing (SGHC) algorithms, can be applied to a wide variety of sets of related discrete optimization problems. The SGHC algorithm probabilistically moves between these discrete optimization problems according to a problem generation probability function. This dissertation establishes that the problem generation probability function is a stochastic process that satisfies the Markov property. Therefore, given a SGHC algorithm, movement between these discrete optimization problems can be modeled as a Markov chain. Sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are presented. Moreover, sufficient conditions are obtained that guarantee that a SGHC algorithm will visit the globally optimal solution over all the problems in a set of related discrete optimization problems. Computational results are presented with SGHC algorithms for a set of traveling salesman problems. For comparison purposes, GHC algorithms are also applied individually to each traveling salesman problem. These computational results suggest that optimal/near optimal solutions can often be reached more quickly using a SGHC algorithm.
Ph. D.

Airships provide an eco-friendly and cost-effective means to suit sustained airborne operations. Smaller autonomous airships are highly susceptible to adverse atmospheric conditions owing to their under-actuated, underpowered and bulky size relative to other types of unmanned aerial vehicles (UAVs). To mitigate these limitations, careful considerations of the size and shape must be made at the design stage. This research presents a methodology for obtaining an optimized shape of a semi-rigid airship. Rapid descent of the LTA ship is achieved by means of a moving gondola attached to a rigid keel mounted under the helium envelope from the bow to the mid-section of the hull. The study entails the application of a robust hybrid genetic algorithm (HGA) for the multi-disciplinary design and optimization of an airship capable of rapid descent, with lower drag and optimum surface area. A comprehensive sensitivity analysis was also performed on the basis of algorithmic parameters and atmospheric conditions. With the help of HGA, a semi-rigid airship capable of carrying a payload of 0.25 kg to 1.0 kg and capable of pitching at right angles is conceptually designed. The algorithm is also tested on commercially available vehicles to validate the results. In multi-objective optimization problems (MOOPs), the significance of different objectives is dependent on the user.

There are many combinatorial optimization problems such as traveling salesman problem, quadratic-assignment problem, flow shop scheduling, that are computationally intractable. Tabu search based simulated annealing is a stochastic search algorithm that is widely used to solve combinatorial optimization problems. Due to excessive run time, there is a strong demand for a parallel version that can be applied to any problem with minimal modifications. Existing advanced and/or parallel versions of tabu search algorithms are specific to the problem at hand. This leads to a drawback of optimization only for that particular problem. In this work, we propose a parallel version of tabu search based SA on the Graphics Processing Unit (GPU) platform. We propose two variants of the algorithm based on where the tabu list is stored (global vs. local). In the first version, the list is stored in the global shared memory such that all threads can access this list. Multiple random walks in solution space are carried out. Each walk avoids the moves made in rest of the walks due to their access to global tabu list at the expense of more time. In the second version, the list is stored at the block level and is shared by only the block threads. Groups of random walks are performed in parallel and a walk in a group avoids the moves made by the rest of the walks within that group due to their access to shared local tabu list. This version is better than the first version in terms of execution time. On the other hand, the first version finds the global optima more often. We present experimental results for six difficult optimization functions with known global optima. Compared to the CPU implementation with similar workload, the proposed GPU versions are faster by approximately three orders of magnitude and often find the global optima.

Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions.
Ph. D.

Fundamental to the electronic security of information and communication systems, is the correct use and application of appropriate ciphers. The strength of these ciphers, particularly in their ability to resist cryptanalytic attacks, directly in uences the overall strength of the entire system. The strength of the underlying cipher is reliant upon a robust structure and the carefully designed interaction between components in its architecture. Most importantly, however, cipher strength is critically dependent on the strength of the individual components of which it is comprised. Boolean functions and substitution boxes (s-boxes) are among the most common and essential components of ciphers. This is because they are able to provide a cipher with strengthening properties to resist known and potential cryptanalytic attacks. Thus, it is not surprising that significant research effort has been made in trying to develop ways of obtaining boolean functions and substitution boxes with optimal achievable measures of desirable cryptographic properties. Three of the main cryptographic properties required by strong boolean functions and s-boxes are nonlinearity, correlation immunity and propagation criteria, with different cryptographic applications requiring different acceptable measures of these and other properties. As combinations of cryptographic properties exhibited by functions can be conicting, finding cryptographically strong functions often means that a trade-off needs to be made when optimizing property values. Throughout this thesis, the term "optimization" specifically refers to seeking to obtain the best achievable combination of target property values which may be exhibited by boolean functions and s-boxes, regardless of whether the relevant properties are conflicting or complementary. This thesis focusses on a particular class of techniques for obtaining strong functions for cryptographic applications, referred to as heuristic methods or, simply, heuristics. Three new heuristic methods, each aimed at generating boolean functions optimizing one or more of the main cryptographic properties mentioned above, in addition to other desirable properties, are presented. The first of the new heuristic methods developed for this thesis focusses on generating boolean functions which are balanced and exhibit very high nonlinearities. Highly nonlinear balanced functions are critical to many cryptographic applications, as they provide good resistance to linear cryptanalytic attacks. This first method is based on the recursive modification of a starting bent function and is shown to be highly successful and efficient at generating numerous such functions, which also exhibit low autocorrelation values, in a very short computational time. The generation of balanced, correlation immune boolean functions that also exhibit the confl icting property of high nonlinearity is the focus of the second new heuristic method developed for this thesis. By concatenating selected pairs of lower-dimensional boolean functions together in the Walsh Hadamard transform domain, direct optimization for both resilience and nonlinearity was able to take place at each level towards and for the final function. This second method was able to generate examples of boolean functions with almost all of the best known optimal combinations of target property values. Experiments have shown the success of this method in consistently generating highly nonlinear resilient boolean functions, for a range of orders of resilience, with such functions possessing optimal algebraic degree. A third new heuristic method, which searches for balanced boolean functions which satisfy a non-zero degree of propagation criteria and exhibit high nonlinearity, is presented. Intelligent bit manipulations in the truth table of starting functions, based on fundamental relationships between boolean function transforms and measures, provide the design rationale for this method. Two new function generation schemes have been proposed for this method, to efficiently satisfy the requirements placed on the starting functions utilized in the computational process. An optional process attempts to increase the algebraic degree of the resulting functions, without sacrificing the optimalities that are achievable. The validity of this method is demonstrated through the success of various experimental trials. Switching the focus from single output boolean functions to multiple output boolean functions (s-boxes), the effectiveness of existing heuristic techniques (namely Genetic Algorithm, Hill Climbing Method and combined Genetic Algorithm/Hill Climbing) in primarily being applied to improve the nonlinearity of s-boxes of various dimensions, is investigated. The prior success of these heuristic techniques for improving the nonlinearity of boolean functions has been previously demonstrated, as has the success of hill climbing in isolation when applied to bijective s-boxes. An extension to the bijective s-box optimization work is presented in this thesis. In this new research, a Genetic Algorithm, Hill Climbing Method and the two in combination are applied to the nonlinearity and autocorrelation optimization of regular NxM s-boxes (N > M) to investigate the effectiveness and efficiency of each of these heuristics. A new breeding scheme, utilized in the Genetic Algorithm and combined Genetic Algorithm/Hill Climbing trials, is also presented. The success of experimental results compared to random regular s-box generation is demonstrated. New research in applying the Hill Climbing Method to construct NxM sboxes (N > M) required to meet specific property criteria is presented. The consideration of the characteristics desired by the constructed s-boxes largely dictated the generation process. A discussion on the generation process of the component functions is included. Part of the results produced by experimental trials were incorporated into a commonly used family of stream ciphers, thus further supporting the use of heuristic techniques as a useful means of obtaining strong functions suitable for incorporation into practical ciphers. An analysis of the cryptographic properties of the s-box used in the MARS block cipher, the method of generation and the computational time taken to obtain this s-box, led to the new research reported in this thesis on the generation of MARS-like s-boxes. It is shown that the application of the Hill Climbing Method, with suitable requirements placed on the component boolean functions, was able to generate multiple MARS-like s-boxes which satisfied the MARS sbox requirements and provided additional properties. This new work represented an alternative approach to the generation of s-boxes satisfying the MARS sbox property requirements but which are cryptographically superior and can be obtained in a fraction of the time than that which was taken to produce the MARS s-box. An example MARS-like s-box is presented in this thesis. The overall value of heuristic methods in generating strong boolean functions and substitution boxes is clearly demonstrated in this thesis. This thesis has made several significant contributions to the field, both in the development of new, specialized heuristic methods capable of generating strong boolean functions, and in the analysis and optimization of substitution boxes, the latter achieved through applying existing heuristic techniques.

Made available in DSpace on 2014-06-11T19:23:39Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-09-06Bitstream added on 2014-06-13T18:51:01Z : No. of bitstreams: 1 ferreira_ab_me_ilha.pdf: 5542320 bytes, checksum: ac4ab4f7279192ce563639cce31eb895 (MD5)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Desenvolveu-se neste trabalho a implementação computacional de um algoritmo genético. Este se constituiu de uma população inicial sobre a qual agem quatro operadores fundamentais: seleção, “crossover”, substituição e mutação, e produz uma nova população. Sobre a qual agem novamente os operadores genéticos, e assim sucessivamente produzindo uma seqüência de populações. O operador seleção foi implementado em três algoritmos básicos: roda da roleta, amostragem estatística universal e torneio. O “crossover” também foi desenvolvido em algumas opções: um ponto, dois pontos, múltiplos pontos, e uniforme. A substituição de indivíduos da população pelos filhos ocorre de três maneiras básicas: dos pais, dos menos aptos, e dos indivíduos sorteados aleatoriamente. A mutação ocorre de apenas uma maneira. Inicialmente, o algoritmo genético foi executado em computador de maneira seqüencial. Resolveu-se um conjunto de problemas de otimização multidimensional e também o Problema do Caixeiro Viajante (TSP – Traveler Salesman Problem). Fez-se um estudo paramétrico dos vários parâmetros que aparecem no algoritmo genético, tais como: tamanho da população, número de gerações, taxa de seleção, probabilidade de mutação, e taxa de elitismo. No caso de problemas de otimização multidimensional a representação do cromossomo de cada indivíduo é binária, já no caso do TSP a representação é inteira decimal. Em ambos os casos da otimização multidimensional e do TSP também foi utilizada a técnica de hill-climbing visando aumentar a taxa de convergência da solução. A técnica de janelamento foi utilizada somente no caso de otimização multidimensional, também visando aumentar a taxa de convergência. Posteriormente, o algoritmo genético foi executado também em processamento computacional paralelo,...
It was developed in this work the computational implementation of a genetic algorithm. That is constituted of an initial population upon which act four basic operators: selection, crossover, substitution and mutation, producing a new population. Upon which act again the genetic operators, and thus, successively, producing a sequence of populations. The operator selection was implemented in three basic algorithms: roulette wheel, stochastic universal sampling, and tournament. The crossover also was developed in some options: one point, two points, several points, and uniform. Substitution of individuals from the population by the newborns happens in three basic ways: the fathers, the less apt, and the individuals sorted randomly. Mutation happens in only one manner. Initially, the genetic algorithm was processed sequentially in the computer. It was solved a set of multidimensional optimization problems and also the Traveler Salesman Problem - TSP. It was done a parametric study of the several parameters that appear in the genetic algorithm, such as: population size, number of generations, selection rate, mutation probability, and elitism rate. In the case of multidimensional optimization problems the chromosome representation of each individual is binary, but in the case of TSP the representation is integer decimal. In both cases of multidimensional optimization and TSP also it were used the hill-climbing technique aiming to increase the solution convergence rate. The windowing technique was used just for the multidimensional optimization case, also aiming to increase the convergence rate. Lately, the genetic algorithm was also performed in a computational parallel processing mode, using several computers linked by a net. In each computer it was executed one genetic algorithm upon a local population. The interaction among several populations was done through the migration ...(Complete abstract, click electronic access below)

Realistically, organizational and/or system efficiency performance is dynamic, non-linear, and a function of multiple interactions in production. However, in the efficiency literature, system performance is frequently evaluated considering linear combinations of the input/output variables, without explicitly taking into account the interactions and feedback mechanisms that explain the causes of efficiency behavior, the dynamic nature of production, and non-linear combinations of the input/output variables. Consequently, policy decisions based on these results may be sub-optimized because the non-linear relationships among variables, causal relationships, and feedback mechanisms are ignored. This research takes the initial steps of evaluating system efficiency performance in a dynamic environment, by relating the factors that effect system efficiency performance to the policies that govern it. First, this research extends the concepts of the static production axioms into a dynamic realm, where inputs are not instantaneously converted into outputs. The relationships of these new dynamic production axioms to the basic behaviors associated with system dynamics structures are explored. Second, this research introduces a methodological approach that combines system dynamics modeling with the measurement of productive efficiency. System dynamics is a modeling paradigm that evaluates system policies by exploring the causal relationships of the important elements within the system. This paradigm is coupled with the fundamental assumptions of production theory in order to evaluate the productive efficiency of a production system operating within a dynamic and non-linear environment. As a result, a subsystem within the system dynamics model is introduced that computes efficiency scores based on the fundamental notions of productive efficiency. The framework's ability to combine prescriptive and descriptive modeling characteristics, as well as dynamic and combinatorial complexity, can potentially have a greater impact on policy decisions and how they affect system efficiency performance. Finally, the utility of these concepts is demonstrated in an implementation case study. This methodology generates a prescriptive dynamical production frontier which defines the optimal production resources required to satisfy system requirements. Additionally, the dynamical production frontier allows for analysis for comparisons between options during a transient period, insight into possible unintended consequences, and the ability to forecast optimal times for introducing system or process improvements.
Ph. D.

This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing.
Master of Science

Orientador: João Batista Aparecido
Banca: Emanuel Rocha Woiski
Banca: Luis Carlos de Castro Santos
Resumo: Desenvolveu-se neste trabalho a implementação computacional de um algoritmo genético. Este se constituiu de uma população inicial sobre a qual agem quatro operadores fundamentais: seleção, "crossover", substituição e mutação, e produz uma nova população. Sobre a qual agem novamente os operadores genéticos, e assim sucessivamente produzindo uma seqüência de populações. O operador seleção foi implementado em três algoritmos básicos: roda da roleta, amostragem estatística universal e torneio. O "crossover" também foi desenvolvido em algumas opções: um ponto, dois pontos, múltiplos pontos, e uniforme. A substituição de indivíduos da população pelos filhos ocorre de três maneiras básicas: dos pais, dos menos aptos, e dos indivíduos sorteados aleatoriamente. A mutação ocorre de apenas uma maneira. Inicialmente, o algoritmo genético foi executado em computador de maneira seqüencial. Resolveu-se um conjunto de problemas de otimização multidimensional e também o Problema do Caixeiro Viajante (TSP - Traveler Salesman Problem). Fez-se um estudo paramétrico dos vários parâmetros que aparecem no algoritmo genético, tais como: tamanho da população, número de gerações, taxa de seleção, probabilidade de mutação, e taxa de elitismo. No caso de problemas de otimização multidimensional a representação do cromossomo de cada indivíduo é binária, já no caso do TSP a representação é inteira decimal. Em ambos os casos da otimização multidimensional e do TSP também foi utilizada a técnica de hill-climbing visando aumentar a taxa de convergência da solução. A técnica de janelamento foi utilizada somente no caso de otimização multidimensional, também visando aumentar a taxa de convergência. Posteriormente, o algoritmo genético foi executado também em processamento computacional paralelo, ...(Resumo completo, clicar acesso eletrônico abaixo)
Abstract: It was developed in this work the computational implementation of a genetic algorithm. That is constituted of an initial population upon which act four basic operators: selection, crossover, substitution and mutation, producing a new population. Upon which act again the genetic operators, and thus, successively, producing a sequence of populations. The operator selection was implemented in three basic algorithms: roulette wheel, stochastic universal sampling, and tournament. The crossover also was developed in some options: one point, two points, several points, and uniform. Substitution of individuals from the population by the newborns happens in three basic ways: the fathers, the less apt, and the individuals sorted randomly. Mutation happens in only one manner. Initially, the genetic algorithm was processed sequentially in the computer. It was solved a set of multidimensional optimization problems and also the Traveler Salesman Problem - TSP. It was done a parametric study of the several parameters that appear in the genetic algorithm, such as: population size, number of generations, selection rate, mutation probability, and elitism rate. In the case of multidimensional optimization problems the chromosome representation of each individual is binary, but in the case of TSP the representation is integer decimal. In both cases of multidimensional optimization and TSP also it were used the hill-climbing technique aiming to increase the solution convergence rate. The windowing technique was used just for the multidimensional optimization case, also aiming to increase the convergence rate. Lately, the genetic algorithm was also performed in a computational parallel processing mode, using several computers linked by a net. In each computer it was executed one genetic algorithm upon a local population. The interaction among several populations was done through the migration ...(Complete abstract, click electronic access below)
Mestre

Made available in DSpace on 2014-07-29T15:08:20Z (GMT). No. of bitstreams: 1 dissertacao geraldo valeriano eec.pdf: 1215973 bytes, checksum: 4ceb98a1d5250ad33d16a8997882d277 (MD5) Previous issue date: 2009-06-29
This work presents two methods to solve the problem of Electric Distribution Networks (EDN) with geographical and power restrictions. The high cost of the project involving EDN together with lack of efficient methods when working with real applications justifies the development of this research. Taking into account concepts of heuristic and metaheuristic two methods are proposed: The first is based on the Hill-Climbing (HC) heuristic and the second is based on the Simulated Annealing (SA) metaheuristic. The possible paths are provided by the Delaunay triangulation and it is considered the natural and socio-political obstacles of the site where you want to locate a new energy network. The dimension of the EDN feeders is calculated using the power flow results from the Forward-Backward method. The initial solution is found using an intelligent method. Then the SA metaheuristic and/or HC heuristic are used providing a good solution for a new EDN in comparison with the heuristic used to find the initial solution. A comparison is also made between the two proposed methods
RESUMO Neste trabalho são apresentados dois métodos para resolver o problema de planejamento de rede de distribuição de energia elétrica (RDEE) com restrições geográficas e elétricas. O custo elevado que envolve o projeto de RDEE unido à escassez de métodos eficientes quando se trata de aplicações reais justificam o desenvolvimento desta pesquisa. Considerando os conceitos de heurística e metaheurística são propostos dois métodos: o primeiro é baseado na heurística Hill-Climbing (HC) e o segundo é baseado na metaheurística Simulated Annealing (SA). Os possíveis caminhos são fornecidos pela triangulação de Delaunay e são considerados os obstáculos naturais e políticosociais (restrições geográficas) do local onde se deseja implantar a nova rede de energia elétrica. O dimensionamento dos alimentadores da RDEE é feito utilizando-se do fluxo de potência calculado pelo método Backward-Forward. A solução inicial é encontrada utilizando-se um método inteligente. A metaheurística SA e/ou a heurística HC são então utilizadas, fornecendo uma boa solução para uma nova RDEE, em relação à heurística utilizada para encontrar a solução inicial. Também é realizada uma comparação entre os dois métodos propostos.

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2017-11-17T16:18:59Z No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-11-20T10:11:34Z (GMT) No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2017-11-20T10:11:34Z (GMT). No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-09-28
The present work presents the development of a computational tool for the optimization of processes in the elaboration of electromechanical projects of conventional electricity distribution networks. The current process of elaboration of distribution network projects that has significant topographical interferences is slow and depends on software with a technological lag that requires post processing of the data to generate the final project, besides demanding specific technical knowledge and too much elaboration time. This elaboration time, as well as the errors occurred in the post-processing stage, hinder the approval process of the projects in the electric power concessionaires, and delay the connection of final consumers. For modeling the process, the typologies of the terrain where the network path is to be determined through surveys of the topographic data are verified first. Afterwards, mechanical forces and stresses are observed in each type of electromechanical structure, defining the minimum mounting distances in compliance with related technical norms, as well as incident variables such as wind speed and mechanical variations of the conductors during the operation. The modeling of the decision variables is applied a recursive heuristic method with the application of the Hill Climbing optimization method, which sweeps the entire line defined by topography, performing the mechanical evaluations and calculations with the optimization of technical budget criteria, generating uniform solutions and Automated. The tool obtained is developed in Web platform with friendly interface and updated, and can be used through any browser. The software, besides providing the elaboration of the project with embedded normative criteria, can be easily used for project analysis, providing integrated visualization of the planialtimetric profiles through Google Maps, optimizing the process of visual evaluation.
O presente trabalho apresenta o desenvolvimento de um método computacional destinado à otimização de processos na elaboração de projetos eletromecânicos de redes de distribuição convencional de energia elétrica. O processo atual de elaboração de projetos de redes de distribuição que possui interferências topográficas é lento e depende de softwares com defasagem tecnológica que necessitam de pós processamento dos dados para gerar o projeto final, além de demandar conhecimento técnico específico e demasiado tempo de elaboração. Esse tempo de elaboração, bem como os erros ocorridos na etapa de pós processamento, dificultam o processo de aprovação dos projetos nas concessionárias de energia elétrica, e atrasam a ligação dos consumidores finais. Para modelagem do processo, são verificados primeiramente as tipologias do terreno onde se deseja definir o caminhamento da rede através de levantamentos dos dados topográficos. Após, são observados os esforços e solicitações mecânicas pontualmente em cada tipo de estrutura eletromecânica, definindo as distâncias mínimas de montagem em observância às normas técnicas relacionadas, e também, variáveis incidentes como a velocidade do vento e variações mecânicas dos condutores durante a operação. Realizada a modelagem das variáveis de decisão é aplicado um método heurístico recursivo com a aplicação do método de otimização Hill Climbing, que varre toda a linha definida pela topografia, realizando as avaliações e cálculos mecânicos com a otimização de critérios técnicos orçamentários, gerando soluções uniformizadas e automatizadas. O método computacional é desenvolvido em plataforma Web com interface amigável e atualizada, podendo ser utilizada através de um navegador qualquer. O software além de proporcionar a elaboração do projeto com critérios normativos embutidos, pode ser facilmente utilizada para análise de projetos, proporcionando visualização integrada dos perfis planialtimétricos através Google Maps, otimizando o processo de avaliação visual.

La conception des filtres a réponse impulsionnelle finie (RIF) peut être formulée comme un problème d'optimisation non linéaire réputé pour être difficile sa résolution par les approches conventionnelles. Afin d'optimiser la conception des filtres RIF, nous explorons plusieurs méthodes stochastiques capables de traiter de grands espaces. Nous proposons un nouvel algorithme génétique dans lequel certains concepts innovants sont introduits pour améliorer la convergence et rendre son utilisation plus facile pour les praticiens. Le point clé de notre approche découle de la capacité de l'algorithme génétique (AG) pour adapter les opérateurs génétiques au cours de la vie génétique tout en restant simple et facile à mettre en oeuvre. Ensuite, l’optimisation par essaim de particules (PSO) est proposée pour la conception de filtres RIF. Finalement, un algorithme génétique hybride (HGA) est proposé pour la conception de filtres numériques. L'algorithme est composé d'un processus génétique pur et d’une approche locale dédiée. Notre contribution vise à relever le défi actuel de démocratisation de l'utilisation des AG’s pour les problèmes d’optimisation. Les expériences réalisées avec différents types de filtres mettent en évidence la contribution récurrente de l'hybridation dans l'amélioration des performances et montrent également les avantages de notre proposition par rapport à d'autres approches classiques de conception de filtres et d’autres AG’s de référence dans ce domaine d'application
The design of finite impulse response (FIR) filters can be formulated as a non-linear optimization problem reputed to be difficult for conventional approaches. In order to optimize the design of FIR filters, we explore several stochastic methodologies capable of handling large spaces. We propose a new genetic algorithm in which some innovative concepts are introduced to improve the convergence and make its use easier for practitioners. The key point of our approach stems from the capacity of the genetic algorithm (GA) to adapt the genetic operators during the genetic life while remaining simple and easy to implement. Then, the Particle Swarm Optimization (PSO) is proposed for FIR filter design. Finally, a hybrid genetic algorithm (HGA) is proposed for the design of digital filters. The algorithm is composed of a pure genetic process and a dedicated local approach. Our contribution seeks to address the current challenge of democratizing the use of GAs for real optimization problems. Experiments performed with various types of filters highlight the recurrent contribution of hybridization in improving performance. The experiments also reveal the advantages of our proposal compared to more conventional filter design approaches and some reference GAs in this field of application

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.