M.Sc. Computer Science
http://hdl.handle.net/10464/2881
2014-07-10T11:54:20ZMulti-Objective Genetic Algorithms for the Single Allocation Hub Location Problem
http://hdl.handle.net/10464/4985
Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem
Asobiela, Stephen Yamzuuga
Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is ﬁrst explored. Next, a multi-objective GA employing various ﬁtness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.
2013-09-12T00:00:00ZHeuristics for the Critical Node Detection Problem in Large Complex Networks
http://hdl.handle.net/10464/4984
Heuristics for the Critical Node Detection Problem in Large Complex Networks
Edalatmanesh, Mahmood
Complex networks have recently attracted a significant amount of research attention
due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required
in such circumstances, but none currently exist. In this thesis, such an algorithm
is proposed. The methodology is based on a depth-first search traversal of the network,
and a specially designed ranking function that considers information local to each vertex.
Due to the variety of network structures, a number of characteristics must be taken
into consideration and combined into a single rank that measures the utility of removing
each vertex. Since removing a vertex in sequential fashion impacts the network structure,
an efficient post-processing algorithm is also proposed to quickly re-rank vertices.
Experiments on a range of common complex network models with varying number of
vertices are considered, in addition to real world networks. The proposed algorithm,
DFSH, is shown to be highly competitive and often outperforms existing strategies such
as Google PageRank for minimizing pairwise connectivity.
2013-09-12T00:00:00ZAutomatic Inference of Graph Models for Complex Networks with Genetic Programming
http://hdl.handle.net/10464/4719
Automatic Inference of Graph Models for Complex Networks with Genetic Programming
Bailey, Alexander
Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.
2013-07-26T00:00:00ZGenetic Programming for Non-Photorealistic Rendering
http://hdl.handle.net/10464/4304
Genetic Programming for Non-Photorealistic Rendering
Baniasadi, Maryam
This thesis focuses on developing an evolutionary art system using genetic programming. The main goal is to produce new forms of evolutionary art that filter existing images into new non-photorealistic (NPR) styles, by obtaining images that look like traditional media such as watercolor or pencil, as well as brand new effects. The approach permits GP to generate creative forms of NPR results. The GP language is extended with different techniques and methods inspired from NPR research such as colour mixing expressions, image processing filters and painting algorithm. Colour mixing is a major new contribution, as it enables many familiar and innovative NPR effects to arise. Another major innovation is that many GP functions process the canvas (rendered image), while is dynamically changing. Automatic fitness scoring uses aesthetic evaluation models and statistical analysis, and multi-objective fitness evaluation is used. Results showed a variety of NPR effects, as well as new, creative possibilities.
2013-04-18T00:00:00Z