Over the last two decades, chip design has been conducted at the register transfer (RT) Level using Hardware Descriptive Languages (HDL), such as VHDL and Verilog. The modeling at the behavioral level not only allows for better representation and understanding of the design, but also allows for encapsulation of the sub-modules as well, thus increasing productivity. Despite these benefits, validating a RTL design is not necessarily easier. Today, design validation is considered one of the most time and resource consuming aspects of hardware design. The high costs associated with late detection of bugs can be enormous. Together with stringent time to market factors, the need to guarantee the correct functionality of the design is more critical than ever. The work done in this thesis tackles the problem of RTL design validation and presents new frameworks for functional test generation. We use branch coverage as our metric to evaluate the quality of the generated test stimuli. The initial effort for test generation utilized simulation based techniques because of their scalability with design size and ease of use. However, simulation based methods work on input spaces rather than the DUT's state space and often fail to traverse very narrow search paths in large input spaces. To encounter this problem and enhance the ability of test generation framework, in the following work in this thesis, certain design semantics are statically extracted and recurrence relationships between different variables are mined. Information such as relations among variables and loops can be extremely valuable from test generation point of view. The simulation based method is hybridized with Z3 based symbolic backward execution engine with feedback among different stages. The hybridized method performs loop abstraction and is able to traverse narrow design paths without performing costly circuit analysis or explicit loop unrolling. Also structural and functional unreachable branches are identified during the process of test generation. Experimental results show that the proposed techniques are able to achieve high branch coverage on several ITC'99 benchmark circuits and their modified variants, with significant speed up and reduction in the sequence length. / Master of Science

When creating a muffler to be installed on a noise generating machine, the design parameters as well as the placements of sound attenuating elements has to be optimized in order to minimize the sound coming out of the equipage. This is exemplified in a small project task for students of a basic course in optimization at KTH. The task is however flawed, since both the way in which the optimization problem is formed is overly simplistic and the algorithm used to solve the problem, fmincon, does not cope well with the mathematical complexity of the model, meaning it gets stuck in a local optimum that is not a global optimum. This thesis is about investigating how to solve both of these problems. The model is modified to combine several frequencies and adjusting them to the sensitivity to different frequencies in the human ear. By doing this, the objective is changed from the previous way of maximizing Dynamic Insertion Loss Dilfor a specific frequency to minimize the total perceived sound level LA.  The model is based on the modular design of TMM from four-pole theory. This divides the muffler into separate parts, with the sound attenuating elements being mathematically defined only by what T matrix it has. The element types to choose from are the Expansion Chamber, the Quarter Wave Resonator and the Helmholtz Resonator. The global optimization methods to choose from are Global Search, MultiStart, Genetic Algorithm, Pattern Search and Simulated Annealing. By combining the different types of sound attenuating elements in every way and solving each case with every global optimization method, the best combination to implement to the model is chosen. The choice is two Quarter Wave Resonators being solved by MultiStart, which provides satisfactory results. Further analysis is done to ensure the robustness of chosen implementation, which does not reveal any significant flaws. The purpose of this thesis is fulfilled. / När man skapar en ljuddämpare som ska installeras på en ljud-genererande maskin bör designparametrarna samt placeringarna av ljuddämpande element optimeras för att minimera ljudet som kommer ut ur ekipaget. Detta exemplifieras i en liten projektuppgift för studenter till en grundkurs i optimering på KTH. Uppgiften är dock bristfällig, eftersom både det sätt som optimeringsproblemet är utformat är alltför förenklat och den algoritm som används för att lösa problemet, fmincon, inte klarar av modellens matematiska komplexitet bra, vilket menas med att den fastnar i ett lokalt optimum som inte är ett globalt optimum. Detta examensarbete handlar om att undersöka hur man kan lösa båda dessa problem. Modellen är modifierad för att kombinera flera frekvenser och anpassa dem till känsligheten för olika frekvenser i det mänskliga örat. Genom att göra detta är målet ändrat från det tidigare sättet att maximera den dynamiska insatsisoleringen DIL för en specifik frekvens till att minimera den totala upplevda ljudnivån LA. Modellen bygger på den modulära designen av TMM från 4-polsteori. Detta delar upp ljuddämparen i separata delar, med ljuddämpande element som matematiskt endast definieras av vilken T matris de har. De elementtyper att välja mellan är expansionskammare, kvartsvågsresonator och Helmholtzresonator. De globala optimeringsmetoder att välja mellan är Global Search, MultiStart, Genetic Algorithm, Pattern Search och Simulated Annealing. Genom att kombinera de olika typerna av ljuddämpande element på alla sätt och lösa varje fall med varje global optimeringsmetod, blir den bästa kombinationen vald och implementerad i modellen. Valet är två kvartsvågsresonatorer som löses genom MultiStart, vilket ger tillfredsställande resultat. Ytterligare analyser görs för att säkerställa robustheten av den valda implementationen, som inte avslöjar några väsentliga brister. Syftet med detta examensarbete är uppfyllt.

The research is a study of the efficiency and robustness of genetic algorithm to instances of both discrete and continuous global optimization problems. We developed genetic algorithm based heuristics to find the global minimum to problem instances considered. In the discrete category, we considered two instances of real-world space allocation problems that arose from an academic environment in a developing country. These are the university timetabling problem and hostel space allocation problem. University timetabling represents a difficult optimization problem and finding a high quality solution is a challenging task. Many approaches, based on instances from developed countries, have been reported in the literature. However, most developing countries are yet to appreciate the deployment of heuristics and metaheuristics in handling the timetabling problem. We therefore worked on an instance from a university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling problem. We adopt a simplified bottom up approach in which timetable are build around departments. Thus a small portion of real data was used for experimental testing purposes. As with similar baseline studies in literature, we employ genetic algorithm to solve this instance and show that efficient solutions that meet stated constraints can be obtained with the metaheuristics. This thesis further focuses on an instance of university space allocation problem, namely the hostel space allocation problem. This is a new instance of the space allocation problems that has not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at the allocation of categories of students into available hostel space. This must be done without violating any hard constraints but satisfying as many soft constraints as possible and ensuring optimum space utilization. We identified some issues in the problem that helped to adapt metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first highlight an initial investigation based on genetic algorithm adapted to find a good solution within the search space of the hostel space allocation problem. Some ideas are introduced to increase the overall performance of initial results based on instance of the problem from our case study. Computational results obtained are reported to demonstrate the effectiveness of the solution approaches employed. Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to determine the best parameter values that consistently give good solutions. We noted that the genetic algorithms perform well specially, when repair strategies are incorporated. This thesis pioneers the application of metaheuristics to solve the hostel space allocation problem. It provides a baseline study of the problem based on genetic algorithms with associated test data sets. We report the best known results for the test instances. It is a known fact that many real-life problems are formulated as global optimization problems with continuous variables. On the continuous global optimization category therefore, we focus on improving the efficiency and reliability of real coded genetic algorithm for solving unconstrained global optimization, mainly through hybridization with exploratory features. Hybridization has widely been recognized as one of the most attractive approach to solving unconstrained global optimization. Literatures have shown that hybridization helps component heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We therefore derived three modified forms of real coded genetic algorithm by hybridizing the standard real-coded genetic algorithm with pattern search and vector projection. These are combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The hybridization strategy used and results obtained are reported and compared with the standard real-coded genetic algorithm. Experimental studies show that all the modified algorithms perform better than the original algorithm.

Este trabalho tem por objetivo apresentar o desenvolvimento e a implementação, em uma rotina computacional, de um algoritmo para localização de faltas em linhas de transmissão com compensação série baseado em método heurístico. O algoritmo de localização de faltas proposto neste trabalho é capaz de identificar o ponto de ocorrência da falta utilizando informações sobre os parâmetros da linha de transmissão, os sinais de tensões e correntes registrados nos terminais dessa linha, bem como as características das unidades de compensação série empregadas. O algoritmo desenvolvido no âmbito desta pesquisa foi codificado no ambiente Matrix Laboratory (MATLAB), bem como o método heurístico escolhido (pattern search) e a sua validação foi conduzida a partir de simulações computacionais utilizando modelos de rede implementados no Alternate Transient Program (ATP). / This work aims to describe the development and implementation in a computational routine, an algorithm to locate faults in series-compensated transmission lines based on an heuristic method. The fault location algorithm proposed in this work is capable of identifying the fault point using information about the parameters of the transmission line, voltages and currents signals recorded at the line terminals, as well as the characteristics of the series compensation units. The optimization method used for objective functions was pattern search. The algorithm developed during this research was coded using MATLAB, as well as the heuristic method chosen (pattern search) and its validation was based on computer simulations using network models implemented in ATP.

Este trabalho tem por objetivo apresentar o desenvolvimento e a implementação, em uma rotina computacional, de um algoritmo para localização de faltas em linhas de transmissão com compensação série baseado em método heurístico. O algoritmo de localização de faltas proposto neste trabalho é capaz de identificar o ponto de ocorrência da falta utilizando informações sobre os parâmetros da linha de transmissão, os sinais de tensões e correntes registrados nos terminais dessa linha, bem como as características das unidades de compensação série empregadas. O algoritmo desenvolvido no âmbito desta pesquisa foi codificado no ambiente Matrix Laboratory (MATLAB), bem como o método heurístico escolhido (pattern search) e a sua validação foi conduzida a partir de simulações computacionais utilizando modelos de rede implementados no Alternate Transient Program (ATP). / This work aims to describe the development and implementation in a computational routine, an algorithm to locate faults in series-compensated transmission lines based on an heuristic method. The fault location algorithm proposed in this work is capable of identifying the fault point using information about the parameters of the transmission line, voltages and currents signals recorded at the line terminals, as well as the characteristics of the series compensation units. The optimization method used for objective functions was pattern search. The algorithm developed during this research was coded using MATLAB, as well as the heuristic method chosen (pattern search) and its validation was based on computer simulations using network models implemented in ATP.

<p>Antimicrobial peptides (AMPs) play a key role in the innate immune response. They can be ubiquitously found in a wide range of eukaryotes including mammals, amphibians, insects, plants, and protozoa. In lower organisms, AMPs function merely as antibiotics by permeabilizing cell membranes and lysing invading microbes. Prediction of antimicrobial peptides is important because experimental methods used in characterizing AMPs are costly, time consuming and resource intensive and identification of AMPs in insects can serve as a template for the design of novel antibiotic. In order to fulfil this, firstly, data on antimicrobial peptides is extracted from UniProt, manually curated and stored into a centralized database called dragon antimicrobial peptide database (DAMPD). Secondly, based on the curated data, models to predict antimicrobial peptides are created using support vector machine with optimized hyperparameters. In particular, global optimization methods such as grid search, pattern search and derivative-free methods are utilised to optimize the SVM hyperparameters. These models are useful in characterizing unknown antimicrobial peptides. Finally, a webserver is created that will be used to predict antimicrobial peptides in haemotophagous insects such as Glossina morsitan and Anopheles gambiae.</p>

<p>Antimicrobial peptides (AMPs) play a key role in the innate immune response. They can be ubiquitously found in a wide range of eukaryotes including mammals, amphibians, insects, plants, and protozoa. In lower organisms, AMPs function merely as antibiotics by permeabilizing cell membranes and lysing invading microbes. Prediction of antimicrobial peptides is important because experimental methods used in characterizing AMPs are costly, time consuming and resource intensive and identification of AMPs in insects can serve as a template for the design of novel antibiotic. In order to fulfil this, firstly, data on antimicrobial peptides is extracted from UniProt, manually curated and stored into a centralized database called dragon antimicrobial peptide database (DAMPD). Secondly, based on the curated data, models to predict antimicrobial peptides are created using support vector machine with optimized hyperparameters. In particular, global optimization methods such as grid search, pattern search and derivative-free methods are utilised to optimize the SVM hyperparameters. These models are useful in characterizing unknown antimicrobial peptides. Finally, a webserver is created that will be used to predict antimicrobial peptides in haemotophagous insects such as Glossina morsitan and Anopheles gambiae.</p>

Philosophiae Doctor - PhD / Antimicrobial peptides (AMPs) play a key role in the innate immune response. They can be ubiquitously found in a wide range of eukaryotes including mammals, amphibians, insects, plants, and protozoa. In lower organisms, AMPs function merely as antibiotics by permeabilizing cell membranes and lysing invading microbes. Prediction of antimicrobial peptides is important because experimental methods used in characterizing AMPs are costly, time consuming and resource intensive and identification of AMPs in insects can serve as a template for the design of novel antibiotic. In order to fulfil this, firstly, data on antimicrobial peptides is extracted from UniProt, manually curated and stored into a centralized database called dragon antimicrobial peptide database (DAMPD). Secondly, based on the curated data, models to predict antimicrobial peptides are created using support vector machine with optimized hyperparameters. In particular, global optimization methods such as grid search, pattern search and derivative-free methods are utilised to optimize the SVM hyperparameters. These models are useful in characterizing unknown antimicrobial peptides. Finally, a webserver is created that will be used to predict antimicrobial peptides in haemotophagous insects such as Glossina morsitan and Anopheles gambiae. / South Africa

Orientador: Maria Aparecida Diniz Ehrhardt / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação / Made available in DSpace on 2018-08-22T06:10:21Z (GMT). No. of bitstreams: 1 Ferreira_DeiseGoncalves_M.pdf: 2631020 bytes, checksum: 45eb84901394375843735b1fdef599ad (MD5) Previous issue date: 2013 / Resumo: Neste trabalho voltamos nossa atenção para métodos de otimização que não fazem uso de derivadas. Dentre esses, estamos interessadas em um método de busca padrão para minimização de funções com restrições lineares. Abordamos um algoritmo proposto por Lewis e Torczon, cuja ideia geral é que o padrão deve conter direções de busca ao longo das quais iterações factíveis sejam determinadas. O algoritmo possui resultados de convergência global. Realizamos sua implementação computacional, e propomos novas estratégias de busca e atualização do tamanho do passo, além de um novo padrão de direções de busca. Realizamos testes numéricos, de modo a analisar o desempenho das estratégias propostas e comparar o desempenho do padrão de direções que introduzimos com o proposto por Lewis e Torczon / Abstract: In this work, our interest lies on derivative-free optimization methods. Among these, our aim is to study a pattern search method for linearly constrained minimization. We studied an algorithm proposed by Lewis and Torsion, whose general idea is that the pattern must contain search directions in which feasible iterations must be computed. The algorithm has global convergence results. We accomplished its computational implementation and we propose new strategies of search and updating rule for the step-length control parameter. We also propose a new pattern of search directions. We accomplished numerical experiments in order to analyze the performance of our proposals and also to compare the performance of our pattern with the one proposed by Lewis and Torczon / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Two computer programs were developed and used to determine the optimum operating parameters of a fedbatch and a continuous two-stage process for fermentation of recombinant bacteria. The study was conducted in three phases: (a) developing two computer programs for simulation and optimization of the above processes, (b) conducting batch culture fermentations to verify the performance of the biokinetic model, and (c) conducting fedbatch and two-stage continuous fermentation experiments to closely examine the simulation and optimization results. The Miao and Kompala (1992) biokinetic model was used for simulation of the bacterial growth and cloned gene expression. The Pattern-Search method, developed by Hooke and Jeeves (1962), was incorporated in the programs to determine the optimum values of the parameters. Extensive studies of the optimization results showed 30-40% higher productivities for the two stage continuous process over the fedbatch process when using the same media in both processes. In addition, increasing the number of stages in the continuous two-stage process resulted in very limited improvement in the productivity of the process (10-12%). The information from the process optimization was then used to design batch, fedbatch nd two stage continuous experiments. Recombinant <i>E. coli </i>(strain BL21DE3) with an inducible gene (sensitive to IPTG, isopropyl-â-D-thiogalactopyranoside) was used throughout the experiments. The experimental results from the fedbatch and two stage continuous processes clearly showed good agreement with the simulation and optimization results $(\cong$15% deviation). The experiments also revealed that the maintenance of plasmid harboring cells over the long-term operation could be an important barrier in achieving the predicted high productivity in the two stage continuous process. Finally, in addition to computer programs for optimization of genetically modified microorganisms, a new computer program with a generic algorithm for optimization of multiple CFSTR fermentation with any kind of biokinetic model was developed. The program was used to optimize multiple CFSTRs with the cybernetic biokinetic model for the first time. Besides finding the optimum residence times for multiple CFSTRs operation, the effect of inaccuracies in different cybernetic model parameters on the overall productivity of the process was investigated. The simulation results illustrated that, a single CFSTR was more sensitive in its operation to inaccuracies in the biokinetic constants as compared to optimized CFSTRs in series (2-8 times more sensitive).