Dissertations / Theses on the topic 'Evolutionary problems'
To see the other types of publications on this topic, follow the link: Evolutionary problems.
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 'Evolutionary problems.'
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
Weicker, Karsten. "Evolutionary algorithms and dynamic optimization problems /." Osnabrück : Der Andere Verl, 2003. http://www.gbv.de/dms/ilmenau/toc/365163716weick.PDF.
Full text
2
Soylu, Banu. "An Evolutionary Algorithm For Multiple Criteria Problems." Phd thesis, METU, 2007. http://etd.lib.metu.edu.tr/upload/2/12608134/index.pdf.
Full textAbstract:
In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights according to the Tchebycheff distance function. Some seed solutions at initial population and a crowding measure also help to achieve satisfactory results.
In order to test the performance of our evolutionary algorithm, we use some continuous and combinatorial problems. The continuous test problems taken from the literature have special difficulties that an evolutionary algorithm has to deal with. Experimental results of our algorithm on these problems are provided.
One of the combinatorial problems we address is the multi-objective knapsack problem. We carry out experiments on test data for this problem given in the literature.
We work on two bi-criteria p-hub location problems and propose an evolutionary algorithm to approximate the Pareto frontiers of these problems. We test the performance of our algorithm on Turkish Postal System (PTT) data set (TPDS), AP (Australian Post) and CAB (US Civil Aeronautics Board) data sets.
The main contribution of this thesis is in the field of developing a multi-objective evolutionary algorithm and applying it to a number of multi-objective continuous and combinatorial optimization problems.
3
Guenther, Chris. "Pseudospectral techniques for non-smooth evolutionary problems." Morgantown, W. Va. : [West Virginia University Libraries], 1998. http://etd.wvu.edu/templates/showETD.cfm?recnum=202.
Full textAbstract:
Thesis (Ph. D.)--West Virginia University, 1998.Title from document title page. Document formatted into pages; contains xi, 116 p. : ill. (some col.) Includes abstract. Includes bibliographical references (p. 94-98).
4
Mason, Andrew J. "Genetic algorithms and scheduling problems." Thesis, University of Cambridge, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.335134.
Full text
5
Demir, Erdem. "Analysis Of Evolutionary Algorithms For Constrained Routing Problems." Master's thesis, METU, 2004. http://etd.lib.metu.edu.tr/upload/12605083/index.pdf.
Full textAbstract:
This study focuses on two types of routing problems based on standard Traveling Salesman Problem, which are TSP with pickup and delivery (TSPPD) and TSP with backhauls (TSPB). In both of these problems, there are two types of customers, i.e. &ldquodelivery customers&rdquo
demanding goods from depot and &ldquo
pickup customers&rdquo
sending goods to depot. The objective is to minimize the cost of the tour that visits every customer once without violating the side constraints. In TSPB, delivery customers should precede the pickup customers, whereas the vehicle capacity should not be exceeded in TSPPD. The aim of the study is to propose good Evolutionary Algorithms (EA) for these two problems and also analyze the adaptability of an EA, originally designed for the standard TSP, to the problems with side constraints. This effort includes commenting on the importance of feasibility of the solutions in the population with respect to these side constraints. Having this in mind, different EA strategies involving feasible or infeasible solutions are designed. These strategies are compared by quantitative experiments realized over a set of problem instances and the results are given.
6
Barkat, Ullah Abu Saleh Shah Muhammad Engineering & Information Technology Australian Defence Force Academy UNSW. "An integrated evolutionary system for solving optimization problems." Awarded by:University of New South Wales - Australian Defence Force Academy. Engineering & Information Technology, 2009. http://handle.unsw.edu.au/1959.4/43764.
Full textAbstract:
Many real-world decision processes require solving optimization problems which may involve different types of constraints such as inequality and equality constraints. The hurdles in solving these Constrained Optimization Problems (COPs) arise from the challenge of searching a huge variable space in order to locate feasible points with acceptable solution quality. Over the last decades Evolutionary Algorithms (EAs) have brought a tremendous advancement in the area of computer science and optimization with their ability to solve various problems. However, EAs have inherent difficulty in dealing with constraints when solving COPs. This thesis presents a new Agent-based Memetic Algorithm (AMA) for solving COPs, where the agents have the ability to independently select a suitable Life Span Learning Process (LSLP) from a set of LSLPs. Each agent represents a candidate solution of the optimization problem and tries to improve its solution through cooperation with other agents. Evolutionary operators consist of only crossover and one of the self-adaptively selected LSLPs. The performance of the proposed algorithm is tested on benchmark problems, and the experimental results show convincing performance. The quality of individuals in the initial population influences the performance of evolutionary algorithms, especially when the feasible region of the constrained optimization problems is very tiny in comparison to the entire search space. This thesis proposes a method that improves the quality of randomly generated initial solutions by sacrificing very little in diversity of the population. The proposed Search Space Reduction Technique (SSRT) is tested using five different existing EAs, including AMA, by solving a number of state-of-the-art test problems and a real world case problem. The experimental results show SSRT improves the solution quality, and speeds up the performance of the algorithms. The handling of equality constraints has long been a difficult issue for evolutionary optimization methods, although several methods are available in the literature for handling functional constraints. In any optimization problems with equality constraints, to satisfy the condition of feasibility and optimality the solution points must lie on each and every equality constraint. This reduces the size of the feasible space and makes it difficult for EAs to locate feasible and optimal solutions. A new Equality Constraint Handling Technique (ECHT) is presented in this thesis, to enhance the performance of AMA in solving constrained optimization problems with equality constraints. The basic concept is to reach a point on the equality constraint from its current position by the selected individual solution and then explore on the constraint landscape. The technique is used as an agent learning process in AMA. The experimental results confirm the improved performance of the proposed algorithm. This thesis also proposes a Modified Genetic Algorithm (MGA) for solving COPs with equality constraints. After achieving inspiring performance in AMA when dealing with equality constraints, the new technique is used in the design of MGA. The experimental results show that the proposed algorithm overcomes the limitations of GA in solving COPs with equality constraints, and provides good quality solutions.
7
Priestley, A. "Lagrange and characteristic Galerkin methods for evolutionary problems." Thesis, University of Oxford, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.376942.
Full text
8
Liu, Wudong. "Evolutionary multiobjective optimisation for expensive and complex problems." Thesis, University of Essex, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.537937.
Full text
9
Garcia, Najera Abel. "Multi-Objective evolutionary algorithms for vehicle routing problems." Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/1069/.
Full textAbstract:
The Vehicle Routing Problem, which main objective is to find the lowest-cost set of routes to deliver goods to customers, has many applications in transportation services. In the past, costs have been mainly associated to the number of routes and the travel distance, however, in real-world problems there exist additional objectives. Since there is no known exact method to efficiently solve the problem in polynomial time, many heuristic techniques have been considered, among which, evolutionary methods have proved to be suitable for solving the problem. Despite this method being able to provide a set of solutions that represent the trade-offs between multiple objectives, very few studies have concentrated on the optimisation of more than one objective, and even fewer have explicitly considered the diversity of solutions, which is crucial for the good performance of any evolutionary computation technique. This thesis proposes a novel Multi-Objective Evolutionary Algorithm to solve two variants of the Vehicle Routing Problem, regarding the optimisation of at least two objectives. This approach incorporates a method for measuring the similarity of solutions, which is used to enhance population diversity, and operators that effectively explore and exploit the search space. The algorithm is applied to typical benchmark problems and empirical analyses indicate that it efficiently solves the variants being studied. Moreover, the proposed method has proved to be competitive with recent approaches and outperforms the successful multi-objective optimiser NSGA-II.
10
Mohammed, Ali Hind. "Behavior study of an evolutionary design for permutation problems." Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCD033.
Full textAbstract:
Cette thèse étudie une combinaison évolutionnaire représentation_croisement pour des problèmes de permutation. Ceux-ci sont très étudiés dans la littérature en raison de leur complexité et de la diversité de leurs applications. Des méthodes efficaces existent pour résoudre les problèmes de permutation. Mais les états de l’art récents montrent que les applications réelles font émerger de nouvelles instances qui sont fortement dynamiques et conjuguent de nombreux objectifs et contraintes, notamment de synchronisation. Cette contribution se concentre sur les approches évolutionnaires. Elle explore en détail le comportement d’une combinaison représentation_croisement donnée. Le but est de vérifier si cette conception évolutive pourrait constituer un moyen complémentaire intéressant de s’attaquer efficacement à certaines contraintes. Ce travail étudie le lien entre la représentation utilisée, les opérateurs de recombinaison choisis et les caractéristiquesdu problème à résoudre, en se focalisant sur une représentation par code de Lehmer et le croisement à k-points. Ceci permet de déduire certaines hypothèses (certaines d’entre elles étant contradictoires) concernant le comportement de lacombinaison de croisements k-points appliqués à la représentation Lehmer. Une phase d’expérience est utilisée pour vérifier ces hypothèses. Elle est réalisée par comparaison avec un codage direct de permutation classique, couplé à un croisement PMX. Des mesures sont utilisées pour observer le comportement des mécanismes évolutifs, à la fois dans l’espace de recherche (en termes de génotype) et dans l’espace objectif (en termes de phénotype et de critère de qualité associé). Les remarques de conclusion, les implications et les directions de recherche futures concluent le travailThis thesis studies an evolutionary representation - crossover combination for permutation problems. These are widely studied in literature due to their hardness and the diversity of their application fields. Efficient methods exist to solve permutation problems. But several recent surveys show that real applications induce new instances that are strongly dynamic and characterized by the conjunction of particular constraints and objectives, particularly synchronization. This contribution focuses on evolutionary approaches. It explores in details the behaviour of a given representation crossovercombination. The goal is to check if this evolutionary design could be an interesting complementary way to tackle efficiently some of the constraints. This work studies the link between the representation used, the chosen recombination operators and the characteristics of the problem to be solved, focusing on Lehmer code representation and kpoint crossover. This review permits to deduce some assumptions (some of them being contradictory) regarding the behaviour of the Lehmer Code representation k-point crossover combination. Experiments are used to verify these assumptions, performed by comparison with permutation encoding coupled with PMX crossover. Measurements are used to observe the behavior of evolutionary mechanisms, both in the search space (in terms of genotype) and in the objective space ( in terms of phenotype and associated quality criterion). Concluding remarks, implications and future research directions conclude the work
11
Andrade, Carlos Eduardo de 1981. "Evolutionary algorithms for some problems in telecommunications = Algoritmos evolutivos para alguns problemas em telecomunicações." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275653.
Full textAbstract:
Orientadores: Flavio Keidi Miyazawa, Mauricio Guilherme de Carvalho ResendeTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-27T21:53:09Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_D.pdf: 4654702 bytes, checksum: 566cb3ea8fc876147ffa6df2ec8482b3 (MD5) Previous issue date: 2015
Resumo: Nos últimos anos, as redes de telecomunicação tem experienciado um grande aumento no fluxo de dados. Desde a utilização massiva de vídeo sob demanda até o incontável número de dispositivos móveis trocando texto e vídeo, o tráfego alcançou uma escala capaz de superar a capacidade das redes atuais. Portanto, as companhias de telecomunicação ao redor do mundo tem sido forçadas a aumentar a capacidade de suas redes para servir esta crescente demanda. Como o custo de instalar uma infraestrutura de rede é geralmente muito grande, o projeto de redes usa fortemente ferramentas de otimização para manter os custos tão baixos quanto possível. Nesta tese, nós analisamos vários aspectos do projeto e implementação de redes de telecomunicação. Primeiramente, nós apresentamos um novo problema de projeto de redes usado para servir demandas sem fio de dispositivos móveis e rotear tal tráfego para a rede principal. Tais redes de acesso são baseadas em tecnologias sem fio modernos como Wi-Fi, LTE e HSPA. Este problema consideramos várias restrições reais e é difícil de ser resolvido. Nós estudamos casos reais nas vizinhanças de uma grande cidade nos Estados Unidos. Em seguida, nós apresentamos uma variação do problema de localização de hubs usado para modelar as redes principais (backbones ou laços centrais). Este problema também pode ser utilizado para modelar redes de transporte de cargas e passageiros. Nós também estudamos o problema de clusterização correlacionada com sobreposições usado para modelar o comportamento dos usuários quando utilizam seus equipamentos móveis. Neste problema, nós podemos rotular um objeto usando múltiplos rótulos e analisar a conexão entre eles. Este problema é adequado para análise de mobilidade de equipamentos que pode ser usada para estimar o tráfego em uma dada região. E finalmente, nós analisamos o licenciamento de espectro sobre uma perspectiva governamental. Nestes casos, uma agência do governo deseja vender licenças para companhias de telecomunicação para que operem em uma dada faixa de espectro. Este processo usualmente é conduzido usando leilões combinatoriais. Para todos problemas, nós propomos algoritmos genéticos de chaves aleatórias viciadas e modelos de programação linear inteira mista para resolvê-los (exceto para o problema de clusterização correlacionada com sobreposição, devido sua natureza não-linear). Os algoritmos que propusemos foram capazes de superar algoritmos do estado da arte para todos problemas
Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances
Abstract: In last twenty years, telecommunication networks have experienced a huge increase in data utilization. From massive on-demand video to uncountable mobile devices exchanging text and video, traffic reached scales that overcame the network capacities. Therefore, telecommunication companies around the world have been forced to increase their capacity to serve this increasing demand. As the cost to deploy network infrastructure is usually very large, the design of a network heavily uses optimization tools to keep costs as low as possible. In this thesis, we analyze several aspects of the design and deployment of communication networks. First, we present a new network design problem used to serve wireless demands from mobile devices and route the traffic to the core network. Such access networks are based on modern wireless access technologies such as Wi-Fi, LTE, and HSPA. This problem has several real world constraints and it is hard to solve. We study real cases of the vicinity of a large city in the United States. Following, we present a variation of the hub-location problem used to model these core networks. Such problem is also suitable to model transportation networks. We also study the overlapping correlation clustering problem used to model the user's behavior when using their mobile devices. In such problem, one can label an object with multiple labels and analyzes the connections between them. Although this problem is very generic, it is suitable to analyze device mobility which can be used to estimate traffic in geographical regions. Finally, we analyze spectrum licensing from a governmental perspective. In these cases, a governmental agency wants to sell rights for telecommunication companies to operate over a given spectrum range. This process usually is conducted using combinatorial auctions. For all problems we propose biased random-key genetic algorithms and mixed integer linear programming models (except in the case of the overlapping correlation clustering problem due its non-linear nature). Our algorithms were able to overcome the state of the art algorithms for all problems
Doutorado
Ciência da Computação
Doutor em Ciência da Computação
12
Di, Pietro Anthony. "Optimising evolutionary strategies for problems with varying noise strength." University of Western Australia. School of Computer Science and Software Engineering, 2007. http://theses.library.uwa.edu.au/adt-WU2007.0210.
Full textAbstract:
For many real-world applications of evolutionary computation, the fitness function is obscured by random noise. This interferes with the evaluation and selection processes and adversely affects the performance of the algorithm. Noise can be effectively eliminated by averaging a large number of fitness samples for each candidate, but the number of samples used per candidate (the resampling rate) required to achieve this is usually prohibitively large and time-consuming. Hence there is a practical need for algorithms that handle noise without eliminating it. Moreover, the amount of noise (noise strength and distribution) may vary throughout the search space, further complicating matters. We study noisy problems for which the noise strength varies throughout the search space. Such problems have generally been ignored by previous work, which has instead generally focussed on the specific case where the noise strength is the same at all points in the search domain. However, this need not be the case, and indeed this assumption is false for many applications. For example, in games of chance such as Poker, some strategies may be more conservative than others and therefore less affected by the inherent noise of the game. This thesis makes three significant contributions in the field of noisy fitness functions: We present the concept of dynamic resampling. Dynamic resampling is a technique that varies the resampling rate based on the noise strength and fitness for each candidate individually. This technique is designed to exploit the variation in noise strength and fitness to yield a more efficient algorithm. We present several dynamic resampling algorithms and give results that show that dynamic resampling can perform significantly better than the standard resampling technique that is usually used by the optimisation community, and that dynamic resampling algorithms that vary their resampling rates based on both noise strength and fitness can perform better than algorithms that vary their resampling rate based on only one of the above. We study a specific class of noisy fitness functions for which we counterintuitively find that it is better to use a higher resampling rate in regions of lower noise strength, and vice versa. We investigate how the evolutionary search operates on such problems, explain why this is the case, and present a hypothesis (with supporting evidence) for classifying such problems. We present an adaptive engine that automatically tunes the noise compensation parameters of the search during the run, thereby eliminating the need for the user to choose these parameters ahead of time. This means that our techniques can be readily applied to real-world problems without requiring the user to have specialised domain knowledge of the problem that they wish to solve. These three major contributions present a significant addition to the body of knowledge for noisy fitness functions. Indeed, this thesis is the first work specifically to examine the implications of noise strength that varies throughout the search domain for a variety of noise landscapes, and thus starts to fill a large void in the literature on noisy fitness functions.
13
Smirnov, Oleg. "Formal evolutionary modeling and the problems of political science /." view abstract or download file of text, 2005. http://wwwlib.umi.com/cr/uoregon/fullcit?p3190550.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 2005.Typescript. Includes vita and abstract. Includes bibliographical references (leaves 113-131). Also available for download via the World Wide Web; free to University of Oregon users.
14
Britt, Winard. "A meta-parallel evolutionary system for solving optimization problems." Auburn, Ala., 2007. http://repo.lib.auburn.edu/2007%20Spring%20Theses/BRITT_WINARD_18.pdf.
Full text
15
Xing, Huanlai. "Evolutionary approaches for network coding based multicast routing problems." Thesis, University of Nottingham, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.596088.
Full textAbstract:
Network coding is an emerging technique in communication networks, where the intennediate nodes are allowed to combine (code) the data received from different incoming links if necessary. The thesis investigates a nwnber of routing problems for network coding based multicast (NCM). which belong to combinatorial optimization problems (COPs). Evolutionary algorithms (EAs) are used to srudy the problems. The work of the thesis are described below. We propose three EAs for the network coding resource minimization (NCRM) problem where the objective is to minimize the number of coding operations while meeting the data rate requirement based on NCM. The three EAs are population based incremental learning (PBIL), compact genetic algorithm (cGA) and path-oriented encoding EA (PEA), all specially developed for tackling the NCRM problem. Ta support real-time multimedia applications, we for the first time extend the NCRM problem by introducing the maximum transmission delay into the problem as a constraint, which is called the delay constrained NCRM problem. Benchmark datasets are created based on the datasels for the NCRM problem. Three EAs originally used for the NCRM problem are adapted for the delay constrained NCRM ptoblem, including GAs and PBIL. To study the conflicting interests of service providers and network users, we for the first time fonnulate a multi-objective NCM routing problem considering two objectives, cost and delay. The cost is the summation of the coding cost and link cost incurred in the NCM. The delay is the maximum transmission delay of paths in the NCM. This problem is referred to as the cost-delay bi-objective optimization (CDBO) problem. Benchmark datasets for the delay constrained NCRM problem are used to generate the datasets for the CDBO problem. Elitist nondominated sorting GA (NSGA-II) is adapted for the CDBO problem.
16
Guo, Qiang. "Evolutionary algorithms and hyper-heuristics for orthogonal packing problems." Thesis, University of Nottingham, 2011. http://eprints.nottingham.ac.uk/29311/.
Full textAbstract:
This thesis investigates two major classes of Evolutionary Algorithms, Genetic Algorithms (GAs) and Evolution Strategies (ESs), and their application to the Orthogonal Packing Problems (OPP). OPP are canonical models for NP-hard problems, the class of problems widely conceived to be unsolvable on a polynomial deterministic Turing machine, although they underlie many optimisation problems in the real world. With the increasing power of modern computers, GAs and ESs have been developed in the past decades to provide high quality solutions for a wide range of optimisation and learning problems. These algorithms are inspired by Darwinian nature selection mechanism that iteratively select better solutions in populations derived from recombining and mutating existing solutions. The algorithms have gained huge success in many areas, however, being stochastic processes, the algorithms' behaviour on different problems is still far from being fully understood. The work of this thesis provides insights to better understand both the algorithms and the problems. The thesis begins with an investigation of hyper-heuristics as a more general search paradigm based on standard EAs. Hyper-heuristics are shown to be able to overcome the difficulty of many standard approaches which only search in partial solution space. The thesis also looks into the fundamental theory of GAs, the schemata theorem and the building block hypothesis, by developing the Grouping Genetic Algorithms (GGA) for high dimensional problems and providing supportive yet qualified empirical evidences for the hypothesis. Realising the difficulties of genetic encoding over combinatorial search domains, the thesis proposes a phenotype representation together with Evolution Strategies that operates on such representation. ESs were previously applied mainly to continuous numerical optimisation, therefore being less understood when searching in combinatorial domains. The work in this thesis develops highly competent ES algorithms for OPP and opens the door for future research in this area.
17
Jin, Nanlin. "Constraint-based co-evolutionary genetic programming for bargaining problems." Thesis, University of Essex, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.438140.
Full text
18
Trostorff, Sascha. "Exponential Stability and Initial Value Problems for Evolutionary Equations." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2018. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-236494.
Full textAbstract:
The thesis deals with so-called evolutionary equations, a class of abstract linear operator equations, which cover a huge class of partial differential equation with and without memory. We provide a unified Hilbert space framework for the well-posedness of such equations. Moreover, we inspect the exponential stability of those problems and construct spaces of admissible inital values and pre-histories, on which a strongly continuous semigroup could be associated with the given problem. The theoretical results are illustrated by several examples.
19
Thompson, Evan Benjamin. "The application of genetic and evolutionary algorithms to spanning tree problems." Thesis, University of Exeter, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.288698.
Full text
20
Wong, King Hei. "Solving combinatorial based chemical engineering problems via parallel evolutionary approaches /." View abstract or full-text, 2009. http://library.ust.hk/cgi/db/thesis.pl?CBME%202010%20WONGK.
Full text
21
Gigli, Elena. "Evolutionary genetics of homo neanderthalensis :adaptive traits and methodological problems." Doctoral thesis, Universitat Pompeu Fabra, 2011. http://hdl.handle.net/10803/77656.
Full textAbstract:
The evolutionary history of H. neanderthalensis, interwoven with that of H. sapiens, has always fascinated the scientific world. Recent adavncess in paleogenetics shedds new light on the phylogenetic relationship between Neandertals and modern humans. The studies developed in this thesis intend principally to control the contaminants through the development of an anti-contamination protocol for decreasing the human contamination in pre-laboratory phases. We designed a PCR-based method specific for reducing human contamination during the laboratory analysis, and we analyzed the fragmentation pattern of the ancient sequences by massively parallel sequencing technologies. Furthermore, we studied two nuclear genes, TAS2R38 -associated to bitter taste perception- and ABO blood group system –involved in natural immunity- that provide specific information on aspects of the Neanderthal phenotype and adaptation.La historia evolutiva d’H. neanderthalensis, imbricada amb la d’H. sapiens, ha fascinat sempre el món científic. Avenços recents en paleogenètica aporten una nova llum sobre la rel•lació filogenètica entre els neandertals i els humans moderns. Els treballs d’aquesta tesi intenten principalment controlar els contaminants mitjançant el desenvolupament d’un protocol d’anti-contaminació que disminueixi la contaminació humana de les mostres en la fase de pre-laboratori. Hem desenvolupat un mètode basat en la PCR específic per a reduïr els contaminants humans durant l’anàlisi en el laboratori, i hem analitzat el patró de fragmentació de les seqüències antigues amb tècniques de seqüenciació massiva en paral•lel. A més a més, hem estudiat dos gens nuclears, el TAS2R38 –associat a la percepció del gust amarg- i el grup sanguini ABO –implicat en la immunitat natural- que proporcionen informació específca sobre aspectes del fenotip i de les adaptacions dels neandertals.
22
Cryan, Mary Elizabeth. "Learning and approximation algorithms for problems motivated by evolutionary trees." Thesis, University of Warwick, 1999. http://wrap.warwick.ac.uk/61093/.
Full textAbstract:
In this thesis we consider some computational problems motivated by the biological problem of reconstructing evolutionary trees. In this thesis, we are concerned with the design and analysis of efficient algorithms for clearly defined combinatorial problems motived by this application area. We present results for two different kinds of problem. Our first problem is motivated by models of evolution that describe the evolution of biological species in terms of a stochastic process that alters the DNA of species. The particular stochastic model that we considered is called the Two-State General Markov Model. In this model, an evolutionary tree can be associated with a distribution on the different "patterns" that may appear among the sequences for all the species in the evolutionary tree. Then the data for a collection of species whose evolutionary tree is unknown can be viewed as samples from this (unknown) distribution. An interesting problem asks whether we can use samples from an unknown evolutionary tree M to find another tree M*for those species, so that the distribution of M* is similar to that of M. This is essentially a PAC-learning problem ("Probably Approximately Correct") in the sense of Valiant and Kearns et al. Our results show that evolutionary trees in the Two-State General Markov can be efficiently PAC-learned in the variation distance metric using a "reasonable" number of samples. The two other problems that we consider are combinatorial problems that are also motivated by evolutionary tree construction. The input to each of these problems consists of a fixed tree topology whose leaves are bijectively labelled by the elements of a species set, as well as data for those species. Both problems involve labelling the internal nodes in the fixed topology in order to minimize some function on that tree (both functions that we consider are assumed to test the quality of the tree topology in some way). The two problems that we consider are known to be NP-hard. Our contribution is to present efficient approximation algorithms for both problems.
23
Elbergali, Abdalla Kh. "Factor analysis : theory and applications to evolutionary problems in chemometrics." Thesis, University of Bristol, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.282138.
Full text
24
CRUZ, ANDRE VARGAS ABS DA. "QUANTUM-INSPIRED EVOLUTIONARY ALGORITHMS FOR PROBLEMS BASED ON NUMERICAL REPRESENTATION." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2007. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=10640@1.
Full textAbstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICODesde que foram propostos como método de otimização, os algoritmos evolutivos têm sido usados com sucesso para resolver problemas complexos nas mais diversas áreas como, por exemplo, o projeto automático de circuitos e equipamentos, planejamento de tarefas, engenharia de software e mineração de dados, entre tantos outros. Este sucesso se deve, entre outras coisas, ao fato desta classe de algoritmos não necessitar de formulações matemáticas rigorosas a respeito do problema que se deseja otimizar, além de oferecer um alto grau de paralelismo no processo de busca. No entanto, alguns problemas são computacionalmente custosos no que diz respeito à avaliação das soluções durante o processo de busca, tornando a otimização por algoritmos evolutivos um processo lento para situações onde se deseja uma resposta rápida do algoritmo (como por exemplo, problemas de otimização online). Diversas maneiras de se contornar este problema, através da aceleração da convergência para boas soluções, foram propostas, entre as quais destacam-se os Algoritmos Culturais e os Algoritmos Co-Evolutivos. No entanto, estes algoritmos ainda têm a necessidade de avaliar muitas soluções a cada etapa do processo de otimização. Em problemas onde esta avaliação é computacionalmente custosa, a otimização pode levar um tempo proibitivo para alcançar soluções ótimas. Este trabalho propõe um novo algoritmo evolutivo para problemas de otimização numérica (Algoritmo Evolutivo com Inspiração Quântica usando Representação Real - AEIQ- R), inspirado no conceito de múltiplos universos da física quântica, que permite realizar o processo de otimização com um menor número de avaliações de soluções. O trabalho apresenta a modelagem deste algoritmo para a solução de problemas benchmark de otimização numérica, assim como no treinamento de redes neurais recorrentes em problemas de aprendizado supervisionado de séries temporais e em aprendizado por reforço em tarefas de controle. Os resultados obtidos demonstram a eficiência desse algoritmo na solução destes tipos de problemas.
Since they were proposed as an optimization method, the evolutionary algorithms have been successfully used for solving complex problems in several areas such as, for example, the automatic design of electronic circuits and equipments, task planning and scheduling, software engineering and data mining, among many others. This success is due, among many other things, to the fact that this class of algorithms does not need rigorous mathematical formulations regarding the problem to be optimized, and also because it offers a high degree of parallelism in the search process. However, some problems are computationally intensive when it concerns the evaluation of solutions during the search process, making the optimization by evolutionary algorithms a slow process for situations where a quick response from the algorithm is desired (for instance, in online optimization problems). Several ways to overcome this problem, by speeding up convergence time, were proposed, including Cultural Algorithms and Coevolutionary Algorithms. However, these algorithms still have the need to evaluate many solutions on each step of the optimization process. In problems where this evaluation is computationally expensive, the optimization might take a prohibitive time to reach optimal solutions. This work proposes a new evolutionary algorithm for numerical optimization problems (Quantum- Inspired Evolutionary Algorithm for Problems based on Numerical Representation - QIEA-R), inspired in the concept of quantum superposition, which allows the optimization process to be carried on with a smaller number of evaluations. The work presents the modelling for this algorithm for solving benchmark numerical optimization problems, and for training recurrent neural networks in supervised learning and reinforcement learning. The results show the good performance of this algorithm in solving these kinds of problems.
25
Hatzakis, Iason. "Multi-objective evolutionary methods for time-changing portfolio optimization problems." Thesis, Massachusetts Institute of Technology, 2007. http://hdl.handle.net/1721.1/42307.
Full textAbstract:
Thesis (S.M. in Ocean Systems Management)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering, 2007.Includes bibliographical references (p. 77-79).
This thesis is focused on the discovery of efficient asset allocations with the use of evolutionary algorithms. The portfolio optimization problem is a multi-objective optimization problem for the conflicting criteria of risk and expected return. Furthermore the nonstationary nature of the market makes it a time-changing problem in which the optimal solution is likely to change as time advances. Hence the portfolio optimization problem naturally lends itself to an exploration with multi-objective evolutionary algorithms for time-changing environments. Two different risk objectives are treated in this work: the established measure of standard deviation, and the Value-at-Risk. While standard deviation is convex as an objective function, historical Value-at-Risk is non-convex and often discontinuous, making it difficult to approach with most conventional optimization techniques. The value of evolutionary algorithms is demonstrated in this case by their ability to handle the Value-at-Risk objective, since they do not have any convexity or differentiability requirements. The D-QMOO time-changing evolutionary algorithm is applied to the portfolio optimization problem. Part of the philosophy behind D-QMOO is the exploitation of predictability in the optimal solution's motion. This problem however is characterized by minimal or non-existent predictability, since asset prices are hard to forecast. This encourages the development of new time-changing optimization heuristics for the efficient solution of this problem. Both the static and time-changing forms of the problem are treated and characteristic results are presented. The methodologies proposed are verified through comparison with established methods and through the performance of the produced portfolios as compared to the overall market. In general, this work demonstrates the potential for the use of evolutionary algorithms in time-changing portfolio optimization as a tool for portfolio managers and financial engineers.
by Iason Hatzakis.
S.M.in Ocean Systems Management
26
Jayachandran, Jayakanth. "Improving resiliency using graph based evolutionary algorithms." Diss., Rolla, Mo. : Missouri University of Science and Technology, 2010. http://scholarsmine.mst.edu/thesis/pdf/Jayachandran_09007dcc807d6ba6.pdf.
Full textAbstract:
Thesis (M.S.)--Missouri University of Science and Technology, 2010.Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed July 19, 2010) Includes bibliographical references (p. 56-62).
27
Fu, Ser-Geon. "Genetic and evolutionary protocols for solving distributed asymmetric constraint satisfaction problems." Auburn, Ala., 2007. http://repo.lib.auburn.edu/2007%20Spring%20Dissertations/FU_SER-GEON_10.pdf.
Full text
28
Androulakakis, Pavlos. "Analysis of Evolutionary Algorithms in the Control of Path Planning Problems." Wright State University / OhioLINK, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=wright1535549741081137.
Full text
29
Mirjalili, Seyedali. "Confidence-based Robust Optimisation of Engineering Design Problems." Thesis, Griffith University, 2016. http://hdl.handle.net/10072/366690.
Full textAbstract:
Robust optimisation refers to the process of combining good performance with low sensitivity to possible perturbations. Due to the presence of different un- certainties when optimising real problems, failure to employ robust optimisation techniques may result in finding unreliable solutions. Robust optimisation techniques play key roles in finding reliable solutions when considering possible uncertainties during optimisation.
Evolutionary optimisation algorithms have become very popular for solving real problems in science and industry mainly due to simplicity, gradient-free mechanism, and flexibility. Such techniques have been employed widely as very reliable alternatives to mathematical optimisation approaches for tackling diffi- culties of real search spaces such as constraints, local optima, multiple objectives, and uncertainties. Despite the advances in considering the first three difficulties in the literature, there is significant room for further improvements in the area of robust optimisation, especially combined with multi-objective approaches.
Finding optimal solutions that are less sensitive to perturbations requires a highly systematic robust optimisation algorithm design process. This includes designing challenging robust test problems to compare algorithms, performance metrics to measure by how much one robust algorithm is better than another, and computationally cheap robust algorithms to find robust solutions for optimi- sation problems. The first two phases of a systematic algorithm design process, developing test functions and performance metrics, are prerequisite to the third phase, algorithm development. Firstly, this thesis identifies the current gaps in the literature relating to each of these phases to establish a systematic robust algorithm design process as follows:
The need for more standard and challenging robust test functions for both single- and multi-objective algorithms.
The need for more standard performance metrics for quantifying the per- formance of robust multi-objective algorithms.
The need for more investigation and analysis of the current robustness metrics.
High computational cost of the current robust optimisation techniques that rely on additional function evaluations.
Low reliability of the current robust optimisation techniques that rely on the search history (sampled points during optimisation).Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
30
Li, Miqing. "Evolutionary many-objective optimisation : pushing the boundaries." Thesis, Brunel University, 2015. http://bura.brunel.ac.uk/handle/2438/11778.
Full textAbstract:
Many-objective optimisation poses great challenges to evolutionary algorithms. To start with, the ineffectiveness of the Pareto dominance relation, which is the most important criterion in multi-objective optimisation, results in the underperformance of traditional Pareto-based algorithms. Also, the aggravation of the conflict between proximity and diversity, along with increasing time or space requirement as well as parameter sensitivity, has become key barriers to the design of effective many-objective optimisation algorithms. Furthermore, the infeasibility of solutions' direct observation can lead to serious difficulties in algorithms' performance investigation and comparison. In this thesis, we address these challenges, aiming to make evolutionary algorithms as effective in many-objective optimisation as in two- or three-objective optimisation. First, we significantly enhance Pareto-based algorithms to make them suitable for many-objective optimisation by placing individuals with poor proximity into crowded regions so that these individuals can have a better chance to be eliminated. Second, we propose a grid-based evolutionary algorithm which explores the potential of the grid to deal with many-objective optimisation problems. Third, we present a bi-goal evolution framework that converts many objectives of a given problem into two objectives regarding proximity and diversity, thus creating an optimisation problem in which the objectives are the goals of the search process itself. Fourth, we propose a comprehensive performance indicator to compare evolutionary algorithms in optimisation problems with various Pareto front shapes and any objective dimensionality. Finally, we construct a test problem to aid the visual investigation of evolutionary search, with its Pareto optimal solutions in a two-dimensional decision space having similar distribution to their images in a higher-dimensional objective space. The work reported in this thesis is the outcome of innovative attempts at addressing some of the most challenging problems in evolutionary many-objective optimisation. This research has not only made some of the existing approaches, such as Pareto-based or grid-based algorithms that were traditionally regarded as unsuitable, now effective for many-objective optimisation, but also pushed other important boundaries with novel ideas including bi-goal evolution, a comprehensive performance indicator and a test problem for visual investigation. All the proposed algorithms have been systematically evaluated against existing state of the arts, and some of these algorithms have already been taken up by researchers and practitioners in the field.
31
Urquhart, Neil B. "Solving real-world routing problems using evolutionary algorithms and multi-agent-systems." Thesis, Edinburgh Napier University, 2003. http://researchrepository.napier.ac.uk/Output/2748.
Full textAbstract:
This thesis investigates the solving of routing problems using Evolutionary Algorithms (EAs). Routing problems are known to be hard and may possess complex search spaces. Evolutionary algorithms are potentially powerful tools for finding solutions within complex search spaces. The problem investigated is the routing of deliveries to households within an urban environment; the most common instance of this problem is that of daily postal deliveries. A representation known as Street Based Routing (SBR) is presented. This is a problem representation that makes use of the real world groupings of streets and houses. This representation is an indirect problem representation designed specifically for use with EAs. The SBR representation is incorporated within an EA and used to construct delivery routes around a variety of problem instances. The EA based system is compared against a Travelling Salesman Problem (TSP) solver, and the results are presented. The EA based system produces routes that are on average slightly longer than those produced by the TSP solver. Real world problems may often involve the construction of a network of delivery routes that are subject to multiple hard and soft constraints. A Multi Agent System (MAS) based framework for building delivery networks is presented that makes use of the SBR based EA presented earlier. Each agent within the system uses an EA to construct a single route. Agents may exchange work (via auctions or by directly negotiated exchanges) allowing the optimisation of their route. It is demonstrated that this approach has much potential and is capable of constructing delivery networks meeting set constraints, over a range of problem instances and constraint values.
32
Raj, Ashish. "Evolutionary Optimization Algorithms for Nonlinear Systems." DigitalCommons@USU, 2013. http://digitalcommons.usu.edu/etd/1520.
Full textAbstract:
Many real world problems in science and engineering can be treated as optimization problems with multiple objectives or criteria. The demand for fast and robust stochastic algorithms to cater to the optimization needs is very high. When the cost function for the problem is nonlinear and non-differentiable, direct search approaches are the methods of choice. Many such approaches use the greedy criterion, which is based on accepting the new parameter vector only if it reduces the value of the cost function. This could result in fast convergence, but also in misconvergence where it could lead the vectors to get trapped in local minima. Inherently, parallel search techniques have more exploratory power. These techniques discourage premature convergence and consequently, there are some candidate solution vectors which do not converge to the global minimum solution at any point of time. Rather, they constantly explore the whole search space for other possible solutions. In this thesis, we concentrate on benchmarking three popular algorithms: Real-valued Genetic Algorithm (RGA), Particle Swarm Optimization (PSO), and Differential Evolution (DE). The DE algorithm is found to out-perform the other algorithms in fast convergence and in attaining low-cost function values. The DE algorithm is selected and used to build a model for forecasting auroral oval boundaries during a solar storm event. This is compared against an established model by Feldstein and Starkov. As an extended study, the ability of the DE is further put into test in another example of a nonlinear system study, by using it to study and design phase-locked loop circuits. In particular, the algorithm is used to obtain circuit parameters when frequency steps are applied at the input at particular instances.
33
Muthuswamy, Shanthi. "Discrete particle swarm optimization algorithms for orienteering and team orienteering problems." Diss., Online access via UMI:, 2009.
Find full text
34
Asco, Amadeo. "Constructive and evolutionary algorithms for airport baggage sorting station and gate assignment problems." Thesis, University of Nottingham, 2013. http://eprints.nottingham.ac.uk/13784/.
Full textAbstract:
Correct assignment of airport resources can greatly affect the quality of service which airlines and airports provide to their customers. Good assignments can help airlines and airports to keep to published schedules, by minimising changes in these schedules and reducing delays. Given the expected increases in civil air traffic, the complexities of resource scheduling and assignment continue to increase. For this reason, as well as the dynamic nature of the problems, scheduling and assignment are becoming increasingly more difficult. The assignment of baggage sorting stations to flights is one of the resource assignment problems at an airport, and like many other real world optimisation problems, it naturally has several objectives, which conflict with each other. A model of the problem is presented, different approaches to obtaining good solutions are looked at and studied to gain an insight into their qualities. Furthermore, algorithms are studied to improve the already good solutions obtained by the approaches considered and their performance is studied where some characteristics of the problem change, such as the number of baggage sorting stations or the topology of the airport. Changes to the flight schedule on the day of operation may invalidate previous assignments of flights to resources. These perturbations may not only affect the disrupted flights but also other flights already assigned. Some existing approaches are looked at, and others are suggested to take account of these potential perturbations at the time the assignments are generated with the aim of mitigating their detrimental effect on the day of operation. The constructive search algorithms and robustness methods are potentially important in a wider variety of problems other than the Airport Baggage Sorting Station Assignment Problem (ABSSAP). By way of illustration, the same techniques are applied to the widely studied Airport Gate Assignment Problem (AGAP).
35
Syberfeldt, Anna. "A multi-objective evolutionary approach to simulation-based optimisation of real-world problems." Thesis, De Montfort University, 2009. http://hdl.handle.net/2086/2770.
Full textAbstract:
This thesis presents a novel evolutionary optimisation algorithm that can improve the quality of solutions in simulation-based optimisation. Simulation-based optimisation is the process of finding optimal parameter settings without explicitly examining each possible configuration of settings. An optimisation algorithm generates potential configurations and sends these to the simulation, which acts as an evaluation function. The evaluation results are used to refine the optimisation such that it eventually returns a high-quality solution. The algorithm described in this thesis integrates multi-objective optimisation, parallelism, surrogate usage, and noise handling in a unique way for dealing with simulation-based optimisation problems incurred by these characteristics. In order to handle multiple, conflicting optimisation objectives, the algorithm uses a Pareto approach in which the set of best trade-off solutions is searched for and presented to the user. The algorithm supports a high degree of parallelism by adopting an asynchronous master-slave parallelisation model in combination with an incremental population refinement strategy. A surrogate evaluation function is adopted in the algorithm to quickly identify promising candidate solutions and filter out poor ones. A novel technique based on inheritance is used to compensate for the uncertainties associated with the approximative surrogate evaluations. Furthermore, a novel technique for multi-objective problems that effectively reduces noise by adopting a dynamic procedure in resampling solutions is used to tackle the problem of real-world unpredictability (noise). The proposed algorithm is evaluated on benchmark problems and two complex real-world problems of manufacturing optimisation. The first real-world problem concerns the optimisation of a production cell at Volvo Aero, while the second one concerns the optimisation of a camshaft machining line at Volvo Cars Engine. The results from the optimisations show that the algorithm finds better solutions for all the problems considered than existing, similar algorithms. The new techniques for dealing with surrogate imprecision and noise used in the algorithm are identified as key reasons for the good performance.
36
Fu, Ser-Geon. "Genetic and evolionary protocols for solving distributed asymmetric contraint satisfaction problems." Auburn, Ala., 2007. http://repo.lib.auburn.edu/07M%20Dissertations/FU_SER-GEON_10.pdf.
Full text
37
Cameron, Mark A., and Mark Cameron@csiro au. "A Problem Model for Decision Support Systems." The Australian National University. Faculty of Engineering and Information Technology, 2000. http://thesis.anu.edu.au./public/adt-ANU20020717.144031.
Full textAbstract:
This body of research focuses on supporting problem-stakeholders, decision-makers and
problem-solvers faced with an ill-defined and complex real world problem. An ill-defined
problem has a characteristic trait of continual refinement. That is, the definition
of the problem changes throughout the problem investigation and resolution process.
The central theme of this research is that a support system should provide problem
stakeholders with a problem definition model for constructing and manipulating a
representation of the definition of the problem as they understand it. The approach
adopted herein is to first develop a problem definition model for ill-defined problems
the 6-Component problem definition model. With this model, it is then possible to move
on to identifying the types of changes or modifications to the problem definition that
problem stakeholders, decision makers and problem solvers may wish to explore.
Importantly, there must be a connection between the surface representation of the
problem and the underlying implementation of the support system. This research argues
that by focusing the support system around the problem definition, it is possible to
reduce the mismatch between the problem objectives and the representation of the
problem that the support system offers. This research uses the Unified Modelling
Language to record and explore the requirements that problem stakeholders, faced with
an evolving problem definition, place on a support system. The 6-Component problem
definition model is then embedded within a design for an evolutionary support system.
This embedding, supported by collaboration diagrams, shows how a system using the
6-Component problem definition model will support stakeholders in their exploration,
evaluation and resolution of an ill-defined and complex real-world problem. A case
study provides validation of the effectiveness of the 6-Component problem definition
model proposed and developed in this work. The case study uses the 6-Component
problem definition model as a basis for implementing the Integration Workbench, an
evolutionary support system for land-use planning. Stakeholders explore, communicate,
evaluate and resolve the Tasmanian Regional Forest Agreement problem with
assistance from the Integration Workbench.
38
Aldogan, Deniz. "Memetic Algorithms For Timetabling Problems In Private Schools." Master's thesis, METU, 2005. http://etd.lib.metu.edu.tr/upload/3/12606218/index.pdf.
Full textAbstract:
The aim of this study is to introduce a real-world timetabling problem that exists in some private schools in Turkey and to solve such problem instances utilizing memetic algorithms.
Being a new type of problem and for privacy reasons, there is no real data available. Hence for benchmarking purposes, a random data generator has been implemented. Memetic algorithms (MAs) combining genetic algorithms and hill-climbing are applied to solve synthetic problem instances produced by this generator.
Different types of recombination and mutation operators based on the hierarchical structure of the timetabling problem are proposed. A modified version of the violation directed hierarchical hill-climbing method (VDHC), introduced by A. Alkan and E. Ozcan, coordinates the process of 12 different low-level hill-climbing operators grouped in two distinct arrangements that attempt to resolve corresponding constraint violations. VDHC is an adaptive method advocating cooperation of hill-climbing operators. In addition, MAs with VDHC are compared with different versions of multimeme algorithms and pure genetic algorithms.
Experimental results on synthetic benchmark data set indicate the success of the proposed MA.
39
Tometzki, Thomas [Verfasser]. "Hybrid Evolutionary Algorithms for the Efficient Solution of Planning Problems under Uncertainty / Thomas Tometzki." Aachen : Shaker, 2011. http://d-nb.info/1070152730/34.
Full text
40
Abo, Alsabeh Rewayda. "An evolutionary approach to solving the maximum size consecutive ones submatrix and related problems." Thesis, University of Essex, 2017. http://repository.essex.ac.uk/20792/.
Full textAbstract:
The Consecutive Ones Submatrix (C1S) has a vital role in real world applications. Consequently, there are continuous concern and demand to solve this problem via efficient algorithms. These algorithms are judged on the basis of their robustness, ease of use, and their computational time. The main aim of this thesis is to convert a Pure Integer Linear Programming (ILP) with (0, 1)−matrix into Mixed Integer Linear Programming (MILP) by finding the C1S submatrix. Given a (0, 1)−matrix, we consider the C1S problem which aims to maximize the number of columns having only one block of consecutive 1’s in each row by permuting them. We suggest an evolutionary approach to solve the problem. The Genetic Algorithm (GA) is the one proposed here to rearrange the columns of the matrix by pushing them in large blocks of 1’s. We also consider the Consecutive Blocks Minimization (CBM) problem which is related to C1S. A new procedure is proposed to improve the C1S submatrix, which is the column insertion approach. Moreover, preprocessing by minimum degree ordering is also used. On the other hand, we suggest another approach to solve the C1S. It is using the MVEE problem. To pave the way we first solve the problem. Given a set of points C = {x 1 ,x 2 ,...,x m } ⊆ R^n , what is the minimum volume ellipsoid that encloses it? Equally interestingly, one may ask: What is the maximum volume ellipsoid that can be embedded in the set of points without containing any? These problems have a number of applications beside being interesting in their own right. If one requires that at least k of m points, k < m be enclosed in the minimum volume ellipsoid, then the problem becomes more difficult but has the potential, once solved, to detect outliers among the n points. We suggest an evolutionary-type approach for their solution. We will also highlight application areas and include computational results.
41
Hasan, S. M. Kamrul Engineering & Information Technology Australian Defence Force Academy UNSW. "Evolutionary algorithms for solving job-shop scheduling problems in the presence of process interruptions." Awarded by:University of New South Wales - Australian Defence Force Academy. Engineering & Information Technology, 2009. http://handle.unsw.edu.au/1959.4/43768.
Full textAbstract:
In this thesis, the Job Shop Scheduling Problem (JSSP) is the problem of interest. The classical JSSP is well-known as an NP-hard problem. Although with current computational capabilities, the small problems are solvable using deterministic methods, it is out of reach when they are larger in size. The complexity of JSSP is further increased when process interruptions, such as machine breakdown and/or machine unavailability, are introduced. Over the last few decades, several stochastic algorithms have been proposed to solve JSSPs. However, none of them are suitable for all kinds of problems. Genetic and Memetic algorithms have proved their effectiveness in these regards, because of their diverse searching behavior. In this thesis, we have developed one genetic algorithm and three different Memetic Algorithms (MAs) for solving JSSPs. Three priority rules are designed, namely partial re-ordering, gap reduction and restricted swapping, and these have been used as local search techniques in designing our MAs. We have solved 40 well-known benchmark problems and compared the results obtained with some of the established algorithms available in the literature. Our algorithm clearly outperforms those established algorithms. For better justification of the superiority of MAs over GA, we have performed statistical significance testing (Student's t-test). The experimental results show that MA, as compared to GA, not only significantly improves the quality of solutions, but also reduces the overall computation. We have extended our work by proposing an improved local search technique, shifted gap-reduction (SGR), which improves the performance of MAs when tested with the relatively difficult test problems. We have also modified the new algorithm to accommodate JSSPs with machine unavailability and also developed a new reactive scheduling technique to re-optimize the schedule after machine breakdowns. We have considered two scenarios of machine unavailability. Firstly, where the unavailability information is available in advance (predictive), and secondly, where the information is known after a real breakdown (reactive). We show that the revised schedule is mostly able to recover if the interruptions occur during the early stages of the schedules. We also confirm that the effect of a single continuous breakdown has more impact compared to short multiple breakdowns, even if the total durations of the breakdowns are the same. Finally, for convenience of implementation, we have developed a decision support system (DSS). In the DSS, we have built a graphical user interface (GUI) for user friendly data inputs, model choices, and output generation. This DSS tool will help users in solving JSSPs without understanding the complexity of the problem and solution approaches, as well as will contribute in reducing the computational and operational costs.
42
Butans, Jevgenijs. "Addressing real-time control problems in complex environments using dynamic multi-objective evolutionary approaches." Thesis, Cranfield University, 2011. http://dspace.lib.cranfield.ac.uk/handle/1826/7275.
Full textAbstract:
The demand for increased automation of industrial processes generates control problems that are dynamic, multi-objective and noisy at the same time. The primary hypothesis underlying this research is that dynamic evolutionary methods could be used to address dynamic control problems where con icting control criteria are necessary. The aim of this research is to develop a framework for on-line optimisation of dynamic problems that is capable of a) representing problems in a quantitative way, b) identifying optimal solutions using multi-objective evolutionary algorithms, and c) automatically selecting an optimal solution among alternatives. A literature review identi es key problems in the area of dynamic multi-objective optimisation, discusses the on-line decision making aspect, analyses existing Multi- Objective Evolutionary Algorithms (MOEA) applications and identi es research gap. Dynamic evolutionary multi-objective search and on-line a posteriori decision maker are integrated into an evolutionary multi-objective controller that uses an internal process model to evaluate the tness of solutions. Using a benchmark multi-objective optimisation problem, the MOEA ability to track the moving optima is examined with di erent parameter values, namely, length of pre-execution, frequency of change, length of prediction interval and static mutation rate. A dynamic MOEA with restricted elitism is suggested for noisy environments.To address the on-line decision making aspect of the dynamic multi-objective optimisation, a novel method for constructing game trees for real-valued multiobjective problems is presented. A novel decision making algorithm based on game trees is proposed along with a baseline random decision maker. The proposed evolutionary multi-objective controller is systematically analysed using an inverted pendulum problem and its performance is compared to Proportional{ Integral{Derivative (PID) and nonlinear Model Predictive Control (MPC) approaches. Finally, the proposed control approach is integrated into a multi-agent framework for coordinated control of multiple entities and validated using a case study of a tra c scheduling problem.
43
Trostorff, Sascha [Verfasser], and Ralph [Gutachter] Chill. "Exponential Stability and Initial Value Problems for Evolutionary Equations / Sascha Trostorff ; Gutachter: Ralph Chill." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2018. http://d-nb.info/1160875545/34.
Full text
44
Pickardt, Christoph W. "Evolutionary methods for the design of dispatching rules for complex and dynamic scheduling problems." Thesis, University of Warwick, 2013. http://wrap.warwick.ac.uk/59757/.
Full textAbstract:
Three methods, based on Evolutionary Algorithms (EAs), to support and automate the design of dispatching rules for complex and dynamic scheduling problems are proposed in this thesis. The first method employs an EA to search for problem instances on which a given dispatching rule performs badly. These instances can then be analysed to reveal weaknesses of the tested rule, thereby providing guidelines for the design of a better rule. The other two methods are hyper-heuristics, which employ an EA directly to generate effective dispatching rules. In particular, one hyper-heuristic is based on a specific type of EA, called Genetic Programming (GP), and generates a single rule from basic job and machine attributes, while the other generates a set of work centre-specific rules by selecting a (potentially) different rule for each work centre from a number of existing rules. Each of the three methods is applied to some complex and dynamic scheduling problem(s), and the resulting dispatching rules are tested against benchmark rules from the literature. In each case, the benchmark rules are shown to be outperformed by a rule (set) that results from the application of the respective method, which demonstrates the effectiveness of the proposed methods.
45
Filograsso, Gianni <1997>. "Adaptive evolutionary algorithms for portfolio selection problems: state of the art and experimental analysis." Master's Degree Thesis, Università Ca' Foscari Venezia, 2021. http://hdl.handle.net/10579/19820.
Full textAbstract:
This thesis aims at solving complex portfolio selection problems by introducing an adaptive strategy for parameter control in EAs, with the aim of achieving accurate and robust solutions. In chapter 1 we review a broad set of parameter tuning and parameter control strategies, then we implement an adaptive policy, based on the parameter control technique proposed by Maturana (2010), on a variety of non-convex risk measures, that display many local optima, for which traditional minimization strategies like gradient descent methods are not suitable. The idea behind this method is to solve problems by managing the well-known EvE balance in the context of evolutionary computation, which is widely acknowledged as a key issue in terms of search performance. This approach allows the EA to use an appropriate parameter setting in different stages of the search process, typically by generating large improvements of the solution quality at the beginning and finally by fine-tuning the solution. We apply this method to large scale optimization problems; in particular, we start by considering relatively basic programming problems with easy constraints, then we take into account a set of NP-hard integer programming problems, which display well-known computational issues.
46
Fabritius, Björn. "Application of genetic algorithms to problems in computational fluid dynamics." Thesis, University of Exeter, 2014. http://hdl.handle.net/10871/15236.
Full textAbstract:
In this thesis a methodology is presented to optimise non–linear mathematical models in numerical engineering applications. The method is based on biological evolution and uses known concepts of genetic algorithms and evolutionary compu- tation. The working principle is explained in detail, the implementation is outlined and alternative approaches are mentioned. The optimisation is then tested on a series of benchmark cases to prove its validity. It is then applied to two different types of problems in computational engineering. The first application is the mathematical modeling of turbulence. An overview of existing turbulence models is followed by a series of tests of different models applied to various types of flows. In this thesis the optimisation method is used to find improved coefficient values for the k–ε, the k–ω-SST and the Spalart–Allmaras models. In a second application optimisation is used to improve the quality of a computational mesh automatically generated by a third party software tool. This generation can be controlled by a set of parameters, which are subject to the optimisation. The results obtained in this work show an improvement when compared to non–optimised results. While computationally expensive, the genetic optimisation method can still be used in engineering applications to tune predefined settings with the aim to produce results of higher quality. The implementation is modular and allows for further extensions and modifications for future applications.
47
Roudenko, Olga. "Application des Algorithmes Evolutionnaires aux problèmes d'optimisation muti-objectif avec contraintes." Palaiseau, Ecole polytechnique, 2004. http://www.theses.fr/2004EPXX0005.
Full text
48
Sävhammar, Simon. "Tillämpbarheten av Learning Backtracking Search Optimization Algoritmen vid Lösning av Sudoku-problemet." Thesis, Högskolan i Skövde, Institutionen för informationsteknologi, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-14087.
Full textAbstract:
Den här rapporten undersöker egenskaper hos en algoritm som är baserad på Learning Backtracking Search Optimization Algorithm (LBSA) som introducerades av Chen et. al. (2017). Undersökningen genomfördes genom att tillämpa algoritmen på Sudokuproblemet och jämföra lösningsgraden och diversiteten i den sista populationen med en algoritm som är baserad på Hybrid Genetic Algorithm (HGA) som introducerades av Deng och Li (2011). Resultaten visar att implementationen av den LBSA-baserade algoritmen har en lägre lösningsgrad än den HGA-baserade algoritmen för alla genomförda experiment, men att algoritmen håller en högre diversitet i den sista populationen för tre av de fem gjorda experimenten. Slutsatsen är att den LBSA-baserade algoritmen inte är lämplig för att lösa Sudokuproblemet på grund av en låg lösningsgrad och att implementationen har en hög komplexitet.This report examines the properties of an algorithm based on the Learning Backtracking Optimization Algorithm (LBSA) introduced by Chen et. al. (2017). The examination was performed by applying the algorithm on the Sudoku problem and then comparing the solution rate and the diversity in the final population with an algorithm based on the Hybrid Genetic Algorithm introduced by Deng and Li (2011). The results show the implementation of the LBSA based algorithm have a lower solution rate than the HGA based algorithm for all executed experiments. But the LBSA based algorithm manage to keep a higher diversity in the final population in three of the five performed experiments. The conclusion is that the LBSA based algorithm is not suitable for solving the Sudoku problem since the algorithm has a lower solution rate and the implementation have a high complexity.
49
Le, Khoi Nguyen. "A study of evolutionary multiobjective algorithms and their application to knapsack and nurse scheduling problems." Thesis, University of Nottingham, 2011. http://eprints.nottingham.ac.uk/13116/.
Full textAbstract:
Evolutionary algorithms (EAs) based on the concept of Pareto dominance seem the most suitable technique for multiobjective optimisation. In multiobjective optimisation, several criteria (usually conflicting) need to be taken into consideration simultaneously to assess a quality of a solution. Instead of finding a single solution, a set of trade-off or compromise solutions that represents a good approximation to the Pareto optimal set is often required. This thesis presents an investigation on evolutionary algorithms within the framework of multiobjective optimisation. This addresses a number of key issues in evolutionary multiobjective optimisation. Also, a new evolutionary multiobjective (EMO) algorithm is proposed. Firstly, this new EMO algorithm is applied to solve the multiple 0/1 knapsack problem (a wellknown benchmark multiobjective combinatorial optimisation problem) producing competitive results when compared to other state-of-the-art MOEAs. Secondly, this thesis also investigates the application of general EMO algorithms to solve real-world nurse scheduling problems. One of the challenges in solving real-world nurse scheduling problems is that these problems are highly constrained and specific-problem heuristics are normally required to handle these constraints. These heuristics have considerable influence on the search which could override the effect that general EMO algorithms could have in the solution process when applied to this type of problems. This thesis outlines a proposal for a general approach to model the nurse scheduling problems without the requirement of problem-specific heuristics so that general EMO algorithms could be applied. This would also help to assess the problems and the performance of general EMO algorithms more fairly.
50
Mikki, Said M. "Theoretical-physics approach to selected problems in engineering electromagnetics : evolutionary optimization and low-dimensional nanostructures /." Full text available from ProQuest UM Digital Dissertations, 2008. http://0-proquest.umi.com.umiss.lib.olemiss.edu/pqdweb?index=0&did=1814477871&SrchMode=1&sid=1&Fmt=2&VInst=PROD&VType=PQD&RQT=309&VName=PQD&TS=1257874503&clientId=22256.
Full textAbstract:
Thesis (Ph.D.)--University of Mississippi, 2008.Typescript. Vita. "October 2008." Dissertation advisor: Ahmed A. Kishk Includes bibliographical references (leaves 307-328). Also available online via ProQuest to authorized users.