Dissertations / Theses on the topic 'Heuristics'
To see the other types of publications on this topic, follow the link: Heuristics.
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 'Heuristics.'
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
Peake, Katharine Louise. "Composition heuristics and theories and a proposed heuristic for business writing." CSUSB ScholarWorks, 2007. https://scholarworks.lib.csusb.edu/etd-project/3282.
Full text
2
Monk, Monika Patrice. "Mobile Exergaming Heuristics." Thesis, Virginia Tech, 2014. http://hdl.handle.net/10919/50581.
Full textAbstract:
An alarming number of adolescents experience obesity and related health issues, in part because of a lack of exercise. Increased mobile technology availability can have negative effects on amount of exercise, but they can have positive effects as well. Leveraging mobile technology to encourage and motivate exercise has potential to decrease unhealthy lifestyles, especially among young people. Mobile exergaming is an emerging field that has the potential to motivate users to exercise while also having fun. However, much of the early development work on mobile exergames has been ad-hoc, with little guidance available for designers. This work seeks to identify heuristics catered for mobile exergaming. This thesis presents four mobile exergaming heuristics were identified based on recent literature and on the author's mobile exergame design and development efforts: 1) Motivational game concepts that promote physical activity; 2) Game cues that engage active users; 3) Physically and temporally appropriate game structure to encourage continual, recurring play; 4) Game play movements that are safe for the user and for the device. This thesis describes the development of the mobile exergame heuristics, along with the creation and distribution of an ExergameApp Suite comprised of three mobile exergames: Fish Out of Water, Color Hunt and Space Rayders.Master of Science
3
Yee, Michael 1978. "Inferring noncompensatory choice heuristics." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/36226.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006.Includes bibliographical references (p. 121-128).
Human decision making is a topic of great interest to marketers, psychologists, economists, and others. People are often modeled as rational utility maximizers with unlimited mental resources. However, due to the structure of the environment as well as cognitive limitations, people frequently use simplifying heuristics for making quick yet accurate decisions. In this research, we apply discrete optimization to infer from observed data if a person is behaving in way consistent with a choice heuristic (e.g., a noncompensatory lexicographic decision rule). We analyze the computational complexity of several inference related problems, showing that while some are easy due to possessing a greedoid language structure, many are hard and likely do not have polynomial time solutions. For the hard problems we develop an exact dynamic programming algorithm that is robust and scalable in practice, as well as analyze several local search heuristics. We conduct an empirical study of SmartPhone preferences and find that the behavior of many respondents can be explained by lexicographic strategies.
(cont.) Furthermore, we find that lexicographic decision rules predict better on holdout data than some standard compensatory models. Finally, we look at a more general form of noncompensatory decision process in the context of consideration set formation. Specifically, we analyze the computational complexity of rule-based consideration set formation, develop solution techniques for inferring rules given observed consideration data, and apply the techniques to a real dataset.
by Michael J. Yee.
Ph.D.
4
Panthulu, Pradeep. "Intelligent Memory Management Heuristics." Thesis, University of North Texas, 2003. https://digital.library.unt.edu/ark:/67531/metadc4399/.
Full textAbstract:
Automatic memory management is crucial in implementation of runtime systems even though it induces a significant computational overhead. In this thesis I explore the use of statistical properties of the directed graph describing the set of live data to decide between garbage collection and heap expansion in a memory management algorithm combining the dynamic array represented heaps with a mark and sweep garbage collector to enhance its performance. The sampling method predicting the density and the distribution of useful data is implemented as a partial marking algorithm. The algorithm randomly marks the nodes of the directed graph representing the live data at different depths with a variable probability factor p. Using the information gathered by the partial marking algorithm in the current step and the knowledge gathered in the previous iterations, the proposed empirical formula predicts with reasonable accuracy the density of live nodes on the heap, to decide between garbage collection and heap expansion. The resulting heuristics are tested empirically and shown to improve overall execution performance significantly in the context of the Jinni Prolog compiler's runtime system.
5
Petracca, Enrico <1983>. "Essays in structural heuristics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6284/1/Petracca_Enrico_Tesi.pdf.
Full textAbstract:
This dissertation introduces and develops a new method of rational reconstruction called structural heuristics. Structural heuristics takes assignment of structure to any given object of investigation as the starting point for its rational reconstruction. This means to look at any given object as a system of relations and of transformation laws for those relations. The operational content of this heuristics can be summarized as follows: when facing any given system the best way to approach it is to explicitly look for a possible structure of it. The utilization of structural heuristics allows structural awareness, which is considered a fundamental epistemic disposition, as well as a fundamental condition for the rational reconstruction of systems of knowledge.
In this dissertation, structural heuristics is applied to reconstructing the domain of economic knowledge. This is done by exploring four distinct areas of economic research: (i) economic axiomatics; (ii) realism in economics; (iii) production theory; (iv) economic psychology. The application of structural heuristics to these fields of economic inquiry shows the flexibility and potential of structural heuristics as epistemic tool for theoretical exploration and reconstruction.
6
Petracca, Enrico <1983>. "Essays in structural heuristics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6284/.
Full textAbstract:
This dissertation introduces and develops a new method of rational reconstruction called structural heuristics. Structural heuristics takes assignment of structure to any given object of investigation as the starting point for its rational reconstruction. This means to look at any given object as a system of relations and of transformation laws for those relations. The operational content of this heuristics can be summarized as follows: when facing any given system the best way to approach it is to explicitly look for a possible structure of it. The utilization of structural heuristics allows structural awareness, which is considered a fundamental epistemic disposition, as well as a fundamental condition for the rational reconstruction of systems of knowledge.
In this dissertation, structural heuristics is applied to reconstructing the domain of economic knowledge. This is done by exploring four distinct areas of economic research: (i) economic axiomatics; (ii) realism in economics; (iii) production theory; (iv) economic psychology. The application of structural heuristics to these fields of economic inquiry shows the flexibility and potential of structural heuristics as epistemic tool for theoretical exploration and reconstruction.
7
Clark, Andrew J. "Optimisation heuristics for cryptology." Thesis, Queensland University of Technology, 1998. https://eprints.qut.edu.au/15777/1/Andrew_Clark_Thesis.pdf.
Full textAbstract:
The aim of the research presented in this thesis is to investigate the use of various optimisation heuristics in the fields of automated cryptanalysis and automated cryptographic function generation. These techniques were found to provide a successful method of automated cryptanalysis of a variety of the classical ciphers. Also, they were found to enhance existing fast correlation attacks on certain stream ciphers. A previously proposed attack of the knapsack cipher is shown to be flawed due to the absence of a suitable solution evaluation mechanism. Finally, a new approach for finding highly nonlinear Boolean functions is introduced.
8
Clark, Andrew J. "Optimisation Heuristics for Cryptology." Queensland University of Technology, 1998. http://eprints.qut.edu.au/15777/.
Full textAbstract:
The aim of the research presented in this thesis is to investigate the use of various optimisation heuristics in the fields of automated cryptanalysis and automated cryptographic function generation. These techniques were found to provide a successful method of automated cryptanalysis of a variety of the classical ciphers. Also, they were found to enhance existing fast correlation attacks on certain stream ciphers. A previously proposed attack of the knapsack cipher is shown to be flawed due to the absence of a suitable solution evaluation mechanism. Finally, a new approach for finding highly nonlinear Boolean functions is introduced.
9
Lü, Haili, and 吕海利. "A comparative study of assembly job shop scheduling using simulation, heuristics and meta-heuristics." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2011. http://hub.hku.hk/bib/B47029018.
Full text
10
Pasch, Kenneth Alan. "Heuristics for Job-Shop Scheduling." Thesis, Massachusetts Institute of Technology, 1988. http://hdl.handle.net/1721.1/6847.
Full textAbstract:
Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure.
11
Seib, Jerod Drew. "Unclear ideology heuristics and voting /." Available to subscribers only, 2006. http://proquest.umi.com/pqdweb?did=1240706151&sid=4&Fmt=2&clientId=1509&RQT=309&VName=PQD.
Full text
12
Haslum, Patrik. "Admissible Heuristics for Automated Planning." Doctoral thesis, Linköping : Department of Computer and Information Science, Linköpings universitet, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-6042.
Full text
13
Sheasby, Janice. "Lagrangean heuristics for vehicle routing." Thesis, Coventry University, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.320251.
Full text
14
Aldinger, Johannes [Verfasser], and Bernhard [Akademischer Betreuer] Nebel. "Relaxation heuristics for numeric planning." Freiburg : Universität, 2018. http://d-nb.info/1175875155/34.
Full text
15
Cox, Karl. "Heuristics for use case descriptions." Thesis, Bournemouth University, 2002. http://eprints.bournemouth.ac.uk/301/.
Full textAbstract:
Use cases, as part of the Unified Modelling Language, have become an industry standard. The major focus has been on the use case diagram. It is only recently that any detailed attention has been paid to the use case description. The description should be written in such a way as to make it communicable to its reader. However, this does not always appear to be the case. This thesis presents the 7 C's of Communicability as quality features of use case descriptions that make them more comprehensible. The 7 C's are derived from software engineering best practice on use case descriptions and from theories of text comprehension. To help in writing descriptions, the CP Use Case Writing Rules are proposed, a small set of guidelines derived from the 7 C's. Going beyond requirements, software engineers often employ use case descriptions to help them build initial design models of the proposed system. Despite Jacobson's claim that "objects naturally fall out of use cases", fording design-oriented classes and objects in use case descriptions is shown not to be straightforward. This thesis proposes a Question Set which allows the engineer to interrogate the description for important elements of specification and design. Experimentation shows that the CP Writing Rules furnish descriptions that are as comprehensible as those written by other guidelines proposed in the literature. It is also suggested that descriptions be written from the perspective of their intended audience. The limitations of conducting requirements engineering experiments using students are considered and it is suggested that experimenters should not expect large effects from the results. An industrial case study shows that although the CP Rules could not be applied to all events in the use case descriptions, they were applied to most and at varying levels of abstraction. The case study showed that the 7 C's did identify problems with the written descriptions. The Question Set was well received by the case study stakeholders, but it was considered time consuming. One of the overriding findings from the case study was that project time constraints would not allow the company to use the techniques suggested, although they recognised the need to do so. Automation would make industrial application of the CP Rules and 7 C's more feasible.
16
Gibbon, Cleveland Augustine. "Heuristics for object-oriented design." Thesis, University of Nottingham, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.388318.
Full text
17
MENDES, CARLOS RAONI DE ALENCAR. "COVERING CODES: BOUNDS AND HEURISTICS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2009. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=15365@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORCompreensão de dados, codificação digital da fala, telecomunicações via celular, correção de erros de transmissão, são algumas das aplicações práticas do estudo dos códigos de cobertura, um importante ramo da área da matemática denominada teoria dos códigos. Neste trabalho são abordados dois problemas de códigos de cobertura: o problema clássico de códigos de cobertura e o recente problema denominado de códigos curtos de cobertura. Apresenta-se uma aplicação da metaeurística Busca Tabu Reativa, uma importante variação da Busca Tabu clássica, para os problemas citados. Além disto, apresenta-se uma nova técnica heurística para resolução de problemas de otimização combinatória denominada Heurística de Melhoria via Geração de Colunas (HMGC), juntamente com uma aplicação da mesma aos problemas em questão. A HMGC combina a geração atrasada de colunas, técnica usada na resolução de problemas com um grande número de variáveis de decisão (colunas), e heurísticas de busca local. É feita uma comparação dos resultados obtidos pela Busca Tabu Reativa, a Busca Tabu sem o mecanismo de reação e a HMGC, de forma a avaliar a qualidade das heurísticas apresentadas.
Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.
18
Christodoulides, Marios Andreas. "Design heuristics : facilitating architectural thought." Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/65239.
Full textAbstract:
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Architecture, 1997.Includes bibliographical references (p. 48).
As D A Schon describes the problem space is not given with the presentation of the design task, but constructed by the designer as he/she invents the moves by which he/she attempts to find solutions. From such a design process two episodes emerge, the first one comprised of all the moves a designer makes to construct and organize a problem space, and the second one describing how a designer might navigate through such a problem space in his/her attempt to arrive at solutions. It is the methods which designers use in these episodes which I define as 'design heuristics'. These can facilitate the early stages of the design process in several ways. First they can help set up a platform upon which designers can begin to operate, and which can become the catalyst for further development and refinement to occur. Secondly, they help introduce into the problem space any concerns the designer chooses to address, whether those emerge from site, climate, or other potential factors. These help to complement programmatic concerns, set up hierarchies, and subsequently help the designer determine the important aspects of the problem he/she is attempting to address. Thirdly, the introduction of different 'design heuristics' in both episodes of the design process helps to limit the range of possible solutions, and therefore eliminate the need for exhaustive search. In this thesis an iterative process of investigation is carried out in order to gain a better understanding into the nature of different 'design heuristics' and examine the potential for the development of a tool that can facilitate their implementation. Different categories of rules are introduced in an attempt to create an environment where deSign operations, independent of particular design problems, can be identified. Rules such as the grid, line, and boundary are implemented to investigate concepts of alignment, articulation, and envelope respectively. A random generator is used upon which these rules are superimposed, allowing for a better understanding of the potential and limitations of single rules, or combinations of them. The careful evaluation of a series of experimental products gave rise to a series of concepts that could be critical in the development of an appropriate tool offering more insight as to how one should proceed next. Introducing 'flexibility' for each one of these rules allowed for the development of hierarchies of importance among the different heuristics a deSigner might choose to apply. 'Directional constraints' for each of the rules emerged as critical allowing the development of different variants from each one of the rules described above. The grid for example could have different constrains in anyone of its three axis. The 'sequence' by which these rules are applied emerged as important in the articulation of each one of these rules. The rule applied first would have to compromise the most following the application of subsequent rules. The careful study of products utilizing different variations of such concepts gave better insight as to how these concepts might be further developed and also allowed for new ones to emerge. Furthermore an attempt is made to address both episodes described above by defining a stage of 'generation' followed by a stage of 'post-generation control'. A collection of such concepts can begin to clarify some of the operations that are part of the design activity, setting up the ground for the development of a design tool that facilitates the application of heuristics in the early stages of the design process.
by Marios Andreasa Christodoulides.
M.S.
19
Löfvenberg, Johanna. "Poietic design : Heuristics and applications." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-297084.
Full textAbstract:
Good design is often derived from user-centred design, and systems have to be too adapted for their users. This delimits the system and the user alike. With poietic design, the system is designed to be less limited and the user is encouraged to get a deeper, more intuitive understanding of how it works. The properties of the proposed design philosophy poietic design are based on theoretical research and examples of artefacts that excel in communicating how they work. The properties, or heuristics, are used to analyse a digital system and a display, and to propose poietic redesigns. An experiment is conducted where the performance of the poietically designed display is compared to an ecological interface design (EID) display. The EID display was optimised for one of the tasks executed while the poietic display was designed to perform approximately as good for both tasks. The results show that the poietic design performed better than the EID display in the task that the EID design was not specifically designed for. This implies that poietic design has good potential to be used as a way to design information visualisation displays.
20
Sprinkle, Zachary Joseph. "Heuristics in Construction Project Management." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/87089.
Full textAbstract:
Modern construction projects are delivered in complex, fast pace environments. Stakeholders are required to participate in dynamic project settings with resource constraints, information constraints, and time constraints. To overcome gaps in knowledge, to deliver decisions quickly, and to overcome human limits in cognitive ability, decision makers typically employ heuristics, or rules of thumb to arrive at relatively quick answers. Heuristics are cognitive shortcuts that an individual employs to arrive at quick decisions (Goodwin et al., 2004). These heuristics are used in a variety of ways, ranging from using the process of elimination (elimination heuristic) to applying different cognitive weights to options based on recent experience, reputation, or familiarity (Shah and Oppenheimer, 2008). This research aims to identify heuristics present in the implementation phase of construction. By summarizing the results of two studies conducted with a Mid-Atlantic Contractor, this thesis prescribes seven heuristics commonly used by construction stakeholders.Master of Science
21
Elhag, Anas. "Hyper-heuristics for grouping problems." Thesis, University of Nottingham, 2015. http://eprints.nottingham.ac.uk/34217/.
Full textAbstract:
Grouping problems are hard to solve combinatorial optimization problems which require partitioning of objects into a minimum number of subsets while another additional objective is simultaneously optimized. Considerable research e ort has recently been directed towards automated problem-independent reusable heuristic search methodologies such as hyper-heuristics, which operate on a space formed by a set of low level heuristics rather than solutions, directly. Hyper-heuristics are commonly split into two main categories: selection hyper-heuristics, which are the focus of the work presented in this thesis, and generation hyper-heuristics. Most of the recently proposed selection hyper-heuristics are iterative and make use of two key methods which are employed successively; heuristic selection and move acceptance. At each step, a new solution is produced after a selected heuristic is applied to the solution at hand and then the move acceptance method is used to decide whether the resultant solution replaces the current one or not. This thesis presents a novel generic single point-based selection hyper-heuristic search framework, referred to as grouping hyper-heuristic framework. The proposed framework deals with one solution at any given decision point during the search process and embeds axed set of reusable standard low level heuristics specifically designed for the grouping problems. The use of standard heuristics enables the re-usability of the whole framework across different grouping problem domains with less development effort. The proposed grouping hyper-heuristic framework is based on a bi-objective formulation of any given grouping problem. Inspired from multi-objective optimization, a set of high quality solutions is maintained during the search process, capturing the trade-of between the number of groups and the additional objective for the given grouping problem. Moreover, the grouping framework includes a special two-phased acceptance mechanism that use the traditional move acceptance method only to make a preliminary decision regarding whether to consider the new solution for acceptance or not. The performance of different selection hyper-heuristics combining different components, implemented based on the proposed framework is investigated on a range of sample grouping problem domains, including graph coloring, exam timetabling and data clustering domains. Additionally, the selection hyper-heuristics performing the best on each domain are compared to the previously proposed problem-specific algorithms from the scientific literature. The empirical results shows that the grouping hyper-heuristics built based on the proposed framework are not only sufficiently general, but also able to obtain high quality solutions, competitive to some previously proposed approaches. The selection hyper-heuristic employing the 'reinforcement learning' heuristic selection method and embedding the 'iteration limited threshold accepting' move acceptance method performs the best in the overall across those grouping problem domains.
22
Barsky, David Edward. "Entrepreneurial Heuristics and Serial Entrepreneurs." Diss., Temple University Libraries, 2010. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/66251.
Full textAbstract:
Business AdministrationPh.D.
This dissertation is comprised of three separate entrepreneurship papers. Paper 1, "Entrepreneurial Heuristics...", found that being mentored, rather than either having extensive higher education or more work experience, was primarily responsible for entrepreneurs acquiring the simplified decision rules (heuristics) that can be useful to them in their business pursuits. The study also found that entrepreneurs do not seem to switch their decision making processes from a "rational man" (thorough) mode to a more abbreviated, heuristic mode as some current thinking suggests. Also in Paper 1 this researcher presented and utilized a 27 item heuristics scale which was used to identify "use of heuristics" by the entrepreneurs studied. Paper 2, "Female Serial Entrepreneurs...", examined the characteristics of female serial entrepreneurs (SE's) as a group of growing size and importance. Three areas- business size, hours worked in the business, and amount and type of capital raised- were explored through contrasting female SE's with female non-SE's and male SE's. The primary findings were as follows: the businesses of female SE's are larger than those of female non-SE's, and female SE's in the professional, technical and scientific services industry borrow more debt than female SE's in this industry, but they do not work longer hours than female non-SE's. It was also found that female SE businesses, in the industries examined in the study, have come to rival male SE businesses in size, as measured in revenues. Paper 3, "The Serial Entrepreneur Dilemma...", explained a conundrum: why serial entrepreneurs do not seem to outperform novice entrepreneurs. A literature review is given consisting of the scholarly thinking about the causes of the conundrum, and then three hypotheses are tested to explore the dilemma. It was found that looking at serial entrepreneurs and novices over time, rather than cross-sectionally, helps to explain the conundrum: the SE's are willing to take losses early on (thus not performing higher than the novices) in expectation of future profits. It was also found that in slow-moving industries, serial entrepreneurs performed much better than novice entrepreneurs in revenues, whereas in fast-moving industries the difference between the two groups in performance was negligible.
Temple University--Theses
23
Basu, Nandini. "Heuristics for searching chemical structures." Diss., Columbia, Mo. : University of Missouri-Columbia, 2007. http://hdl.handle.net/10355/5000.
Full textAbstract:
Thesis (M.S.)--University of Missouri-Columbia, 2007.The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file (viewed Apr. 9, 2009). Includes bibliographical references.
24
Hong, Libin. "Hyper-heuristic approaches to automatically designing heuristics as mutation operators for evolutionary programming on function classes." Thesis, University of Nottingham, 2018. http://eprints.nottingham.ac.uk/52348/.
Full textAbstract:
A hyper-heuristic is a search method or learning mechanism for selecting or generating heuristics to solve computational search problems. Researchers classify hyper-heuristics according to the source of feedback during learning: Online learning hyper-heuristics learn while solving a given instance of a problem; Offline learning hyper-heuristics learn from a set of training instances, a method that can generalise to unseen instances. Genetic programming (GP) can be considered a specialization of the more widely known genetic algorithms (GAs) where each individual is a computer program. GP automatically generates computer programs to solve specified tasks. It is a method of searching a space of computer programs. GP can be used as a kind of hyper-heuristic to be a learning algorithm when it uses some feedback from the search process. Our research mainly uses genetic programming as offline hyper-heuristic approach to automatically design various heuristics for evolutionary programming.
25
BERGMARK, FABIAN, and JOHAN STENBERG. "Heuristics in MCTS-based Computer Go : Can heuristics improve the performance of MCTS-based computer go?" Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-157529.
Full textAbstract:
The subject of computer Go is an active eld under AI and has achieved much attention in research. The current state of the art computer Go im-plementations uses a game tree search approach rather than advanced heuristics. This thesis aims to bridge these two approaches and combineMonte Carlo Tree Search with heuristics to deduce if any general results can be found. The results of the thesis indicate that the performance of a combined MCTS-heuristic approach correlates strongly with performance of the heuristic. Furthermore, MCTS can be used with any heuristic to improve its performance.1
26
RAUF, MIAN SHAMS, and MOHAMMAD ZAINULLAH. "Entrepreneurial Learning, Heuristics and Venture Creation." Thesis, Jönköping University, JIBS, EMM (Entrepreneurship, Marketing, Management), 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:hj:diva-9335.
Full textAbstract:
After rigorous criticism on trait approach and with the emergence of behavioral approach in entrepreneurship during 1980s, the researchers started to introduce learning and cognitive theories in entrepreneurship to describe and explain the dynamic nature of entrepreneurship. Many researchers have described venture creation as a core and the single most important element of entrepreneurship. This thesis will discuss and present the role of entrepreneurial learning and heuristics in venture creation. Hence, the purpose of this research thesis is to study and analyze the role of entrepreneurial learning and heuristics in venture creation.
To fulfill the purpose of this thesis, we followed qualitative research and conducted semi structured interviews with open ended questionnaires to collect empirical data. For this study, we have included only four interviews which were conducted on four different businesses based in Jönköping, Sweden, following convenience sampling. In the analysis, we used data analysis model of Walker, Cooke and McAllister (2008) and inductively generated three propositions, depicting the role and importance of entrepreneurial learning and heuristics in venture creation.
Individuals adopt entrepreneurship in their careers with necessary skills, abilities, and knowledge, which are learned or gained through experiential learning and/or vicarious learning (i.e., learning by observing or modeling the actions of others). Learning by doing is considered the most important factor by entrepreneurs which helped them to overcome different business start up hurdles, to make various entrepreneurial decisions and to perform many entrepreneurial activities during venture creation. Similarly, individuals within their own situation use, learning by observing or modeling other people’s behaviour, actions and consequences of the actions. Entrepreneurs use learning by modeling the behaviour and actions of others as benchmarking strategy during venture creation. Entrepreneurs believe that without any learning they will not be able to start their own businesses. Heuristics as decisions making mechanism, particularly during venture creation, is used by entrepreneurs as simplifying strategy when sufficient information related to a specific market, certain industry and products are scarce. Additionally, entrepreneurs are passionate to grab profitable business opportunity, and due to time pressure and brief window of opportunity, they can’t go for gathering each and every information of the potential business or product. Hence, heuristics as decisions making mechanism is considered the best suitable approach to make many entrepreneurial decisions during venture creation.
27
Mabrouk, Emad Hamdy Ahmed. "Meta-Heuristics Programming and Its Applications." 京都大学 (Kyoto University), 2011. http://hdl.handle.net/2433/142132.
Full text
28
Kolen, A. W. J., Kan A. H. G. Rinnooy, Hoesel C. P. M. Van, and Albert Wagelmans. "Sensitivity Analysis of List Scheduling Heuristics." Massachusetts Institute of Technology, Operations Research Center, 1990. http://hdl.handle.net/1721.1/5268.
Full textAbstract:
When jobs have to be processed on a set of identical parallel machines so as to minimize the makespan of the schedule, list scheduling rules form a popular class of heuristics. The order in which jobs appear on the list is assumed here to be determined by the relative size of their processing times; well known special cases are the LPT rule and the SPT rule, in which the jobs are ordered according to non-increasing and non-decreasing processing time respectively. When one of the job processing times is gradually increased, the schedule produced by a list scheduling rule will be affected in a manner reflecting its sensitivity to data perturbations. We analyze this phenomenon and obtain analytical support for the intuitively plausible notion that the sensitivity of a list scheduling rule increases with the quality of the schedule produced.
29
Shields, Ian Beaumont. "Hamilton Cycle Heuristics in Hard Graphs." NCSU, 2004. http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/.
Full textAbstract:
In this thesis, we use computer methods to investigate Hamilton cycles and paths in several families of graphs where general results are incomplete, including Kneser graphs, cubic Cayley graphs and the middle two levels graph. We describe a novel heuristic which has proven useful in finding Hamilton cycles in these families and compare its performance to that of other algorithms and heuristics. We describe methods for handling very large graphs on personal computers. We also explore issues in reducing the possible number of generating sets for cubic Cayley graphs generated by three involutions.
30
LaDuca, Robert James. "Optimizing steering heuristics for clustered microarchitectures." Diss., Online access via UMI:, 2006.
Find full text
31
Peterson, Bruce Jeffrey. "An instructional design model for heuristics." [Bloomington, Ind.] : Indiana University, 2007. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3297107.
Full textAbstract:
Thesis (Ph.D.)--Indiana University, School of Education, 2007.Title from dissertation home page (viewed Sept. 26, 2008). Source: Dissertation Abstracts International, Volume: 69-02, Section: A, page: 0493. Adviser: Charles M. Reigeluth.
32
Catanas, Fernando Jorge de Lyz Girou Rodrigues. "Heuristics for the dynamic portfolio problem." Thesis, Imperial College London, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.322226.
Full text
33
Koshich, P. A. "University course timetabling of meta-heuristics." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.433470.
Full text
34
Banerjea-Brodeur, Monica. "Selection hyper-heuristics for healthcare scheduling." Thesis, University of Nottingham, 2013. http://eprints.nottingham.ac.uk/14395/.
Full textAbstract:
A variety of approaches have been used to solve a variety of combinatorial optimisation problems. Many of those approaches are tailored to the particular problem being addressed. Recently, there has been a growing number of studies towards providing more general search methodologies than currently exist which are applicable to different problem domains without requiring any algorithmic modification. Hyper-heuristics represent a class of such general methodologies which are capable of automating the design of search process via generating new heuristics and/or mixing existing heuristics to solve hard computational problems. This study focuses on the design of selection hyper-heuristics which attempt to improve an initially created solution iteratively through heuristic selection and move acceptance processes and their application to the real-world healthcare scheduling problems, particularly, nurse rostering and surgery admission planning. One of the top previously proposed general hyper-heuristic methodology was an adaptive hyper-heuristic consisting of many parameters, although their values were either fixed or set during the search process, with a complicated design. This approach ranked the first at an international cross-domain heuristic search challenge among twenty other competitors for solving instances from six different problem domains, including maximum satisfiability, one dimensional bin packing, permutation flow shop, personnel scheduling, travelling salesman, vehicle routing problems. The hyper-heuristics submitted to the competition along with the problem domain implementations can now be considered as the benchmark for hyper-heuristics. This thesis describes two new easy-to-implement selection hyper-heuristics and their variants based on iterated and greedy search strategies. A crucial feature of the proposed hyper-heuristics is that they necessitate setting of less number of parameters when compared to many of the existing approaches. This entails an easier and more efficient implementation, since less time and effort is required for parameter tuning. The empirical results show that our most efficient and effective hyper-heuristic which contains only a single parameter outperforms the top ranking algorithm from the challenge when evaluated across all six problem domains. Moreover, experiments using additional nurse rostering problems which are different than the ones used in the challenge and surgery scheduling problems show that the results found by the proposed hyper-heuristics are very competitive, yielding with the best known solutions in some cases.
35
VIANNA, DALESSANDRO SOARES. "HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2004. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=5178@1.
Full textAbstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOUma filogenia é uma árvore que relaciona unidades taxonômicas, baseada na similaridade de seus conjuntos de características. O problema da filogenia consiste em encontrar uma filogenia com o número mínimo de passos evolutivos. O principal objetivo deste trabalho é desenvolver heurísticas híbridas para este problema. Duas estratégias são propostas. A primeira combina a metaheurística GRASP baseada em uma nova estrutura de vizinhança (k-SPR) proposta neste trabalho com um procedimento VND de busca local. A segunda estratégia híbrida combina algoritmos genéticos com uma estratégia de cruzamento inovadora, a qual é uma extensão da técnica de intensificação denominada reconexão por caminhos que foi originalmente aplicada no contexto de outras metaheurísticas, tais como busca tabu e GRASP. Os experimentos computacionais realizados sobre instâncias geradas aleatoriamente e instâncias da literatura científica mostram que os novos algoritmos são bastante robustos e que superaram os outros algoritmos existentes na literatura em termos de qualidade de solução e tempos computacionais obtidos.
A phylogeny is a tree that relates taxonomic units, based on their similarities over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. The main goal of this work is to develop hybrid heuristics for this problem. Two strategies are proposed. The first combines the GRASP metaheuristic using a new neighborhood structure (k-SPR) proposed in this work with a VND local search procedure. The second hybrid strategy combines genetic algorithms with an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originally applied in the context of other metaheuristics such as tabu search and GRASP. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristics are quite robust and outperform the others algorithms in the literature in terms of solution quality and computational time.
36
AMARAL, FERNANDO NAUFEL DO. "TOPOS-BASED MODEL THEORY FOR HEURISTICS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2004. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=5254@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOREste trabalho emprega conceitos e ferramentas de Teoria das Categorias e Teoria de Topoi para construir um modelo matemático de problemas, reduções entre problemas, espaços e estratégias de busca heurística. Mais precisamente, uma estratégia de construção de espaços de busca é representada por um funtor de uma certa categoria de problemas para uma certa categoria de florestas. A coleção de todos estes funtores forma um topos, um modelo específico equipado com uma lógica interna própria. Esta lógica interna é usada, então, para definir estratégias de busca e heurísticas em Teoria Local dos Conjuntos. Possíveis aplicações do trabalho incluem (1) a especificação lógica e a classificação de heurísticas e meta-heurísticas usadas na prática e (2) uma versão mais abstrata e geral de resultados específicos relacionando a estrutura de problemas com métodos de resolução adequados.
This work employs concepts and tools from Category Theory and Topos Theory to construct a mathematical model for problems, reductions between problems, heuristic search spaces and strategies. More precisely, a search space construction strategy is represented by a functor from a certain category of problems to a certain category of forests. The collection of all such functors forms a topos, a specific model equipped with its own internal logic. This internal logic is then used to define search satrategies and heuristics in Local Set Theory. Possible applications of this work include (1) the logical specification and classification of heuristics and metaheuristics used in pratice and (2) a more abstract and general rendering of specific results relating the structure of problems to adequate problem-solving methods.
37
Bash, K. E. "Spatial poetries : heuristics for experimental poiesis." Thesis, University College London (University of London), 2011. http://discovery.ucl.ac.uk/1337102/.
Full textAbstract:
The theme of this research is the study of how things take form in experience, consciousness and language. In large part, it explores the identification and the naming of ephemeral event phenomena that are as of yet unnamed, a process of becoming I describe as symmetry-breaking. This exploration is pursued within the framework of a Lived Spatial Inquiry called Experimental Poiesis, a particularly experimental form of making where inquiry is the formal philosophical and poietic tool where the original matrix of the site in question is embedded in what is made. The methods of this inquiry facilitate both the study and the subversion of normal habits of language-focused perception and are called Heuristics—experimental aesthetic practices that are site-adjustable and engaged iteratively, where the results of one experiment become the starting point of the next. Spatial Poetries is the name I have given to the results of these experiments, hybrid in form and prompting shifts in lived experience in the reader. This thesis pays homage to Observations upon Experimental Philosophy (1666), by the Duchess of Newcastle Margaret Cavendish, as well as The Manual of Scientific Enquiry; Prepared for the Use of Officers in Her Majesty’s Navy; And Travellers in General (1859), edited by Sir John F. W. Herschel. In addition, I engage with the work of Gregory Bateson, John Dewey, Ian Hacking, Dalibor Vesely and Roberto Casati, and have found resonance with practices such as medieval monastic rhetoric as presented in the writings of Mary Carruthers, the work of the architecture school Pontificia Universidad Católica de Valparaíso in the Ciudad Abierta (Open City), and the site-based poetic and philosophical works of Ian Hamilton Finlay. As a hybrid object, the thesis contains a manual for the discovery, analysis and naming of ephemeral phenomena. The Manual is composed of images, text, audio, video, and diagrams. As an assemblage, it both documents a process of inquiry and attempts to provide a taxonomy and rationale for that process and is presented in the form of the Atlas of Experimental Poiesis, a central contribution of this research. This Atlas allows for a process of philosophic reflection that feeds back into and has the capacity to enrich lived spatial-aesthetic experience of readers in general. In specific, it offers a vocabulary and visual structure to undertake the processes of observation, detection and creation of new forms, and the challenge of bringing those experiences to language.
38
Ortmann, Frank. "Heuristics for offline rectangular packing problems." Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/3992.
Full textAbstract:
Thesis (PhD (Logistics))--University of Stellenbosch, 2010.ENGLISH ABSTRACT: Packing problems are common in industry and there is a large body of literature on the subject. Two packing problems are considered in this dissertation: the strip packing problem and the bin packing problem. The aim in both problems is to pack a speci ed set of small items, the dimensions of which are all known prior to packing (hence giving rise to an o ine problem), into larger objects, called bins. The strip packing problem requires packing these items into a single bin, one dimension of which is unbounded (the bin is therefore referred to as a strip). In two dimensions the width of the strip is typically speci ed and the aim is to pack all the items into the strip, without overlapping, so that the resulting packing height is a minimum. The bin packing problem, on the other hand, is the problem of packing the items into a speci ed set of bins (all of whose dimensions are bounded) so that the wasted space remaining in the bins (which contain items) is a minimum. The bins may all have the same dimensions (in which case the problem is known as the single bin size bin packing problem), or may have di erent dimensions, in which case the problem is called the multiple bin size bin packing problem (MBSBPP). In two dimensions the wasted space is the sum total of areas of the bins (containing items) not covered by items. Many solution methodologies have been developed for above-mentioned problems, but the scope of the solution methodologies considered in this dissertation is restricted to heuristics. Packing heuristics follow a xed set of rules to pack items in such a manner as to nd good, feasible (but not necessarily optimal) solutions to the strip and bin packing problems within as short a time span as possible. Three types of heuristics are considered in this dissertation: (i) those that pack items into levels (the heights of which are determined by the heights of the tallest items in these levels) in such a manner that all items are packed along the bottom of the level, (ii) those that pack items into levels in such a manner that items may be packed anywhere between the horizontal boundaries that de ne the levels, and (iii) those heuristics that do not restrict the packing of items to levels. These three classes of heuristics are known as level algorithms, pseudolevel algorithms and plane algorithms, respectively. A computational approach is adopted in this dissertation in order to evaluate the performances of 218 new heuristics for the strip packing problem in relation to 34 known heuristics from the literature with respect to a set of 1 170 benchmark problem instances. It is found that the new level-packing heuristics do not yield signi cantly better solutions than the known heuristics, but several of the newly proposed pseudolevel heuristics do yield signi cantly better results than the best of the known pseudolevel heuristics in terms of both packing densities achieved and computation times expended. During the evaluation of the plane algorithms two classes of heuristics were identi ed for packing problems, namely sorting-dependent and sortingindependent algorithms. Two new sorting techniques are proposed for the sorting-independent algorithms and one of them yields the best-performing heuristic overall. A new heuristic approach for the MBSBPP is also proposed, which may be combined with level and pseudolevel algorithms for the strip packing problem in order to nd solutions to the problem very rapidly. The best-performing plane-packing heuristic is modi ed to pack items into the largest bins rst, followed by an attempted repacking of the items in those bins into smaller bins with the aim of further minimising wasted space. It is found that the resulting plane-packing algorithm yields the best results in terms of time and packing density, but that the solution di erences between pseudolevel algorithms are not as marked for the MBSBPP as for the strip packing problem.
AFRIKAANSE OPSOMMING: Inpakkingsprobleme kom algemeen in die industrie voor en daar is 'n aansienlike volume literatuur oor hierdie onderwerp. Twee inpakkingsprobleme word in hierdie proefskrif oorweeg, naamlik die strook-inpakkingsprobleem en die houer-inpakkingsprobleem. In beide probleme is die doel om 'n gespesi seerde versameling klein voorwerpe, waarvan die dimensies almal voordat inpakking plaasvind, bekend is (en die probleem dus 'n sogenaamde a yn-probleem is), in een of meer groter houers te pak. In die strook-inpakkingsprobleem word hierdie voorwerpe in een houer, waarvan een dimensie onbegrens is, ingepak (hierdie houer word dus 'n strook genoem). In twee dimensies word die wydte van die strook gewoonlik gespesi seer en is die doel om al die voorwerpe sonder oorvleueling op s o 'n manier in die strook te pak dat die totale inpakkingshoogte geminineer word. In die houer-inpakkingsprobleem, daarenteen, is die doel om die voorwerpe op s o 'n manier in 'n gespesi seerde aantal houers (waarvan al die dimensies begrens is) te pak dat die vermorste of oorblywende ruimte in die houers (wat wel voorwerpe bevat) 'n minimum is. Die houers mag almal dieselfde dimensies h^e (in welke geval die probleem as die enkelgrootte houer-inpakkingsprobleem bekend staan), of mag verskillende dimensies h^e (in welke geval die probleem as die veelvuldige-grootte houer-inpakkingsprobleem bekend staan, afgekort as VGHIP). In twee dimensies word die vermorste ruimte geneem as die somtotaal van daardie deelareas van die houers (wat wel voorwerpe bevat) waar daar geen voorwerpe geplaas word nie. Verskeie oplossingsmetodologie e is al vir die bogenoemde twee inpakkingsprobleme ontwikkel, maar die bestek van die metodologie e wat in hierdie proefskrif oorweeg word, word beperk tot heuristieke. 'n Inpakkingsheuristiek volg 'n vaste stel re els waarvolgens voorwerpe in houers gepak word om so spoedig moontlik goeie, toelaatbare (maar nie noodwendig optimale) oplossings tot die strook-inpakkingsprobleem en die houer-inpakkingsprobleem te vind. Drie tipes inpakkingsheuristieke word in hierdie proefskrif oorweeg, naamlik (i) heuristieke wat voorwerpe langs die onderste randte van horisontale vlakke in die houers pak (die hoogtes van hierdie vlakke word bepaal deur die hoogtes van die hoogste item in elke vlak), (ii) heuristieke wat voorwerpe op enige plek binne horisontale stroke in die houers pak, en (iii) heuristieke waar inpakking nie volgens horisontale vlakke of stroke beperk word nie. Hierdie drie klasse heuristieke staan onderskeidelik as vlakalgoritmes, pseudo-vlakalgoritmes en platvlakalgoritmes bekend. 'n Berekeningsbenadering word in hierdie proefskrif gevolg deur die werkverrigting van die 218 nuwe heuristieke vir die strook-inpakkingsprobleem met die werkverrigting van 34 bekende heuristieke uit die literatuur te vergelyk, deur al die heuristieke op 1 170 toetsprobleme toe te pas. Daar word bevind dat die nuwe vlakalgoritmes nie 'n noemenswaardige verbetering in oplossingskwaliteit in vergeleke met soortgelyke bestaande algoritmes in die literatuur lewer nie, maar dat verskeie nuwe pseudo-vlakalgoritmes wel noemenswaardige verbeteringe in terme van beide inpakkingsdigthede en oplossingstye in vergeleke met die beste bestaande algoritmes in die literatuur lewer. Assessering van die platvlakalgoritmes het gelei tot die identi kasie van twee deelklasse van algoritmes, naamlik sorteringsafhanklike- en sorteringsonafhanklike algoritmes. Twee nuwe sorteringstegnieke word ook vir die deelklas van sorteringsonafhanklike algoritmes voorgestel, en een van hulle lewer die algeheel beste inpakkingsheursitiek. 'n Nuwe heuristiese benadering word ook vir die VGHIP ontwikkel. Hierdie benadering kan met vlak- of pseudo-vlakalgoritmes vir die strook-inpakkingsprobleem gekombineer word om baie vinnig oplossings vir die VGHIP te vind. Die beste platvlakheuristiek vir die strookinpakkingsprobleem word ook aangepas om voorwerpe eers in die grootste houers te pak, en daarna in kleiner houers te herpak met die doel om vermorste ruimte verder te minimeer. Daar word bevind dat die resulterende platvlakalgoritme die beste resultate in terme van beide inpakkingsdigtheid en oplossingstyd lewer, maar dat oplossingsverskille tussen die pseudovlakalgoritmes nie so opmerklik vir die VGHIP is as wat die geval met die strookinpakkingsprobleem was nie.
39
Piacentini, Chiara. "Enhanced heuristics for numeric temporal planning." Thesis, King's College London (University of London), 2015. https://kclpure.kcl.ac.uk/portal/en/theses/enhanced-heuristics-for-numeric-temporal-planning(8b51dcec-1714-41b5-9e73-dfb5a0f685e6).html.
Full textAbstract:
After 50 years of fundamental research, domain independent planning has recently started to be applied to numerous real world problems. However, this has shown that the techniques developed until now are not completely mature: improvements can be made in different directions, such as in the area of metric temporal planning. This PhD research is focused on how we can use more sophisticated and informative heuristics in the general context of automated planning, when numeric and temporal constraints are a significant part of the problem. As a starting point, we will use as a reference example the voltage control problem in distributed electricity networks of power systems. This domain is a real world application of planning in which non-linear numeric effects and exogenous events are combined, challenging the state of the art planners. A power system is a nation-wide infrastructure which delivers electricity from suppliers to consumers. Technical and economic considerations impose constraints on the different elements of the network and subsequently on control and controlling variables of interest. One of the main parameters is the voltage, which must lie in strict boundaries. The voltage, as well as all the other physical quantities involved, is subject to the variation of the electrical output that changes through time. Effects of these changes propagate all across the network. This comes with a substantial computational burden and calls for extensions to be developed to enable the application of automated planning. In addition to this, the presence of events representing predicted load and supply over time require the planner to interact with uncontrollable events. The voltage control problem is the starting point for our investigation on how the standard delete-relaxation behaves in the presence of numeric and temporal constraints. Fully relaxing all the negative effects can result in a too poorly informed heuristic. In this thesis we explore different ways to enhance the heuristic, adding selected negative effects, while not compromising too much the efficiency of the heuristic computation. In particular we have studied the numeric temporal heuristic of the planner popf2, based on the Temporal Relaxed Planning Graph (TRPG), and propose a way to take into account numeric effects that are calculated by external modules connected to the planner. Negative effects of predictable numeric exogenous events in the presence of trajectory constraints are also taken into account in the heuristic.
40
Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.
Full textAbstract:
Une coloration propre d’un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que deux sommets voisins ont des couleurs distinctes. Les colorations permettent de modéliser des problèmes d’ordonnancement, d’allocation de fréquences ou de registres. Le problème de trouver une coloration propre d’un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d’évaluer quelques heuristiques pour le problème d’e la coloration propre. Nous commençons par dresser un état de l’art des résultats sur ces deux paramètres. Puis nous montrons que déterminer le nombre de Grundy est NP-difficile pour un graphe cordal et polynomial sur le graphe sans P5 bipartis. Ensuite nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. Nombre b-chromatique) et en particulier, nous montrons que décider sir le nombre de Grundy (ou le nombre b-chromatique) d’un graphe G est au moins V(G)-k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d’un grapheA proper coloring of a graph is a function that assigns a color to each vertex with the restriction that adjacent vertices are assigned with distinct colors. Proper colorings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper coloring of a graph with the minimum number of colors is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colorings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy Number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number or a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and p4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least V(G)-k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameter of a graph
41
Skiöld, David, and Kristian Toro. "Comparing Evaluation Heuristics with Human Testers." Thesis, Malmö universitet, Fakulteten för teknik och samhälle (TS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-20637.
Full textAbstract:
Abstract - Through our work we validated the symmetry and leniency heuristics used to evaluate content which has been procedurally generated in a mixed-initiative tool called the Evolutionary Dungeon Designer (EDD). This was done by analyzing and comparing how said heuristics differs from what a human player perceives the metrics to be. A user study was performed for which we developed a game for human testers to try and experience different dungeons, in order to collect the data needed for making the necessary comparisons. We propose potential improvements to the metrics that are intended to represent difficulty and aesthetics used in EDD so that they could better match their intended goals. In general, the testers found the maps to be close to the expected difficulty but there was a big discrepancy in the symmetry metric and how aesthetic they found the maps. We further discuss how the research performed by us could be expanded upon for the purpose of making further improvements to automatic evaluation heuristics, by either making similar research on games of different genres or on games with different game mechanics.
42
Kaparis, Konstantinos. "Knapsack problems : inequalities, separation and heuristics." Thesis, Lancaster University, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.525341.
Full text
43
Lavinus, Joseph W. "Heuristics for laying out information graphs." Thesis, This resource online, 1992. http://scholar.lib.vt.edu/theses/available/etd-12302008-063333/.
Full text
44
Kramer, Oliver. "Self-adaptive heuristics for evolutionary computation." Berlin Heidelberg Springer, 2008. http://d-nb.info/991461002/34.
Full text
45
Fang, Xiao. "Knowledge refreshing: Model, heuristics and applications." Diss., The University of Arizona, 2003. http://hdl.handle.net/10150/289930.
Full textAbstract:
With the wide application of information technology in organizations, especially the rapid growth of E-Business, masses of data have been accumulated. Knowledge Discovery in Databases (KDD) gives organizations the tools to sift through vast data stores to extract knowledge supporting organizational decision making. Most of the KDD research has assumed that data is static and focused on either efficiency improvement of the KDD process (e.g., designing more efficient KDD algorithms) or business applications of KDD. However, data is dynamic in reality (i.e., new data continuously added in). Knowledge discovered using KDD becomes obsolete rapidly, as the discovered knowledge only reflects the status of its dynamic data source when running KDD. Newly added data could bring in new knowledge or invalidate some discovered knowledge. To support effective decision making, knowledge discovered using KDD needs to be updated along with its dynamic data source. In this dissertation, we research on knowledge refreshing, which we define as the process to keep knowledge discovered using KDD up-to-date with its dynamic data source. We propose an analytical model based on the theory of Markov decision process, solutions and heuristics for the knowledge refreshing problem. We also research on how to apply KDD to such application areas as intelligent web portal design and network content management. The knowledge refreshing research identifies and solves a fundamental and general problem appearing in all KDD applications; while the applied KDD research provides a test environment for solutions resulted from the knowledge refreshing research.
46
Alanazi, Fawaz. "Reinforcement learning hyper-heuristics for optimisation." Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/42204/.
Full textAbstract:
Hyper-heuristics are search algorithms which operate on a set of heuristics with the goal of solving a wide range of optimisation problems. It has been observed that different heuristics perform differently between different optimisation problems. A hyper-heuristic combines a set of predefined heuristics, and applies a machine learning technique to predict which heuristic is the most suitable to apply at a given point in time while solving a given problem. A variety of machine learning techniques have been proposed in the literature. Most of the existing machine learning techniques are reinforcement learning mechanisms interacting with the search environment with the goal of adapting the selection of heuristics during the search process. The literature on the theoretical foundation of reinforcement learning hyper-heuristics is almost nonexisting. This work provides theoretical analyses of reinforcement learning hyper-heuristics. The goal is to shed light on the learning capabilities and limitations of reinforcement learning hyper-heuristics. This improves our understanding of these hyper-heuristics, and aid the design of better reinforcement learning hyper-heuristics. It is revealed that the commonly used additive reinforcement learning mechanism, under a mild assumption, chooses asymptotically heuristics uniformly at random. This thesis also proposes the problem of identifying the most suitable heuristic with a given error probability. We show a general lower bound on the time that "every" reinforcement learning hyper-heuristic needs to identify the most suitable heuristic with a given error probability. The results reveal a general limitation to learning achieved by this computational approach. Following our theoretical analysis, different reusable and easyto-implement reinforcement learning hyper-heuristics are proposed in this thesis. The proposed hyper-heuristics are evaluated on well-known combinatorial optimisation problems. One of the proposed reinforcement learning hyper-heuristics outperformed a state-of-the-art algorithm on several benchmark problems of the well-known CHeSC 2011.
47
Rocchi, Elena <1986>. "Model-Based Heuristics for Combinatorial Optimization." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amsdottorato.unibo.it/7301/1/rocchi_elena_tesi.pdf.
Full textAbstract:
Many problems arising in several and different areas of human knowledge share the characteristic of being intractable in real cases. The relevance of the solution of these problems, linked to their domain of action, has given birth to many frameworks of algorithms for solving them. Traditional solution paradigms are represented by exact and heuristic algorithms. In order to overcome limitations of both approaches and obtain better performances, tailored combinations of exact and heuristic methods have been studied, giving birth to a new paradigm for solving hard combinatorial optimization
problems, constituted by model-based metaheuristics. In the present thesis, we deepen the issue of model-based metaheuristics, and present some methods, belonging to this class, applied to the solution of combinatorial
optimization problems.
48
Rocchi, Elena <1986>. "Model-Based Heuristics for Combinatorial Optimization." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amsdottorato.unibo.it/7301/.
Full textAbstract:
Many problems arising in several and different areas of human knowledge share the characteristic of being intractable in real cases. The relevance of the solution of these problems, linked to their domain of action, has given birth to many frameworks of algorithms for solving them. Traditional solution paradigms are represented by exact and heuristic algorithms. In order to overcome limitations of both approaches and obtain better performances, tailored combinations of exact and heuristic methods have been studied, giving birth to a new paradigm for solving hard combinatorial optimization
problems, constituted by model-based metaheuristics. In the present thesis, we deepen the issue of model-based metaheuristics, and present some methods, belonging to this class, applied to the solution of combinatorial
optimization problems.
49
Bergmark, Max. "Tetris: A Heuristic Study : Using height-based weighing functions and breadth-first search heuristics for playing Tetris." Thesis, KTH, Skolan för teknikvetenskap (SCI), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-168306.
Full textAbstract:
This paper studies the performance of height-based weighing functions and compares the results to using the commonly used non height-based weighing functions for holes. For every test performed, the heuristic methods studied in this paper performed better than the commonly used heuristic function. This study also analyses the effect of adding levels of prediction to the heuristic algorithm, which increases the average number of cleared lines by a factor of 85 in total. Utilising these methods can provide increased performance for a Tetris AI. The polynomic weighing functions discussed in this paper provide a performance increase without increasing the needed computation, increasing the number of cleared lines by a factor of 3. The breadth-first search provide a bigger performance increase, but every new level of prediction requires 162 times more computation. Every level increases the number of cleared lines by a factor of 9 from what has been observed in this study.
50
Kim, Dong-Gook. "An Analysis of Ecological and Social Rationality: When are Lexicographic Heuristics Preferred?" unrestricted, 2008. http://etd.gsu.edu/theses/available/etd-08182008-212550/.
Full textAbstract:
Thesis (Ph. D.)--Georgia State University, 2008.Title from file title page. Thomas Whalen, committee chair; Julian Diaz III, C. S. Thachenkary, Rodney Schultz, committee members. Electronic text (168 p. : ill. (some col.)) : digital, PDF file. Description based on contents viewed November 3, 2008. Includes bibliographical references (p. 164-168).