Tesi sul tema "Hill climbing"

Thesis (Ph. D.) -- University of Maryland, College Park, 2006.
Thesis research directed by: Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

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.

Many real-world problems can be modelled as constraint optimisation problems (COPs). Each COP includes a set of variables with domains of values, constraints on the assignments to the variables, and an objective function, which should be minimised or maximised. In this thesis, we consider only combinatorial COPs, where domains of the variables are discrete. A component is a subproblem of a COP with specific variables, assignable values or constraints. Most practical COPs, including waste collection, mail delivery, supply chain management, and travelling thief problem (TTP), have more than one component. Existing methods for solving COPs, especially multi-component COPs, repeatedly solve the same problem or subproblem but do not take advantage of learning during the search. This research aimed to apply memorising and online or adaptive machine learning models. The memory buffers and the ML models are built, deployed, and updated during the search to improve search efficacy and efficiency in solving COPs, especially multi-component ones. In this research, we have developed a history memorising method to enhance diversity and effectiveness in solving COPs. Also, we have developed three online machine learning-based methods, one coordination learning for improving efficacy and two surrogate models for enhancing the efficiency of TTP solving. Our proposed solver, CoCo, is currently the state-of-the-art solver for solving TTP. History memorising is an online low-level learning method to keep previously visited solutions or their objective values to avoid or escape from local optima during the search. The Late Acceptance Hill Climbing (LAHC) is a history memorising metaheuristic with promising performance on some COP domains. It aims to overcome the main downside of the traditional Hill Climbing (HC) search, which is often quickly trapped in a local optimum due to strictly accepting only non-worsening moves within each iteration. In contrast, LAHC also accepts worsening moves by keeping the objective values of the previously visited solutions in a limited-size circular memory. It compares the fitness values of candidate solutions against the least recent element in the circular memory to decide on accepting or rejecting them. However, we have realised that whenever all values in memory become the same, LAHC behaves like HC and gets stuck in local optima. We propose an improved form of LAHC called Diversified Late Acceptance Search (DLAS) for solving COPs in general, which usually uses much smaller memory, converges much faster than LAHC and escapes local optima much better than LAHC. The proposed DLAS approach outperforms LAHC on benchmark sets of Travelling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP) instances. TTP is an academic proxy for the waste collection and mail delivery real-world optimisation problems composed of TSP and Knapsack Problem (KP). In TTP, a thief makes a cyclic tour through a set of cities while collecting profitable items scattered over the cities into a rented capacitated knapsack. As the weight of the knapsack increases, the thief’s speed decreases; hence the renting cost increases. Solving TTP aims to maximise profit while minimising the renting cost simultaneously, which means maximising the difference between profit and renting cost. Existing TTP solvers typically employ interleaving and solve one component at a time while keeping the solution of the other component unchanged. This form of interleaving essentially means poor coordination in solving TTP. In this thesis, we first show that a simple local search based coordination approach does not work in TTP. Then, to adequately address interdependence between TSP and KP components, we propose a human-designed coordination heuristic that adjusts collection plans during the exploration of cyclic tours. We further propose another human-designed coordination heuristic that explicitly exploits the cyclic tours in selecting items during collection plan exploration. Lastly, we propose an online machine learning-based coordination heuristic that captures the characteristics of the two human-designed coordination heuristics while solving any TTP instance. Our proposed coordination-based approaches help our TTP solver, cooperative coordination (CoCo), significantly outperform existing state-of-the-art TTP solvers on a set of benchmark TTP instances. Our proposed CoCo solver modifies a TTP instance’s underlying TSP and KP solutions in an iterative interleaved fashion. The TSP solution as a cyclic tour is typically changed in a deterministic way using the steepest-ascent Hill-Climbing (HC) search similar to other cooperative solvers. In contrast, changes to the KP solution typically involve a random HC search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once CoCo reaches a plateau, it restarts the iterative search of the TTP solution space by using a new initial cyclic tour. We have noticed that the final objective value remains almost the same if the same or similar initial cyclic tour is tried several times by CoCo or the other cooperative TTP solvers. Considering this semideterministic nature of the state-of-the-art cooperative TTP solvers, we propose two adaptive and online surrogate models to filter out non-promising initial cyclic tours to improve search efficiency. These surrogate models are automatically built, updated and deployed while solving any TTP instance. The first model is a Support Vector Regression (SVR)-based black-box model, and the second is a K Nearest Neighbour (KNN)-based white-box simulation model. Both models help to filter out non-promising initial cyclic tours while losing a small number of the cyclic tours leading to the best overall solutions. However, the KNN-based white-box simulation model is more accurate and efficient.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Info & Comm Tech
Science, Environment, Engineering and Technology
Full Text

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-07T16:35:24Z No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5)
Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-07T16:52:21Z (GMT) No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5)
Made available in DSpace on 2014-11-07T16:52:21Z (GMT). No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) Previous issue date: 2014
Este trabalho trata um problema particular de planejamento de lavra de uma mineradora localizada no quadrilátero ferrífero do Estado de Minas Gerais, Brasil. Neste problema há um conjunto de frentes de lavra, um conjunto de equipamentos de carga de diferentes produtividades, um conjunto de caminhões de diferentes capacidades e um conjunto de pontos de descarga para o material lavrado. Cada frente de lavra é subdividida em blocos, os quais, por sua vez, são subdivididos em sub-blocos. Cada sub-bloco pode conter um dentre quatro tipos de material: hematita, canga, itabirito e estéril. Além disso, cada sub-bloco somente pode ser lavrado se os sub-blocos precedentes tiverem sido totalmente lavrados. A cada ponto de descarga está associada uma meta de produção e uma qualidade de material a ser atendida. O objetivo é determinar a alocação das carregadeiras aos blocos e o número de viagens que cada caminhão deve fazer a cada sub-bloco, saindo de um determinado ponto de descarga, de forma a atender as metas de produção e qualidade estabelecidas para cada descarga. Para resolvê-lo foi desenvolvido um algoritmo heurístico baseado nas metaheurísticas Greedy Randomized Adaptive Search Procedures (GRASP) e Late Acceptance Hill-Climbing (LAHC). O algoritmo explora o espaço de soluções usando busca locais autoadaptativas. Experimentos computacionais comparam os resultados do algoritmo proposto com aqueles do otimizador LINGO aplicado a um modelo de programação linear inteira mista e mostram a efetividade da proposta. ________________________________________________________________________________________________
ABSTRACT: This work deals with a particular problem of mine planning at a mining company located in the Iron Quadrangle of Minas Gerais, Brazil. In this problem there is a set of pit mining, a set of loader equipment of different yields, a set of trucks of different capacities and a set of delivery points for the discharge of materials. Each pit is subdivided into blocks, which, in turn, are subdivided into sub-blocks. Each sub-block can contain one of four types of material: hematite, canga, itabirito and waste. Furthermore, each sub-block can only be drawn up if the preceding sub-blocks have been fully drawn up. Every point of discharge is associated with a production and quality targets of material to be answered. The objective is to determine the allocation of loaders to blocks and the number of trips that each truck must do for each sub-block, leaving a certain point of discharge in order to meet production and quality targets requirements for each discharge. A heuristic algorithm, based on the metaheuristics Greedy Randomized Adaptive Search Procedures and Late Acceptance Hill-Climbing, was developed in order to solve this problem. The algorithm explores the solution space using self-adaptive local search. Computational experiments compare the results of the proposed algorithm with those of the optimizer LINGO model applied to a mixed integer linear programming and show its effectiveness.

Spatial layout design must consider not only ease of movement for pedestrians under normal conditions, but also their safety in panic situations, such as an emergency evacuation in a theatre, stadium or hospital. Using pedestrian simulation statistics, the movement of crowds can be used to study the consequences of different spatial layouts. Previous works either create an optimal spatial arrangement or an optimal pedestrian circulation. They do not automatically optimise both problems simultaneously. Thus, the idea behind the research in this thesis is to achieve a vital architectural design goal by automatically producing an optimal spatial layout that will enable smooth pedestrian flow. The automated process developed here allows the rapid identification of layouts for large, complex, spatial layout problems. This is achieved by using Cellular Automata (CA) to model pedestrian simulation so that pedestrian flow can be explored at a microscopic level and designing a fitness function for heuristic search that maximises these pedestrian flow statistics in the CA simulation. An analysis of pedestrian flow statistics generated from feasible novel design solutions generated using the heuristic search techniques (hill climbing, simulated annealing and genetic algorithm style operators) is conducted. The statistics that are obtained from the pedestrian simulation is used to measure and analyse pedestrian flow behaviour. The analysis from the statistical results also provides the indication of the quality of the spatial layout design generated. The technique has shown promising results in finding acceptable solutions to this problem when incorporated with the pedestrian simulator when demonstrated on simulated and real-world layouts with real pedestrian data.

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.

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores
Esta tese apresenta um circuito conversor DC-DC (“step-up”) para aplicações de “energy harvest”. Este circuito utiliza uma arquitectura “Switched capacitor voltage tripler”, controlada por um circuito MPPT baseado nos métodos “Load Voltage Maximization” e “Hill Climbing”. Este circuito foi desenhado usando a tecnologia “0.13 μm CMOS” de forma a funcionar com uma célula fotoeléctrica de “a-silicon”. Este circuito tem uma fonte de alimentação local também controlada pelo mesmo circuito MPPT, que é uma réplica do conversor “SC voltage tripler”, redimensionado a 3% da área deste último. Este circuito utiliza a combinação de transístores PMOS e NMOS de forma a reduzir a área ocupada. Um esquema de reutilização de cargas é utilizado para compensar as grandes resistências parasitas associadas aos transístores MOS. Os resultados das simulações mostram que o circuito pode fornecer uma potência de 9636 μW à carga, utilizando uma potência de 1274 μW na célula fotoeléctrica,correspondendo a uma eficiência na ordem dos 75,66%. As simulações mostram também que o circuito é capaz de se iniciar com apenas 19% do nível de iluminação máximo da célula fotoeléctrica.

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.

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)

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.

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.

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.

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-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.

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

Submitted by João Arthur Martins (joao.arthur@ufpe.br) on 2015-03-10T18:13:40Z No. of bitstreams: 2 Dissertacao Felipe Borgiani.pdf: 3365746 bytes, checksum: fbfcefa352bee971420dbb93de7d9b5a (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Made available in DSpace on 2015-03-11T17:39:59Z (GMT). No. of bitstreams: 2 Dissertacao Felipe Borgiani.pdf: 3365746 bytes, checksum: fbfcefa352bee971420dbb93de7d9b5a (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-09-06
O trânsito caótico das grandes cidades, especialmente em países em desenvolvimento, impacta diretamente na qualidade de vida dos cidadãos, principalmente daqueles que necessitam diariamente dos sistemas de transporte público rodoviários. Diversas abordagens para amenizar esses problemas vem sido apresentadas por pesquisadores do mundo todo, na forma de diferentes propostas de sistemas de transporte inteligentes. Tendo em vista o desenvolvimento tecnológico dos últimos anos, aliado à expansão e popularização do uso de dispositivos computacionais portáteis como smartphones e tablets, este trabalho propõe-se a apresentar um sistema, componente do Sistema de Transporte Inteligente UbiBus, denominado Pilgrim, capaz de gerar e classificar rotas de ônibus em tempo real, e seja sensível ao contexto que permeia o sistema de transporte público rodoviário, em especial o trânsito. Para tanto, serão propostas duas abordagens utilizando técnicas de otimização da inteligência artificial, Algoritmos Genéticos e Hill-Climbing com Reinício Aleatório, para o desenvolvimento do sistema, e apresentadas a arquitetura, a modelagem e os detalhes da implementação. Este trabalho ainda apresenta os experimentos realizados para avaliar o desempenho de ambas as abordagens, comparando-as, e também uma pesquisa feita com potenciais usuários do sistema UbiBus, com o objetivo de avaliar a qualidade das rotas geradas pelo sistema Pilgrim.

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

Modellazione di un impianto fotovoltaico connesso alla rete. Simulazione con software Simulink del funzionamento dell'intero sistema fotovoltaico e confronto delle prestazioni legate all'utilizzo degli algoritmi MPPT più comuni, quali Hill Climbing e Incremental Conductance.

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.

The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).

碩士
國立金門技術學院
電資研究所
98
Hill-Climbing(HC) is an optimization algorithm that is widely known. It’s simple and fast. However, HC will be trapped when it fall into local optima, and cannot find global optimal solution. In this paper, we design a jumping strategy to help HC escape from local optima. The new algorithm is called Hill-Climbing with Jumping Strategies(HCJ). This text adopts three popular Nonlinear Programming problems - G1, G7, G9, to test the effect of HCJ algorithm. The result showed that HCJ had excellent performances on G1, G9, but HCJ couldn't work well on G7. Through analyzing the experiment, we realized that G7 may contain a problem itself, this is a problem which HCJ cannot solve at the moment, but it is also an area which HCJ could be improved in the future. However, when comparing HCJ with other single-particle algorithm, such as HC and SA, HC shows much improvement in its accuracy with its performance and solutions; when compared with multi-particle algorithm, we have found out that when HCJ is obtaining a solution, although it is not as good as the modified PSO and GA, but it is better than the original PSO and GA. This is resulted from the modification of the HCJ jumping strategy, it also shows the improvement in the potential of the HCJ jumping strategy.

碩士
中華大學
生物資訊學系碩士班
99
The nurse rostering problem has been studied since 1976. However the best solution has never been found. The major cause is the limitations of the problem are different and the solution will be hard to fulfil all of nurses needs. This paper proposes a set of graph algorithm to improve the application of hill-climbing, Tested to speed up the program execution time is about 3.5 times speed up and fine-tuning a more in line with restrictions nurse scheduling table, to expect to provide more in line with the needs of nursing classes table, improve nurses performance and service quality.

To protect non-timber resources such as wildlife, water quality and aesthetics, harvesting regulations have been introduced that limit opening size, and set minimum green-up times. Many constraints have been introduced to long-term, multiple-use forest planning problems. Proper scheduling of cut blocks for the large-scale integrated forest planning is important in order to produce the maximum amount of timber from the land base without violating the constraints. Also, these problems are difficult to solve due to the problem size and the constraint structure. These non-linear combinatorial optimization problems are difficult and even impossible to solve to optimality with present- day computers. In this thesis, three models based on evolution programs, simulated annealing and hill climbing were developed with C and C++ for solving forest planning problems. Both evolution programs an d simulated annealing are probabilistic algorithms that will accept inferior moves within the search space as a means of searching out global optima. They differ from hill climbing algorithms that only accept superior solutions, and often stall at local optima. Evolution programs simultaneously work with a population of solutions, while simulated annealing is a specific case where the population size is reduced to one. Evolution programs and simulated annealing are applicable to a broad range of problems for which very little prior knowledge is available. However, many opportunities exist for improving the performance of these algorithms by incorporating problem specific knowledge and heuristics. This is the first time that simulated annealing theory is used on a problem- specific gene recombination operator working on individual chromosomes. It is believed that the evolution programs can be applied to many more problems. It was found that all solutions generated by all these methods were within 3.12% of the best solution found. All the solutions found by simulated annealing are within 1.00%; evolution programs, 2.54% and hill climbing, 3.12% of this best solution. However, simulated annealing converged much faster on the optimum than did the evolution program. Using a 486/50 MHz computer, the evolution program took 378 minutes with a population of 30 chromosomes, 431 harvest blocks and 10,000 generations. Simulated annealing took only 36.8 minutes, while hill climbing took 32.7 minutes on the same problem.

碩士
國立交通大學
資訊科學與工程研究所
99
Genetic algorithms (GAs) are commonly used methods for discrete valued optimization problems. However, GAs often spend a significant amount of computational time in searching for the optimal solution of discrete structural optimization problems, especially when the search space has enormous number of potential solutions. Moreover, GAs are possible perform unstable computational results as the set of bad working parameters is used for them. Therefore, this work attempts to optimize the design of truss structures with discrete sizing variables through an enhanced search performance by incorporating a hill-climbing strategy and two greedy notions into a simple GA. The hill-climbing strategy is integrated into the GA to reduce the search space, while the greedy notions help the GA to explore the search space for identifying the most promising search region. Four truss design problems selected from the literatures are adopted for the performance of tests of the proposed GA. The computational results indicate that the proposed GA has the strong capability and stability for finding the optimal design of truss structures with discrete sizing variables within a small number of iterations.

A powerful attraction of photovoltaic (PV) power systems is that they produce electric power without harming the environment, by directly transforming a free inexhaustible source of energy, solar irradiation, into electricity. This fact, together with the continuing decrease in PV array cost and increase in efficiency, implies a promising role for PV generation systems in the near future. The study started with the requirement that photovoltaic power systems should be integrated with specific control algorithms to deliver maximum possible power. In this thesis, the PV power system was introduced at the beginning, and a simple maximum power point tracking (MPPT) system was presented and analyzed. Next, different existing MPPT control approaches were discussed and a proposed control algorithm, namely modified adaptive hill climbing (MAHC) method, was introduced. Then, the results of simulation proved that the performance could be improved in both transient and steady state of the suggested control system. Finally, a simple test bed system with digital signal processor (DSP) was designed and implemented with optimized control software to verify the proposals.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

A geração de horários é uma tarefa de dificuldade elevada e requer trabalho árduo devido à necessidade de gerir os diversos conflitos de restrições impostos aos recursos a ser usados, mais concretamente alunos, professores e salas. A grande variedade de restrições associada às diferentes necessidades de diferentes sistemas de ensino e até mesmo entre escolas do mesmo nível, tem dificultado a elaboração de formatos standard que permitam não só caracterizar as próprias restrições/regras mas também os recursos de grandes variedades de sistemas de ensino, possibilitando a comparação de práticas e avaliação de desempenho assim como proporcionar uma estrutura capaz de ser manipulada por sistemas com capacidade de gerar horários. Esta dissertação aborda o problema da elaboração de horários académicos, focando-se no caso da Academia da Força Aérea (AFA). São apresentados vários exemplos de sistemas de ensino e um formato de especificação em XML para benchmarking de horários académicos, no qual são especificadas as restrições impostas aos horários da Academia da Força Aérea. Várias técnicas de pesquisa local restringida que são tradicionalmente usadas para resolver este tipo de problemas, nomeadamente as técnicas de Hill-Climbing (HC), Simulated Annealing (SA) e Tabu Search (TS), são discutidas e são exploradas para resolver o problema da geração de horários na AFA. Este trabalho avalia esta abordagem e foi elaborada uma ferramenta para resolução de horários académicos, que para além de validar a completude de informação fornecida na representação XML (e estendê-la), permite obter soluções que satisfazem um conjunto de restrições obrigatórias (como a não sobreposição de recursos) e otimizam um conjunto de preferências adicionais (boas práticas pedagógicas, como a não existência de furos). A eficiência da ferramenta é estudada por comparação com ferramentas que já utilizam a representação XML referida.

Indiana University-Purdue University Indianapolis (IUPUI)
This thesis focuses on optimization of wind power tracking control systems in order to capture maximum wind power for the generation system. In this work, a mathematical simulation model is developed for a variable speed wind turbine power generation system. The system consists a wind turbine with necessary transmission system, and a permanent magnet synchronous generator and its vector control system. A new fuzzy based hill climbing method for power tracking control is proposed and implemented to optimize the wind power for the system under various conditions. Two existing power tracking control methods, the tip speed ratio (TSR) control method and the speed sensorless control method are also implemented with the wind power system. The computer simulations with a 5 KW wind power generation system are performed. The results from the proposed control method are compared with those obtained using the two existing methods. It is illustrated that the proposed method generally outperforms the two existing methods, especially when the operating point is far away from the maximum point. The proposed control method also has similar stable characteristic when the operating point is close to the peak point in comparison with the existing methods. The proposed fuzzy control method is computationally efficient and can be easily implemented in real-time.

Questa tesi approfondisce la tematica del miglioramento, in termini di velocità e regolarità, del funzionamento dei sistemi di trasporto collettivo in sede stradale, attraverso strategie di controllo in tempo reale. In particolare in questo lavoro vengono approfondite le strategie di intervento annoverabili nelle due categorie della “Vehicle Priority” e del “Vehicle Holding”, potenzialmente contraddittorie fra loro. L’analisi della letteratura scientifica e delle buone pratiche ha evidenziato come le due strategie di intervento, orientate l’una alla massimizzazione della velocità commerciale e l’altra alla massimizzazione della regolarità di servizio, vengano al momento considerate perlopiù indipendentemente l’una dall’altra, sia nel campo delle applicazioni pratiche che in quello della speculazione teorica. In questo lavoro viene presentato un nuovo approccio unitario che contempera entrambe le strategie di intervento, e viene introdotto un metodo, tradotto in prototipo software, per il calcolo della strategia ottima di regolazione della marcia dei veicoli attraverso punti di controllo fissi (ad es. segnali semaforici stradali) che consenta di perseguire congiuntamente obiettivi di massimizzazione della velocità e della regolarità di servizio. Il metodo di ottimizzazione qui formulato e testato si basa sull’uso combinato di (meta)euristiche (di tipo Genetico, PSO ed Hill Climbing) e metodi di simulazione del traffico capaci di riprodurre e prevedere le traiettorie temporali dei singoli veicoli di trasporto collettivo. La capacità di previsione a breve termine insita nell’uso di strumenti simulativi consente di generare soluzioni al problema di regolazione estese “in avanti” sia nello spazio stradale che nel tempo, consentendo quindi un approccio alla regolazione che sia al contempo anticipatorio e non-locale: queste caratteristiche consentono in generale di realizzare riallocazioni nell’uso della capacità tra intersezioni vicine consentendo quindi, ove possibile, di ridurre la competizione tra modi di trasporto diversi nell’uso della capacità stradale. In questo lavoro vengono infine presentati i risultati di una serie di test attuati sia nell’ipotesi di realizzare il controllo attraverso un normale schema semaforico a ciclo e fasi ripetitivi per ciascun segnale, sia nell’ipotesi meno restrittiva di tempi di rosso e di verde in generale variabili per lo stesso segnale. I tempi di calcolo del prototipo realizzato inoltre suggeriscono la possibilità, attraverso ulteriori sviluppi, di utilizzare tale metodo in applicazioni real-time.
This thesis explores the theme of improving, in terms of speed and regularity, the road-operation of public transport systems, through control strategies in real time. Specifically in this work are highlighted intervention strategies that falls in the two categories of "Vehicle Priority" and "Vehicle Holding", potentially conflicting the one with the other. The analysis of scientific literature and best practice has shown that the two intervention strategies, leading the first at maximizing the commercial speed and the second to the maximization of regularity of service, are currently considered one independently from the other, both in the field of practical applications than in the one of theoretical speculation. In this work is presented a new unified approach that reconciles both the strategies of intervention; moreover a method is introduced, implemented into a prototype software, for the calculation of the optimal strategy of the vehicle operating through regulation of fixed control points (eg. Signals road traffic lights) to allow a joint pursuit of speed maximization objectives and regularity of service. The optimization method here formulated and tested is based on the combined use of (meta) heuristics (Genetic Algorythm, PSO and Hill Climbing) and traffic simulation methods able to reproduce and predict the temporal trajectories of individual public transport vehicles. The short-term prediction capabilities inherent in the use of simulation tools allows to generate solutions to the regulation problem which are extended "forward" both in the road space and time, thus allowing an approach to regulation that is both anticipatory and non-local. These characteristics allow in general to achieve road capacity relocation between neighboring intersections thus enabling, where possible, to reduce the competition between different modes of transport in the use of road capacity. In this work are finally presented the results of a series of tests carried out both in the case of realizing the control through a normal signal pattern with ripetitive cycle and phases for each signal, both in the hypothesis less restrictive of red and green times generally variables during time for each signal. The calculation effort of the prototype also suggest the possibility, through further developments, to use this method for real-time applications.