Esta tese explora características de sistemas de manufatura celular virtual, de técnicas de escalonamento e despacho em tempo de execução e de algoritmos genéticos para assegurar um alto grau de flexibilidade de rotas de processo e eficiência na programação de tarefas de sistemas de manufatura do tipo (NDDJSS – non-deterministic dynamic job shop system). Desenvolve-se assim, um método de programação baseado em duas novas técnicas, de clustering e de escalonamento e despacho, respectivamente, aplicado a sistemas de manufatura do tipo NDDJSS. Apresentam-se inicialmente os conceitos fundamentais considerados na organização de sistemas de manufatura em células de trabalho e suas implicações em termos de esforço de coordenação e controle das células e das tarefas; a abordagem por organização funcional das células de manufatura virtuais; ascaracterísticas, definições e notação usadas para problemas de escalonamento; a descrição de técnicas de escalonamento e despacho de sistemas de manufatura; aspectos relevantes de computação evolutiva, mais especificamente, de algoritmos genéticos. Em seguida, introduz-se a nova técnica de clustering e a nova técnica de escalonamento e despacho, juntamente com os requisitos e as formulações associadas. A nova técnica de clustering forma células de manufatura virtuais balanceadas quanto ao volume de trabalho, com alto grau de flexibilidade de rotas de processo. A nova técnica de escalonamento e despacho é autônoma, estável, adaptativa, flexível, contingente, monotônica e relativamente robusta, permitindo a geração de escalas em tempo de execução, ao mesmo tempo em que mantém a medida de desempenho, o makespan, dentro de uma faixa de desempenho pré-estabelecida. Exemplificam-se as aplicações das duas novas técnicas, através de exemplos extraídos da literatura técnica e simulados através de um programa de computador chamado (DEVICE – Design of virtual cells), desenvolvido especialmente para esta pesquisa. Após simulação obtêm-se os resultados de forma estruturada para análise. Os respectivos resultados da aplicação do método de programação proposto comprovam o potencial dessa abordagem. / This thesis explores characteristics of virtual cellular manufacturing systems, of scheduling and dispatching techniques for real time requirements and genetic algorithms for assures a high level of routeing flexibility and efficiency in tasks programming for (NDDJSS – non-deterministic dynamic job shop system). It introduces a programming method based in two new clustering and scheduling and dispatching techniques, respectively, applied in NDDJSS manufacturing systems. Initialy, the work presents basic concepts considered in the organization of cellular manufacturing systems and its implications for coordination and control efforts of cells and tasks, respectively; an approach of virtual mufacturing cells through the functional organization; the characteristics, definitions and notation used for scheduling problems; the description of more manufacturing systems scheduling and dispatching techniques; relevant aspects of evolutionary computation in specialty, the genetic algorithms. Subsequently, the work also introduces the new clustering and scheduling and dispatching techniques, the requirements and the formulas associated. The new clustering technique builds balanced workload with high flexibility of process routeing. Also, the new scheduling and dispatching technique is autonomous, stable, adaptative, flexible, contingent, monotonic and relatively robust, providing scales generating in running mode (real time) and mantaining the performance measures “makespan” within the stabilished range of performance. The applications of the two new techniquesare exemplified based on two examples picked from technique literature and so simulated through a new software called (DEVICE – design of virtual cells). The software DEVICE was designed specialty for this research. After run some simulations, the structured form results are obtained for analisys. The respectively results obtained for the proposed method application proves the powerful of this approach.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-09-13T17:11:28Z No. of bitstreams: 1 texto completo.pdf: 2362432 bytes, checksum: b178db47eb7f33a8f9592f074db75e42 (MD5) / Made available in DSpace on 2018-09-13T17:11:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2362432 bytes, checksum: b178db47eb7f33a8f9592f074db75e42 (MD5) Previous issue date: 2018-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A sociedade moderna é altamente dependente de estruturas funcionais em rede, como redes de comunicação ou de transporte. Assim, o estudo de ataques em redes e o entendi- mento de sua robustez/fragilidade são fundamentais na procura de redes mais eficientes. Muitos estudos envolvendo ataques em redes subestimam a importância de processos di- nâmicos evoluindo nessas redes atacadas para prevenir danos futuros. A maioria dos estudos em redes atacadas foca na caracterização da estrutura das componentes não da- nificadas da rede. No entanto, muito menos atenção tem sido dedicada para analisar a influência desses ataques na propagação de epidemias ou informação. Nesse traba- lho, investigamos a propagação de epidemias nos modelos suscetível-infectado-suscetível e suscetível-infectado-recuperado em redes após os ataques com diferentes estratégias, enfa- tizando o estudo dos limiares epidêmicos dos modelos. Nós estudamos duas intensidades de ataques: um brando no qual a componente gigante da rede possui tamanho comparável a rede original e outro mais destrutivo mas ainda apresentando uma componente gigante grande. Ataques aleatórios, que não modificam a distribuição de grau de redes sem es- cala, não alteram o comportamento do limiar epidêmico em relação às redes intactas e continua indo para zero com o aumento do tamanho da rede. Investigamos outras duas estratégias de ataque de contatos: uma em que um primeiro vizinho de um vértice esco- lhido ao acaso é removido com probabilidade 1 e outra em que se remove o vizinho com uma probabilidade que protege os vértices de graus mais elevados de serem removidos. Observamos que a dependência do limiar epidêmico com o tamanho da rede se altera dra- maticamente, saturando em um valor constante no limite de redes grandes, ou diminuindo mais lentamente do que uma lei de potência ou até mesmo aumentando com o tamanho da rede em alguns casos, a depender da estratégia e da intensidade do ataque. Também concluímos que ambos ataques são mais efetivos quando aumentada a heterogeneidade da rede. Mostramos que mesmo os ataques de contato abaixo do limiar de percolação, que não fragmentam a rede, são capazes de tornar a rede inoperante para a propagação da epidemia no modelo SIS. Além disso, comparamos os resultados das simulações com a teoria de campo médio heterogêneo, conhecida como HMF (do inglês heterogeneous mean field), que leva em conta apenas o grau do vértice, e a teoria de campo médio que leva em conta toda a estrutura da rede por meio da matriz de adjacência, conhecida como QMF (do inglês quenched mean field) e observamos que a primeira captura as mudanças no limiar epidêmico com maior precisão do que a segunda. / The modern society is highly dependent of functioning networked structures such as com- munication and transportation networks. Thus, the study of attacks in networks and the understanding of their robustnesses/fragilities are imperative for the search of more efficient networks. Many studies involving network attacks underestimate the importance of dynamic processes evolving on these attacked networks to prevent further damage. Most of the studies on network attack is held on the characterization of the structure of the undamaged components of the networks. However, much less attention has been devoted to the influence of these attacks on the epidemic and information spreading. In this work, we investigate the epidemic spreading of susceptible-infected-susceptible and susceptible-infected-recovered models on networks after the attack according diffe- rent strategies aiming at the study of the epidemic thresholds. We investigate two attack intensities: a mild one with a giant component with size comparable to the original and other more destructive but still presenting a large giant component. Random attacks, which don’t alter the degree distribution on scale free networks, don’t change the epide- mic threshold behavior in relation to the undamaged network that goes to zero as the network size increases. We investigate other two acquaitance attack strategies: one where a nearest neighbor of a randomly chosen vertex is deleted with probability 1 and other that remove the neighbor with a probability that protect the vertices of higher degree from being deleted. We observe that the threshold scaling changes dramatically, reaching a constant value for the limit of large networks, or decreasing slower than a power law, or even increasing with the size of the network, depending on the model and intensity of the attacks. We also conclude that both attacks are more effective as the heterogeneity of the networks increases. We show that even acquaitance attacks below the percolation threshold, which are not sufficient to fragment the network, are able to make the network ineffective for the epidemic spreading in the SIS model. Furthermore, we compare the results from the simulations with the heterogeneous mean field (HMF) theory, which con- siders that the vertex degree is the only relevant quantity and the quenched mean field (QMF) theory, which include the whole structure of network through the adjacency ma- trix. We observed that the HMF theory captures the changes in the epidemic threshold more accurately than the QMF theory.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-01-30T11:47:34Z No. of bitstreams: 1 texto completo.pdf: 2510159 bytes, checksum: b0cc4178edbf1a6dbc030047dedef671 (MD5) / Made available in DSpace on 2017-01-30T11:47:34Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2510159 bytes, checksum: b0cc4178edbf1a6dbc030047dedef671 (MD5) Previous issue date: 2016-04-27 / Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O objetivo deste estudo foi avaliar a eficiência do algoritmo de aprendizagem supervisionado Máquina de Vetores de Suporte (MVS) para regressão, em dados obtidos pelos sensores AVNIR-2 e o PALSAR a bordo do satélite ALOS, para estimativa de volume de madeira e biomassa aérea de povoamentos florestais de eucalipto. O trabalho também avaliou a redução do número de dados para treinamento, bem como a busca de estruturas de MVS mais simples. O estudo foi conduzido em áreas de reflorestamento na região leste do estado de Minas Gerais. Foram testados dois tipos de regressão ɛ-MVS e -MVS, bem como as seguintes funções kernel: linear, polinomial, RBF (Gaussian Radial Basis Function) e sigmoide. Foram utilizadas 190 parcelas, sendo 75% (142) para treinamento das MVS. A integração de todos os dados dos sensores AVNIR-2 e PALSAR, como variáveis de entrada das MVS, geraram estimativas para generalizações com os maiores valores de coeficiente de correlação (r y ) e menores valores da raiz quadrada do erro quadrático médio (RQEM), tanto para a variável volume quanto para a biomassa aérea. As -MVS com a função RBF resultaram em maior exatidão, e foram então utilizadas para as análises subsequentes. Em um treinamento com 95 parcelas obteve-se exatidão satisfatória nas generalizações para ambas as variáveis alvo. Para estimar volume dos povoamentos, generalizações relativamente satisfatórias dos dados foram encontradas combinando as bandas AV3 ou AV4 do sensor AVNIR-2 com uma polarização cruzada (L HV ou L VH ) do sensor PALSAR. A combinação da banda AV4 e a polarização L VH apresentou um r y de 0,991 e RQEM de 4,120 m3, equivalente a 1,617% da média das parcelas testadas. Já para biomassa aérea boas generalizações foram alcançadas combinando a banda AV4 do sensor AVNIR-2 com a polarização L HV ou L VV . No melhor desempenho de MVS para estimativas de biomassa aérea, utilizando a combinação AV4 e L VV , obteve-se um r y de 0,951 e RQEM de 5,338 t.ha -1 , o equivalente a 2,095% da média das parcelas testadas. A análise gráfica dos resíduos se mostrou primordial para a seleção de MVS com menor viés quantitativo. A simplicidade de ajuste das MVS, atrelada ao poder de generalização dos dados mostrou o potencial operacional do algoritmo nas atividades de quantificação e mapeamento dos recursos florestais. / The key intention of this study was to evaluate the performance of Support Vector Regression (SVR) algorithm on Eucaliptus spp. timber stand volume and Above Ground Biomass (AGB) retrieval based on ALOS imagery. The sensors used were AVNIR-2 and PALSAR for optical and RADAR dataset respectively. This study also examined SVRs with a reduced number of inputs and training samples in order to reduce the amount of field measures. This study was carried out with 190 sample plots of eucalyptus stands from eastern region of Minas Gerais State, Brazil. The generalization ablity of ɛ-SVR and -SVE were compared, as well as the performance of following kernel functions: linear, polinomial, Gaussian Radial Basis Function (RBF) and sigmoid. Inicially, 142 samples were used for the training of SVRs and the remaining samples were used for the generalization test. The best generalization performances for volume and AGB estimates were obtained using -SVR with RBF as kernel function, and by combining all inputs from AVNIR-2 and PALSAR. This setting was used for subsequent generalized data analysis. Results with no loss of accuracy were obtained using just 95 training samples with a reduced number of inputs. The combination of AV3 or AV4 from AVNIR-2 with a cross-polarized input (L HV ou L VH ) from PALSAR showed good performances for stand volume timber retrieval. The best result for volume output variable obtained a coeficient correlation (r y ) value of 0,991 and 4,120 m3 of root-mean-quare error (RMSE). For AGB, the combination of AV4 optic data with L HV or L VV palarization input showed the best results. The best performance for AGB retrieval obtained a r y value of 0,951 and 5,338 t/ha of RMSE. The residual graphic analysis was essencial for selecting less biased SVRs. Therefore, the good generalization ability places the SVR as potentially usefull approach for remote sensing-based forest parameters retrieval.

Atualmente, diversas metaheurísticas têm sido desenvolvidas para tratarem problemas de otimização multiobjetivo. Os Algoritmos de Estimação de Distribuição são uma classe específica de metaheurísticas que exploram o espaço de variáveis de decisão para construir modelos de distribuição de probabilidade a partir das soluções promissoras. O modelo probabilístico destes algoritmos captura estatísticas das variáveis de decisão e suas interdependências com o problema de otimização. Além do modelo probabilístico, a incorporação de métodos de busca local em Algoritmos Evolutivos Multiobjetivo pode melhorar consideravelmente os resultados. Estas duas técnicas têm sido aplicadas em conjunto na resolução de problemas de otimização multiobjetivo. Nesta tese, um algoritmo de estimação de distribuição híbrido, denominado HMOBEDA (Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm ), o qual é baseado em redes bayesianas e busca local é proposto no contexto de otimização multi e com muitos objetivos a fim de estruturar, no mesmo modelo probabilístico, as variáveis, objetivos e as configurações dos parâmetros da busca local. Diferentes versões do HMOBEDA foram testadas utilizando instâncias do problema da mochila multiobjetivo com dois a cinco e oito objetivos. O HMOBEDA também é comparado com outros cinco métodos evolucionários (incluindo uma versão modificada do NSGA-III, adaptada para otimização combinatória) nas mesmas instâncias do problema da mochila, bem como, em um conjunto de instâncias do modelo MNK-landscape para dois, três, cinco e oito objetivos. As fronteiras de Pareto aproximadas também foram avaliadas utilizando as probabilidades estimadas pelas estruturas das redes resultantes, bem como, foram analisadas as interações entre variáveis, objetivos e parâmetros de busca local a partir da representação da rede bayesiana. Os resultados mostram que a melhor versão do HMOBEDA apresenta um desempenho superior em relação às abordagens comparadas. O algoritmo não só fornece os melhores valores para os indicadores de hipervolume, capacidade e distância invertida geracional, como também apresenta um conjunto de soluções com alta diversidade próximo à fronteira de Pareto estimada. / Nowadays, a number of metaheuristics have been developed for dealing with multiobjective optimization problems. Estimation of distribution algorithms (EDAs) are a special class of metaheuristics that explore the decision variable space to construct probabilistic models from promising solutions. The probabilistic model used in EDA captures statistics of decision variables and their interdependencies with the optimization problem. Moreover, the aggregation of local search methods can notably improve the results of multi-objective evolutionary algorithms. Therefore, these hybrid approaches have been jointly applied to multi-objective problems. In this work, a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA), which is based on a Bayesian network, is proposed to multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and configuration parameters of an embedded local search (LS). We tested different versions of HMOBEDA using instances of the multi-objective knapsack problem for two to five and eight objectives. HMOBEDA is also compared with five cutting edge evolutionary algorithms (including a modified version of NSGA-III, for combinatorial optimization) applied to the same knapsack instances, as well to a set of MNK-landscape instances for two, three, five and eight objectives. An analysis of the resulting Bayesian network structures and parameters has also been carried to evaluate the approximated Pareto front from a probabilistic point of view, and also to evaluate how the interactions among variables, objectives and local search parameters are captured by the Bayesian networks. Results show that HMOBEDA outperforms the other approaches. It not only provides the best values for hypervolume, capacity and inverted generational distance indicators in most of the experiments, but it also presents a high diversity solution set close to the estimated Pareto front.

Made available in DSpace on 2015-03-04T18:51:09Z (GMT). No. of bitstreams: 1 tese Marx.pdf: 13309696 bytes, checksum: c9f52e4492b104fdb02b2a485e043412 (MD5) Previous issue date: 2009-04-15 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / Proteins are biological macromolecules comprised of amino acid polymers that play a wide range of biological roles involved in every process of living organisms. Together with X-ray diffraction, Nuclear Resonance Spectroscopy (NMR) is one of the two main experimental techniques that are capable of delivering atomic-level resolution of protein structures. Prediction of proteic structures using experimental information from NMR experiments is a global optimization problem with restraints. GAPF is a computer program that uses a Genetic Algorithm (GA) developed for ab initio prediction -- the determination of the structure of a protein from its amino acid sequence only -- using a multiple minima approach and a fitness function derived from a classic molecular force field. The work presented here describes GAPF-NMR, an alternate version of GAPF that uses experimental restraints from NMR to support the search for the best protein structures that correspond to a given sequence. Five different versions of the algorithm have been developed, each with a variation on how the energy function is calculated during the course of the program run. GAPF was tested on a test set comprised of 7 proteins with known structure and it was capable of achieving a correct or approximate fold for every one of these proteins. It was noted that the versions of the algorithm that progressively increase the area of the protein used in the energy function have performed better than the other versions, and that the multiple minima approach was important to the achievement of good results. Results were compared to those obtained by GENFOLD -- to the moment, the only known alternate implementation of a GA to the problem of protein structure prediction using NMR data -- and the current version of GAPF was shown to be superior to GENFOLD for two of the three proteins that compose its test set. / Proteínas são macromoléculas biológicas formadas por polímeros de aminoácidos, as quais estão envolvidas em todos os processos vitais dos organismos, compreendendo um amplo leque de funções. A espectropia por Ressonância Magnética Nuclear (RMN) é, ao lado da difração de raios-X em cristais, uma das duas principais técnicas experimentais capazes de permitir a elucidação da estrutura de proteínas em resolução atômica. A predição de estruturas protéicas utilizando informações experimentais de RMN é um problema de otimização global com restrições. O GAPF é um programa que utiliza um Algoritmo Genético (AG) desenvolvido para predição ab initio -- isto é, para determinação da estrutura de uma proteína apenas a partir do conhecimento de sua seqüência de aminoácidos -- utilizando uma abordagem de múltiplos mínimos, baseada em uma função aptidão derivada de um campo de força molecular clássico. Neste trabalho, é descrito o GAPF-NMR, uma versão derivada do GAPF, que utiliza restrições experimentais de RMN para auxiliar na busca pelas melhores estruturas protéicas correspondentes a uma seqüência dada. Cinco versões diferentes do algoritmo foram desenvolvidas, com diferentes variações na maneira como a função de energia é calculada ao longo da execução. O programa desenvolvido foi aplicado a um conjunto-teste de 7 proteínas de estrutura já conhecida e, para todas elas, foi capaz de chegar a uma estrutura com o enovelamento correto ou aproximado. Foi observado que as versões do algoritmo que aumentam progressivamente a região da proteína usada no cálculo de energia tiveram desempenho superior às demais, e que a abordagem de múltiplos mínimos foi importante para a obtenção de bons resultados. Os resultados foram comparados aos descritos para o GENFOLD -- que é, até o momento, a única implementação alternativa conhecida de um AG para o problema de predição de estruturas a partir de dados de RMN -- e a versão atual do GAPF-NMR se mostrou superior ao GENFOLD na determinação de duas das três proteínas do conjunto-teste deste.

O setor agropecuário gera uma enorme quantidade de resíduos que constituem um grave problema ambiental quando não são corretamente dispostos ou reaproveitados. A busca pela sustentabilidade nesse setor e os problemas associados à crise energética e ao aquecimento global incentivam o uso de resíduos agropecuários como fonte de energia. Porém, a instalação de uma central para a geração da bioenergia requer altos investimentos e volume de resíduos. Estes acabam sendo estímulos para a cooperação entre produtores rurais. No Brasil, a geração conjunta de energia por meio de fontes renováveis é autorizada pela Agência Nacional de Energia Elétrica - ANEEL. Nesse sentido, o objetivo deste trabalho foi identificar alternativas de parcerias estratégicas entre propriedades rurais para a geração de bioenergia. O estudo foi realizado em propriedades rurais criadoras de bovinos e/ou suínos, associadas a uma cooperativa agroindustrial, localizadas no município de Castro-Paraná-Brasil. A metodologia baseou-se na criação de um cenário de parcerias, levando em consideração as variáveis consumo de energia, potencial de geração de bioenergia e localização geográfica das propriedades rurais. O potencial de geração de bioenergia foi calculado por meio de uma média entre os índices obtidos na literatura. O método Elbow definiu o número ideal de agrupamentos. Os cenários de parcerias foram criados pelo algoritmo kmeans, por meio do software de geoprocessamento QGIS e do software estatístico SPSS. Foram obtidos três cenários de parcerias entre as propriedades rurais. A sobreposição deles resultou em um cenário final de parcerias, composto por três agrupamentos. As propriedades que constituem o agrupamento 1 tem potencial para atender 36% de sua demanda energética; as propriedades do agrupamento 2 tem potencial para atender 32% de sua demanda energética; e, por fim, as propriedades do agrupamento 3 tem potencial para atender 72% de sua demanda energética. A metodologia desenvolvida neste trabalho possibilitou encontrar alternativas de parcerias para a geração de bioenergia entre as propriedades rurais estudadas, podendo ser replicada em outras amostras. A produção conjunta de bioenergia contribui com a sustentabilidade e a segurança energética do setor rural. / The agricultural sector generates a lot of residues. These residues are a serious environmental problem when they are not properly disposed or reused. The search for sustainability in this sector and the problems associated with the energy crisis and global warming encourage the use of agricultural waste as an energy source. However, the installation of a plant for the generation of bioenergy requires high investments and volume of waste. These are stimuli for cooperation between rural producers. In Brazil, the joint generation of energy through renewable sources is authorized by the National Electric Energy Agency. In this sense, the objective of this work was to identify alternatives of strategic partnerships between rural properties for the generation of bioenergy. The study was carried out on cattle and/or pigs farms, associated to an agroindustrial cooperative, located in the municipality of Castro-Paraná-Brazil. The methodology was based on the creation of a partnership scenario. The variables energy consumption, bioenergy generation potential and geographic location of rural properties were taken into account. The bioenergy generation potential was calculated by means of a mean between the indices obtained in the literature. The Elbow method defined the optimal number of clusters. The partnership scenarios were created by the k-means algorithm, using the QGIS geoprocessing software and the SPSS statistical software. Three scenarios of partnerships between rural properties were obtained. The overlap of the scenarios generated a final scenario of partnerships, composed of three groups. The group 1 has the potential to meet 36% of its energy demand; the group 2 has the potential to meet 32% of its energy demand; and, finally, the group 3 has the potential to meet 72% of its energy demand. The methodology developed in this work made it possible to find alternative partnerships for the generation of bioenergy among the rural properties studied. This methodology can be applied in other samples. The joint production of bioenergy contributes to the sustainability and energy security of the rural sector.

Esta dissertação de mestrado apresenta um novo algoritmo de seleção de relays utilizando lógica fuzzy. O algoritmo proposto é distribuído, ao ser processado independentemente em cada nó dispensando a necessidade de uma entidade central, e multiobjetivo, visto que ele busca maximizar tanto o tempo de vida da rede como a vazão fim-a-fim. O novo método leva em conta o estado do canal instantâneo do canal relay-destino e a energia residual da bateria do nó. Como resultado, o algoritmo atribui um grau de relevância a cada candidato a relay, de forma que o nó com maior relevância é escolhido para retransmitir a mensagem proveniente da fonte. Os resultados mostram que um aumento considerável no tempo de vida de rede pode ser obtido sem comprometer a vazão fim-a-fim. / In this master thesis we present a new relay selection algorithm using fuzzy logic. The proposed algorithm is distributed, runs independently at each node, not requiring a central entity for coordination, and is multi-objective, since it aims to maximize both network lifetime and end-to-end throughput. The new method takes into account the instantaneous channel state of the relay-destination link and the residual energy of the node battery. As a result, the algorithm assigns a degree of relevance to each relay, such that the with a higher relevance is chosen to forward the source message. Results show that a considerable increase in the network lifetime can be obtained without compromising the end-to-end throughput.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

O monitoramento de forma integrada pode se tornar complexo em ambientes com bancos de dados heterogêneos, devido às particularidades na sintaxe e em ferramentas disponíveis. Em particular, bancos de dados ativos permitem o desenvolvimento de mecanismos e a automação de processos que envolvam os dados ou objetos. Este trabalho propõe o desenvolvimento de uma arquitetura para identificar e monitorar eventos DDL (Data Definition Language), utilizando a abordagem de banco de dados ativos e recomendação. As aplicações desta arquitetura variam desde o simples monitoramento de eventos DDL em um ou mais bancos de dados, até a recomendação de possíveis configurações ou mudanças que podem ser realizadas no banco de dados monitorado. Neste contexto, essa dissertação propõe: (i) uma arquitetura integrada de banco de dados ativos e recomendação; (ii) a adaptação de um algoritmo de recomendação; e (iii) a validação dos conceitos aplicados através de um protótipo. / Integrated environments monitoring can become complex with heterogeneous databases, due to the particularities in the language syntax and available tools. In particular, active databases allow developing mechanisms and automation of processes involving data or objects. This work proposes the development of an architecture to identify and monitor DDL (Data Definition Language), exploring the active databases and recommendations approach. This architecture could be explored in several ways: simple monitoring of DDL events in one or more databases, or recommendation of future DDLs or settings within the monitored database. In this context, this work proposes: (i) an integrated architecture of active databases and recommendation; (ii) the adaptation of a recommendation algorithm; and (iii) the validation of concepts through a prototype.

CNPq / Nesta tese, os Sistemas Imunológicos Artificiais são aplicados a diferentes instâncias do despacho econômico e econômico/ambiental de energia elétrica. Os sistemas imunes considerados são baseados no princípio da seleção clonal e usam uma representação real com operador de \emph{aging} puro e operadores de hipermutação utilizando distribuições de probabilidade Gaussianas e de Cauchy. Algoritmos Culturais utilizando fontes de conhecimento normativo, situacional, histórico e topográfico são incorporados para melhorar a capacidade de otimização global dos sistemas imunes. Todas as abordagens propostas possuem vários pontos de auto-adaptação e a maioria utiliza um operador de busca local baseado na técnica quase-simplex. Uma sequência caótica também é considerada como uma potencial fonte de melhoria na variação cultural do algoritmo. Procedimentos de reparação constituem outra contribuição do trabalho e são aplicados para evitar lidar com soluções infactíveis em todos os problemas abordados. Na primeira parte dos experimentos, quatro instâncias do problema do despacho econômico de energia são consideradas. Em todos os casos, foi utilizada uma função não suave de custo de combustível levando em consideração os efeitos de ponto de válvula. Uma das instâncias também considera as perdas na transmissão de energia. Nos experimentos de comparação entre as abordagens propostas, as versões imuno-culturais superam a versão puramente imune. O método cultural proposto que apresenta melhor resultado é escolhido para ser comparado a outras técnicas modernas de otimização reportadas na literatura recente. Em todos os casos mono-objetivo considerados, a abordagem proposta é capaz de encontrar o menor custo de combustível. A segunda parte dos experimentos trata do problema do despacho econômico/ambiental. Esta é uma versão do problema do despacho econômico de energia onde a emissão de poluentes é adicionada como um novo objetivo, tornando este um problema de otimização multiobjetivo não-linear com restrições. Algoritmos imuno-culturais baseados em fatores de escalarização e dominância de Pareto são propostos para este caso. Várias instâncias do problema são utilizadas nos experimentos, algumas das quais consideram perdas na transmissão de energia. Os algoritmos propostos são favoravelmente comparados com um algoritmo do estado-da-arte para otimização multiobjetivo. O melhor algoritmo proposto também é comparado com métodos reportados na literatura recente. As comparações mostram o bom desempenho da melhor abordagem proposta e confirmam seu potencial para resolver o problema do despacho econômico/ambiental de energia. / In this thesis, Artificial Immune Systems are applied to solve different instances of the economic and environmental/economic load dispatch problems. The immune systems considered here are based on the clonal selection principle and use a real coded representation with pure aging operator and hypermutation operators utilizing Gaussian and Cauchy distributions. Cultural Algorithms using normative, situational, historical and topographical knowledge sources are incorporated to improve the global optimization capability of immune systems. All the proposed approaches have several points of self-adaptation and most of them use a local search operator that is based on a quasi-simplex technique. A chaotic sequence is also considered as a potential source of improvement to the cultural variation. Repair procedures represent another contribution of this work and are applied to avoid dealing with infeasible solutions in all the considered problems. In the first part of the experiments, four instances of the economic load dispatch problem are considered. In all the cases, a non-smooth fuel cost function which takes into account the valve-point loading effects is utilized. One of instances also considers energy transmission losses. In the experiments conducted to compare the proposed approaches, the immune-cultural based approaches outperformed the pure immune version. The proposed cultural method which presents the best performance is chosen to be compared with other modern optimization techniques reported in the recent literature. In all the mono-objective cases considered, the proposed approach is capable of finding the minimum fuel cost value. The second part of the experiments deals with the environmental/economic load dispatch problem. This is a multi-objective version of the economic load dispatch where pollution emission is added as an objective, it is formulated as a non-linear constrained multi-objective optimization problem. Cultural immune algorithms based on scalarizing factors and Pareto-dominance are proposed for this case. Several instances of the problem are considered, some dealing with energy transmission losses. The proposed algorithms are favorably compared with a state-of-art algorithm for multi-objective optimization (the Non-dominated Sorting Genetic Algorithm II - NSGA - II). The best proposed algorithm is also compared with methods reported in recent literature. The comparisons demonstrate the good performance of the best proposed approach and confirm its potential to solve the environmental/economic load dispatch problem.