A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

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.

Heuristics for the Critical Node Detection Problem in Large Complex Networks

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.

Dynamics in large scale networks

In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabási-Albert random graph. We establish some bounds on the number of motifs in this graph.

The Catharanthus roseus 16-hydroxytabersonine O-methyltransferase involved in vindoline biosynthesis /

Madagascar periwinkle (Catharanthus roseus) produces the well known and remarkably complex dimeric anticancer alkaloids vinblastine and vincristine that are derived by coupling vindoline and catharanthine monomers. This thesis describes the novel application of carborundum abrasion (CA) technique as a tool for large scale isolation of leaf epidermis enriched proteins. This technique was used to facilitate the purification to apparent homogeneity of 16-hydroxytabersonine-16-0-methyltransferse (l60MT) that catalyses the second step in the 6 step pathway that converts tabersonine into vindoline. This versatile tool was also used to harvest leaf epidermis enriched mRNAs that facilitated the molecular cloning of the 160MT. Functional expression and biochemical characterization of recombinant 160MT enzyme showed that it had a very narrow substrate specificity and high affinity for 16-hydroxytabersonine, since other closely related monoterpene indole alkaloids (MIAs) did not act as substrates. In addition to allowing the cloning of this gene, CA technique clearly showed that 160MT is predominantly expressed in Catharanthus leaf epidermis, in contrast to several other OMTs that appear to be expressed in other Catharanthus tissues. The results provide compelling evidence that most of the pathway for vindoline biosynthesis including the 0- methylation of 16-hydroxytabersonine occurs exclusively in leaf epidermis, with subsequent steps occurring in other leaf cell types. Small molecule O-methyltransferases (OMTs) (E.C. 2.1.1.6.x) catalyze the transfer of the reactive methyl group of S-adenosyl-L-methionine (SAM) to free hydroxyl groups of acceptor molecules. Plant OMTs, unlike their monomeric mammalian homologues, exist as functional homodimers. While the biological advantages for dimer fonnation with plant OMTs remain to be established, studies with OMTs from the benzylisoquinoline producing plant, Thalictrum tuberosum, showed that co-expression of 2 recombinant OMTs produced novel substrate specificities not found when each rOMT was expressed individually (Frick, Kutchan, 1999) . These results suggest that OMTs can fonn heterodimers that confer novel substrate specificities not possible with the homodimer alone. The present study describes a 160MT model based strategy attempting to modify the substrate specificity by site-specific mutagenesis. Our failure to generate altered substrate acceptance profiles in our 160MT mutants has lead us to study the biochemical properties ofhomodimers and heterodimers. Experimental evidence is provided to show that active sites found on OMT dimers function independently and that bifunctional heterodimeric OMTs may be fonned in vivo to produce a broader and more diverse range of natural products in plants.