M.Sc. Computer Science
http://hdl.handle.net/10464/2881
2017-12-17T05:58:09ZA Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization
http://hdl.handle.net/10464/9277
A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization
Maltese, Justin
Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective 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 many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.
Properties and Algorithms of the KCube Interconnection Networks
http://hdl.handle.net/10464/8912
Properties and Algorithms of the KCube Interconnection Networks
Noroozi, Keivan
The KCube interconnection network was first introduced in 2010 in order to exploit the
good characteristics of two well-known interconnection networks, the hypercube and the
Kautz graph. KCube links up multiple processors in a communication network with high
density for a fixed degree. Since the KCube network is newly proposed, much study is
required to demonstrate its potential properties and algorithms that can be designed to solve
parallel computation problems.
In this thesis we introduce a new methodology to construct the KCube graph. Also,
with regard to this new approach, we will prove its Hamiltonicity in the general KC(m; k).
Moreover, we will find its connectivity followed by an optimal broadcasting scheme in
which a source node containing a message is to communicate it with all other processors.
In addition to KCube networks, we have studied a version of the routing problem in the
traditional hypercube, investigating this problem: whether there exists a shortest path in a
Qn between two nodes 0n and 1n, when the network is experiencing failed components. We
first conditionally discuss this problem when there is a constraint on the number of faulty
nodes, and subsequently introduce an algorithm to tackle the problem without restrictions
on the number of nodes.
GA approach for finding Rough Set decision rules based on bireducts
http://hdl.handle.net/10464/7698
GA approach for finding Rough Set decision rules based on bireducts
Rybkin, Oleg
Feature selection plays an important role in knowledge discovery and data mining nowadays. In traditional rough set theory, feature selection using reduct - the minimal discerning set of attributes - is an important area. Nevertheless, the original definition of a reduct is restrictive, so in one of the previous research it was proposed to take into account not only the horizontal reduction of information by feature selection, but also a vertical reduction considering suitable subsets of the original set of objects.
Following the work mentioned above, a new approach to generate bireducts using a multi--objective genetic algorithm was proposed. Although the genetic algorithms were used to calculate reduct in some previous works, we did not find any work where genetic algorithms were adopted to calculate bireducts.
Compared to the works done before in this area, the proposed method has less randomness in generating bireducts. The genetic algorithm system estimated a quality of each bireduct by values of two objective functions as evolution progresses, so consequently a set of bireducts with optimized values of these objectives was obtained.
Different fitness evaluation methods and genetic operators, such as crossover and mutation, were applied and the prediction accuracies were compared. Five datasets were used to test the proposed method and two datasets were used to perform a comparison study. Statistical analysis using the one-way ANOVA test was performed to determine the significant difference between the results.
The experiment showed that the proposed method was able to reduce the number of bireducts necessary in order to receive a good prediction accuracy. Also, the influence of different genetic operators and fitness evaluation strategies on the prediction accuracy was analyzed. It was shown that the prediction accuracies of the proposed method are comparable with the best results in machine learning literature, and some of them outperformed it.
Feature Selection and Classification Using Age Layered Population Structure Genetic Programming
http://hdl.handle.net/10464/7329
Feature Selection and Classification Using Age Layered Population Structure Genetic Programming
Awuley, Anthony
The curse of dimensionality is a major problem in the fields of machine learning, data mining and knowledge discovery. Exhaustive search for the most optimal subset of relevant features from a high dimensional dataset is NP hard. Sub–optimal population based stochastic algorithms such as GP and GA are good choices for searching through large search spaces, and are usually more feasible than exhaustive and determinis- tic search algorithms. On the other hand, population based stochastic algorithms often suffer from premature convergence on mediocre sub–optimal solutions. The Age Layered Population Structure (ALPS) is a novel meta–heuristic for overcoming the problem of premature convergence in evolutionary algorithms, and for improving search in the fitness landscape. The ALPS paradigm uses an age–measure to control breeding and competition between individuals in the population. This thesis uses a modification of the ALPS GP strategy called Feature Selection ALPS (FSALPS) for feature subset selection and classification of varied supervised learning tasks. FSALPS uses a novel frequency count system to rank features in the GP population based on evolved feature frequencies. The ranked features are translated into probabilities, which are used to control evolutionary processes such as terminal–symbol selection for the construction of GP trees/sub-trees. The FSALPS meta–heuristic continuously refines the feature subset selection process whiles simultaneously evolving efficient classifiers through a non–converging evolutionary process that favors selection of features with high discrimination of class labels. We investigated and compared the performance of canonical GP, ALPS and FSALPS on high–dimensional benchmark classification datasets, including a hyperspectral image. Using Tukey’s HSD ANOVA test at a 95% confidence interval, ALPS and FSALPS dominated canonical GP in evolving smaller but efficient trees with less bloat expressions. FSALPS significantly outperformed canonical GP and ALPS and some reported feature selection strategies in related literature on dimensionality reduction.