Browsing M.Sc. Computer Science by Title
Now showing items 91104 of 104

The Salmon Algorithm  A New Population Based Search MetaheuristicThis thesis introduces the Salmon Algorithm, a search metaheuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems  optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

A Scalability Study and New Algorithms for LargeScale ManyObjective OptimizationMany realworld optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multiobjective problems (MOPs). Over the past few decades, a plethora of multiobjective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as manyobjective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a wellspread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for largescale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of manyobjective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming stateoftheart manyobjective algorithms.

Shortest Path Routing on the Hypercube with Faulty NodesInterconnection networks are widely used in parallel computers. There are many topologies for interconnection networks and the hypercube is one of the most popular networks. There are a variety of different routing paradigms that need to be investigated on the hypercube. In this thesis we investigate the shortest path routing between two nodes on the hypercube when some nodes are faulty and cannot be used. In this thesis the shortest path between two nodes is considered as the Hamming distance of them. Regarding the shortest path problem in a faulty hypercube, some efficient algorithms have been proposed when each processor (node) has limited information regarding the status of other processors (whether they are faulty or not). There are also some proposed algorithms for the case where there is no limitation on the data of each processor but they are not efficient and are exponential in terms of number of faulty nodes and dimension of the hypercube. To check whether there is a shortest path between two given nodes in a faulty hypercube, we propose a polynomial algorithm with time complexity of O(n^2 * m^2) where n is the dimension of the hypercube and m is the number of faulty nodes. Our algorithm only requires the source node to know the state of all other nodes. The proposed algorithm first checks whether there is a shortest path from the source node to the target node and then it can construct it efficiently. Our idea is based on a socalled ordering and permutation model of paths in the hypercube. We use a constructive approach to find the path which is a permutation as well. We then use inclusionexclusion and dynamic programming techniques to make our method efficient. We also propose an algorithm for counting all possible shortest paths in the hypercube.

Statistical Image Analysis for Image EvolutionThis thesis is focused on using genetic programming to evolve images based on lightweight features extracted from a given target image. The main motivation of this thesis is research by Lombardi et al. in which an image retrieval system is developed based on lightweight statistical features of images for comparing and classifying them in painting style categories; primarily based on color matching. In this thesis, automatic fitness scoring of variations of up to 17 lightweight image features using manyobjective fitness evaluation was used to evolve textures. Evolved results were shown to have similar color characteristics to target images. Although a human survey was conducted to confirm those results, it was inconclusive.

Strategies for Evolving Diverse and Effective Behaviours in Pursuit DomainsEvolutionary algorithms have a tendency to overuse and exploit particular behaviours in their search for optimality, even across separate runs. The resulting set of monotonous solutions caused by this tendency is a problem in many applications. This research explores different strategies designed to encourage an interesting set of diverse behaviours while still maintaining an appreciable level of efficacy. Embodied agents are situated within an open plane and play against each other in various pursuit game scenarios. The pursuit games consist of a single predator agent and twenty prey agents, with the goal always requiring the predator to catch as many prey as possible before the time limit is reached. The predator's controller is evolved through genetic programming while the preys' controllers are handcrafted. The fitness of a solution is first calculated in a traditional manner. Inspired by Lehman and Stanley's novelty search strategy, the fitness is then combined with the diversity of the solution to produce the final fitness score. The original fitness score is determined by the number of captured prey, and the diversity score is determined through the combination of four behaviour measurements. Among many promising results, a particular diversitybased evaluation strategy and weighting combination was found to provide solutions that exhibit an excellent balance between diversity and efficacy. The results were analyzed quantitatively and qualitatively, showing the emergence of diverse and effective behaviours.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic RepresentationsOrdered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other stateoftheart DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Surface Areas of Some Interconnection NetworksAn interesting property of an interconnected network (G) is the number of nodes at distance i from an arbitrary processor (u), namely the node centered surface area. This is an important property of a network due to its applications in various fields of study. In this research, we investigate on the surface area of two important interconnection networks, (n, k)arrangement graphs and (n, k)star graphs. Abundant works have been done to achieve a formula for the surface area of these two classes of graphs, but in general, it is not trivial to find an algorithm to compute the surface area of such graphs in polynomial time or to find an explicit formula with polynomially many terms in regards to the graph's parameters. Among these studies, the most efficient formula in terms of computational complexity is the one that Portier and Vaughan proposed which allows us to compute the surface area of a special case of (n, k)arrangement and (n, k)star graphs when k = n1, in linear time which is a tremendous improvement over the naive solution with complexity order of O(n * n!). The recurrence we propose here has the linear computational complexity as well, but for a much wider family of graphs, namely A(n, k) for any arbitrary n and k in their defined range. Additionally, for (n, k)star graphs we prove properties that can be used to achieve a simple recurrence for its surface area.

Swarmbased Algorithms for Neural Network TrainingThe main focus of this thesis is to compare the ability of various swarm intelligence algorithms when applied to the training of artificial neural networks. In order to compare the performance of the selected swarm intelligence algorithms both classification and regression datasets were chosen from the UCI Machine Learning repository. Swarm intelligence algorithms are compared in terms of training loss, training accuracy, testing loss, testing accuracy, hidden unit saturation, and overfitting. Our observations showed that Particle Swarm Optimization (PSO) was the best performing algorithm in terms of Training loss and Training accuracy. However, it was also found that the performance of PSO dropped considerably when examining the testing loss and testing accuracy results. For the classification problems, it was found that firefly algorithm, ant colony optimization, and fish school search outperformed PSO for testing loss and testing accuracy. It was also observed that ant colony optimization was the algorithm that performed the best in terms of hidden unit saturation.

A System for Models of First Order TheoriesIf you want to know whether a property is true or not in a specific algebraic structure,you need to test that property on the given structure. This can be done by hand, which can be cumbersome and erroneous. In addition, the time consumed in testing depends on the size of the structure where the property is applied. We present an implementation of a system for finding counterexamples and testing properties of models of firstorder theories. This system is supposed to provide a convenient and paperless environment for researchers and students investigating or studying such models and algebraic structures in particular. To implement a firstorder theory in the system, a suitable firstorder language.( and some axioms are required. The components of a language are given by a collection of variables, a set of predicate symbols, and a set of operation symbols. Variables and operation symbols are used to build terms. Terms, predicate symbols, and the usual logical connectives are used to build formulas. A firstorder theory now consists of a language together with a set of closed formulas, i.e. formulas without free occurrences of variables. The set of formulas is also called the axioms of the theory. The system uses several different formats to allow the user to specify languages, to define axioms and theories and to create models. Besides the obvious operations and tests on these structures, we have introduced the notion of a functor between classes of models in order to generate more co~plex models from given ones automatically. As an example, we will use the system to create several lattices structures starting from a model of the theory of preorders.

Towards automated derivation in the theory of allegoriesWe provide an algorithm that automatically derives many provable theorems in the equational theory of allegories. This was accomplished by noticing properties of an existing decision algorithm that could be extended to provide a derivation in addition to a decision certificate. We also suggest improvements and corrections to previous research in order to motivate further work on a complete derivation mechanism. The results presented here are significant for those interested in relational theories, since we essentially have a subtheory where automatic proofgeneration is possible. This is also relevant to program verification since relations are wellsuited to describe the behaviour of computer programs. It is likely that extensions of the theory of allegories are also decidable and possibly suitable for further expansions of the algorithm presented here.

Using Age Layered Population Structure for the MultiDepot Vehicle Routing ProblemThis thesis studies the NPhard multidepot vehicle routing problem (MDVRP) which is an extension of the classical VRP with the exception that vehicles based at one of several depots should service every customer assigned to that depot. Finding the optimal solution to MDVRP is computationally intractable for practical sized problem sets, and various metaheuristics including genetic algorithms have been proposed in the literature. In this work, an e fficient multipopulation genetic algorithm based on age layered population structures for the MDVRP is proposed. Three interlayer transfer strategies are proposed and multiobjective fi tness evaluation is compared with weighted sum approach. An empirical study comparing the proposed approach with existing genetic algorithms and other metaheuristics is carried out using well known benchmark data. The performance found in terms of solution quality is very promising.

Using Deep Learning for Predicting Stock TrendsDeep learning has shown great promise in solving complicated problems in recent years. One applicable area is finance. In this study, deep learning will be used to test the predictability of stock trends. Stock markets are known to be volatile, prices fluctuate, and there are many complicated financial indicators involved. While the opinion of researchers differ about the predictability of stocks, it has been shown by previous empirical studies that some aspects of stock markets can be predictable to some extent. Various data including news or financial indicators can be used to predict stock prices. In this study, the focus will be on using past stock prices and using technical indicators to increase the performance of the results. The goal of this study is to measure the accuracy of predictions and evaluate the results. Historical data is gathered for Apple, Microsoft, Google and Intel stocks. A prediction model is created by using past data and technical indicators were used as features in the model. The experiments were performed by using long shortterm memory networks. Different approaches and techniques were tested to boost the performance of the results. To prove the usability of the final model in the real world and measure the profitability of results backtesting was performed. The final results show that while it is not possible to predict the exact price of a stock in the future to gain profitable results, deep learning can be used to predict the trend of stock markets to generate buy and sell signals.

Using genetic algorithms for the single allocation hub location problemHub location problem is an NPhard problem that frequently arises in the design of transportation and distribution systems, postal delivery networks, and airline passenger flow. This work focuses on the Single Allocation Hub Location Problem (SAHLP). Genetic Algorithms (GAs) for the capacitated and uncapacitated variants of the SAHLP based on new chromosome representations and crossover operators are explored. The GAs is tested on two wellknown sets of realworld problems with up to 200 nodes. The obtained results are very promising. For most of the test problems the GA obtains improved or bestknown solutions and the computational time remains low. The proposed GAs can easily be extended to other variants of location problems arising in network design planning in transportation systems.

Winâ Foy : functional objectoriented programming languageThis thesis will introduce a new strongly typed programming language utilizing Self types, named Win*Foy, along with a suitable user interface designed specifically to highlight language features. The need for such a programming language is based on deficiencies found in programming languages that support both Self types and subtyping. Subtyping is a concept that is taken for granted by most software engineers programming in objectoriented languages. Subtyping supports subsumption but it does not support the inheritance of binary methods. Binary methods contain an argument of type Self, the same type as the object itself, in a contravariant position, i.e. as a parameter. There are several arguments in favour of introducing Self types into a programming language (11. This rationale led to the development of a relation that has become known as matching [4, 5). The matching relation does not support subsumption, however, it does support the inheritance of binary methods. Two forms of matching have been proposed (lJ. Specifically, these relations are known as higherorder matching and Ibound matching. Previous research on these relations indicates that the higherorder matching relation is both reflexive and transitive whereas the fbound matching is reflexive but not transitive (7]. The higherorder matching relation provides significant flexibility regarding inheritance of methods that utilize or return values of the same type. This flexibility, in certain situations, can restrict the programmer from defining specific classes and methods which are based on constant values [21J. For this reason, the type This is used as a second reference to the type of the object that cannot, contrary to Self, be specialized in subclasses. Fbound matching allows a programmer to define a function that will work for all types of A', a subtype of an upper bound function of type A, with the result type being dependent on A'. The use of parametric polymorphism in fbound matching provides a connection to subtyping in objectoriented languages. This thesis will contain two main sections. Firstly, significant details concerning deficiencies of the subtype relation and the need to introduce higherorder and fbound matching relations into programming languages will be explored. Secondly, a new programming language named Win*Foy Functional ObjectOriented Programming Language has been created, along with a suitable user interface, in order to facilitate experimentation by programmers regarding the matching relation. The construction of the programming language and the user interface will be explained in detail.