Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

Made available in DSpace on 2016-06-02T19:30:03Z (GMT). No. of bitstreams: 1 6147.pdf: 5742623 bytes, checksum: c8c36ae76a987b5bc30a219a1f3c9bee (MD5) Previous issue date: 2014-06-06 / Universidade Federal de Sao Carlos / The objective of this study was to analyze the structure, composition, trophic ecology and food items shared by the fish fauna in the stream Beija -Flor, located in Jataí Ecological Station ( 21 ⁰ 36'32 .8 " S 47 ⁰ 48'0 .54 " W ), besides characterizing the trophic ecology of the species Hemigrammus marginatus, one of the most abundant in the Beija-Flor stream. The samples of fish were collected monthly from August 2011 to July 2012, using gill nets, trawl nets and baited traps in five sampling stations distributed along the Beija-Flor stream. The fish were fixed in 10% formalin in the field and in the laboratory were identified and subjected to biometric measurements. The stomachs were weighed and transferred to 70% alcohol and stomach contents were examined under a stereomicroscope to the lowest possible taxonomic level. Forty four fish species belonging to 33 genera, 16 families and 5 orders were collected. Most species were accidental ( 43.18 % ), followed by constant species ( 38.64 % ) and accessory (18.18 % ). The diet of 30 species was analyzed. The main dietary habit was insectivorous, followed by omnivorous habits, herbivorous, piscivorous and detritivore. The dietary overlap was high in several species during periods of dry and flood. Hemigrammus marginatus was classified as an insectivore. Food items of autochthonous origin of the orders Ephemeroptera and Trichoptera were more important during the dry season, while the items of allochthonous origin of the order Hymenoptera, were more important in the rainy season. The increase in the quantity and variety of food items during the flooding causes some species of fish to become more generalist and share food resources. Hemigrammus marginatus, Astyanax altiparanae, Metynnis maculatus, Serrapinnus notomelas and Oligosarcus pintoi, have complex of interactions with the food items and can be considered key species for stream Beija- Flor. The results showed that the stream Beija-Flor is a preserved, with high species diversity by being located within the Jataí Ecological Station, but is highly threatened by being surrounded by sugar cane plantations. / O Córrego Beija-Flor, localizado na Estação Ecológica de Jataí (21⁰36 32.8 S 47⁰48 0.54 W), é formado pelos córregos da Bandeira, do Jordão e das Cabaças, e deságua no rio Mogi-Guaçu, bacia do alto Paraná. O objetivo deste trabalho foi analisar a estrutura, a composição, a ecologia trófica, e o compartilhamento de itens alimentares pela ictiofauna e caracterizar a ecologia trófica da espécie Hemigrammus marginatus, uma das espécies mais abundantes do córrego Beija-Flor. As coletas de peixes foram realizadas mensalmente no período de agosto de 2011 a julho de 2012, utilizando-se redes de espera, rede de arrasto e armadilhas iscadas do tipo covo, em cinco estações de coleta distribuídas ao longo do córrego Beija-Flor. Os peixes foram fixados em formol 10% no campo e em laboratório foram identificados e submetidos a medidas biométricas. Os estômagos foram pesados e transferidos para álcool 70% e o conteúdo estomacal foi analisado em estereomicroscópio até o menor nível taxonômico possível. Foram coletadas 44 espécies de peixes pertencentes a 33 gêneros, 16 famílias e 5 ordens. A maioria das espécies foi de ocorrência acidental (43,18 %), seguida pelas espécies constantes (38,64 %) e acessórias (18,18 %). A dieta de 30 espécies foi analisada. O principal hábito alimentar foi insetívoro, seguido pelos hábitos onívoro, herbívoro, piscívoro e detritívoro. A sobreposição alimentar foi alta em diversas espécies nos períodos de seca e cheia. Hemigrammus marginatus foi considerado insetívoro. Os itens alimentares de origem autóctone das ordens Ephemeroptera e Trichoptera foram mais importantes no período de seca, enquanto os itens de origem alóctone, da ordem Hymenoptera, tiveram maior importância no período de cheia. O aumento na quantidade e variedade de itens alimentares no período de cheia faz com que algumas espécies de peixes se tornem mais generalistas e partilhem os recursos alimentares. Hemigrammus marginatus, Astyanax altiparanae, Metynnis maculatus, Serrapinnus notomelas e Oligosarcus pintoi, possuem um complexo de interações com os itens alimentares e podem ser consideradas espécies chaves para o córrego Beija- Flor. Os resultados mostraram que o córrego Beija-Flor é um riacho preservado, com alta diversidade de espécies por estar localizado dentro da Estação Ecológica de Jataí, mas encontra-se fortemente ameaçado por estar cercado por plantações de cana de açúcar.

The problem of feature selection is critical in several areas of machine learning and data analysis such as, for example, cancer classification using gene expression data, text categorization, etc. In this work, we consider feature selection for supervised learning problems, where one wishes to select a small set of features that facilitate learning a good prediction model in the reduced feature space. Our interest is primarily in filter methods that select features independently of the learning algorithm to be used and are generally faster to implement compared to other types of feature selection algorithms. Many common filter methods for feature selection make use of information-theoretic criteria such as those based on mutual information to guide their search process. However, even in simple binary classification problems, mutual information based methods do not always select the best set of features in terms of the Bayes error. In this thesis, we develop a general approach for selecting a set of features that directly aims to minimize the Bayes error in the reduced feature space with respect to the loss or performance measure of interest. We show that the mutual information based criterion is a special case of our setting when the loss function of interest is the logarithmic loss for class probability estimation. We give a greedy forward algorithm for approximately optimizing this criterion and demonstrate its application to several supervised learning problems including binary classification (with 0-1 error, cost-sensitive error, and F-measure), binary class probability estimation (with logarithmic loss), bipartite ranking (with pairwise disagreement loss), and multiclass classification (with multiclass 0-1 error). Our experiments suggest that the proposed approach is competitive with several state-of-the art methods.

In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied geometric proximity structures. These graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Locally Gabriel Graphs(LGGs) were proposed. A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel graphs are planar graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these graphs for various parameters like edge complexity(the maximum number of edges in these graphs),size of an independent set and dilation. We show that computing an edge maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V). We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance graphs(UDGs) are well studied geometric graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these graphs is 2n−7 when all the points are in convex position. A bipartite graph is called an ordered bipartite graph when the vertex set in each partition has a total order on its vertices. We introduce a family of ordered bipartite graphs with restrictions on some paths called path restricted ordered bi partite graphs (PRBGs)and show that their study is motivated by LGGs and UDGs on convex point sets. We show that a PRBG can be extracted from the UDGs/LGGs on convex point sets. First, we characterize a special kind of paths in PRBGs called forward paths, then we study some structural properties of these graphs. We show that a PRBG on n vertices has O(nlogn) edges and the bound is tight. It gives an alternate proof of O(nlogn)upper bound for the maximum number of edges in UDGs/LGGs on convex point sets. We study PRBGs with restrictions to the length of the forward paths and show an improved bound on the edge complexity when the length of the longest forward path is bounded. Then, we study the hierarchical structure amongst these graphs classes. Notably, we show that the class of UDGs on convex point sets is a strict sub class of LGGs on convex point sets.

Hypergraph partitioning lies at the heart of a number of problems in machine learning as well as other engineering disciplines. While partitioning uniform hypergraphs is often required in computer vision problems that involve multi-way similarities, non-uniform hypergraph partitioning has applications in database systems, circuit design etc. As in the case of graphs, it is known that for given objective and balance constraints, the problem of optimally partitioning a hypergraph is NP-hard. Yet, over the last two decades, several efficient heuristics have been studied in the literature and their empirical success is widely appreciated. In contrast to the extensive studies related to graph partitioning, the theoretical guarantees of hypergraph partitioning approaches have not received much attention in the literature. The purpose of this thesis is to establish the statistical error bounds for certain spectral algorithms for partitioning uniform as well as non-uniform hypergraphs. The mathematical framework considered in this thesis is the following. Let V be a set of n vertices, and ψ : V ->{1,…,k} be a (hidden) partition of V into k classes. A random hypergraph (V,E) is generated according to a planted partition model, i.e., subsets of V are independently added to the edge set E with probabilities depending on the class memberships of the participating vertices. Let ψ' be the partition of V obtained from a certain algorithm acting on a random realization of the hypergraph. We provide an upper bound on the number of disagreements between ψ and ψ'. To be precise, we show that under certain conditions, the asymptotic error is o(n) with probability (1-o(1)). In the existing literature, such error rates are only known in the case of graphs (Rohe et al., Ann. Statist., 2011; Lei \& Rinaldo, Ann. Statist., 2015), where the planted model coincides with the popular stochastic block model. Our results are based on matrix concentration inequalities and perturbation bounds, and the derived bounds can be used to comment on the consistency of spectral hypergraph partitioning algorithms. It is quite common in the literature to resort to a spectral approach when the quantity of interest is a matrix, for instance, the adjacency or Laplacian matrix for graph partitioning. This is certainly not true for hypergraph partitioning as the adjacency relations cannot be encoded into a symmetric matrix as in the case of graphs. However, if one restricts the problem to m-uniform hypergraphs for some m ≥ 2, then a symmetric tensor of order m can be used to express the multi-way interactions or adjacencies. Thus, the use of tensor spectral algorithms, based on the spectral theory of symmetric tensors, is a natural choice in this scenario. We observe that a wide variety of uniform hypergraph partitioning methods studied in the literature can be related to any one of two principle approaches: (1) solving a tensor trace maximization problem, or (2) use of the higher order singular value decomposition of tensors. We derive statistical error bounds to show that both these approaches lead to consistent partitioning algorithms. Our results also hold when the hypergraph under consideration allows weighted edges, a situation that is commonly encountered in computer vision applications such as motion segmentation, image registration etc. In spite of the theoretical guarantees, a tensor spectral approach is not preferable in this setting due to the time and space complexity of computing the weighted adjacency tensor. Keeping this practical scenario in mind, we prove that consistency can still be achieved by incorporating certain tensor sampling strategies. In particular, we show that if the edges are sampled according to certain distribution, then consistent partitioning can be achieved with only few sampled edges. Experiments on benchmark problems demonstrate that such sampled tensor spectral algorithms are indeed useful in practice. While vision tasks mostly involve uniform hypergraphs, in database and electronics applications, one often finds non-uniform hypergraphs with edges of varying sizes. These hypergraphs cannot be expressed in terms of adjacency matrices or tensors, and hence, use of a spectral approach is tricky in this context. The partitioning problem gets more challenging due to the fact that, in practice, these hypergraphs are quite sparse, and hence, provide less information about the partition. We consider spectral algorithms for partitioning clique and star expansions of hypergraphs, and study their consistency under a sparse planted partition model. The results of hypergraph partitioning can be further extended to address the well-known hypergraph vertex coloring problem, where the objective is to color the vertices such that no edge is monochromatic. The hardness of this problem is well established. In fact, even when a hypergraph is bipartite or 2-colorable, it is NP-hard to find a proper 2-coloring for it. We propose a spectral coloring algorithm, and show that if the non-monochromatic subsets of vertices are independently added to the edge set with certain probabilities, then with probability (1-o(1)), our algorithm succeeds in coloring bipartite hypergraphs with only two colors. To the best our knowledge, these are the first known results related to consistency of partitioning general hypergraphs.

中文摘要 有限離散條件分配相容性問題可依相容性檢驗、唯一性檢驗以及找出所有的聯合機率分配三層次來討論。目前的文獻資料有幾種研究方法，本文僅分析、比較其中的比值矩陣法和圖形法。 二維中，我們發現簡化二分圖的分支與IBD矩陣中的對角塊狀矩陣有密切的對應關係。在檢驗相容性時，圖形法只需檢驗簡化二分圖中的每個分支，正如同比值矩陣法只需檢驗IBD矩陣中的每一個對角塊狀矩陣即可。在檢驗唯一性時，圖形法只需檢驗簡化二分圖中的分支數是否唯一，正如同比值矩陣法只需檢驗IBD矩陣中的對角塊狀數是否唯一即可。在求所有的聯合機率分配時，運用比值矩陣法可推算出所有的聯合機率分配，但是圖形法則無法求出。 三維中，本文提出了修正比值矩陣法，將比值數組按照某種索引方式在平面上有規則地呈現，可降低所需處理矩陣的大小。此外，我們也發現修正比值矩陣中的橫直縱迴路和簡化二分圖中的迴路有對應的關係，因此可觀察出兩種方法所獲致某些結論的關聯性。在檢驗唯一性時，圖形法是檢驗簡化二分圖中的分支數是否唯一，而修正比值矩陣法是檢驗兩個修正比值矩陣是否分別有唯一的GROPE矩陣。修正比值矩陣法可推算出所有的聯合機率分配。 圖形法可用於任何維度中，修正比值矩陣法也可推廣到任何維度中，但在應用上，修正比值矩陣法比圖形法較為可行。 / The issue of the compatibility of finite discrete conditional distributions could be discussed hierarchically according to the compatibility, the uniqueness, and finding all possible joint probability distributions. There are several published methods, but only the Ratio Matrix Method and the Graphical Method are analyzed and compared in this thesis. In bivariate case, a close correspondence between the components of the reduced bipartite graph and the diagonal block matrices of the IBD matrix can be found. When we examine the compatibility, just as simply each diagonal block matrix of the IBD matrix needs to be examined using the Ratio Matrix Method, so does each component of the reduced bipartite graph using the Graphical Method. When we examine the uniqueness, just as whether the number of the diagonal blocks of the IBD matrix is unique needs to be examined, so does the number of the components of the reduced bipartite graph. The Ratio Matrix Method can provide all possible joint probability distributions, but the Graphical Method cannot. In trivariate case, this thesis proposes a Revised Ratio Matrix Method, in which we can present the ratio array regularly in the plane according to the index and reduce the corresponding matrix size. It is also found that each circuit in the revised ratio matrix corresponds to a circuit in the reduced bipartite graph. Therefore, the relation between the results of the two methods can be observed. When we examine the uniqueness with the Graphical Method, we examine whether the number of the components in the reduced bipartite graph is unique. But with the Revised Ratio Matrix Method, we examine whether each revised ratio matrix has a unique GROPE matrix. All possible joint probability distributions can be derived through the Revised Ratio Matrix Method. The Graphical Method can be applied to the higher dimensional cases, so can the Revised Ratio Matrix Method. But the Revised Ratio Matrix Method is more feasible than the Graphical Method in application.

The Master Thesis deals with the design of hardware component interconnection inference algorithm that is supposed to be used in the FPGA schema editor that was integrated into educational integrated development environment VLAM IDE. The aim of the algorithm is to support user by finding an optimal interconnection of two given components. The editor and the development environment are implemented as an Eclipse plugin using GMF framework. A brief description of this technologies and the embedded systems design are followed by the design of the inference algorithm. This problem is a topic of combinatorial optimization, related to the bipartite matching and assignment problem. After this, the implementation of the algorithm is described, followed by tests and a summary of achieved results.

Immersion based technologies such as Augmented Reality (AR), Virtual Reality (VR) and Mixed Reality (MR), together falling under the umbrella of Extended Reality (XR) have taken the world by storm in the recent past. However, with the growing market and the increasing number of applications of XR, multiple challenges have arisen. To maintain acceptable levels of motion-to-photon latency, there is a need to serve the users with ultra low latency and with high reliability. To provide high quality rendering, these solutions have traditionally been deployed with wired connections, but severely inhibiting user mobility. Thus, the need to develop wireless solutions promising ultra low latency and high reliability emerges. Cloud/Edge based solutions promise to provide great dividends in this regard but it still remains crucial to understand how different scheduling policies perform against one another in terms of average throughput, mean system time, the number of UEs which can be serviced simultaneously etc. In this thesis, we explore how online packet scheduling policies such as first-come-first-serve, earliestdeadline-first, maximum weight scheduling etc. compare against other Quality of Experience(QoE)/ packet weight aware online scheduling policies and also against optimal offline schemes such as maximum-weighted-bipartitematching. We perform a detailed analysis of how these policies fare by studying various metrics such as the average-packet system time, competitive ratios, packet drop percentages and weight throughput, amongst others. Finally, we also explore how the introduction of multi-layered video encoding impacts XR service. Amongst the findings of the thesis, we conclude that it is possible to come up with solutions such as EDFα (which is a deadline and weight aware derivative of the earliest deadline first scheduling policy), which can either increase the weight throughput when compared to other baselines while also providing lesser packet drops and lower average system times for the scheduled packets. This algorithm can be further tuned by varying α to accordingly alter the weight throughput, system time and packet drop ratio depending on the precise user application. Additionally, we establish with the help of simulations that the introduction of multi-layered video encoding conclusively helps in reducing the average system time and eventually allows for more users to be accommodated in an XR based system at the cost of worsening video quality. / Immersionsbaserade teknologier som Augmented Reality (AR), Virtual Reality (VR) och Mixed Reality (MR), som tillsammans faller under paraplyet Extended Reality (XR) har tagit världen med storm på senare tid. Men med den växande marknaden och det ökande antalet tillämpningar av XR har flera utmaningar uppstått. För att förhindra åksjuka hos användare och för att upprätthålla acceptabla nivåer av rörelse-till-foton-latens, finns det ett behov av att betjäna användarna med ultralåg latens och med hög tillförlitlighet. För att ge högkvalitativ rendering har dessa lösningar traditionellt implementerats med trådbundna anslutningar, men de hämmar kraftigt användarens rörlighet. Därför uppstår behovet av att utveckla trådlösa lösningar som lovar ultralåg latens och hög tillförlitlighet. Moln/Edge-baserade lösningar lovar att ge stor utdelning i detta avseende, men det är fortfarande viktigt att förstå hur olika schemaläggningspolicyer fungerar mot varandra när det gäller genomsnittlig genomströmning, genomsnittlig systemtid, antalet UE:er som kan betjänas samtidigt etc. I den här avhandlingen undersöker vi hur online-paketschemaläggningspolicyer som round robin, först till kvarnförst-kvarn, tidigast-deadline-först, schemaläggning för maximal vikt etc. jämförs med andra Quality of Experience (QoE)/Viktmedvetna onlineschemaläggningspolicyer och även mot optimala offline-scheman såsom maximalt viktad-bipartite-matchning. Vi utför en detaljerad analys av hur dessa policyer klarar sig genom att studera olika mätvärden, såsom den genomsnittliga paketets systemtid, konkurrensförhållanden, procentsatser för paketnedgång och viktad genomströmning, bland annat. Slutligen undersöker vi också hur introduktionen av flerskiktad videokodning påverkar XRtjänsten. Bland resultaten av avhandlingen drar vi slutsatsen att det är möjligt att komma med lösningar som EDFα (som är en deadline- och viktmedveten derivata av Earliest deadline first scheduling policy), som antingen kan öka den viktade genomströmning jämfört med andra baslinjer samtidigt som det ger mindre paketnedgångar och lägre genomsnittliga systemtider för de schemalagda paketen. Denna algoritm kan ställas in ytterligare genom att variera α för att följaktligen ändra den viktade genomströmningen, systemtiden och paketnedgångshastigheten beroende på den exakta användarapplikationen. Dessutom fastställer vi med hjälp av simuleringar att införandet av flerskiktsvideokodning definitivt hjälper till att minska den genomsnittliga systemtiden och så småningom tillåter fler användare att få plats i ett XR-baserat system.