Current Search: Algorithm (x)
Pages


Title

CONTROLLING RANDOMNESS: USING PROCEDURAL GENERATION TO INFLUENCE PLAYER UNCERTAINTY IN VIDEO GAMES.

Creator

Fort, Travis, McDaniel, Rudy, University of Central Florida

Abstract / Description

As video games increase in complexity and length, the use of automatic, or procedural, content generation has become a popular way to reduce the stress on game designers. However, the usage of procedural generation has certain consequences; in many instances, what the computer generates is uncertain to the designer. The intent of this thesis is to demonstrate how procedural generation can be used to intentionally affect the embedded randomness of a game system, enabling game designers to...
Show moreAs video games increase in complexity and length, the use of automatic, or procedural, content generation has become a popular way to reduce the stress on game designers. However, the usage of procedural generation has certain consequences; in many instances, what the computer generates is uncertain to the designer. The intent of this thesis is to demonstrate how procedural generation can be used to intentionally affect the embedded randomness of a game system, enabling game designers to influence the level of uncertainty a player experiences in a nuanced way. This control affords game designers direct control over complex problems like dynamic difficulty adjustment, pacing, or accessibility. Game design will be examined from the perspective of uncertainty and how procedural generation can be used to intentionally add or reduce uncertainty. Various procedural generation techniques will be discussed alongside the types of uncertainty, using case studies to demonstrate the principles in action.
Show less

Date Issued

2015

Identifier

CFH0004772, ucf:45386

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFH0004772


Title

ON WELLQUASIORDERINGS.

Creator

Thurman, Forrest, Brennan, Joseph, University of Central Florida

Abstract / Description

A quasiorder is a relation on a set which is both reflexive and transitive, while a wellquasiorder has the additional property that there exist no infinite strictly descending chains nor infinite antichains. Wellquasiorderings have many interesting applications to a variety of areas which includes the strength of certain logical systems, the termination of algorithms, and the classification of sets of graphs in terms of excluded minors. My thesis explores how wellquasiorderings are...
Show moreA quasiorder is a relation on a set which is both reflexive and transitive, while a wellquasiorder has the additional property that there exist no infinite strictly descending chains nor infinite antichains. Wellquasiorderings have many interesting applications to a variety of areas which includes the strength of certain logical systems, the termination of algorithms, and the classification of sets of graphs in terms of excluded minors. My thesis explores how wellquasiorderings are related to these topics through examples of four known wellquasiorderings which are given by Dickson's Lemma, Higmans's Lemma, Kruskal's Tree Theorem, and the RobertsonSeymour Theorem. The wellquasiordering conjecture for matroids is also discussed, and an original proof of Higman's Lemma is presented.
Show less

Date Issued

2013

Identifier

CFH0004455, ucf:45082

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFH0004455


Title

IMITATING INDIVIDUALIZED FACIAL EXPRESSIONS IN A HUMANLIKE AVATAR THROUGH A HYBRID PARTICLE SWARM OPTIMIZATION  TABU SEARCH ALGORITHM.

Creator

Husk, Evan, Gonzalez, Avelino, University of Central Florida

Abstract / Description

This thesis describes a machine learning method for automatically imitating a particular person's facial expressions in a humanlike avatar through a hybrid Particle Swarm Optimization  Tabu Search algorithm. The muscular structures of the facial expressions are measured by Ekman and Friesen's Facial Action Coding System (FACS). Using a neutral face as a reference, the minute movements of the Action Units, used in FACS, are automatically tracked and mapped onto the avatar using a hybrid...
Show moreThis thesis describes a machine learning method for automatically imitating a particular person's facial expressions in a humanlike avatar through a hybrid Particle Swarm Optimization  Tabu Search algorithm. The muscular structures of the facial expressions are measured by Ekman and Friesen's Facial Action Coding System (FACS). Using a neutral face as a reference, the minute movements of the Action Units, used in FACS, are automatically tracked and mapped onto the avatar using a hybrid method. The hybrid algorithm is composed of Kennedy and Eberhart's Particle Swarm Optimization algorithm (PSO) and Glover's Tabu Search (TS). Distinguishable features portrayed on the avatar ensure a personalized, realistic imitation of the facial expressions. To evaluate the feasibility of using PSOTS in this approach, a fundamental proofofconcept test is employed on the system using the OGRE avatar. This method is analyzed indepth to ensure its proper functionality and evaluate its performance compared to previous work.
Show less

Date Issued

2012

Identifier

CFH0004286, ucf:44949

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFH0004286


Title

ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIESPARALLEL GRAPHS.

Creator

Enciso, Rosa, Dutton, Ronald, University of Central Florida

Abstract / Description

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as...
Show moreAlliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NPcomplete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of seriesparallel graphs into alliances. The class of seriesparallel graphs is a special class in graph theory since many problems known to be NPcomplete on general graphs have been shown to have polynomial time algorithms on seriesparallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to seriesparallel graphs . Seriesparallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning seriesparallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of seriesparallel graphs that allow a partition into defensive alliances and a subclass of seriesparallel graphs with a satisfactory partitions.
Show less

Date Issued

2009

Identifier

CFE0002956, ucf:47945

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0002956


Title

ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS.

Creator

Tener, Greg, Deo, Narsingh, University of Central Florida

Abstract / Description

The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualizationrefinement paradigm, pioneered by Brendan McKay in 1981 with his...
Show moreThe graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualizationrefinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representativean approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nautylike algorithms. This dissertation investigates why these graph families pose difficulty for individualizationrefinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualizationrefinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial timethus obviating the only known exponential upperbound on individualizationrefinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guidetree data structure of the preceding technique to use a stronger vertexinvariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.
Show less

Date Issued

2009

Identifier

CFE0002894, ucf:48018

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0002894


Title

AN ADAPTIVE MULTIOBJECTIVE EVOLUTIONARY APPROACH TO OPTIMIZE ARTMAP NEURAL NETWORKS.

Creator

Kaylani, Assem, Georgiopoulos, Michael, University of Central Florida

Abstract / Description

This dissertation deals with the evolutionary optimization of ART neural network architectures. ART (adaptive resonance theory) was introduced by a Grossberg in 1976. In the last 20 years (19872007) a number of ART neural network architectures were introduced into the literature (Fuzzy ARTMAP (1992), Gaussian ARTMAP (1996 and 1997) and Ellipsoidal ARTMAP (2001)). In this dissertation, we focus on the evolutionary optimization of ART neural network architectures with the intent of optimizing...
Show moreThis dissertation deals with the evolutionary optimization of ART neural network architectures. ART (adaptive resonance theory) was introduced by a Grossberg in 1976. In the last 20 years (19872007) a number of ART neural network architectures were introduced into the literature (Fuzzy ARTMAP (1992), Gaussian ARTMAP (1996 and 1997) and Ellipsoidal ARTMAP (2001)). In this dissertation, we focus on the evolutionary optimization of ART neural network architectures with the intent of optimizing the size and the generalization performance of the ART neural network. A number of researchers have focused on the evolutionary optimization of neural networks, but no research has been performed on the evolutionary optimization of ART neural networks, prior to 2006, when Daraiseh has used evolutionary techniques for the optimization of ART structures. This dissertation extends in many ways and expands in different directions the evolution of ART architectures, such as: (a) uses a multiobjective optimization of ART structures, thus providing to the user multiple solutions (ART networks) with varying degrees of merit, instead of a single solution (b) uses GA parameters that are adaptively determined throughout the ART evolution, (c) identifies a proper size of the validation set used to calculate the fitness function needed for ART's evolution, thus speeding up the evolutionary process, (d) produces experimental results that demonstrate the evolved ART's effectiveness (good accuracy and small size) and efficiency (speed) compared with other competitive ART structures, as well as other classifiers (CART (Classification and Regression Trees) and SVM (Support Vector Machines)). The overall methodology to evolve ART using a multiobjective approach, the chromosome representation of an ART neural network, the genetic operators used in ART's evolution, and the automatic adaptation of some of the GA parameters in ART's evolution could also be applied in the evolution of other exemplar based neural network classifiers such as the probabilistic neural network and the radial basis function neural network.
Show less

Date Issued

2008

Identifier

CFE0002212, ucf:47907

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0002212


Title

Methods to Calculate Cut Volumes for Fault Trees with Dependencies Induced by Spatial Locations.

Creator

Hanes, Phillip, Wiegand, Rudolf, Wu, Annie, DeMara, Ronald, Song, Zixia, University of Central Florida

Abstract / Description

Fault tree analysis (FTA) is used to find and mitigate vulnerabilities in systems based on their constituent components. Methods exist to efficiently find minimal cut sets (MCS), which are combinations of components whose failure causes the overall system to fail. However, traditional FTA ignores the physical location of the components. Components in close proximity to each other could be defeated by a single event with a radius of effect, such as an explosion or fire. Events such as the...
Show moreFault tree analysis (FTA) is used to find and mitigate vulnerabilities in systems based on their constituent components. Methods exist to efficiently find minimal cut sets (MCS), which are combinations of components whose failure causes the overall system to fail. However, traditional FTA ignores the physical location of the components. Components in close proximity to each other could be defeated by a single event with a radius of effect, such as an explosion or fire. Events such as the Deepwater Horizon explosion and subsequent oil spill demonstrate the potentially devastating risk posed by such spatial dependencies. This motivates the search for techniques to identify this type of vulnerability. Adding physical locations to the fault tree structure can help identify possible points of failure in the overall system caused by localized disasters. Since existing FTA methods cannot address these concerns, using this information requires extending existing solution methods or developing entirely new ones.A problem complicating research in FTA is the lack of benchmark problems for evaluating methods, especially for fault trees over one hundred components. This research presents a method of using Lindenmeyer systems (Lsystems) to generate fault trees that are reproducible, capable of producing fault trees with similar properties to realworld designs, and scalable while maintaining predictable structural properties. This approach will be useful for testing and analyzing different methodologies for FTA tasks at different scales and under different conditions.Using a set of benchmark fault trees derived from Lsystems, three approaches to finding these vulnerabilities were explored in this research. These approaches were compared by defining a metric called (")minimal cut volumes(") (MCV) for describing volumes of effect that defeat the system. Since no existing methods are known for solving this problem, the methods are compared to each other to evaluate performance.1) The control method executes traditional FTA software to find minimal cut sets (MCS), then extends this approach by searching for clusters in the resulting MCS to find MCV.2) The next method starts by searching for clusters of components in the three dimensional space, then evaluates combinations of clusters to find MCV that defeat the system.3) The last method uses an evolutionary algorithm to search the space directly by selecting center points, then using the radius of the smallest sphere(s) as the fitness value for identifying MCV.Results generated using each method are presented. The performance of the methods are compared to the control method and their utilities evaluated accordingly.
Show less

Date Issued

2018

Identifier

CFE0007403, ucf:52075

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007403


Title

Analysis of largescale population genetic data using efficient algorithms and data structures.

Creator

Naseri, Ardalan, Zhang, Shaojie, Hughes, Charles, Yooseph, Shibu, Zhi, Degui, University of Central Florida

Abstract / Description

With the availability of genotyping data of very large samples, there is an increasing need for tools that can efficiently identify genetic relationships among all individuals in the sample. Modern biobanks cover genotypes up to 0.1%1% of an entire large population. At this scale, genetic relatedness among samples is ubiquitous. However, current methods are not efficient for uncovering genetic relatedness at such a scale. We developed a new method, Random Projection for IBD Detection (RaPID)...
Show moreWith the availability of genotyping data of very large samples, there is an increasing need for tools that can efficiently identify genetic relationships among all individuals in the sample. Modern biobanks cover genotypes up to 0.1%1% of an entire large population. At this scale, genetic relatedness among samples is ubiquitous. However, current methods are not efficient for uncovering genetic relatedness at such a scale. We developed a new method, Random Projection for IBD Detection (RaPID), for detecting IdenticalbyDescent (IBD) segments, a fundamental concept in genetics in large panels. RaPID detects all IBD segments over a certain length in time linear to the sample size. We take advantage of an efficient population genotype index, Positional BWT (PBWT), by Richard Durbin. PBWT achieves linear time query of perfectly identical subsequences among all samples. However, the original PBWT is not tolerant to genotyping errors which often interrupt long IBD segments into short fragments. The key idea of RaPID is that the problem of approximate highresolution matching over a long range can be mapped to the problem of exact matching of lowresolution subsampled sequences with high probability. PBWT provides an appropriate data structure for biallelic data. With the increasing sample sizes, more multiallelic sites are expected to be observed. Hence, there is a necessity to handle multiallelic genotype data. We also introduce a multiallelic version of the original Positional BurrowsWheeler Transform (mPBWT).The increasingly large cohorts of whole genome genotype data present an opportunity for searching genetically related people within a large cohort to an individual. At the same time, doing so efficiently presents a challenge. The PBWT algorithm offers constant time matching between one haplotype and an arbitrarily large panel at each position, but only for the maximal matches. We used the PBWT data structure to develop a method to search for all matches of a given query in a panel. The matches larger than a given length correspond to the all shared IBD segments of certain lengths between the query and other individuals in the panel. The time complexity of the proposed method is independent from the number of individuals in the panel. In order to achieve a time complexity independent from the number of haplotypes, additional data structures are introduced.Some regions of genome may be shared by multiple individuals rather than only a pair. Clusters of identical haplotypes could reveal information about the history of intermarriage, isolation of a population and also be medically important. We propose an efficient method to find clusters of identical segments among individuals in a large panel, called cPBWT, using PBWT data structure. The time complexity of finding all clusters of identical matches is linear to the sample size. Human genome harbors several runs of homozygous sites (ROHs) where identical haplotypes are inherited from each parent. We applied cPBWT on UKBiobank and searched for clusters of ROH region that are shared among multiple. We discovered strong associations between ROH regions and some noncancerous diseases, specifically autoimmune disorders.
Show less

Date Issued

2018

Identifier

CFE0007764, ucf:52393

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007764


Title

MultiVehicle Dispatching and Routing with Time Window Constraints and Limited Dock Capacity.

Creator

ElNashar, Ahmed, Nazzal, Dima, Sepulveda, Jose, Geiger, Christopher, Hosni, Yasser, University of Central Florida

Abstract / Description

The Vehicle Routing Problem with Time Windows (VRPTW) is an important and computationally hard optimization problem frequently encountered in Scheduling and logistics. The Vehicle Routing Problem (VRP) can be described as the problem of designing the most efficient and economical routes from one depot to a set of customers using a limited number of vehicles. This research addresses the VRPTW under the following additional complicating features that are often encountered in practical problems...
Show moreThe Vehicle Routing Problem with Time Windows (VRPTW) is an important and computationally hard optimization problem frequently encountered in Scheduling and logistics. The Vehicle Routing Problem (VRP) can be described as the problem of designing the most efficient and economical routes from one depot to a set of customers using a limited number of vehicles. This research addresses the VRPTW under the following additional complicating features that are often encountered in practical problems:1. Customers have strict time windows for receiving a vehicle, i.e., vehicles are not allowed to arrive at the customer's location earlier than the lower limit of the specified time window, which is relaxed in previous research work.2. There is a limited number of loading/unloading docks for dispatching/receiving the vehicles at the depotThe main goal of this research is to propose a framework for solving the VRPTW with the constraints stated above by generating nearoptimal routes for the vehicles so as to minimize the total traveling distance. First, the proposed framework clusters customers into groups based on their proximity to each other. Second, a Probabilistic Route Generation (PRG) algorithm is applied to each cluster to find the best route for visiting customers by each vehicle; multiple routes per vehicle are generated and each route is associated with a set of feasible dispatching times from the depot. Third, an assignment problem formulation determines the best dispatching time and route for each vehicle that minimizes the total traveling distance.iiiThe proposed algorithm is tested on a set of benchmark problems that were originally developed by Marius M. Solomon and the results indicate that the algorithm works well with about 1.14% average deviation from the bestknown solutions. The benchmark problems are then modified by adjusting some of the customer time window limits, and adding the staggered vehicle dispatching constraint. For demonstration purposes, the proposed clustering and PRG algorithms are then applied to the modified benchmark problems.
Show less

Date Issued

2012

Identifier

CFE0004532, ucf:49233

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0004532


Title

RAIN RATE ALGORITHM FOR AQUARIUS/SACD MICROWAVE RADIOMETER.

Creator

Menzerotolo, Rosa, Jones, W. Linwood, University of Central Florida

Abstract / Description

Microwave radiometers are used to measure blackbody microwave emissions emitted by natural targets. Radiative transfer theory provides a well founded physical relationship between the atmosphere and surface geophysical parameters and the brightness temperature measured by these radiometers. The atmospheric brightness temperature is proportional to the integral of the microwave absorption of water vapor, oxygen, and liquid water between the top of the atmosphere and the surface. Inverse...
Show moreMicrowave radiometers are used to measure blackbody microwave emissions emitted by natural targets. Radiative transfer theory provides a well founded physical relationship between the atmosphere and surface geophysical parameters and the brightness temperature measured by these radiometers. The atmospheric brightness temperature is proportional to the integral of the microwave absorption of water vapor, oxygen, and liquid water between the top of the atmosphere and the surface. Inverse radiative transfer models use to retrieve the water vapor, cloud liquid and oxygen content in the atmosphere are very well known; however, the retrieval of rain rate in the atmosphere is still a challenge. This project presents a theoretical basis for the rain rate retrieval algorithm, which will be implemented in the Aquarius/SACD Microwave Radiometer (MWR). This algorithm was developed based on the radiative transfer model theory for a single layer atmosphere using four WindSat channels. Transmissivity due to liquid water (rain and cloud liquid water) is retrieved from the four channel brightness temperatures, and a statistical regression is performed to relate the rain rate, rain physical temperature and rain height to the liquid water transmissivities at 24 GHz and 37 GHz. Empirical validation results are presented using the WindSat radiometer observations.
Show less

Date Issued

2011

Identifier

CFE0003571, ucf:48911

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0003571


Title

Algorithms for Community Identification in Complex Networks.

Creator

Vasudevan, Mahadevan, Deo, Narsingh, Hughes, Charles, Guha, Ratan, Chatterjee, Mainak, Zhao, Yue, University of Central Florida

Abstract / Description

Complex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;sR(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such...
Show moreComplex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;sR(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such property inherent to these networks. A community may informally be defined as a locallydense induced subgraph, of significant size, in a large globallysparse graph. Recent empirical results reveal communities in networks spanning across different disciplines () physics, statistics, sociology, biology, and linguistics. At least two different questions may be posed on the community structure in large networks: (i) Given a network, detect or extract all (i.e., sets of nodes that constitute) communities; and (ii) Given a node in the network, identify the best community that the given node belongs to, if there exists one. Several algorithms have been proposed to solve the former problem, known as Community Discovery. The latter problem, known as Community Identification, has also been studied, but to a much smaller extent. Both these problems have been shown to be NPcomplete, and a number of approximate algorithms have been proposed in recent years. A comprehensive taxonomy of the existing community detection algorithms is presented in this work. Global exploration of these complex networks to pull out communities (community discovery) is time and memory consuming. A more confined approach to mine communities in a given network is investigated in this research. Identifying communities does not require the knowledge of the entire graph. Community identification algorithms exist in the literature, but to a smaller extent. The dissertation presents a thorough description and analysis of the existing techniques to identify communities in large networks. Also a novel heuristic for identifying the community to which a given seed node belongs using only its neighborhood information is presented. An improved definition of a community based on the average degree of the induced subgraph is discussed thoroughly and it is compared with the various definitions in the literature. Next, a faster and accurate algorithm to identify communities in complex networks based on maximizing the average degree is described. The divisive nature of the algorithm (as against the existing agglomerative methods) efficiently identifies communities in large complex networks. The performance of the algorithm on several synthetic and realworld complex networks has also been thoroughly investigated.
Show less

Date Issued

2012

Identifier

CFE0004294, ucf:49463

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0004294


Title

Computational Methods for Comparative Noncoding RNA Analysis: From Structural Motif Identification to Genomewide Functional Classification.

Creator

Zhong, Cuncong, Zhang, Shaojie, Hu, Haiyan, Hua, Kien, Li, Xiaoman, University of Central Florida

Abstract / Description

Noncoding RNA (ncRNA) plays critical functional roles such as regulation, catalysis, and modification etc. in the biological system. Noncoding RNAs exert their functions based on their specific structures, which makes the thorough understanding of their structures a key step towards their complete functional annotation. In this dissertation, we will cover a suite of computational methods for the comparison of ncRNA secondary and 3D structures, and their applications to ncRNA molecular...
Show moreNoncoding RNA (ncRNA) plays critical functional roles such as regulation, catalysis, and modification etc. in the biological system. Noncoding RNAs exert their functions based on their specific structures, which makes the thorough understanding of their structures a key step towards their complete functional annotation. In this dissertation, we will cover a suite of computational methods for the comparison of ncRNA secondary and 3D structures, and their applications to ncRNA molecular structural annotation and their genomewide functional survey.Specifically, we have contributed the following five computational methods. First, we have developed an alignment algorithm to compare RNA structural motifs, which are recurrent RNA 3D structural fragments. Second, we have improved upon the previous alignment algorithm by incorporating basestacking information and devise a new branchandbond algorithm. Third, we have developed a clustering pipeline for RNA structural motif classification using the above alignment methods. Fourth, we have generalized the clustering pipeline to a genomewide analysis of RNA secondary structures. Finally, we have devised an ultrafast alignment algorithm for RNA secondary structure by using the sparse dynamic programming technique.A large number of novel RNA structural motif instances and ncRNA elements have been discovered throughout these studies. We anticipate that these computational methods will significantly facilitate the analysis of ncRNA structures in the future.
Show less

Date Issued

2013

Identifier

CFE0004966, ucf:49580

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0004966


Title

The Power of Quantum Walk: Insights, Implementation, and Applications.

Creator

Chiang, ChenFu, Wocjan, Pawel, Marinescu, Dan, Dechev, Damian, Mucciolo, Eduardo, University of Central Florida

Abstract / Description

In this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two...
Show moreIn this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two reflections in the walk operator provides a quadratic speedup, in comparison to the classical counterpart. For the implementation of quantum walks, I show the construction of an efficient circuit for realizing one single step of the quantum walk operator. Furthermore, I devise a more succinct circuit to approximately implement quantum phase estimation with constant precision controlled phase shift operators. From an implementation perspective, efficient circuits are always desirable because the realization of a phase shift operator with high precision would be a costly task and a critical obstacle. For the applications of quantum walks, I apply the quantum walk technique along with other fundamental quantum techniques, such as phase estimation, to solve the partition function problem. However, there might be some scenario in which the speedup of spectral gap is insignificant. In a situation like that that,I provide an amplitude amplificationbased approach to prepare the thermal Gibbs state. Such an approach is useful when the spectral gap is extremely small. Finally, I further investigate and explore the effect of noise (perturbation)on the performance of quantum walks.
Show less

Date Issued

2011

Identifier

CFE0004094, ucf:49148

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0004094


Title

Optimal distribution network reconfiguration using metaheuristic algorithms.

Creator

Asrari, Arash, Wu, Thomas, Lotfifard, Saeed, Haralambous, Michael, Atia, George, Pazour, Jennifer, University of Central Florida

Abstract / Description

Finding optimal configuration of power distribution systems topology is an NPhard combinatorial optimization problem. It becomes more complex when time varying nature of loads in largescale distribution systems is taken into account. In the second chapter of this dissertation, a systematic approach is proposed to tackle the computational burden of the procedure. To solve the optimization problem, a novel adaptive fuzzy based parallel genetic algorithm (GA) is proposed that employs the...
Show moreFinding optimal configuration of power distribution systems topology is an NPhard combinatorial optimization problem. It becomes more complex when time varying nature of loads in largescale distribution systems is taken into account. In the second chapter of this dissertation, a systematic approach is proposed to tackle the computational burden of the procedure. To solve the optimization problem, a novel adaptive fuzzy based parallel genetic algorithm (GA) is proposed that employs the concept of parallel computing in identifying the optimal configuration of the network. The integration of fuzzy logic into GA enhances the efficiency of the parallel GA by adaptively modifying the migration rates between different processors during the optimization process. A computationally efficient graph encoding method based on Dandelion coding strategy is developed which automatically generates radial topologies and prevents the construction of infeasible radial networks during the optimization process. The main shortcoming of the proposed algorithm in Chapter 2 is that it identifies only one single solution. It means that the system operator will not have any option but relying on the found solution. That is why a novel hybrid optimization algorithm is proposed in the third chapter of this dissertation that determines Pareto frontiers, as candidate solutions, for multiobjective distribution network reconfiguration problem. Implementing this model, the system operator will have more flexibility in choosing the best configuration among the alternative solutions. The proposed hybrid optimization algorithm combines the concept of fuzzy Pareto dominance (FPD) with shuffled frog leaping algorithm (SFLA) to recognize nondominated suboptimal solutions identified by SFLA. The local search step of SFLA is also customized for power systems applications so that it automatically creates and analyzes only the feasible and radial configurations in its optimization procedure which significantly increases the convergence speed of the algorithm. In the fourth chapter, the problem of optimal network reconfiguration is solved for the case in which the system operator is going to employ an optimization algorithm that is automatically modifying its parameters during the optimization process. Defining three fuzzy functions, the probability of crossover and mutation will be adaptively tuned as the algorithm proceeds and the premature convergence will be avoided while the convergence speed of identifying the optimal configuration will not decrease. This modified genetic algorithm is considered a step towards making the parallel GA, presented in the second chapter of this dissertation, more robust in avoiding from getting stuck in local optimums. In the fifth chapter, the concentration will be on finding a potential smart grid solution to more highquality suboptimal configurations of distribution networks. This chapter is considered an improvement for the third chapter of this dissertation for two reasons: (1) A fuzzy logic is used in the partitioning step of SFLA to improve the proposed optimization algorithm and to yield more accurate classification of frogs. (2) The problem of system reconfiguration is solved considering the presence of distributed generation (DG) units in the network. In order to study the new paradigm of integrating smart grids into power systems, it will be analyzed how the quality of suboptimal solutions can be affected when DG units are continuously added to the distribution network.The heuristic optimization algorithm which is proposed in Chapter 3 and is improved in Chapter 5 is implemented on a smaller case study in Chapter 6 to demonstrate that the identified solution through the optimization process is the same with the optimal solution found by an exhaustive search.
Show less

Date Issued

2015

Identifier

CFE0005575, ucf:50238

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0005575


Title

STUDIES OF A QUANTUM SCHEDULING ALGORITHM AND ON QUANTUM ERROR CORRECTION.

Creator

Lu, Feng, Marinescu, Dan, University of Central Florida

Abstract / Description

Quantum computation has been a rich field of study for decades because it promises possible spectacular advances, some of which may run counter to our classically rooted intuitions. At the same time, quantum computation is still in its infancy in both theoretical and practical areas. Efficient quantum algorithms are very limited in number and scope; no real breakthrough has yet been achieved in physical implementations. Grover's search algorithm can be applied to a wide range of problems;...
Show moreQuantum computation has been a rich field of study for decades because it promises possible spectacular advances, some of which may run counter to our classically rooted intuitions. At the same time, quantum computation is still in its infancy in both theoretical and practical areas. Efficient quantum algorithms are very limited in number and scope; no real breakthrough has yet been achieved in physical implementations. Grover's search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems can be reformulated to take advantage of quantum parallelism and entanglement leading to algorithms which show a square root speedup over their classical counterparts. This dissertation discusses a systematic way to formulate such problems and gives as an example a quantum scheduling algorithm for an RC_max problem. This thesis shows that quantum solution to such problems is not only feasible but in some cases advantageous. The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting only a single error per error correction cycle. Yet, timecorrelated errors are common for physical implementations of quantum systems; an error corrected during a certain cycle may reoccur in a later cycle due to physical processes specific to each physical implementation of the qubits. This dissertation discusses quantum error correction for a restricted class of timecorrelated errors in a spinboson model. The algorithm proposed allows the correction of two errors per error correction cycle, provided that one of them is timecorrelated. The algorithm can be applied to any stabilizer code, perfect or nonperfect, and simplified the circuit complexity significantly comparing to the classic quantum error correction codes.
Show less

Date Issued

2007

Identifier

CFE0001873, ucf:47391

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0001873


Title

GENETICALLY ENGINEERED ADAPTIVE RESONANCE THEORY (ART) NEURAL NETWORK ARCHITECTURES.

Creator

AlDaraiseh, Ahmad, Georgiopoulos, Michael, University of Central Florida

Abstract / Description

Fuzzy ARTMAP (FAM) is currently considered to be one of the premier neural network architectures in solving classification problems. One of the limitations of Fuzzy ARTMAP that has been extensively reported in the literature is the category proliferation problem. That is Fuzzy ARTMAP has the tendency of increasing its network size, as it is confronted with more and more data, especially if the data is of noisy and/or overlapping nature. To remedy this problem a number of researchers have...
Show moreFuzzy ARTMAP (FAM) is currently considered to be one of the premier neural network architectures in solving classification problems. One of the limitations of Fuzzy ARTMAP that has been extensively reported in the literature is the category proliferation problem. That is Fuzzy ARTMAP has the tendency of increasing its network size, as it is confronted with more and more data, especially if the data is of noisy and/or overlapping nature. To remedy this problem a number of researchers have designed modifications to the training phase of Fuzzy ARTMAP that had the beneficial effect of reducing this phenomenon. In this thesis we propose a new approach to handle the category proliferation problem in Fuzzy ARTMAP by evolving trained FAM architectures. We refer to the resulting FAM architectures as GFAM. We demonstrate through extensive experimentation that an evolved FAM (GFAM) exhibits good (sometimes optimal) generalization, small size (sometimes optimal size), and requires reasonable computational effort to produce an optimal or suboptimal network. Furthermore, comparisons of the GFAM with other approaches, proposed in the literature, which address the FAM category proliferation problem, illustrate that the GFAM has a number of advantages (i.e. produces smaller or equal size architectures, of better or as good generalization, with reduced computational complexity). Furthermore, in this dissertation we have extended the approach used with Fuzzy ARTMAP to other ART architectures, such as Ellipsoidal ARTMAP (EAM) and Gaussian ARTMAP (GAM) that also suffer from the ART category proliferation problem. Thus, we have designed and experimented with genetically engineered EAM and GAM architectures, named GEAM and GGAM. Comparisons of GEAM and GGAM with other ART architectures that were introduced in the ART literature, addressing the category proliferation problem, illustrate similar advantages observed by GFAM (i.e, GEAM and GGAM produce smaller size ART architectures, of better or improved generalization, with reduced computational complexity). Moverover, to optimally cover the input space of a problem, we proposed a genetically engineered ART architecture that combines the category structures of two different ART networks, FAM and EAM. We named this architecture UART (Universal ART). We analyzed the order of search in UART, that is the order according to which a FAM category or an EAM category is accessed in UART. This analysis allowed us to better understand UART's functionality. Experiments were also conducted to compare UART with other ART architectures, in a similar fashion as GFAM and GEAM were compared. Similar conclusions were drawn from this comparison, as in the comparison of GFAM and GEAM with other ART architectures. Finally, we analyzed the computational complexity of the genetically engineered ART architectures and we compared it with the computational complexity of other ART architectures, introduced into the literature. This analytical comparison verified our claim that the genetically engineered ART architectures produce better generalization and smaller sizes ART structures, at reduced computational complexity, compared to other ART approaches. In review, a methodology was introduced of how to combine the answers (categories) of ART architectures, using genetic algorithms. This methodology was successfully applied to FAM, EAM and FAM and EAM ART architectures, with success, resulting in ART neural networks which outperformed other ART architectures, previously introduced into the literature, and quite often produced ART architectures that attained optimal classification results, at reduced computational complexity.
Show less

Date Issued

2006

Identifier

CFE0000977, ucf:46696

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0000977


Title

MESHLESS HEMODYNAMICS MODELING AND EVOLUTIONARY SHAPE OPTIMIZATION OF BYPASS GRAFTS ANASTOMOSES.

Creator

El Zahab, Zaher, Kassab, Alain, University of Central Florida

Abstract / Description

Objectives: The main objective of the current dissertation is to establish a formal shape optimization procedure for a given bypass grafts endtoside distal anastomosis (ETSDA). The motivation behind this dissertation is that most of the previous ETSDA shape optimization research activities cited in the literature relied on direct optimization approaches that do not guaranty accurate optimization results. Three different ETSDA models are considered herein: The conventional, the Miller cuff,...
Show moreObjectives: The main objective of the current dissertation is to establish a formal shape optimization procedure for a given bypass grafts endtoside distal anastomosis (ETSDA). The motivation behind this dissertation is that most of the previous ETSDA shape optimization research activities cited in the literature relied on direct optimization approaches that do not guaranty accurate optimization results. Three different ETSDA models are considered herein: The conventional, the Miller cuff, and the hood models. Materials and Methods: The ETSDA shape optimization is driven by three computational objects: a localized collocation meshless method (LCMM) solver, an automated geometry preprocessor, and a geneticalgorithmbased optimizer. The usage of the LCMM solver is very convenient to set an autonomous optimization mechanism for the ETSDA models. The task of the automated preprocessor is to randomly distribute solution points in the ETSDA geometries. The task of the optimized is the adjust the ETSDA geometries based on mitigation of the abnormal hemodynamics parameters. Results: The results reported in this dissertation entail the stabilization and validation of the LCMM solver in addition to the shape optimization of the considered ETSDA models. The LCMM stabilization results consists validating a customdesigned upwinding scheme on different onedimensional and twodimensional test cases. The LCMM validation is done for incompressible steady and unsteady flow applications in the ETSDA models. The ETSDA shape optimization include singleobjective optimization results in steady flow situations and biobjective optimization results in pulsatile flow situations. Conclusions: The LCMM solver provides verifiably accurate resolution of hemodynamics and is demonstrated to be third order accurate in a comparison to a benchmark analytical solution of the NavierStokes. The geneticalgorithmbased shape optimization approach proved to be very effective for the conventional and Miller cuff ETSDA models. The shape optimization results for those two models definitely suggest that the graft caliber should be maximized whereas the anastomotic angle and the cuff height (in the Miller cuff model) should be chosen following a compromise between the wall shear stress spatial and temporal gradients. The shape optimization of the hood ETSDA model did not prove to be advantageous, however it could be meaningful with the inclusion of the suture line cut length as an optimization parameter.
Show less

Date Issued

2008

Identifier

CFE0002165, ucf:47927

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0002165


Title

Weierstrass vertices and divisor theory of graphs.

Creator

De Vas Gunasekara, Ajani Ruwandhika, Brennan, Joseph, Song, Zixia, Martin, Heath, University of Central Florida

Abstract / Description

Chipfiring games and divisor theory on finite, connected, undirected and unweighted graphs have been studied as analogs of divisor theory on Riemann Surfaces. As part of this theory, a version of the onedimensional RiemannRoch theorem was introduced for graphs by Matt Baker in 2007. Properties of algebraic curves that have been studied can be applied to study graphs by means of the divisor theory of graphs.In this research, we investigate the property of a vertex of a graph having the...
Show moreChipfiring games and divisor theory on finite, connected, undirected and unweighted graphs have been studied as analogs of divisor theory on Riemann Surfaces. As part of this theory, a version of the onedimensional RiemannRoch theorem was introduced for graphs by Matt Baker in 2007. Properties of algebraic curves that have been studied can be applied to study graphs by means of the divisor theory of graphs.In this research, we investigate the property of a vertex of a graph having the Weierstrass property in analogy to the theory of Weierstrass points on algebraic curves. The weight of the Weierstrass vertices is then calculated in a manner analogous to the algebraic curve case. Although there are many graphs for which all vertices are Weierstrass vertices, there are bounds on the total weight of the Weierstrass vertices as a function of the arithmetic genus.For complete graphs, all of the vertices are Weierstrass when the number of vertices (n) is greater than or equals to $4$ and no vertex is Weierstrass for $n$ strictly less than 4. We study the complete graphs on 4, 5 and 6 vertices and reveal a pattern in the gap sequence for higher cases of n.Furthermore, we introduce a formula to calculate the Weierstrass weight of a vertex of the complete graph on n vertices. Additionally, we prove that Weierstrass semigroup of complete graphs is 2  generated. Moreover, we show that there are no graphs of genus 2 and 6 vertices with all the vertices being normal Weierstrass vertices and generalize this result to any graph with genus g.
Show less

Date Issued

2018

Identifier

CFE0007397, ucf:52072

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007397


Title

Enhancing Cognitive Algorithms for Optimal Performance of Adaptive Networks.

Creator

LugoCordero, Hector, Guha, Ratan, Wu, Annie, Stanley, Kenneth, University of Central Florida

Abstract / Description

This research proposes to enhance some Evolutionary Algorithms in order to obtain optimal and adaptive network configurations. Due to the richness in technologies, low cost, and application usages, we consider Heterogeneous Wireless Mesh Networks. In particular, we evaluate the domains of Network Deployment, Smart Grids/Homes, and Intrusion Detection Systems. Having an adaptive network as one of the goals, we consider a robust noise tolerant methodology that can quickly react to changes in...
Show moreThis research proposes to enhance some Evolutionary Algorithms in order to obtain optimal and adaptive network configurations. Due to the richness in technologies, low cost, and application usages, we consider Heterogeneous Wireless Mesh Networks. In particular, we evaluate the domains of Network Deployment, Smart Grids/Homes, and Intrusion Detection Systems. Having an adaptive network as one of the goals, we consider a robust noise tolerant methodology that can quickly react to changes in the environment. Furthermore, the diversity of the performance objectives considered (e.g., power, coverage, anonymity, etc.) makes the objective function noncontinuous and therefore not have a derivative. For these reasons, we enhance Particle Swarm Optimization (PSO) algorithm with elements that aid in exploring for better configurations to obtain optimal and suboptimal configurations. According to results, the enhanced PSO promotes population diversity, leading to more unique optimal configurations for adapting to dynamic environments. The gradual complexification process demonstrated simpler optimal solutions than those obtained via trial and error without the enhancements.Configurations obtained by the modified PSO are further tuned in realtime upon environment changes. Such tuning occurs with a Fuzzy Logic Controller (FLC) which models human decision making by monitoring certain events in the algorithm. Example of such events include diversity and quality of solution in the environment. The FLC is able to adapt the enhanced PSO to changes in the environment, causing more exploration or exploitation as needed.By adding a Probabilistic Neural Network (PNN) classifier, the enhanced PSO is again used as a filter to aid in intrusion detection classification. This approach reduces miss classifications by consulting neighbors for classification in case of ambiguous samples. The performance of ambiguous votes via PSO filtering shows an improvement in classification, causing the simple classifier perform better the commonly used classifiers.
Show less

Date Issued

2018

Identifier

CFE0007046, ucf:52003

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007046


Title

MultiObjective Optimization for Construction Equipment Fleet Selection and Management In Highway Construction Projects Based on Time, Cost, and Quality Objectives.

Creator

Shehadeh, Ali, Tatari, Omer, AlDeek, Haitham, AbouSenna, Hatem, Flitsiyan, Elena, University of Central Florida

Abstract / Description

The sector of highway construction shares approximately 11% of the total construction industry in the US. Construction equipment can be considered as one of the primary reasons this industry has reached such a significant level, as it is considered an essential part of the highway construction process during highway project construction. This research addresses a multiobjective optimization mathematical model that quantifies and optimize the key parameters for excavator, truck, and motor...
Show moreThe sector of highway construction shares approximately 11% of the total construction industry in the US. Construction equipment can be considered as one of the primary reasons this industry has reached such a significant level, as it is considered an essential part of the highway construction process during highway project construction. This research addresses a multiobjective optimization mathematical model that quantifies and optimize the key parameters for excavator, truck, and motorgrader equipment to minimize time and cost objective functions. The model is also aimed to maintain the required level of quality for the targeted construction activity. The mathematical functions for the primary objectives were formulated and then a genetic algorithmbased multiobjective was performed to generate the timecost Pareto tradeoffs for all possible equipment combinations using MATLAB software to facilitate the implementation. The model's capabilities in generating optimal time and cost tradeoffs based on optimized equipment number, capacity, and speed to adapt with the complex and dynamic nature of highway construction projects are demonstrated using a highway construction case study. The developed model is a decision support tool during the construction process to adapt with any necessary changes into time or cost requirements taking into consideration environmental, safety and quality aspects. The flexibility and comprehensiveness of the proposed model, along with its programmable nature, make it a powerful tool for managing construction equipment, which will help saving time and money within the optimal quality margins. Also, this environmentally friendly decisionsupport tool model provided optimal solutions that help to reduce the CO2 emissions reducing the ripple effects of targeted highway construction activities on the global warming phenomenon. The generated optimal solutions offered considerable time and cost savings.
Show less

Date Issued

2019

Identifier

CFE0007863, ucf:52800

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0007863
Pages