Dissertations / Theses on the topic 'Random search'
To see the other types of publications on this topic, follow the link: Random search.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Random search.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Kapur, Nevin. "Additive functionals on random search trees." Available to US Hopkins community, 2003. http://wwwlib.umi.com/dissertations/dlnow/3080695.
Full text
2
Prudius, Andrei A. "Adaptive Random Search Methods for Simulation Optimization." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/16318.
Full textAbstract:
This thesis is concerned with identifying the best decision among a set of possible decisions in the presence of uncertainty. We are primarily interested in situations where the objective function value at any feasible solution needs to be estimated, for example via a ``black-box' simulation procedure. We develop adaptive random search methods for solving such simulation optimization problems. The methods are adaptive in the sense that they use information gathered during previous iterations to decide how simulation effort is expended in the current iteration. We consider random search because such methods assume very little about the structure of the underlying problem, and hence can be applied to solve complex simulation optimization problems with little expertise required from an end-user. Consequently, such methods are suitable for inclusion in simulation software.
We first identify desirable features that algorithms for discrete simulation optimization need to possess to exhibit attractive empirical performance. Our approach emphasizes maintaining an appropriate balance between exploration, exploitation, and estimation. We also present two new and almost surely convergent random search methods that possess these desirable features and demonstrate their empirical attractiveness.
Second, we develop two frameworks for designing adaptive and almost surely convergent random search methods for discrete simulation optimization. Our frameworks involve averaging, in that all decisions that require estimates of the objective function values at various feasible solutions are based on the averages of all observations collected at these solutions so far. We present two new and almost surely convergent variants of simulated annealing and demonstrate the empirical effectiveness of averaging and adaptivity in the context of simulated annealing.
Finally, we present three random search methods for solving simulation optimization problems with uncountable feasible regions. One of the approaches is adaptive, while the other two are based on pure random search. We provide conditions under which the three methods are convergent, both in probability and almost surely. Lastly, we include a computational study that demonstrates the effectiveness of the methods when compared to some other approaches available in the literature.
3
Lančinskas, Algirdas. "Parallelization of random search global optimization algorithms." Doctoral thesis, Lithuanian Academic Libraries Network (LABT), 2013. http://vddb.laba.lt/obj/LT-eLABa-0001:E.02~2013~D_20130620_110438-17037.
Full textAbstract:
Global optimization problems are relevant in various fields of research and industry, such as chemistry, biology, biomedicine, operational research, etc. Normally it is easier to solve optimization problems having some specific properties of objective function such as linearity, convexity, differentiability, etc. However, there are a lot of practical problems that do not satisfy such properties or even cannot be expressed in an adequate mathematical form. Therefore, it is popular to use random search optimization methods in solving such optimization problems.
The dissertation deals with investigation of random search global optimization algorithms, their parallelization and application to solve practical problems. The work is focused on modification and parallelization of particle swarm optimization and genetic algorithms.
The modification of particle swarm optimization algorithm, based on reduction of the search area is proposed, and several strategies to parallelize the algorithm are investigated. The algorithm is applied to solve Multiple Gravity Assist problem using parallel computing system.
A hybrid global multi-objective optimization algorithm is developed by modifying single agent stochastic search strategy, and incorporating it into multi-objective optimization genetic algorithm. Several strategies to parallelize multi-objective optimization genetic algorithm is proposed. Parallel algorithms are experimentally investigated by solving competitive facility location... [to full text]Optimizavimo uždaviniai sutinkami įvairiose mokslo ir pramonės srityse, tokiose kaip chemija, biologija, biomedicina, operacijų tyrimai ir pan. Paprastai efektyviausiai sprendžiami uždaviniai, turintys tam tikras savybes, tokias kaip tikslo funkcijų tiesiškumas, iškilumas, diferencijuojamumas ir pan. Tačiau ne visi praktikoje pasitaikantys optimizavimo uždaviniai tenkina šias savybes, o kartais iš vis negali būti išreiškiami adekvačia matematine išraiška. Tokiems uždaviniam spręsti yra populiarūs atsitiktinės paieškos optimizavimo metodai. Disertacijoje yra tiriami atsitiktinės paieškos optimizavimo metodai, jų lygiagretinimo galimybės ir taikymas praktikoje pasitaikantiems uždaviniams spręsti. Pagrindinis dėmesys skiriamas dalelių spiečiaus optimizavimo ir genetinių algoritmų modifikavimui ir lygiagretinimui. Disertacijoje yra siūloma dalelių spiečiaus optimizavimo algoritmo modifikacija, grįsta pieškos srities siaurinimu, ir tiriamos kelios algoritmo lygiagretinimo strategijos. Algoritmas yra taikomas erdvėlaivių skrydžių trajektorijų optimizavimo uždaviniui spręsti lygiagrečiųjų skaičiavimų sistemose. Taip pat yra siūlomas hibridinis globaliojo daugiakriterio optimizavimo algoritmas, gautas modifikuojant vieno agento stochastinės paieškos algoritmą ir įkomponuojant į daugiakriterio optimizavimo genetinį algoritmą. Siūlomos kelios daugiakriterio genetinio algoritmo lygiagretinimo strategijos. Jų pagrindu gauti lygiagretieji algoritmai eksperimentiškai tiriami sprendžiant... [toliau žr. visą tekstą]
4
Buhler, Jeremy. "Search algorithms for biosequences using random projection /." Thesis, Connect to this title online; UW restricted, 2001. http://hdl.handle.net/1773/6919.
Full text
5
Kristinsdottir, Birna Pala. "Analysis and development of random search algorithms /." Thesis, Connect to this title online; UW restricted, 1997. http://hdl.handle.net/1773/7108.
Full text
6
Holmgren, Cecilia. "Random Records and Cuttings in Binary Search Trees." Licentiate thesis, Uppsala universitet, Analys och tillämpad matematik, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-141580.
Full text
7
Bui, Hoai Thang Computer Science & Engineering Faculty of Engineering UNSW. "Guided random-walk based model checking." Awarded by:University of New South Wales. Computer Science & Engineering, 2009. http://handle.unsw.edu.au/1959.4/44829.
Full textAbstract:
The ever increasing use of computer systems in society brings emergent challenges to companies and system designers. The reliability of software and hardware can be financially critical, and lives can depend on it. The growth in size and complexity of software, and increasing concurrency, compounds the problem. The potential for errors is greater than ever before, and the stakes are higher than ever before. Formal methods, particularly model checking, is an approach that attempts to prove mathematically that a model of the behaviour of a product is correct with respect to certain properties. Certain errors can therefore be proven never to occur in the model. This approach has tremendous potential in system development to provide guarantees of correctness. Unfortunately, in practice, model checking cannot handle the enormous sizes of the models of real-world systems. The reason is that the approach requires an exhaustive search of the model to be conducted. While there are exceptions, in general model checkers are said not to scale well. In this thesis, we deal with this scaling issue by using a guiding technique that avoids searching areas of the model, which are unlikely to contain errors. This technique is based on a process of model abstraction in which a new, much smaller model is generated that retains certain important model information but discards the rest. This new model is called a heuristic. While model checking using a heuristic as a guide can be extremely effective, in the worst case (when the guide is of no help), it performs the same as exhaustive search, and hence it also does not scale well in all cases. A second technique is employed to deal with the scaling issue. This technique is based on the concept of random walks. A random walk is simply a `walk' through the model of the system, carried out by selecting states in the model randomly. Such a walk may encounter an error, or it may not. It is a non-exhaustive technique in the sense that only a manageable number of walks are carried out before the search is terminated. This technique cannot replace the conventional model checking as it can never guarantee the correctness of a model. It can however, be a very useful debugging tool because it scales well. From this point of view, it relieves the system designer from the difficult task of dealing with the problem of size in model checking. Using random walks, the effort goes instead into looking for errors. The effectiveness of model checking can be greatly enhanced if the above two techniques are combined: a random walk is used to search for errors, but the walk is guided by a heuristic. This in a nutshell is the focus of this work. We should emphasise that the random walk approach uses the same formal model as model checking. Furthermore, the same heuristic technique is used to guide the random walk as a guided model checker. Together, guidance and random walks are shown in this work to result in vastly improved performance over conventional model checking. Verification has been sacrificed of course, but the new technique is able to find errors far more quickly, and deal with much larger models.
8
Yu, Wei, and 余韡. "Reverse Top-k search using random walk with restart." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hdl.handle.net/10722/197515.
Full textAbstract:
With the increasing popularity of social networking applications, large volumes of graph data are becoming available. Large graphs are also derived by structure extraction from relational, text, or scientific data (e.g., relational tuple networks, citation graphs, ontology networks, protein-protein interaction graphs). Nodeto-node proximity is the key building block for many graph based applications that search or analyze the data. Among various proximity measures, random walk with restart (RWR) is widely adapted because of its ability to consider the global structure of the whole network.
Although RWR-based similarity search has been well studied before, there is no prior work on reverse top-k proximity search in graphs based on RWR. We discuss the applicability of this query and show that the direct application of existing methods on RWR-based similarity search to solve reverse top-k queries has very high computational and storage demands. To address this issue, we propose an indexing technique, paired with an on-line reverse top-k search algorithm.
In the indexing step, we compute from the graph G a graph index, which is based on a K X |V| matrix, containing in each column v the K largest approximate proximity values from v to any other node in G. K is application-dependent and represents the highest value of k in a practical reverse top-k query. At each column v of the index, the approximate values are lower bounds of the K largest proximity values from v to all other nodes.
Given the graph index and a reverse top-k query q (k _ K), we prove that the exact proximities from any node v to query q can be efficiently computed by applying the power method. By comparing these with the corresponding lower bounds taken from the k-th row of the graph index, we are able to determine which nodes are certainly not in the reverse top-k result of q. For some of the remaining nodes, we may also be able to determine that they are certainly in the reverse top-k result of q, based on derived upper bounds for the k-th largest proximity value from them. Finally, for any candidate that remains, we progressively refine its approximate proximities, until based on its lower or upper bound it can be determined not to be or to be in the result. The proximities refined during a reverse top-k are used to update the graph index, making its values progressively more accurate for future queries.
Our experimental evaluation shows that our technique is efficient and has manageable storage requirements even when applied on very large graphs. We also show the effectiveness of the reverse top-k search in the scenarios of spam detection and determining the popularity of authors.published_or_final_version
Computer Science
Master
Master of Philosophy
9
Serrano, Bermejo Guillermo (Will). "Internet search assistant based on the random neural network." Thesis, Imperial College London, 2017. http://hdl.handle.net/10044/1/61781.
Full textAbstract:
Web users can not be guaranteed that the results provided by Web search engines or recommender systems are either exhaustive or relevant to their search needs. Businesses have the commercial interest to rank higher on results or recommendations to attract more customers while Web search engines and recommender systems make their profit based on their advertisements. This research analyses the result rank relevance provided by the different Web search engines, metasearch engines, academic databases and recommender systems. We propose an Intelligent Search Assistant (ISA) that addresses these issues from the perspective of end-users acting as an interface between users and the different search engines; it emulates a Web Search Recommender System for general topic queries where the user explores the results provided. Our ISA sends the original query, retrieves the provided options from the Web and reorders the results. The proposed mathematical model of our ISA divides a user query into a multidimensional term vector. Our ISA is based on the Random Neural Network with Deep Learning Clusters. The potential value of each neuron or cluster is calculated by applying our innovative cost function to each snippet and weighting its dimension terms with different relevance parameters. Our ISA adapts to the perceived user interest learning user relevance on an iterative process where the user evaluates directly the listed results. Gradient Descent and Reinforcement Learning are used independently to update the Random Neural Network weights and we evaluate their performance based on the learning speed and result relevance. Finally, we present a new relevance metric which combines relevance and rank. We use this metric to validate and assess the learning performance of our proposed algorithm against other search engines. In some situations, our ISA and its iterative learning outperforms other search engines and recommender systems.
10
Owen, David R. "Random search of AND-OR graphs representing finite-state models." Morgantown, W. Va. : [West Virginia University Libraries], 2002. http://etd.wvu.edu/templates/showETD.cfm?recnum=2317.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2002.Title from document title page. Document formatted into pages; contains vi, 96 p. : ill. Includes abstract. Includes bibliographical references (p. 91-96).
11
Tejedor, Vincent. "Random walks and first-passage properties : trajectory analysis and search optimization." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2012. http://tel.archives-ouvertes.fr/tel-00721294.
Full textAbstract:
Les propriétés de premier passage en général, et parmi elles le temps moyen de premier passage (MFPT), sont fréquemment utilisées dans les processus limités par la diffusion. Les processus réels de diffusion ne sont pas toujours Browniens : durant les dernières années, les comportements non-Browniens ont été observés dans un nombre toujours croissant de systèmes. Les milieux biologiques sont un exemple frappant où ce genre ce comportement a été observé de façon répétée. Nous présentons dans ce manuscrit une méthode basée sur les propriétés de premier passage permettant d'obtenir des informations sur le processus réel de diffusion, ainsi que sur l'environnement où évolue le marcheur aléatoire. Cette méthode permet de distinguer trois causes possibles de sous-diffusion : les marches aléatoires en temps continu, la diffusion en milieu fractal et le mouvement brownien fractionnaire. Nous étudions également l'efficacité des processus de recherche sur des réseaux discrets. Nous montrons comment obtenir les propriétés de premier passage sur réseau afin d'optimiser ensuite le processus de recherche, et obtenons un encadrement général du temps moyen de premier passage global (GMFPT). Grâce à ces résultats, nous estimons l'impact sur l'efficacité de recherche de plusieurs paramtres, notamment la connectivité de la cible, la mobilité de la cible ou la topologie du réseau.
12
Goudjil, Amar. "Data structures, binary search trees : a study of random Weyl trees." Thesis, McGill University, 1998. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=21559.
Full textAbstract:
This thesis covers the study of a particular class of binary search trees, the Weyl trees formed by consecutive insertion of numbers {theta}, {2theta}, {3theta}, ..., where theta is an irrational number from (0,1), and {x} denotes the fractional part of x. Various properties of the structure of these trees are explored and a relationship with the continued fraction expansion of theta is shown. Among these properties, an approximation of the height Hn of a Weyl tree with n nodes is given when theta is chosen at random and uniformly on (0, 1). The main result of this work is that in probability, Hn ∼ (12/pi2) log n log log n.
13
Goudjil, Amar. "Data structures, binary search trees, a study of random Weyl trees." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0026/MQ50778.pdf.
Full text
14
Rachakonda, Ravi Kanth. "Crew rostering problem a random key genetic algorithm with local search /." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1230931714.
Full text
15
Rachakonda, Ravi Kanth. "Crew Rostering Problem: A Random Key Genetic Algorithm With Local Search." The Ohio State University, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=osu1230931714.
Full text
16
Anilkumar, A. K. "Application Of Controlled Random Search Optimization Technique In MMLE With Process Noise." Thesis, Indian Institute of Science, 2000. http://hdl.handle.net/2005/232.
Full textAbstract:
Generally in most of the applications of estimation theory using the Method of Maximum Likelihood Estimation (MMLE) to dynamical systems one deals with a situation where only the measurement noise alone is present. However in many present day applications where modeling errors and random state noise input conditions occur it has become necessary for MMLE to handle measurement noise as well as process noise. The numerical algorithms accounting for both measurement and process noise require significantly an order of magnitude higher computer time and memory. Further more, implementation difficulties and convergence problems are often encountered. Here one has to estimate the quantities namely, the initial state error covariance matrix Po, measurement noise covariance matrix R, the process noise covariance matrix Q and the system parameter 0 and the present work deals with the above.
Since the above problem is fairly involved we need to have a good reference solution. For this purpose we utilize the approach and results of Gemson who considered the above problem via the extended Kalman filter (EKF) route to compare the present results from the MMLE route. The EKF uses the unknown parameters as additional states unlike in MMLE which uses only the system states.
Chapter 1 provides a brief historical perspective followed by parameter identification in the presence of process and measurement noises. The earlier formulations such as natural, innovation, combined, and adaptive approaches are discussed.
Chapter 2 deals with the heuristic adaptive tuning of the Kalman filter parameters for the matrices Q and R by Myers and Tapley originally developed for state estimation problems involving satellite orbit estimation. It turns out that for parameter estimation problems apart from the above matrices even the choice of the initial covariance matrix Po is crucial for obtaining proper parameter estimates with a finite amount of data and for this purpose the inverse of the information matrix for Po is used. This is followed by a description of the original Controlled Random Search (CRS) of Price and its variant as implemented and used in the present work to estimate or tune Q, R, and 0 which is the aim of the present work. The above help the reader to appreciate the setting under which the present study has been carried out.
Chapter 3 presents the results and the analysis of the estimation procedure adopted with respect to a specific case study of the lateral dynamics of an aircraft involving 15 unknown parameters. The reference results for the present work are the ones based on the approach of Gemson and Ananthasayanam (1998). The present work proceeds in two phases. In the first case (i) the EKF estimates for Po, Q, and R are used to obtain 0 and in the second case (ii) the estimate of Po and Q together with a reasonable choice of R are utilized to obtain 0 from the CRS algorithm. Thus one is able to assess the capability of the CRS to estimate only the unknown parameters.
The next Chapter 4 presents the results of utilizing the CRS algorithm with R based on a reasonable choice and for Po from the inverse of the information matrix to estimate both Q and 0. This brings out the efficiency of MMLE with CRS algorithm in the estimation of unknown process noise characteristics and unknown parameters. Thus it demonstratesthofcdifficult Q can be estimated using CRS technique without the attendant difficulties of the earlier MMLE formulations in dealing with process noise.
Chapter 5 discusses the - implementation of CRS to estimate the unknown measurement noise covariance matrix R together with the unknown 0 by utilizing the values of Po and Q obtained through EKF route. The effect of variation of R in the parameter estimation procedure is also highlighted in This Chapter. This Chapter explores the importance of Po in the estimation procedure. It establishes the importance of Po though most of the earlier works do not appear to have recognized such a feature. It turned out that the CRS algorithm does not converge when some arbitrary value of Po is chosen. It has to be necessarily obtained from a scouting pass of the EKF. Some sensitivity studies based on variations of Po shows its importance. Further studies shows the sequence of updates, the random nature of process and measurement noise effects, the deterministic nature of the parameter, play a critical role in the convergence of the algorithm.
The last Chapter 6 presents the conclusions from the present work and suggestions for further work.
17
Xie, Jing, and 謝靜. "Socio-aware random walk search and replication in peer-to-peer networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B43085556.
Full text
18
Xie, Jing. "Socio-aware random walk search and replication in peer-to-peer networks." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B43085556.
Full text
19
Weinig, Walter Theodore 1960. "Calibration of the soil moisture accounting model using the adaptive random search algorithm." Thesis, The University of Arizona, 1991. http://hdl.handle.net/10150/192059.
Full textAbstract:
Random search techniques are being applied to a variety of non-linear parameter estimation problems. Random search for global optimization has the potential to overcome many of the problems associated with direct or pattern search techniques. In this research, an adaptive random search algorithm was applied to a conceptual rainfall-runoff model to study the efficiency of the algorithm in locating an optimum set of model parameters. The goal of the study was to determine how changes in internal algorithm control variables and objective functions affected the efficiency of the algorithm. Results indicated that the value of internal control variables did not have a strong influence on algorithm efficiency. Neither objective function gave demonstrably better results in calibration runs. Variability in results due to the random number seed was observed. Recommendations for further research are presented.
20
Jordanov, Dimitar Dimitrov. "Similarity Search in Document Collections." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236746.
Full textAbstract:
Hlavním cílem této práce je odhadnout výkonnost volně šířeni balík Sémantický Vektory a třída MoreLikeThis z balíku Apache Lucene. Tato práce nabízí porovnání těchto dvou přístupů a zavádí metody, které mohou vést ke zlepšení kvality vyhledávání.
21
Armour, Arthur David 1964. "Adaptive random search evaluated as a method for calibration of the SMA-NWSFS model." Thesis, The University of Arizona, 1990. http://hdl.handle.net/10150/278394.
Full textAbstract:
Random search methods are becoming more widely used to estimate model parameters. Their ability to globally search a parameter space makes them attractive for solving problems that have multi-local optima, as are non-linear hydrologic models such as Conceptual Rainfall-Runoff (CRR) models. The investigation of this thesis is on the ability of the Adaptive Random Search (ARS) to find the global optimum of the CRR model known as the Soil Moisture Accounting Model of the National Weather Service River Forecast System (SMA-NWSRFS) and compares its performance to that of the Uniform Random Search (URS). Research results indicate that, although the ARS was slightly more efficient than the URS, neither strategy demonstrated an ability to converge to the globally optimum parameter set. Factors which inhibit the convergence include model structure characteristics and an insufficient number of points searched. Ways for random search techniques to identify and address these problems are discussed.
22
Mattis, Joseph P. "The application of random search theory to the detection of tactical ballistic missile launchers." Thesis, Monterey, California. Naval Postgraduate School, 1993. http://hdl.handle.net/10945/26889.
Full textAbstract:
The search for Tactical Ballistic Missile (TBM) launchers is modeled mathematically using the Random Search Model. Special provisions are made in the model to account for the fact that the launcher is not always exposed to detection by the searcher. The probability that the launcher is exposed to detection is assumed to be both deterministic and stochastic. The tactical implications of the results of the model are discussed and several methods are provided to improve search performance based on an analysis of the model parameters
23
Горячев, Олексій Євгенійович, Алексей Евгеньевич Горячев, Oleksii Yevheniiovych Horiachev, and I. B. I. B. Moschna. "Solution of Сombinatorial Problems by the Method of Random Search Based on Factorial Numbers." Thesis, Sumy State University, 2018. http://essuir.sumdu.edu.ua/handle/123456789/67951.
Full textAbstract:
Permutations are widely used in solving many combinatorial problems [1]. Permutations are an ordered set of different elements, each of which is represented by a number. In the course of solving a combinatorial problem, it is usually necessary to search through all the permutations with a certain number of elements. Each of the permutations will participate in the calculation of one of the possible solutions to the problem. Then the most effective solution will be chosen according to a predetermined criterion.
24
Kim, Kangmin. "Approximating the Poisson Scan and (A-0) Acoustic Detection model with a random search formula." Thesis, Monterey, California : Naval Postgraduate School, 2009. http://edocs.nps.edu/npspubs/scholarly/theses/2009/Dec/09Dec%5FKim%5FKangmin.pdf.
Full textAbstract:
Thesis (M.S. in Operations Analysis)--Naval Postgraduate School, December 2009.Thesis Advisor(s): Eagle, James N. ; Lee, Sang Heon. Second Reader: Chung, Timothy H. "December 2009." Description based on title screen as viewed on January 27, 2010. Author(s) subject terms: Random Search, Poisson Scan model, (A-0) model, Search and Detection, MATLAB Simulation. Includes bibliographical references (p. 45). Also available in print.
25
Long, Shun. "Adaptive Java optimisation using machine learning techniques." Thesis, University of Edinburgh, 2004. http://hdl.handle.net/1842/567.
Full textAbstract:
There is a continuing demand for higher performance, particularly in the area of scientific and engineering computation. In order to achieve high performance in the context of frequent hardware upgrading, software must be adaptable for portable performance. What is required is an optimising compiler that evolves and adapts itself to environmental change without sacrificing performance. Java has emerged as a dominant programming language widely used in a variety of application areas. However, its architectural independant design means that it is frequently unable to deliver high performance especially when compared to other imperative languages such as Fortran and C/C++. This thesis presents a language- and architecture-independant approach to achieve portable high performance. It uses the mapping notation introduced in the Unified Transformation Framework to specify a large optimisation space. A heuristic random search algorithm is introduced to explore this space in a feedback-directed iterative optimisation manner. It is then extended using a machine learning approach which enables the compiler to learn from its previous optimisations and apply the knowledge when necessary. Both the heuristic random search algorithm and the learning optimisation approach are implemented in a prototype Adaptive Optimisation Framework for Java (AOF-Java). The experimental results show that the heuristic random search algorithm can find, within a relatively small number of atttempts, good points in the large optimisation space. In addition, the learning optimisation approach is capable of finding good transformations for a given program from its prior experience with other programs.
26
Ilchenko, Alexey. "An approach to Graph Isomorphism using Spanning Trees generated by Breadth First Search." Case Western Reserve University School of Graduate Studies / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=case1405079402.
Full text
27
Robertson, Blair Lennon. "Direct Search Methods for Nonsmooth Problems using Global Optimization Techniques." Thesis, University of Canterbury. Mathematics and Statistics, 2010. http://hdl.handle.net/10092/5060.
Full textAbstract:
This thesis considers the practical problem of constrained and unconstrained local optimization. This subject has been well studied when the objective function f is assumed to smooth. However, nonsmooth problems occur naturally and frequently in practice. Here f is assumed to be nonsmooth or discontinuous without forcing smoothness assumptions near, or at, a potential solution. Various methods have been
presented by others to solve nonsmooth optimization problems, however only partial convergence results are possible for these methods.
In this thesis, an optimization method which use a series of local and localized global optimization phases is proposed. The local phase searches for a local minimum
and gives the methods numerical performance on parts of f which are smooth. The localized global phase exhaustively searches for points of descent in a neighborhood of cluster points. It is the localized global phase which provides strong theoretical convergence results on nonsmooth problems.
Algorithms are presented for solving bound constrained, unconstrained and constrained nonlinear nonsmooth optimization problems. These algorithms use direct search methods in the local phase as they can be applied directly to nonsmooth problems because gradients are not explicitly required. The localized global optimization phase uses a new partitioning random search algorithm to direct random sampling into promising subsets of ℝⁿ. The partition is formed using classification and regression trees (CART) from statistical pattern recognition. The CART partition defines desirable subsets where f is relatively low, based on previous sampling, from which further samples are drawn directly. For each algorithm, convergence to an essential local minimizer of f is demonstrated under mild conditions. That is, a point x* for which the set of all feasible points with lower f values has Lebesgue measure zero for all sufficiently small neighborhoods of x*. Stopping rules are derived for each algorithm giving practical convergence to estimates of essential local minimizers. Numerical results are presented on a range of nonsmooth test problems for 2 to 10 dimensions showing the methods are effective in practice.
28
Ceroni, Ruben. "Previsione di agenti inquinanti mediante reti neurali e ottimizzazione degli iperparametri attraverso random search con Hyperas." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16833/.
Full text
29
Hu, Liujia. "Convergent algorithms in simulation optimization." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/54883.
Full textAbstract:
It is frequently the case that deterministic optimization models could be made more practical by explicitly incorporating uncertainty. The resulting stochastic optimization problems are in general more difficult to solve than their deterministic counterparts, because the objective function cannot be evaluated exactly and/or because there is no explicit relation between the objective function and the corresponding decision variables. This thesis develops random search algorithms for solving optimization problems with continuous decision variables when the objective function values can be estimated with some noise via simulation. Our algorithms will maintain a set of sampled solutions, and use simulation results at these solutions to guide the search for better solutions. In the first part of the thesis, we propose an Adaptive Search with Resampling and Discarding (ASRD) approach for solving continuous stochastic optimization problems. Our ASRD approach is a framework for designing provably convergent algorithms that are adaptive both in seeking new solutions and in keeping or discarding already sampled solutions. The framework is an improvement over the Adaptive Search with Resampling (ASR) method of Andradottir and Prudius in that it spends less effort on inferior solutions (the ASR method does not discard already sampled solutions). We present conditions under which the ASRD method is convergent almost surely and carry out numerical studies aimed at comparing the algorithms. Moreover, we show that whether it is beneficial to resample or not depends on the problem, and analyze when resampling is desirable. Our numerical results show that the ASRD approach makes substantial improvements on ASR, especially for difficult problems with large numbers of local optima. In traditional simulation optimization problems, noise is only involved in the objective functions. However, many real world problems involve stochastic constraints. Such problems are more difficult to solve because of the added uncertainty about feasibility. The second part of the thesis presents an Adaptive Search with Discarding and Penalization (ASDP) method for solving continuous simulation optimization problems involving stochastic constraints. Rather than addressing feasibility separately, ASDP utilizes the penalty function method from deterministic optimization to convert the original problem into a series of simulation optimization problems without stochastic constraints. We present conditions under which the ASDP algorithm converges almost surely from inside the feasible region, and under which it converges to the optimal solution but without feasibility guarantee. We also conduct numerical studies aimed at assessing the efficiency and tradeoff under the two different convergence modes. Finally, in the third part of the thesis, we propose a random search method named Gaussian Search with Resampling and Discarding (GSRD) for solving simulation optimization problems with continuous decision spaces. The method combines the ASRD framework with a sampling distribution based on a Gaussian process that not only utilizes the current best estimate of the optimal solution but also learns from past sampled solutions and their objective function observations. We prove that our GSRD algorithm converges almost surely, and carry out numerical studies aimed at studying the effects of utilizing the Gaussian sampling strategy. Our numerical results show that the GSRD framework performs well when the underlying objective function is multi-modal. However, it takes much longer to sample solutions, especially in higher dimensions.
30
Mehrmand, Arash. "A Factorial Experiment on Scalability of Search-based Software Testing." Thesis, Blekinge Tekniska Högskola, Sektionen för datavetenskap och kommunikation, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-4224.
Full textAbstract:
Software testing is an expensive process, which is vital in the industry. Construction of the test-data in software testing requires the major cost and knowing which method to use in order to generate the test data is very important. This paper discusses the performance of search-based algorithms (preferably genetic algorithm) versus random testing, in software test-data generation. A factorial experiment is designed so that, we have more than one factor for each experiment we make. Although many researches have been done in the area of automated software testing, this research differs from all of them due to sample programs (SUTs) which are used. Since the program generation is automatic as well, Grammatical Evolution is used to guide the program generations. They are not goal based, but generated according to the grammar we provide, with different levels of complexity. Genetic algorithm is first applied to programs, then we apply random testing. Based on the results which come up, this paper recommends one method to use for software testing, if the SUT has the same conditions as we had in this study. SUTs are not like the sample programs, provided by other studies since they are generated using a grammar.
31
Liljeqvist, Sandra. "Named Entity Recognition for Search Queries in the Music Domain." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-193332.
Full textAbstract:
This thesis addresses the problem of named entity recognition (NER) in music-related search queries. NER is the task of identifying keywords in text and classifying them into predefined categories. Previous work in the field has mainly focused on longer documents of editorial texts. However, in recent years, the application of NER for queries has attracted increased attention. This task is, however, acknowledged to be challenging due to queries being short, ungrammatical and containing minimal linguistic context. The usage of NER for queries is especially useful for the implementation of natural language queries in domain-specific search applications. These applications are often backed by a database, where the query format otherwise is restricted to keyword search or the usage of a formal query language. In this thesis, two techniques for NER for music-related queries are evaluated; a conditional random field based solution and a probabilistic solution based on context words. As a baseline, the most elementary implementation of NER, commonly applied on editorial text, is used. Both of the evaluated approaches outperform the baseline and demonstrate an overall F1 score of 79.2% and 63.4% respectively. The experimental results show a high precision for the probabilistic approach and the conditional random field based solution demonstrates an F1 score comparable to previous studies from other domains.Denna avhandling redogör för identifiering av namngivna enheter i musikrelaterade sökfrågor. Identifiering av namngivna enheter innebär att extrahera nyckelord från text och att klassificera dessa till någon av ett antal förbestämda kategorier. Tidigare forskning kring ämnet har framför allt fokuserat på längre redaktionella dokument. Däremot har intresset för tillämpningar på sökfrågor ökat de senaste åren. Detta anses vara ett svårt problem då sökfrågor i allmänhet är korta, grammatiskt inkorrekta och innehåller minimal språklig kontext. Identifiering av namngivna enheter är framför allt användbart för domänspecifika sökapplikationer där målet är att kunna tolka sökfrågor skrivna med naturligt språk. Dessa applikationer baseras ofta på en databas där formatet på sökfrågorna annars är begränsat till att enbart använda nyckelord eller användande av ett formellt frågespråk. I denna avhandling har två tekniker för identifiering av namngivna enheter för musikrelaterade sökfrågor undersökts; en metod baserad på villkorliga slumpfält (eng. conditional random field) och en probabilistisk metod baserad på kontextord. Som baslinje har den mest grundläggande implementationen, som vanligtvis används för redaktionella texter, valts. De båda utvärderade metoderna presterar bättre än baslinjen och ges ett F1-värde på 79,2% respektive 63,4%. De experimentella resultaten visar en hög precision för den probabilistiska implementationen och metoden ba- serad på villkorliga slumpfält visar på resultat på en nivå jämförbar med tidigare studier inom andra domäner.
32
Lamborn, Peter C. "January : search based On social insect behavior /." Diss., CLICK HERE for online access, 2005. http://contentdm.lib.byu.edu/ETD/image/etd801.pdf.
Full text
33
Botezat, Petru-Sorin. "File d'attente et généalogies d'un processus de branchement." Paris 11, 2002. http://www.theses.fr/2002PA112157.
Full textAbstract:
On étudie une version d'une correspondance, mise en évidence par Kendall, entre processus de branchement et marches aléatoires. Le Gall et Le Jan l'ont généralisée pour étendre la construction du serpent brownien à des superprocessus à mécanisme de branchement plus général que celui quadratique. Sous des hypothèses encore plus générales, on exhibe une bijection qui transporte les arbres aléatoires marqués, associés à la généalogie d'un processus de branchement, sur les trajectoires d'une file d'attente et qui envoie la loi gouvernant l'histoire de la population sur la loi de la file. Les individus de la population étudiée portent deux marques: le type et la longueur de vie. Les fils de u, conditionné par rapport aux individus qui ne sont pas dans la descendance de u, naissent après des temps exponentiels et portent des marques indépendantes et identiquement distribuées, les lois conditionnelles ne dépendant que du type des ancêtres de u. La file d'attente est obtenue par une exploration déterministe d'abord en profondeur de la généalogie de la population. Cette file est un objet plus général que les processus de Lévy à sauts positifs. Ses propriétés peuvent être étudiées en s'appuyant entièrement sur les propriétés des arbres. Ainsi on montre comment la propriété de Markov de la file d'attente dérive de la propriété de branchement le long d'une branche de l'arbre aléatoire. Pour cela, on remplace le temps réel par un paramètre (branche) plus proche de la généalogie de l'arbre. On prouve la propriété de Markov forte pour la file d'attente dans les nouvelles coordonnées. La propriété de Markov forte en temps réel en découle, les temps optionnels étant des branches optionnelles. Cette technique exige une analyse très fine des rapports s'établissant entre le temps réel qui indexe la file d'attente et la structure généalogique de l'arbre aléatoire sous-jacentWe study a version of the correspondence between branching processes and random walks, that was discovered by Kendall. Le Gall and Le Jan generalized it in order to extend the brownian snake towards superprocesses with more general branching mechanism than the quadratic one. We establish, in more general hypothesis, a deterministic one-to-one map between the labelled random trees describing the genealogy of a branching process and the paths of a queue; this map transports the law which controls the history of the population in the law of the queue. The individuals in the population we study are labelled by their type and longevity. If one conditions with respect to the individuals not in the u's progeny, then u gives birth at exponential times to children bearing independent and identically distributed labels, the conditional laws depending only upon the type of u's ancestry. The queue is obtained via a deterministic depth first exploration of the genealogy of the population. This queue is a more general object than a Lévy process with no negative jumps. Its properties may be studied with the only aid of the corresponding properties of the trees. Thus, we show how the branching property of the tree along branches yields the Markov property of the queue. In this regard, we replace the time with a parameter (the branch) close to the genealogy of the tree and we prove the strong Markov property of the queue in these new coordinates. From this one gets the strong Markov property in real time, because optional times are optional branches. This technique requires a detailed analysis of the relations between the real time indexing the queue and the genealogical structure of the associated random tree
34
Leith, Jason. "The Facilitation of Protein-DNA Search and Recognition by Multiple Modes of Binding." Thesis, Harvard University, 2012. http://dissertations.umi.com/gsas.harvard:10067.
Full textAbstract:
The studies discussed in this thesis unify experimental and theoretical techniques, both established and novel, in investigating the problem of how a protein that binds specific sites on DNA translocates to, recognizes, and stably binds to its target site or sites. The thesis is organized into two parts. Part I outlines the history of the problem and the theory and experiments that have addressed the problem and presents an apparent incompatibility between efficient search and stable, specific binding. To address this problem, we elaborate a model of protein-DNA interaction in which the protein may bind DNA in either a search (S) mode or a recognition (R) mode. The former is characterized by zero or weak sequence-dependence in the binding energy, while the latter is highly sequence-dependent. The protein undergoes a random walk along the DNA in the S mode, and if it encounters its target site, must undergo a conformational transition into the R mode. The model resolves the apparent paradox, and accounts for the observed speed, specificity, and stability in protein-DNA interactions. The model shows internal agreement as regards theoretical and simulated results, as well as external agreement with experimental measurements. Part II reports on research that has tested the applicability of the two-mode model to the tumor suppressor transcription factor p53. It describes in greater depth the experimental techniques and findings up to the present work, and introduces the techniques and biological system used in our research. We employ single-molecule optical microscopy in two projects to study the diffusional kinetics of p53 on DNA. The first project measures the diffusion coefficient of p53 and determines that the protein satisfies a number of requirements for the validity of the two-mode model and for efficient target localization. The second project examines the sequence-dependence in p53's sliding kinetics, and explicitly models the energy landscape it experiences on DNA and relates features of the landscape to observed local variation in diffusion coefficient. The thesis closes with proposed extensions and complements to the projects, and a discussion of the implications of our work and its relation to recent developments in the field.
35
Tejedor, Vincent [Verfasser], Ralf [Akademischer Betreuer] Metzler, and Friedrich C. [Akademischer Betreuer] Simmel. "Random walks and first-passage properties : Trajectory analysis and search optimization / Vincent Tejedor. Gutachter: Friedrich C. Simmel. Betreuer: Ralf Metzler." München : Universitätsbibliothek der TU München, 2012. http://d-nb.info/1024964191/34.
Full text
36
Madrigali, Andrea. "Analysis of Local Search Methods for 3D Data." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2016.
Find full textAbstract:
In questa tesi sono stati analizzati alcuni metodi di ricerca per dati 3D. Viene illustrata una panoramica generale sul campo della Computer Vision, sullo stato dell’arte dei sensori per l’acquisizione e su alcuni dei formati utilizzati per la descrizione di dati 3D. In seguito è stato fatto un approfondimento sulla 3D Object Recognition dove, oltre ad essere descritto l’intero processo di matching tra Local Features, è stata fatta una focalizzazione sulla fase di detection dei punti salienti. In particolare è stato analizzato un Learned Keypoint detector, basato su tecniche di apprendimento di machine learning. Quest ultimo viene illustrato con l’implementazione di due algoritmi di ricerca di vicini: uno esauriente (K-d tree) e uno approssimato (Radial Search). Sono state riportate infine alcune valutazioni sperimentali in termini di efficienza e velocità del detector implementato con diversi metodi di ricerca, mostrando l’effettivo miglioramento di performance senza una considerabile perdita di accuratezza con la ricerca approssimata.
37
Amor, Tatiana María Alonso. "Characterizing and modeling visual persistence, search strategies and fixation times." reponame:Repositório Institucional da UFC, 2017. http://www.repositorio.ufc.br/handle/riufc/22495.
Full textAbstract:
AMOR, T. M. A. Characterizing and modeling visual persistence, search strategies and fixation times. 2017. 114 f. Tese (Doutorado em Física) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017.Submitted by Pós-Graduação em Física (posgrad@fisica.ufc.br) on 2017-04-05T18:55:10Z No. of bitstreams: 1 11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5)
Rejected by Giordana Silva (giordana.nascimento@gmail.com), reason: Boa tarde Ana cleide, Fiz algumas alterações. Só não consegui deletar o arquivo anexado a fim de renomeá-lo. Isto porque o arquivo,conforme as orientações daquele guia, deverá ter a seguimte nomenclatura: 2017_tese_tmaamor O co-orientador é aquele que está no registro? Pergunto isso porque procurei o nome no trabalho e não localizei. Estou concluindo o manual e já lhe envio. on 2017-04-05T19:39:41Z (GMT)
Submitted by Pós-Graduação em Física (posgrad@fisica.ufc.br) on 2017-04-07T16:49:43Z No. of bitstreams: 1 11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5)
Approved for entry into archive by Giordana Silva (giordana.nascimento@gmail.com) on 2017-04-07T18:13:24Z (GMT) No. of bitstreams: 1 11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5)
Made available in DSpace on 2017-04-07T18:13:24Z (GMT). No. of bitstreams: 1 11 TESE - TATIANA MARIA ALONSO AMOR.pdf: 24328367 bytes, checksum: bd1f8abe088f435a872eae56fc9eede0 (MD5) Previous issue date: 2017
To gather information from the world around us, we move our eyes constantly. In different occasions we find ourselves performing visual searches, such as trying to find someone in a crowd or a book in a shelf. While searching, our eyes “jump” from one location to another giving rise to a wide repertoire of patterns, exhibiting distinctive persistent behaviors. Initially, by focusing on saccadic directions and intersaccadic angles, we disclose that the probability distributions of these measures show a clear preference of participants towards a reading-like mechanism (geometrical persistence), whose features and potential advantages for searching/foraging are discussed.We then perform a Multifractal Detrended Fluctuation Analysis (MF-DFA) over the time series of jump magnitudes in the eye trajectory and find that it exhibits a typical multifractal behavior arising from the sequential combination of saccades and fixations. By inspecting the time series composed of only fixational movements, our results reveal instead a monofractal behavior with a Hurst exponent H ∼ 0.7, which indicates the presence of long-range power-law positive correlations (statistical persistence). Motivated by the experimental findings from the study of the distribution of the intersaccadic angles, we developed a simple visual search model that quantifies the wide variety of possible search strategies. From our experiments we know that when searching a target within an image our brain can adopt different strategies. The question then is which one does it choose? We present a simple two-parameter visual search model (VSM) based on a persistent random walk and the experimental inter-saccadic angle distribution. The model captures the basic observed visual search strategies that range from systematic or reading-like to completely random. We compare the results of the model to the experimental data by measuring the space-filling efficiency of the searches. Within the parameter space of the model, we are able to quantify the strategies used by different individuals for three searching tasks and show how the average search strategy changes along these three groups. Even though participants tend to explore a vast range of parameters, when all the items are placed on a regular lattice, participants are more likely to perform a systematic search, whereas in a more complex field, the search trajectories resemble a random walk. In this way we can discern with high sensitivity the relation between the visual landscape and the average strategy, disclosing how small variations in the image induce strategy changes. Finally, we move beyond visual search and study the fixation time distributions across different visual tasks. Fixation times are commonly associated to some cognitive process, as it is in this instances where most of the visual information is gathered. However, the distribution for the fixation durations exhibits certain similarities across a wide range of visual tasks and foveated species. We studied how similar these distributions are, and found that, even though they share some common properties, such as similar mean values, most of them are statistically different. Because fixations durations can be controlled by two different mechanisms: cognitive or ocular, we focus our research into finding a model for the fixation times distribution flexible enough to capture the observed behaviors in experiments that tested these concepts. At the same time, the candidate function to model the distribution needs to be the response of some very robust inner mechanism found in all the aforementioned scenarios. Hence, we discuss the idea of a model based on the microsacaddic inter event time statistics, resulting in the sum of Gamma distributions, each of these related to the presence of a distinctive number of microsaccades in a fixation.
To gather information from the world around us, we move our eyes constantly. In different occasions we find ourselves performing visual searches, such as trying to find someone in a crowd or a book in a shelf. While searching, our eyes “jump” from one location to another giving rise to a wide repertoire of patterns, exhibiting distinctive persistent behaviors. Initially, by focusing on saccadic directions and intersaccadic angles, we disclose that the probability distributions of these measures show a clear preference of participants towards a reading-like mechanism (geometrical persistence), whose features and potential advantages for searching/foraging are discussed.We then perform a Multifractal Detrended Fluctuation Analysis (MF-DFA) over the time series of jump magnitudes in the eye trajectory and find that it exhibits a typical multifractal behavior arising from the sequential combination of saccades and fixations. By inspecting the time series composed of only fixational movements, our results reveal instead a monofractal behavior with a Hurst exponent H ∼ 0.7, which indicates the presence of long-range power-law positive correlations (statistical persistence). Motivated by the experimental findings from the study of the distribution of the intersaccadic angles, we developed a simple visual search model that quantifies the wide variety of possible search strategies. From our experiments we know that when searching a target within an image our brain can adopt different strategies. The question then is which one does it choose? We present a simple two-parameter visual search model (VSM) based on a persistent random walk and the experimental inter-saccadic angle distribution. The model captures the basic observed visual search strategies that range from systematic or reading-like to completely random. We compare the results of the model to the experimental data by measuring the space-filling efficiency of the searches. Within the parameter space of the model, we are able to quantify the strategies used by different individuals for three searching tasks and show how the average search strategy changes along these three groups. Even though participants tend to explore a vast range of parameters, when all the items are placed on a regular lattice, participants are more likely to perform a systematic search, whereas in a more complex field, the search trajectories resemble a random walk. In this way we can discern with high sensitivity the relation between the visual landscape and the average strategy, disclosing how small variations in the image induce strategy changes. Finally, we move beyond visual search and study the fixation time distributions across different visual tasks. Fixation times are commonly associated to some cognitive process, as it is in this instances where most of the visual information is gathered. However, the distribution for the fixation durations exhibits certain similarities across a wide range of visual tasks and foveated species. We studied how similar these distributions are, and found that, even though they share some common properties, such as similar mean values, most of them are statistically different. Because fixations durations can be controlled by two different mechanisms: cognitive or ocular, we focus our research into finding a model for the fixation times distribution flexible enough to capture the observed behaviors in experiments that tested these concepts. At the same time, the candidate function to model the distribution needs to be the response of some very robust inner mechanism found in all the aforementioned scenarios. Hence, we discuss the idea of a model based on the microsacaddic inter event time statistics, resulting in the sum of Gamma distributions, each of these related to the presence of a distinctive number of microsaccades in a fixation.
38
Singer, J. B. "Why solutions can be hard to find : a featural theory of cost for a local search algorithm on random satisfiability instances." Thesis, University of Edinburgh, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.661976.
Full textAbstract:
The local search algorithm WSAT is one of the most successful algorithms for solving the archetypal NP-complete problem of satisfiability (SAT). It is notably effective at solving RANDOM-3-SAT instances near the so-called "satisfiability threshold", which are thought to be universally hard. However, WSAT still shows a peak in search cost near the threshold and large variations in cost over different instances. Why are solutions to the threshold instances so hard to find using WSAT? What features characterise threshold instances which make them difficult for WSAT to solve? We make a number of significant contributions to the analysis of WSAT on these high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are implicates of and instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We undertake a detailed study of the behaviour of the algorithm during search and uncover some interesting patterns. These patterns lead us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for WSAT are those with large backbones which are also backbone-fragile. We suggest that the decay in cost for WSAT beyond the satisfiability threshold, which has perplexed a number of researchers, is due to the decreasing backbone fragility. Our hypothesis makes three correct predictions. First, that a measure of the backbone robustness of an instance (the opposite to backbone fragility) is negatively correlated with the WSAT cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSAT. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone.
39
Jacmenovic, Dennis, and dennis_jacman@yahoo com au. "Optimisation of Active Microstrip Patch Antennas." RMIT University. Electrical and Computer Engineering, 2004. http://adt.lib.rmit.edu.au/adt/public/adt-VIT20060307.144507.
Full textAbstract:
This thesis presents a study of impedance optimisation of active microstrip patch antennas to multiple frequency points. A single layered aperture coupled microstrip patch antenna has been optimised to match the source reflection coefficient of a transistor in designing an active antenna. The active aperture coupled microstrip patch antenna was optimised to satisfy Global Positioning System (GPS) frequency specifications. A rudimentary aperture coupled microstrip patch antenna consists of a rectangular antenna element etched on the top surface of two dielectric substrates. The substrates are separated by a ground plane and a microstrip feed is etched on the bottom surface. A rectangular aperture in the ground plane provides coupling between the feed and the antenna element. This type of antenna, which conveniently isolates any circuit at the feed from the antenna element, is suitable for integrated circuit design and is simple to fabricate. An active antenna design directly couples an antenna to an active device, therefore saving real estate and power. This thesis focuses on designing an aperture coupled patch antenna directly coupled to a low noise amplifier as part of the front end of a GPS receiver. In this work an in-house software package, dubbed ACP by its creator Dr Rod Waterhouse, for calculating aperture coupled microstrip patch antenna performance parameters was linked to HP-EEsof, a microwave computer aided design and simulation package by Hewlett-Packard. An ANSI C module in HP-EEsof was written to bind the two packages. This process affords the client the benefit of powerful analysis tools offered in HP-EEsof and the fast analysis of ACP for seamless system design. Moreover, the optimisation algorithms in HP-EEsof were employed to investigate which algorithms are best suited for optimising patch antennas. The active antenna design presented in this study evades an input matching network, which is accomplished by designing the antenna to represent the desired source termination of a transistor. It has been demonstrated that a dual-band microstrip patch antenna can be successfully designed to match the source reflection coefficient, avoiding the need to insert a matching network. Maximum power transfer in electrical circuits is accomplished by matching the impedance between entities, which is generally acheived with the use of a matching network. Passive matching networks employed in amplifier design generally consist of discrete components up to the low GHz frequency range or distributed elements at greater frequencies. The source termination for a low noise amplifier will greatly influence its noise, gain and linearity which is controlled by designing a suitable input matching network. Ten diverse search methods offered in HP-EEsof were used to optimise an active aperture coupled microstrip patch antenna. This study has shown that the algorithms based on the randomised search techniques and the Genetic algorithm provide the most robust performance. The optimisation results were used to design an active dual-band antenna.
40
McNeill, Gerard M. "Removal of EM coupling from frequency-domain IP data using a homogeneous anisotropic halfspace with complex resistivities in a controlled random search procedure /." Title page, contents and abstract only, 1997. http://web4.library.adelaide.edu.au/theses/09S.M/09s.mm1697.pdf.
Full text
41
Holmgren, Cecilia. "Split Trees, Cuttings and Explosions." Doctoral thesis, Uppsala universitet, Matematiska institutionen, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-112239.
Full textAbstract:
This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to describe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immigration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.
42
Lönneborg, Rosa. "In search of a biosensor for DNT detection : Studies of inducer response and specificity of DntR." Doctoral thesis, Stockholms universitet, Institutionen för biokemi och biofysik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-64129.
Full textAbstract:
The primary aim of the work presented in this thesis was to change the inducer specificity of the DntR protein in order to improve the response to DNT. The long-term goal is to use this protein in a biosensor for DNT, a signature compound for detection of the explosive TNT. Another aspect of this work was to understand the mechanisms of inducer binding and how the binding of an inducer molecule changes the DntR structure into a state that triggers transcriptional activation. In the papers included in this thesis the inducer specificity of wt DntR has been investigated under different conditions. The functional effects of specific mutations have also been investigated, in some cases in combination with structure determination using X-ray crystallography. In addition, structural data offering insights into the details of inducer binding and conformational changes upon inducer binding are presented and discussed in terms of mechanisms for transcriptional activation by DntR. Furthermore, a directed evolution strategy was employed in order to find variants of DntR with improved response to DNT. A variant with a large improvement in the DNT response was isolated and characterized. In optimized growth conditions, this DntR variant had a nearly 10-fold increase in fluorescence in response to DNT compared to wt DntR. Specific substitutions found in this DntR variant are suggested to be important for changing the inducer response.Syftet med denna avhandling har varit att förbättra förmågan hos proteinet DntR att upptäcka DNT. Det långsiktiga målet har varit att använda DntR i en biosensor för att upptäcka sprängämnet TNT, som avger DNT som en ”signaturmolekyl”. En annan aspekt har varit att bättre förstå den detaljerade mekanismen för hur DntR fungerar. DntR är ett protein som binder till en viss DNA sekvens (promotor) och reglerar hur gener intill denna promotorsekvens läses av. När en inducerande molekyl som t.ex. DNT binder till DntR förändras proteinets struktur på ett sådant sätt att DntR kan aktivera transkription av de gener som finns intill promotor-sekvensen. För att mäta hur DntR reagerar på olika inducerande molekyler har DntR uttryckts i bakterien Escherichia coli, som också innehållit promotorn som DntR binder till. Intill promotorn sitter en gen som kodar för proteinet GFP. När en inducerande molekyl binder till DntR, slås avläses gfp-genen, och det fluorescerande proteinet GFP produceras. Ju mer GFP som produceras i cellerna, desto högre fluorescens kan uppmätas när cellerna analyseras. I de artiklar som presenteras i avhandlingen har vi undersökt hur olika substitutioner i DntR proteinet påverkar specificiten och sensitiviteten och hur dessa egenskaper kan påverkas av olika experimentella faktorer. Effekten av substitutioner har relaterats till strukturdata, där bilder av hur proteinet ser ut på molekylär nivå har tagits fram. Dessutom presenteras även en bild av hur DntR förändras beroende på om inducerande molekyler är bundna eller inte. En sådan strukturbild ökar förståelsen för de mekanismer som gör att bindning av en inducerande molekyl orsakar en förändring av formen hos DntR på så sätt att avläsning av gener kan aktiveras. Vi har också använt en metod där evolutionära processer härmats för att få fram varianter av DntR med förbättrad respons till DNT. En variant med en drastisk ökning av DNT-responsen har isolerats, och dess egenskaper har karaktäriserats.
At the time of the doctoral defense, the following paper was unpublished and had a status as follows: Paper 3: Manuscript
43
Ratner, Michael. "Quantum Walks and Structured Searches on Free Groups and Networks." Diss., Temple University Libraries, 2017. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/442825.
Full textAbstract:
MathematicsPh.D.
Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated.
Temple University--Theses
44
Mahalingam, Gayathri. "Connected domination in graphs." [Tampa, Fla.] : University of South Florida, 2005. http://purl.fcla.edu/fcla/etd/SFE0001225.
Full text
45
Lančinskas, Algirdas. "Atsitiktinės paieškos globaliojo optimizavimo algoritmų lygiagretinimas." Doctoral thesis, Lithuanian Academic Libraries Network (LABT), 2013. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2013~D_20130620_110450-24770.
Full textAbstract:
Optimizavimo uždaviniai sutinkami įvairiose mokslo ir pramonės srityse, tokiose kaip chemija, biologija, biomedicina, operacijų tyrimai ir pan. Paprastai efektyviausiai sprendžiami uždaviniai, turintys tam tikras savybes, tokias kaip tikslo funkcijų tiesiškumas, iškilumas, diferencijuojamumas ir pan. Tačiau ne visi praktikoje pasitaikantys optimizavimo uždaviniai tenkina šias savybes, o kartais iš vis negali būti išreiškiami adekvačia matematine išraiška. Tokiems uždaviniam spręsti yra populiarūs atsitiktinės paieškos optimizavimo metodai.
Disertacijoje yra tiriami atsitiktinės paieškos optimizavimo metodai, jų lygiagretinimo galimybės ir taikymas praktikoje pasitaikantiems uždaviniams spręsti. Pagrindinis dėmesys skiriamas dalelių spiečiaus optimizavimo ir genetinių algoritmų modifikavimui ir lygiagretinimui.
Disertacijoje yra siūloma dalelių spiečiaus optimizavimo algoritmo modifikacija, grįsta pieškos srities siaurinimu, ir tiriamos kelios algoritmo lygiagretinimo strategijos. Algoritmas yra taikomas erdvėlaivių skrydžių trajektorijų optimizavimo uždaviniui spręsti lygiagrečiųjų skaičiavimų sistemose.
Taip pat yra siūlomas hibridinis globaliojo daugiakriterio optimizavimo algoritmas, gautas modifikuojant vieno agento stochastinės paieškos algoritmą ir įkomponuojant į daugiakriterio optimizavimo genetinį algoritmą. Siūlomos kelios daugiakriterio genetinio algoritmo lygiagretinimo strategijos. Jų pagrindu gauti lygiagretieji algoritmai eksperimentiškai tiriami sprendžiant... [toliau žr. visą tekstą]Global optimization problems are relevant in various fields of research and industry, such as chemistry, biology, biomedicine, operational research, etc. Normally it is easier to solve optimization problems having some specific properties of objective function such as linearity, convexity, differentiability, etc. However, there are a lot of practical problems that do not satisfy such properties or even cannot be expressed in an adequate mathematical form. Therefore, it is popular to use random search optimization methods in solving such optimization problems. The dissertation deals with investigation of random search global optimization algorithms, their parallelization and application to solve practical problems. The work is focused on modification and parallelization of particle swarm optimization and genetic algorithms. The modification of particle swarm optimization algorithm, based on reduction of the search area is proposed, and several strategies to parallelize the algorithm are investigated. The algorithm is applied to solve Multiple Gravity Assist problem using parallel computing system. A hybrid global multi-objective optimization algorithm is developed by modifying single agent stochastic search strategy, and incorporating it into multi-objective optimization genetic algorithm. Several strategies to parallelize multi-objective optimization genetic algorithm is proposed. Parallel algorithms are experimentally investigated by solving competitive facility location... [to full text]
46
Hansén, Jacob, and Axel Gustafsson. "A Study on Comparison Websites in the Airline Industry and Using CART Methods to Determine Key Parameters in Flight Search Conversion." Thesis, KTH, Matematisk statistik, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-254309.
Full textAbstract:
This bachelor thesis in applied mathematics and industrial engineering and management aimed to identify relationships between search parameters in flight comparison search engines and the exit conversion rate, while also investigating how the emergence of such comparison search engines has impacted the airline industry. To identify such relationships, several classification models were employed in conjunction with several sampling methods to produce a predictive model using the program R. To investigate the impact of the emergence of comparison websites, Porter's 5 forces and a SWOT - analysis were employed to analyze findings of a literature study and a qualitative interview. The classification models developed performed poorly with regards to several assessments metrics which suggested that there were little to no significance in the relationship between the search parameters investigated and exit conversion rate. Porter's 5 forces and the SWOT-analysis suggested that the competitive landscape of the airline industry has become more competitive and that airlines which do not manage to adapt to this changing market environment will experience decreasing profitability.Detta kandidatexamensarbete inriktat på tillämpad matematik och industriell ekonomi syftade till att identifiera samband mellan sökparametrar från flygsökmotorer och konverteringsgraden för utträde till ett flygbolags hemsida, och samtidigt undersöka hur uppkomsten av flygsökmotorer har påverkat flygindustrin för flygbolag. För att identifiera sådana samband, tillämpades flera klassificeringsmodeller tillsammans med stickprovsmetoder för att bygga en predikativ modell i programmet R. För att undersöka påverkan av flygsökmotorer tillämpades Porters 5 krafter och SWOT-analys som teoretiska ramverk för att analysera information uppsamlad genom en litteraturstudie och en intervju. Klassificeringsmodellerna som byggdes presterade undermåligt med avseende på flera utvärderingsmått, vilket antydde att det fanns lite eller inget samband mellan de undersökta sökparametrarna och konverteringsgraden för utträde. Porters 5 krafter och SWOT-analysen visade att flygindustrin hade blivit mer konkurrensutsatt och att flygbolag som inte lyckas anpassa sig efter en omgivning i ändring kommer att uppleva minskande lönsamhet.
47
Kucuktunc, Onur. "Result Diversification on Spatial, Multidimensional, Opinion, and Bibliographic Data." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1374148621.
Full text
48
Jurčík, Lukáš. "Evoluční algoritmy při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2014. http://www.nusl.cz/ntk/nusl-224447.
Full textAbstract:
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.
49
Горобей, О. О. "Інформаційна технологія комп'ютерного моделювання мікроклімату у теплицях." Master's thesis, Сумський державний університет, 2018. http://essuir.sumdu.edu.ua/handle/123456789/72186.
Full text
50
Lima, Tiago Aécio Grangeiro de Souza Barbosa. "Estudos de eficiência em buscas aleatórias unidimensionais." Universidade Federal de Pernambuco, 2010. https://repositorio.ufpe.br/handle/123456789/16645.
Full textAbstract:
Submitted by Sandra Maria Neri Santiago (sandra.neri@ufpe.br) on 2016-04-15T18:46:34Z
No. of bitstreams: 2
license_rdf: 1379 bytes, checksum: ea56f4fcc6f0edcf0e7437b1ff2d434c (MD5)
Dissertação_Tiago Aécio Grangeiro de Souza Barbosa Lima.pdf: 2215610 bytes, checksum: 8993869b89fc394d9e8171a017cfee6e (MD5)Made available in DSpace on 2016-04-15T18:46:34Z (GMT). No. of bitstreams: 2 license_rdf: 1379 bytes, checksum: ea56f4fcc6f0edcf0e7437b1ff2d434c (MD5) Dissertação_Tiago Aécio Grangeiro de Souza Barbosa Lima.pdf: 2215610 bytes, checksum: 8993869b89fc394d9e8171a017cfee6e (MD5) Previous issue date: 2010-07-23
Neste trabalho investigamos o problema do caminhante aleatório unidimensional como modelo para encontrar que distribuição de probabilidades é a melhor estratégia a ser utilizada na busca por sítios-alvos aleatoriamente distribuídos, cuja localização é desconhecida, na situação em que o buscador tem informação limitada sobre sua vizinhança. Embora tal problema tenha surgido na década de 1960, uma nova motivação surgiu nos anos 1990 quando dados empíricos mostraram que várias espécies de animais, sob condições gerais (especialmente escassez de comida), não usam estratégias brownianas de busca, mas sim distribuições de Lévy. A principal diferença entre elas é que as distribuições de Lévy decaem muito mais lentamente com a distância (com cauda do tipo lei de potência no limite de longos passos), não obedecendo, portanto, ao Teorema do Limite Central, e apresentam propriedades interessantes, como fractalidade, superdifusão e autoafinidade. Estes experimentos, juntamente com conceitos evolucionistas, levantaram a suspeita de que tal escolha pode ter sido adotada por ser mais vantajosa para o buscador, uma idéia conhecida como Lévy Flight Foraging Hypothesis. Em nosso estudo, definimos a eficiência da busca e obtemos a sua expressão analítica para o modelo. Utilizamos métodos computacionais para comparar as eficiências associadas às distribuições de Lévy e duas outras dentre as mais citadas na literatura, a gama e a "stretched exponential", concluindo que a de Lévy representa a melhor estratégia. Finalmente, empregamos métodos variacionais de extremização e obtemos a equação de Euler do problema.
In this work we study the one-dimensional random walk problem as a model to find which probability distribution function (pdf) is the best strategy when looking for randomly istributed target sites whose locations are not known, when the searcher has only limited information about its vicinity. Although research on this problem dates back to the 1960’s, a new motivation arose in the 1990’s when empirical data showed that many animal species, under broad conditions (especially scarcity of food), do not use Brownian strategies when looking for food, but Lévy distributions instead. The main difference between them is that the Lévy distribution decay much slower with distance (with a power-law tail in the long-range limit), thereby not obeying the Central Limit Theorem, and present interesting properties, like fractality, superdiffusivityand self-affinity. These experiments, coupled with evolutionary concepts, lead to suspicions that this choice might have been adopted because it is more advantageous for the searcher, an idea now termed as the Lévy Flight Foraging Hypothesis. To study the problem, we define a search efficiency function and obtain its analytical expression for our model. We use computational methods to compare the efficiencies associated with the Lévy and two of the most cited pdfs in the literature, the stretched exponential and Gamma distributions, showing that Lévy is the best search strategy. Finally, we employ variational extremization methods to obtain the problem’s Euler equation.