Search

This thesis presents a new model to protein function prediction using support vector machines, a machine learning approach trained using structural parameters calculated from protein tertiary structure. The model is different from the others paradigms because it is not necessary to search for similarities against the others known proteins in public databases by alignments. In this way, the model is able to associate functional relationships among proteins with no similarities and it could be used when all other methods fail or when the user don t want to use the concept of similarity in function predictions. The proof that the model is valid was accomplished analyzing its performance with unknown proteins, i.e proteins not used in the training set. The validation approach used a set of binding proteins. Fundação de Amparo a Pesquisa do Estado de Alagoas Este trabalho apresenta um novo modelo capaz de prever a função de proteí­nas utilizando máquinas de vetor de suporte, um método de aprendizagem de máquina treinado usando parâmetros estruturais calculados a partir da conformação espacial da própria proteí­na. O modelo difere do paradigma comum de predição por não ser necessário calcular similaridades por meio de alinhamentos entre a proteí­na que se deseja prever a função e as proteí­nas de função conhecida presentes nos bancos de dados públicos. Dessa forma, o modelo é capaz de associar função às proteí­nas que não possuem qualquer semelhança com proteí­nas conhecidas, podendo ser usado quando todos os outros métodos falham ou quando não se deseja utilizar o conceito de similaridade na predição da função. A justificativa de que o modelo é válido foi realizada analisando sua performance ao prever funções de proteí­nas desconhecidas, proteí­nas não usadas no treinamento, utilizando como estudo de caso um conjunto de proteí­nas de ligação.

Orientador: Ulisses Martins Dias Dissertação (mestrado) – Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Futebol é um dos esportes mais populares do mundo, sendo essa popularidade refletida nas movimentações financeiras das competições profissionais, que se tornam cada vez mais competitivas a ponto de qualquer vantagem tática influenciar nos resultados. Este trabalho pretende investigar se, observando os primeiros segundos da tomada de posse de bola por uma equipe, seria possível identificar se aquela posse de bola resultaria em uma jogada de perigo na zona de ataque próxima à grande área do oponente, dado que a maneira de vencer uma partida implica em chegar próximo ao gol adversário com a posse de bola. Para responder a essa questão, utilizamos métricas extraídas da atuação dos jogadores e de suas interações em campo, como, por exemplo: posição dos jogadores de ambas as equipes em função do tempo e métricas de redes (centralidade, entropia, vulnerabilidade da rede). Esses dados são tratados modelando o posicionamento dos jogadores como uma série temporal de grafos em que, a cada instante de tempo, o posicionamento dos jogadores gera uma rede. As métricas dessas redes, quando convertidas em imagens de ritmo visual, permitem a extração de características por meio de arquiteturas de redes convolucionais profundas, o que aproxima o nosso estudo da área de aprendizado profundo (do inglês, deep learning), agregando possibilidades como o uso de técnicas de transferência de aprendizado (do inglês, transfer learning) junto de um refinamento (do inglês, fine-tune). A validação foi feita com a arquitetura EfficientNet B0, sendo utilizada para a transferência de aprendizado a partir de uma rede treinada com dados do ImageNet e com seus pesos ajustados com nossos dados. Dessa forma, características de imagens foram obtidas e aplicadas para o treinamento de uma Rede Neural Profunda (do inglês, Deep Neural Network) para a classificação das amostras. A técnica de grid-search com validação cruzada foi utilizada para otimizar os parâmetros da rede. Essa modelagem pretendem determinar se a posse de bola irá produzir uma jogada ofensiva no campo próximo ao gol do oponente. Além disso, validar quais métricas mais influenciam o resultado do modelo, permitindo assim identificar as mais determinantes para se chegar com a posse de bola na zona de defesa do oponente. Os resultados indicam que as chegadas próximas à grande área adversária podem ser preditas observando somente os primeiros 5 segundos de posse de bola, e que as principais métricas utilizadas pelos modelos encontram embasamento na literatura de análise de partidas de futebol Abstract: The focus of this work is investigated if watching the first seconds of a ball possession interval (BPI) of a team is possible to determine whether the ball possession will arrive in the last fourth of the soccer field, thereafter creating a goal chance situation. For answer this question were extracted metrics of players interactions like: the players positions of both teams in function of time and the graph metrics (centrality, entropy, vulnerably). The players positions were modeled in a temporal series of graphs, where each instant of time is represented as a network. These metrics when converted to images of visual rhythm allow the feature extraction through convolutional networks, what allows use of transfer learning techniques with fine-tuning. Efficient B0 architecture was used for the transfer of learning with fine-tuning, this network was trained begin the ImageNet dataset and your weights adjusted with your data. In this way, the features were obtained and applied to a Deep Neural Network (DNN) that are the responsible for classify the ball possessions. The grid-search technic with cross-validate was utilized to optimize the parameters of the DNN. This modeling intends to determine if the ball possession will produce an offensive play nearest the adversary penalty area. Furthermore, we intend valid which are the metrics that influence in the classifier results, thus allowing to identify the most important metric for the ball possession arrive in the final quarter of the pitch. The results indicate that the arrivals near the opponent box can be predicted only looking the first 5 seconds of ball possession, and that the main metrics utilized by the models has foundation on literature of soccer match analyzes Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia FAPESP 2019/17729-0, 2019/22262-3, 2019/16253-1, 021/00050-4)

Orientadores: Zanoni Dias, Ulisses Martins Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A genômica comparativa é um campo de pesquisa da biologia com foco na comparação de características genéticas entre organismos. Dentre as características genéticas comumente utilizadas, podemos citar a sequência de genes dos genomas. O número de mutações genéticas capazes de transformar uma sequência genética em outra é uma das métricas amplamente utilizada para a comparação de dois genomas. Os rearranjos de genoma são eventos mutacionais que podem afetar grandes trechos de um genoma. A reversão e a transposição são dois dos eventos de rearranjo mais estudados na literatura. Uma reversão inverte um segmento do genoma, enquanto uma transposição troca a posição de dois segmentos adjacentes. Um modelo de rearranjo determina o conjunto de eventos de rearranjo que podem ser utilizados para transformar um genoma em outro. Os primeiros estudos apresentaram resultados considerando modelos de rearranjo constituídos exclusivamente por um único tipo de evento de rearranjo. Estudos posteriores apresentaram resultados considerando modelos de rearranjo compostos por múltiplos tipos de eventos de rearranjo. Quando consideramos apenas o número de eventos de rearranjo necessários para transformar um genoma em outro, assumimos que cada evento tem a mesma probabilidade de ocorrer em um cenário evolutivo, sendo essa abordagem chamada de não ponderada. No entanto, quando assumimos que determinados tipos de eventos ocorrem mais do que outros, é possível atribuir um custo a cada tipo de evento de rearranjo. Nessa nova versão, o objetivo do problema consiste em buscar uma sequência de eventos de rearranjo que transforme um genoma em outro com custo mínimo, sendo essa abordagem chamada de ponderada. Nesta tese, apresentamos uma abordagem que considera uma proporção mínima entre a quantidade de eventos de reversão e o tamanho da sequência de eventos de rearranjo que transforma um genoma em outro. Nós mostramos que a abordagem de proporção naturalmente contorna problemas que podem surgir adotando uma abordagem ponderada ou não ponderada. Além disso, realizamos uma análise de complexidade do problema e apresentamos algoritmos de aproximação com fatores constantes. Estudos têm destacado a importância da informação presente nas regiões intergênicas, que são estruturas presentes entre cada par de genes e nas extremidades de um genoma, e que podem levar a modelos mais realistas considerando um contexto evolutivo. O tamanho de cada região intergênica é dado pelo número de nucleotídeos presentes nela. Desde então, foram apresentados estudos considerando tanto a sequência de genes quanto o tamanho das regiões intergênicas para representar um genoma. Nesta tese, mostramos resultados nesse mesmo contexto, mas consideramos diferentes modelos de rearranjo. Além disso, introduzimos uma generalização dos problemas possibilitando atribuir um grau de flexibilidade em relação ao tamanho das regiões intergênicas desejadas no genoma alvo. Para ambos os casos, realizamos uma análise de complexidade dos problemas, desenvolvemos algoritmos e conduzimos experimentos para verificar o desempenho prático Abstract: Comparative genomics is a field of research in biology focusing on comparing genetic features between organisms. Among the genetic features commonly used, we can mention the sequence of genes in genomes. The number of genetic mutations capable of transforming one gene sequence into another is a widely used metric to compare genomes. Genome rearrangement events are mutational events that can affect large stretches of a genome. Reversal and transposition are two of the most studied rearrangement events in the literature. A reversal inverts a genome segment, while a transposition exchanges the position of two adjacent segments. A rearrangement model determines the set of rearrangement events that can be used to transform one genome into another. Early studies presented results considering a rearrangement model consisting exclusively of a single type of rearrangement event. However, subsequent studies presented results considering rearrangement models composed of multiple rearrangement events. When we consider only the number of rearrangement events that are required to transform one genome into another, we assume that each event has the same probability of occurring in an evolutionary scenario; this is called the unweighted approach. However, when we want certain types of events to occur more than others, it is possible to assign a cost to each type of rearrangement event. The problem goal changes to search for a sequence of rearrangement events that transforms one genome into another with minimal cost; this is called the weighted approach. In this work, we introduce an approach that considers a minimum proportion between the number of reversal events and the size of the rearrangement sequence that transforms one genome into another. We show that the proportion approach naturally overcomes problems that may arise by adopting a weighted or unweighted approach. In addition, we perform a complexity analysis of the problem and present approximation algorithms with constant factors. Another genetic feature that studies pointed out as relevant in a genetic comparison context is the intergenic regions, which are structures between each pair of genes and at the extremities of a genome. The size of each intergenic region is the number of nucleotides within it. Since then, studies were presented considering both the sequence of genes and the size of the intergenic regions to represent a genome. In this work, we show results in this same context but we consider different rearrangement models. In addition, we introduce a generalization of the problems such that it is possible to assign a degree of flexibility regarding the size of the intergenic regions desired in the target genome. For both cases, we conducted a complexity analysis of the problems, developed algorithms, and performed experiments to verify the practical performance Doutorado Ciência da Computação Doutor em Ciência da Computação CNPQ 140272/2020-8 CAPES 001

Orientador: Guilherme Palermo Coelho Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: O mercado de ações é um importante segmento da economia que movimenta diariamente um grande volume de ativos, devido às transações realizadas entre empresas de capital aberto e investidores. Diversos fatores influenciam direta e indiretamente os valores dessas transações, o que pode gerar variações abruptas. Essa oscilação é um problema para aqueles que estudam esse nicho e buscam formas de se estimar valores futuros de ações, o que significaria uma vantagem para maximização de lucros na compra e vendas de ações. O problema é ainda maior quando uma série histórica de valores de ações apresenta o fenômeno de mudança de conceito, ou seja, quando os padrões de valores vão mudando ao longo do tempo. Neste trabalho, buscou-se avaliar se a presença de mecanismos capazes de lidar com mudanças de conceito em preditores baseados em aprendizado de máquina melhora a capacidade de predição de valores futuros de ações. A partir de uma base de dados históricos de 10 ações negociadas na bolsa de valores brasileira, coletados em um período de 20 anos, foi verificada a ocorrência de mudança de conceito em tais séries temporais e comparados os desempenhos de preditores baseados em diferentes paradigmas: Random Forests (RF), Support Vector Machines (SVM), K-Nearest Neighbors (KNN), Online Sequential Extreme Learning Machines (OS-ELM), Dynamic and Online Ensemble for Regression (DOER) e Ensemble of Online Learners With Substituiton of Models (EOS). Dentre esses, OS-ELM, DOER e EOS possuem mecanismos para lidar com mudanças de conceito. Os resultados mostraram que, apesar de as estrategias que incorporam mecanismos para tratamento de mudança de conceito demandarem um maior tempo computacional, elas também tendem a apresentar menores erros de predição. De acordo com o teste estatístico de Bergmann-Hommel foi possível observar que os modelos SVM e RF com uma versão ajustada possuem desempenho similares aos de modelos que lidam com mudança de conceito Abstract: The stock market is an important segment of the economy that circulates a large volume of assets due to transactions between open-ended companies and investors. Several factors, directly and indirectly, affect these transaction values, which can generate abrupt variations. The stock value fluctuation is a problem for those who search for ways to predict future stocks values, which would mean an advantage for profits maximization in buying and selling stocks. The problem becomes even harder when the stock values series presents the concept drift phenomenon, where patterns change over time. In this work, we evaluated whether mechanisms that deal with concept drift in machine learning-based predictors improve their stock market forecasting capabilities. From a historic database of 10 stocks negotiated in the Brazilian stock exchange, considering a time period of 20 years, we verified the occurrence of concept drift and compared the performance of predictors based in different paradigms: Random Forests (RF), Support Vector Machines (SVM), K-Nearest Neighbors (KNN), Online Sequential Extreme Learning Machines (OS-ELM), Dynamic and Online Ensemble for Regression (DOER) and Ensemble of Online Learners With Substitution of Models (EOS). Among these, OS-ELM, DOER and EOS explicitly deal with concept drift. The obtained results showed that, despite the higher computational time required by strategies that include mechanisms for handling concept drift, such strategies also tend to yield smaller predictions errors. Besides, according to the Bergmann-Hommel’s statistical test, it was possible to observe that SVM and RF with an adjusted version models achieve similar performances to models that deal with the concept drift Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES 001

Orientadores: Guilherme Palermo Coelho, Ana Estela Antunes da Silva Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: O desenvolvimento da economia global permite a empresas abrirem o seu capital com o objetivo de obter recursos financeiros para acelerar o seu crescimento. Esse cenário atrai investidores que desejam lucratividade nos mercados financeiros. Assim, a literatura apresenta diversas técnicas voltadas para previsão e análise do mercado financeiro, em especial o mercado de ações. Nesse contexto, destacam-se duas abordagens distintas, denominadas análise técnica e fundamentalista. Enquanto a análise técnica procura prever o mercado tendo como base indicadores calculados considerando o preço passado das ações, a análise fundamentalista considera dados oriundos de notícias, rentabilidade e fatores macroeconômicos. No entanto, a junção de ambas as escolas de pensamento em um único sistema de previsão do mercado de ações ainda é um tópico em aberto na literatura. Por um lado, o uso de Redes Neurais Artificiais (RNAs), principalmente RNAs profundas, tem se mostrado uma abordagem interessante para previsão de valores futuros do mercado de ações, sendo empregadas em muitos problemas voltados à análise técnica. Essas redes têm apresentado melhores resultados de previsão quando comparadas aos modelos estatísticos tradicionais, que utilizam normalmente dados vindos de séries temporais de valores de ações e indicadores técnicos. Por outro lado, mais recentemente, surgiram trabalhos na literatura indicando o uso de Análise de Sentimentos (AS) aplicada a notícias financeiras como um importante indicativo voltado à análise fundamentalista para a previsão da oscilação do mercado acionário. Apesar dos esforços recentes para combinar o uso dessas fontes de dados, a literatura carece de trabalhos em que essas estratégias sejam executadas em uma abordagem totalmente baseada em RNAs profundas, que têm obtido resultados do estado da arte em muitas tarefas de regressão e classificação. Portanto, no sentido de apoiar o processo de tomada de decisão e previsão frente ao grande número de informações disponíveis, este trabalho tem como objetivo principal apresentar uma abordagem de previsão do mercado de ações brasileiro por meio de Aprendizado Profundo, integrando dados voltados tanto à análise técnica quanto à análise fundamentalista, a saber: séries temporais de valores de ações, indicadores técnicos, e de Análise de Sentimentos aplicada a notícias. Os experimentos foram realizados com dados do período de 2010 a 2019, tanto do índice Ibovespa quanto de empresas relevantes do mercado de ações brasileiro: Banco do Brasil, Itaú, Ambev e Gerdau. Os resultados mostram que a combinação de preços de ações, indicadores técnicos e notícias melhora a previsão do mercado de ações considerando tanto o erro de previsão quanto o valor final do investimento Abstract: The global economy has led companies to open their capital to obtain resources to accelerate their growth. This scenario attracts investors who want to profit, stimulating the science community to develop techniques to forecast and analyze the stock market. Thus, two distinct approaches are highlighted, namely technical and fundamental analyses. While technical analysis tries to predict the stock market based on indicators calculated considering the past stock prices, fundamental analysis considers data from news, profitability, and macroeconomic factors. However, the combination of both schools of thought into a single stock market prediction system is still an open challenge in the literature. On the one hand, the use of Artificial Neural Networks (ANNs), mainly deep ANNs, has been shown to be an interesting approach to predicting future stock market values, being employed mainly in technical analysis. These ANNs have shown better prediction results when compared to traditional statistical models, which generally use stock prices and technical indicators as a data source. On the other hand, more recently, studies have indicated that Sentiment Analysis (SA) applied to financial news as an important fundamental analysis indicator to predict the stock market movement. Despite recent efforts to combine the use of these data sources, the literature lacks works in which these strategies are performed in an approach entirely based on deep ANNs, which have obtained state-of-the-art results in many regression and classification tasks. Therefore, in order to support the decision-making and forecasting process considering a large amount of available information, this work aims to present an approach to predict the Brazilian stock market through Deep Learning, integrating data of both technical and fundamental analysis, namely: stock prices, technical indicators, and financial news. The experiments were performed with data from 2010 to 2019, considering the Ibovespa index and the following relevant companies of the Brazilian stock market: Banco do Brasil, Itaú, Ambev, and Gerdau. The results show that the combination of stock prices, technical indicators, and news improves stock market prediction considering both the prediction error and the return on investment Doutorado Sistemas de Informação e Comunicação Doutor em Tecnologia CAPES 001

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Reconstrução filogenética é o campo da Biologia Computacional dedicado a inferir um histórico evolutivo a partir de dados biológicos do presente. Nesta tese de doutorado, apresentamos três trabalhos sobre diferentes problemas relacionados ao tema. O primeiro visa reconstruir o ancestral comum a três genomas de entrada. Apesar da entrada aparentemente limitada, este problema pode ser aplicado para determinar ancestrais em árvores de topologia já conhecida. Nosso trabalho introduz uma forma de representar genomas através de matrizes. A partir disto, definimos o problema da mediana de matrizes, que, dadas três matrizes A, B e C, consiste em encontrar uma matriz M que minimize a soma d(A,M) + d(B,M) + d(C,M), onde d(X,Y) é o posto da matriz Y-X. Para resolver tal problema, apresentamos um algoritmo aproximado que garante resultados no mínimo tão bons quanto um dos genomas de entrada, mas que, em experimentos simulando a evolução de genomas, teve resultados muito mais próximos do ótimo. Além disso, mostramos também uma heurística que traduz uma matriz qualquer, como a resultante do nosso algoritmo, de volta para um genoma. No segundo, o objetivo é reconstruir genomas ancestrais a partir dos históricos evolutivos de suas famílias de genes. Para isto, estendemos o esquema de programação dinâmica do software DeCo, que constrói florestas retratando a evolução de adjacências. Nossa implementação, em vez de escolher apenas as adjacências de uma solução mais parcimoniosa, explora todo o espaço de soluções, escolhendo adjacências em função da sua maior frequência. Com esta abordagem, conseguimos reduzir significativamente o número de inconsistências ao avaliar múltiplas instâncias sobre os mesmos genes. Finalmente, discutimos uma ferramenta capaz de auxiliar na reconstrução de genomas ancestrais, considerando os genomas de espécies descendentes e sem a necessidade dos históricos de todas as famílias de genes. Esta ferramenta é a estrutura de dados chamada árvore PQR, que não só detecta se a entrada tem a propriedade dos uns consecutivos, como também indica os obstáculos que possivelmente impedem a instância de ter a propriedade. Isto é importante porque, ao reconstruir genomas ancestrais, erros na entrada são muito comuns e podem muito facilmente impedir a instância de ter a propriedade dos uns consecutivos. Aqui, consolidamos o conhecimento sobre os algoritmos online e offline para árvores PQR em um único artigo. Com isto, avançamos em três diferentes direções o conhecimento nas áreas de Reconstrução Filogenética e de Biologia Computacional Abstract: Phylogenetic reconstruction is the field of computational biology dedicated to infer evolutionary history from given extant biologic data. In this PhD thesis, we present three works on different issues related to the topic. The first aims to reconstruct the common ancestor to three input genomes. Despite the apparently limited input, this problem can be applied to determine ancestors in trees whose topology is already known. Our work introduces a way to represent genomes using matrices. From this, we define the matrix median problem, which consists of, given three matrices A, B and C, find a matrix M that minimizes the sum d(A,M) + d(B,M) + d(C,M), where d(X,Y) is the rank of the matrix Y-X. To solve this problem, we present an approximate algorithm that ensures results at least as good as one of the input genomes, but that, in the experiments simulating the evolution of genomes, got much closer to optimal results. Furthermore, we also show a heuristic that translates any matrix, like the ones returned by our algorithm, back to a genome. In the second, the goal is to reconstruct ancestral genomes from the evolutionary histories of their respective gene families. For this, we extend the dynamic programming scheme of DeCo, that builds forests depicting the evolution of adjacencies. Our implementation, instead of choosing just the adjacencies of one most parsimonious solution, explores the entire solution space, choosing adjacencies in function of their larger frequency. Using this approach, we managed significantly reduce the number of inconsistencies while evaluating multiple instances on the same genes. Finally, we discuss a tool to assist in the reconstruction of ancient genomes, considering the genomes of descendant species, without the need for the histories of all the gene families. This tool is the data structure called PQR-tree, which not only detects whether the entry has the consecutive ones property, but also the obstacles that possibly prevent the instance from having said property. This is important because, while reconstructing ancient genomes, entry errors are very common and can very easily prevent the instance from having the consecutive ones property. Here, we consolidate the knowledge on the online and offline algorithms for PQR trees in a single paper. With these, we moved knowledge in phylogenetic reconstruction and computational biology forward in three different directions Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES FAPESP 2012/13865-7, 2013/07868-6

Orientadores: Paulo Sérgio Martins Pedro, Edson Luiz Ursini Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Este trabalho procura solucionar um dos problemas mais críticos das redes it Flying AdHoc (FANET), que é a questão da coordenação da recarga de baterias de drones que voam em forma de enxame (Swarms). Para que as recargas sejam realizadas da melhor maneira possível, é desejável que o número de dispositivos de carregamento (estações base) não seja excessivamente alto principalmente devido ao alto custo de implantação. Por outro lado, também é necessário que, quando os drones quiserem recarregar, sempre haja uma fonte de energia disponível. Ou seja, buscamos o equilíbrio entre o número economicamente viável de estações de recarga e o abastecimento adequado dos drones quando isso for necessário. Para essa finalidade, propomos agentes (drones) munidos de inteligência interna, ou seja, com preditores internos que fornecem inteligência na tentativa de prever a próxima taxa de presença nesse dispositivo de carregamento e dessa maneira poder decidir se deve ou não ir abastecer. O ideal é que a previsão seja sempre a melhor possível. Assim, o drone deveria ir quando prevê que deve ir e não deveria ir quando prevê não ir. A utilização do equilíbrio de Nash para este problema, sendo possível pela utilização da modelagem via o Problema El Farol Bar (PEFB), permite o desenvolvimento de uma analogia sem o conluio dos agentes na coordenação da simulação da recarga desse conjunto de drones. Ou seja, com relação à coordenação do enxame para a recarga das baterias não haverá gasto de energia em comunicação, embora esta continue nas demais tarefas inerentes ao {\it swarm} de drones. A verificação da adequação da proposta é feita por meio de Simulação Baseada em Agentes e neste modelo são utilizadas três políticas diferentes para a tomada de decisão do melhor preditor para cada drone. Isso permite verificar o desempenho na operação do sistema por meio do Equilíbrio de Nash. No atual estado dessa analogia considera-se que, caso os drones forem para a estação de recarga e a mesma estiver cheia, não haverá recarga possível porque o sistema estará sobrecarregado. Neste estudo estão incluídas análises microscópicas e macroscópicas do desempenho do swarm. A análise microscópica é a avaliação do desempenho das recompensas de cada preditor em relação a um conjunto de parâmetros de simulação, visando um aumento da eficácia no desempenho microscópico. A análise macroscópica é a avaliação do desempenho do atendimento global do sistema com os três tipos de políticas. Esta última análise é usada como base para o desenvolvimento da analogia de recarga dos drones. Dessa maneira, avalia-se o desempenho dos melhores conjuntos de simulação para a recarga dos drones que permitem abastecer abaixo do limiar de recarga (número de posições disponível de recarga), mas que estão relativamente próximos a esse limiar Abstract: This work seeks to solve one of the most critical problems of the Flying AdHoc (FANET) networks, which is the issue of coordinating the recharging of drones that fly in the form of Swarms. For recharging to be done in the best possible way, it is desirable that the number of charging devices (base stations) did not be excessively high due to the high implementation cost. Conversely, it is also necessary that, when drones want to recharge, they must have a source of energy available. In other words, we search for a balance between the economically viable number of charging stations and the adequate energy supply for the drones when necessary. For this, we propose agents (drones) equipped with internal intelligence, that is, with internal predictors that provide intelligence to attempt to predict the next attendance rate in the charging device and thus be able to decide whether go or not go to the recharging. Ideally, the forecast should be as best as possible. Therefore, the drone should go when it predicts it should go and it shouldn't go when it predicts not to go. The Nash equilibrium usage for this problem is made possible by the modeling via the El Farol Bar Problem (EFBP), which allows the development of this analogy without the collusion of agents in coordinating the simulation of the recharge of this set of drones. In other words, there will be no energy expenditure on communication about the drones' battery recharging coordination, although the communication will continue in the other tasks inherent to the swarm of drones. The verification of the suitability of the proposal is done through Agent-Based Simulation and are used three different policies for the best predictor decision by each drone. This will allow us to verify the performance in the operation of the system through a Nash Equilibrium. In the current state of this analogy is considered that if the drones go to the charging station and it is full, there will be no possible charging because the system is overloaded. This study includes microscopic and macroscopic analysis. Microscopic analysis is the evaluation of the performance of the rewards of each predictor concerning a set of simulation parameters, aiming at a microscopic behavior performance improvement. A macroscopic analysis is the evaluation of the performance of the global service of the system with three types of policies. This latter analysis is used as a basis for evaluating the drone's recharge analogy. In this way, the performance of the best simulation sets for the recharge of drones is evaluated, which allows supplying below the control threshold (attendance below than the number of recharge positions), but which are relatively close to the threshold Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES 001

Orientador: Ricardo da Silva Torres Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Vida artificial é a área de estudo que tem por objetivo reproduzir comportamentos análogos à vida em diferentes tipos de mídia. Na abordagem \emph{soft}, essa tarefa é realizada usando simulações em \emph{software}. Essa tese apresenta um arcabouço de vida artificial, chamado Evocycle, que utiliza diferentes meta-heurísticas bioinspiradas como agentes do sistema. Tais meta-heurísticas são parte do campo da Computação Evolutiva em Ciência da Computação, na qual a teoria biológica da evolução é tomada como inspiração para projetar algoritmos estocásticos de otimização. Na computação evolutiva clássica, frequentemente abordagens elitistas são utilizadas, como por exemplo usar funções de \emph{fitness} para selecionar indivíduos para novas gerações. No entanto, a seleção natural como observada na natureza não possui uma função de \emph{fitness} para avaliação. Neste trabalho, propomos um arcabouço que remove a ênfase do processo de seleção baseado apenas nos valores de {\em fitness}, e tenta uma abordagem diferente, baseada em relações ecológicas de alimentação, reprodução e predação, utilizando assim o valor de \emph{fitness} indiretamente. Nosso sistema de vida artificial forma um ecossistema no qual diferentes espécies são modeladas pela hibridização de algoritmos de inteligência coletiva e evolucionários, e a interação dessas espécies através das relações ecológicas constrói seu comportamento ao longo do tempo. Com essa abordagem, buscamos aumentar a plausibilidade biológica do sistema evolutivo em nossas simulações de vida artificial. Para validar o arcabouço proposto, nós o simulamos com implementações utilizando os algoritmos de \emph{Particle Swarm Optimization} (PSO), no qual a função de velocidade de cada partícula é definida por uma árvore de programação genética (GP), e o algoritmo de otimização \emph{Artificial Bee Colony} (ABC). Ao invés de um ciclo completo de seleção por função de \emph{fitness}, as árvores GP, que codificam cada partícula PSO, evoluem tomando como base a sobrevivência dentro da simulação, levando em conta fatores como energia interna, idade e proximidade de outros indivíduos. Este ecossistema foi estudado em \emph{benchmarks} de otimização contínua, e pela análise da variação da frequência genética de populações de interesse, nós observamos o desenvolvimento de dinâmicas ecológicas promissoras, resultado da pressão seletiva oriunda das interações ecológicas entre os agentes do sistema de vida artificial. Também avaliamos a resiliência da população de predadores no sistema utilizando estudos da teoria de catástrofes em Biologia. As principais contribuições deste trabalho consistem na proposta do sistema de vida artificial em si, o estudo da emergência do comportamento de busca dos agentes do sistema em um cenário evolutivo que buscava maior plausibilidade biológica, e a proposta de uso da análise das taxas de recuperação após perturbações na população para avaliar sua resiliência Abstract: Artificial life is the field of study that aims to reproduce life-like behavior in different types of media. In the soft approach, this task is performed using software simulations. This thesis presents an artificial life framework, named EvoCycle, which uses different bio-inspired meta-heuristics as agents of the system. Such meta-heuristics are part of the Evolutionary Computation field in Computer Science, in which the general theory of evolution is taken as inspiration to design stochastic optimization algorithms. In classic evolutionary computation, often elitist approaches are used, such as those based on fitness functions, to select individuals for new generations. However, natural selection as observed has no explicit fitness evaluation. In this work, we propose a framework that de-emphasizes the selection process based solely on fitness values, and tries a different approach based on ecological relationships of feeding, reproduction, and predation, using the fitness values indirectly. Our artificial life system composes an ecosystem where different species are modelled as a hybridization of swarm intelligence with evolutionary algorithms, and the interaction of the species through ecological relationships shapes their behaviour over time. With this approach, we seek to increase the biological plausibility of the evolution process in our artificial life simulations. To validate the proposed framework, we performed simulations with implementations based on the Particle Swarm Optimization~(PSO) algorithm, in which the velocity rule of each particle is defined by a Genetic Programming~(GP) tree and the Artificial Bee Colony~(ABC) algorithm. Instead of an explicit fitness-selection cycle, the GP trees composing individual PSO particles evolve based on surviving in the simulation, taking into account different factors, such as energy, hunger, mutation, and proximity to other individuals. This ecosystem is investigated on optimization benchmarks, and through the analysis of the variance of the gene frequency, we observed the development of promising ecological dynamics, resulting from the selective pressure coming from the ecological relationships between agents of the artificial life system. We also evaluate the resilience of a predator population in the system using biological studies of the catastrophe theory. The main contributions of the work are the proposal of the artificial life framework itself, the study of the emergence of search behavior of the agents in an evolutionary scenario that aimed to be more biologically plausible, and the proposal of using the analysis of recovery rates after perturbations to investigate the resilience of artificial populations Doutorado Ciência da Computação Doutor em Ciência da Computação CNPQ 141224/2016-9 CAPES 0

Orientador: Ana Estela Antunes da Silva Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: As explosões solares são capazes de afetar o ambiente espacial próximo da órbita do planeta Terra, com possíveis impactos em serviços tecnológicos. Assim, existe a necessidade de melhoria em sistemas de monitoramento para prever as ocorrências de explosões solares. O objetivo deste trabalho é analisar a utilização de algoritmos de classificação e suas combinações em ensembles na predição de explosões solares maiores ou iguais a M1.0 e C1.0 em um tempo de 24h. Para tanto, foram utilizados dados magnéticos do instrumento SDO/HMI (do inglês, Solar Dynamics Observatory's/Helioseismic and Magnetic Imager) e dados de explosões solares do SWPC (do inglês, Space Weather Prediction Center). O SDO/HMI é um instrumento projetado para estudar o campo magnético na superfície solar e o SWPC é um dos centros de meteorologia espacial dos Estados Unidos. Na base de dados integrada a partir dos dados do SDO/HMI e SWPC, foram aplicadas as técnicas: oversampling e undersampling, filtro de localização de regiões ativas, filtro de qualidade dos dados magnéticos, atributos com dados históricos de explosões solares e combinação de classificadores. A partir do treinamento e teste da combinação de classificadores, foi possível prever explosões solares a partir de uma determinada região ativa dentro do período de 24 horas, considerando como métrica de avaliação de desempenho do classificador a métrica True Skill Statistic (TSS). Os experimentos realizados indicam que o uso de: dados magnéticos, dados históricos de explosões solares, filtro de qualidade dos dados magnéticos e combinação de algoritmos, resulta em um método válido para predições de explosões solares em comparação com trabalhos anteriores Abstract: Solar flares are capable of affecting the space environment close to the orbit of planet Earth, with possible impacts on technological services. The objective of this work is to analyze the use of classification algorithms and their combinations in ensembles in the prediction of solar flares greater than or equal to M1.0 and C1.0 in a time of 24h. For this purpose, magnetic data from the SDO/HMI instrument (Solar Dynamics Observatory's/Helioseismic and Magnetic Imager) and solar flare data from the SWPC (Space Weather Prediction Center) were used. The SDO/HMI is an instrument designed to study the magnetic field on the solar surface and the SWPC is one of the United States space meteorology centers. In the integrated database from SDO/HMI and SWPC data, the following techniques were applied: oversampling and undersampling, active region location filter, magnetic data quality filter, attributes with data history of solar flares and combination of classifiers. From the training and testing of the combination of classifiers, it was possible to predict solar flares from a certain active region within a 24-hour period, considering the classifier's performance evaluation metric and True Skill Statistic (TSS) metric. The experiments carried out indicate that the use of: magnetic data, historical data of solar flares, magnetic data quality filter and combination of algorithms, results in a valid method for solar flare predictions compared to previous works Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES 001

Orientadores: Paulo Sérgio Martins Pedro, Edson Luiz Ursini Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: A definição de modos de operação no projeto de um sistema de tempo real tem sido um recurso utilizado para se agregar benefícios ao sistema, dentre eles a adequação dinâmica da operação do sistema para uma determinada fase de operação. Tradicionalmente, as mudanças no modo de operação são realizadas de maneira reativa, ou seja, o sistema altera seu modo em resposta a um evento interno ou externo. Esse trabalho apresenta uma proposta de um modelo proativo para mudanças de modo em sistemas de tempo real de criticalidade mista. Nessa abordagem foram integrados algoritmo de predição e lógica difusa ao escalonamento de mudanças de modo utilizando as políticas de escalonamento Earliest-Deadline-First (EDF) e Fixed-Priority Preemptive Systems (FPPS). Essa abordagem visa a programação proativa de mudanças de modo baseada em valores observados e preditos de variáveis de estado como a lassidão de pior caso das instâncias das tarefas em espera ou em estado de execução a fim de minimizar a perda de prazo das tarefas de baixa criticalidade. Para avaliação de viabilidade, a abordagem proposta foi moldada em um modelo de simulação por eventos discretos que posteriormente fora validado com um modelo analítico (análise de escalonabilidade de pior caso). Oito estudos de caso foram implementados para avaliar o impacto das mudanças de modos proativas na perda de prazo das tarefas. Os resultados mostraram ganhos na adoção da abordagem de previsão para ambos os paradigmas de escalonamento, apresentando uma redução significativa no número de prazos perdidos para tarefas de baixa criticidade Abstract: The definition of modes of operation in the design of a real-time system has been a feature used to add benefits to the system, such as the dynamic adaptation of the systems operation to a specific phase of operation. Traditionally, the changes in mode of operation have been accomplished in a reactive manner, i.e. the system changes its mode in response to an internal or external event. This work presents a proposal for proactive mode-changes in mixed-criticality real-time systems. In this approach, prediction algorithms and fuzzy were integrated into mode-changes using Earliest-Deadline-First (EDF) and Fixed-Priority Preemptive Systems (FPPS) scheduling policies. The aim of this approach is the proactive scheduling for mode-changes based on observed and predicted values of the state variables such as the worst-case laxity of waiting or running tasks. For feasibility evaluation, the proposed approach was modeled on a discrete event simulation model that was later validated with an analytical model (worst case scalability analysis). Eight case studies were implemented to assess the impact of proactive mode-changes on missed deadlines of tasks. The results showed that the approach using prediction for both scheduling paradigms represented a significant reduction in the number of missed deadlines for low-criticality tasks Doutorado Sistemas de Informação e Comunicação Doutor em Tecnologia

Orientadores: Zanoni Dias, Ulisses Martins Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de Genomas são eventos que afetam longos trechos de um genoma durante a evolução. Dentre os rearranjos mais estudados, temos a reversão, que inverte a ordem e a orientação de um bloco consecutivo de genes, e a transposição, que troca a ordem relativa de dois blocos adjacentes. Modelos matemáticos vêm sendo utilizados para estimar a distância evolutiva entre diferentes organismos por rearranjos de genomas. A representação de um genoma se dá, na maioria das vezes, pela atribuição de um número único para cada gene e, ao supor que não existem genes repetidos, essa representação pode ser vista como uma permutação. Supondo que os dois genomas a serem comparados compartilham o mesmo conjunto de genes, calcular a distância evolutiva entre eles se torna o problema de encontrar o menor número de rearranjos necessários que transforma uma permutação em outra. Nesta tese, apresentamos diversos resultados envolvendo problemas de rearranjos de genomas: (i) provas de NP-dificuldade para quatro problemas cuja complexidade era desconhecida; (ii) um algoritmo polinomial exato para um problema cuja complexidade era desconhecida; e (iii) algoritmos de aproximação e provas de NP-dificuldade para problemas onde a representação dos genomas não considera apenas a ordem dos genes. Descrevemos estas contribuições com maior profundidade nos parágrafos a seguir. Dentre os problemas que envolvem rearranjos de genomas, existem quatro versões que permitem o uso de reversões e transposições ao mesmo tempo e que, apesar dos diversos algoritmos propostos nos últimos 20 anos, permaneciam com complexidade desconhecida. A primeira contribuição apresentada é a prova de NP-dificuldade desses quatro problemas. Uma das variações dos problemas de rearranjos de genomas consideram que cada rearranjo pode afetar apenas um pequeno número de genes, também conhecidos como rearranjos curtos e super curtos. Neste contexto, nossa segunda contribuição é a prova de que o único problema cuja complexidade era desconhecida envolvendo reversões super curtas e transposições super curtas admite um algoritmo polinomial exato. A grande maioria das abordagens em problemas de rearranjos existentes na literatura focaram apenas na ordem relativa dos genes de um genoma, desconsiderando outras características importantes existentes no genoma. Recentemente, pesquisadores mostraram que considerar as regiões existentes entre cada par de genes, chamadas de regiões intergênicas, pode resultar em melhores estimadores de distância em dados reais. Desta forma, nossa terceira contribuição investiga a incorporação das regiões intergênicas em modelos já existentes para reversões e transposições, tanto na abordagem sem restrições como na abordagem que considera apenas rearranjos super curtos, onde investigamos diversos algoritmos de aproximação para problemas que são NP-difíceis ou possuem complexidade desconhecida Abstract: Genome rearrangements are events that affect large stretches of a genome during evolution. Two of the most studied rearrangements are reversals, which reverses the order and orientation of a consecutive block of genes, and transpositions, which exchanges the relative order of two adjacent blocks. Mathematical models have been used to estimate the evolutionary distance between different organisms by genome rearrangements. The representation of a genome is very often made by assigning a unique number to each gene. If we assume no repeated genes, this representation can be seen as a permutation. By considering that the two genomes to be compared share the same set of genes, finding the evolutionary distance between them becomes the problem of finding the smallest number of genome rearrangements needed to transform one permutation into the other. In this thesis, we present several results involving genome rearrangement problems: (i) proofs of NP-hardness for four problems whose complexity was unknown; (ii) an exact polynomial algorithm for a problem whose complexity was unknown; and (iii) approximation algorithms and proofs of NP-hardness for problems where the genome representation carry more information than only the gene order. We describe these contributions in more depth in the following paragraphs. Among the problems involving genome rearrangements, four versions that allow the use of reversals and transpositions at the same time remained with unknown complexity despite the various algorithms proposed in the last 20 years. The first contribution presented is then the proofs of NP-hardness for these four problems. A variant of genome rearrangement problems considers that each rearrangement can affect only a small number of genes, also known as short and super short rearrangements. In this context, our second contribution is proof that the only problem involving super short reversals and super short transpositions whose complexity was unknown admits an exact polynomial algorithm. Most of the approaches for genome rearrangement problems in the literature so far have focused only on the relative order of genes in a genome, disregarding other important features presented in it. Recently, researchers have shown that considering the regions between each pair of genes, called intergenic regions, can result in better distance estimators in real data. Thus, our third contribution investigates the incorporation of intergenic regions in existing models for reversals and transpositions, both in the unrestricted and size restricted versions (i.e. super short operations), where we propose several approximation algorithms for problems that are either NP-hard or with unknown complexity Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES CNPQ 140466/2018-5

Orientador: Ulisses Martins Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: A segmentação de imagens consiste em dividir a imagem em regiões com o intuito desimplificar a visualização e facilitar a identificação dos objetos. O processo de segmentaçãopode ser efetuado de várias formas distintas como, por exemplo: segmentação utilizandoo formato dos objetos, intensidade no nível de cinza, histograma de cores, entre outrasformas. Essa vasta gama de técnicas existe porque diferentes situações geram problemasespecíficos e, por esse motivo, os critérios para segmentar e identificar os objetos variamde acordo com a situação apresentada. Dentro do universo da segmentação, destacam-seas técnicas que utilizam níveis de cinza, que podem ser englobadas em duas categoriasprincipais: (i) técnicas que utilizam a detecção de contornos e formatos e (ii) técnicas queutilizam estruturas hierárquicas. Neste trabalho, utilizamos a transformadaWatershedhierárquica como técnica de segmentação e a utilização daÁrvore dos Lagos Críticoscomo estrutura representativa. Adicionalmente, utilizamos como critérios de seleção otamanho e a forma dos objetos. De modo mais específico, definimos uma função que éajustada por meio de um algoritmo genético que otimiza os parâmetros livres da função.Três algoritmos foram desenvolvidos para se obter os resultados. O primeiro algoritmo,denominado deAlgen, consiste em um algoritmo genético que aprimora os resultados nodecorrer da segmentação. O segundo algoritmo, denominado deAlgal, executa o processode segmentação repetidas vezes, alterando os valores de entrada (dentro do intervalopermitido) semi-aleatoriamente. O terceiro algoritmo, denominado deAlmod, é executadoem conjunto com os algoritmosAlgeneAlgal, sendo que sua função é de classificar osresultados ao final de cada processamento. Os processos e algoritmos desenvolvidos nestetrabalho tiveram como foco principal a segmentação de imagens de células, sendo que,todos os testes de otimização e adaptação do algoritmo genético foram realizados noreferido tipo de imagem Abstract: Image segmentation consists of dividing the image into regions in order to simplifythe visualization and the identification of objects. The segmentation process can bebuild in several different ways, for example: segmentation using the shape of the objects,intensity in the gray level, histogram of colors, etc. This wide range of techniques existsbecause different situations generate specific problems and, therefore, the criteria forsegmenting and identifying objects vary according to the situation presented. Within thesegmentation universe, the techniques that use gray levels can be included in two maincategories: (i) techniques that use the detection of contours and shapes and (ii) techniquesthat use hierarchical structures. In this work, we propose the use of the hierarchicalWatershed transform as segmentation technique and the use of Tree of Critical Lakes asa representative structure. Additionally, we use the size and shape of objects. In moredetail, we work with a size range and adopt the elliptical curvature metric to producethe final result, which is obtained through the weighted average between the size scoreand the elliptic curvature score. We developed three algorithms to obtain better results.The first algorithm, called Algen, consists of a genetic algorithm that improves the resultsduring the segmentation. The second algorithm, called Algal, performs the segmentationprocess repeatedly, changing the input values (within the allowed range) semi-randomly.The third algorithm, called Almod, is executed in conjunction with Algen and Algalalgorithms. Almod main function is to classifier all results and it is executed at the endof each segmentation. The processes and algorithms developed in this work had as mainfocus the segmentation of cell images, and all tests of optimization and adaptation of thegenetic algorithm were performed on the referred type of image Mestrado Tecnologia e Inovação Mestre em Tecnologia CAPES 001

Orientador: Ieda Geriberto Hidalgo Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica Resumo: Esta dissertação tem como objetivo auxiliar empresas responsáveis pela produção de grãos e dos subprodutos da soja no planejamento da produção, visando a maximização do lucro. Como subprodutos, são considerados o farelo, o óleo e o biodiesel. A maximização do lucro é feita através da alocação da produção de cada um dos subprodutos da soja. O modelo matemático consiste em uma função objetivo do lucro da empresa, que possui restrições em relação aos recursos e aos limites de operação das máquinas, de forma que a demanda seja atendida. Tais limites de operação são em relação à capacidade de processamento de soja, do refino do óleo e de produção de biodiesel. A metodologia para resolver o problema de otimização consiste na aplicação do Método Simplex. Como ferramenta, o software LINGO foi utilizado. O modelo é aplicado para a usina Granol em quatro estudos de caso, correspondentes aos anos de 2014, 2015, 2016 e 2017. A justificativa para a escolha dessa usina é que ela trabalha com uma produção integrada da soja e de seus subprodutos, além dos dados necessários para esta pesquisa estarem disponíveis. Para cada estudo de caso, o lucro obtido foi comparado com o lucro calculado a partir das quantidades reais da soja e dos seus subprodutos comercializados, assim como sua respectiva análise de sensibilidade. Em geral, o modelo apresenta um lucro 15% maior do que o calculado a partir das quantidades reais dos produtos da Granol comercializadas, desconsiderando o ano de 2017 por apresentar um aumento atípico. Além disto, a empresa teve um maior lucro a partir do farelo e do óleo refinado em todos os quatro anos. Logo, a soja, o óleo bruto e o biodiesel comercializados correspondem às respectivas quantidades mínimas, o que indica a menor importância destes produtos para maximização do lucro. Dentre os trabalhos anteriores, este possui um diferencial em relação a um maior detalhamento da integração das etapas de conversão da soja em seus subprodutos, conforme apresentado no modelo matemático Abstract: This dissertation has the goal to help companies responsible by the production of the soybean and your by-products in the planning of production, aiming to maximize the profit. As by-products, are considered the soybean meal, soybean oil, and biodiesel. The maximization of the profit is through the optimization of the allocation of production of each of the soybean¿s by-products. The mathematical model consists of the objective function of company¿s profit, which has restrictions in relation to the resources and the limits of machines¿ operations, to attend the demand. That operation limits are related to the maximum capacity of the soybean processing, the oil refining and the biodiesel producing. The methodology to resolve the optimization problem is through the application of Simplex Method. As tool, the LINGO software is used. The model is applied to the Granol factory in four study cases, corresponding to the 2014, 2015, 2016 and 2017 years. The reasons to choose that factory are that it works in an integrated model of the soybean and its by-products, besides the necessary data for this research. On each case studies, the profit obtained is compared to the profit calculated using the actual quantities of soybean and its by-products commercialized, as your respective sensibility analysis. In general, the model presents a profit in an average of 15% higher as the profit calculated through the actual quantities of the Granol¿s commercialized products, disregarding the year of 2017 for showing an atypical increase. Also, that factory had a higher profit through the soybean meal and the refined oil through the four years. So, the commercialized soybean, brute oil and biofuel correspond to their respective minimum quantities, which points their minor importance on the profit maximization. Among the earlier works, this has a differential in relation of the more detailed integrated phases of conversion of the soybean for your respective by-products, as presented in the mathematical model Mestrado Planejamento de Sistemas Energéticos Mestre em Planejamento de Sistemas Energéticos CNPQ 131436/2018-0