918 resultados para Árvore geradora mínima - Restrita em grau multiobjetivo
Resumo:
Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches
Resumo:
The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions
Resumo:
The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.
Resumo:
The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.
Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo
Resumo:
The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature
Resumo:
The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments
Resumo:
A Neuromielite Óptica (NMO), anteriormente considerada como um subtipo de Esclerose Múltipla, é uma doença autoimune, inflamatória do sistema nervoso central, na qual o sistema imune ataca a mielina dos neurônios localizados nos nervos ópticos e medula espinhal, produzindo, então, mielite e neurite óptica simultânea ou sequenciais. A patogênese da neuromielite óptica é influenciada pela combinação de fatores genéticos e ambientais, incluindo agentes infecciosos. Diferentes doenças infecciosas podem tanto desencadear como exacerbar a autoimunidade. Portanto, o objetivo do presente estudo foi de analisar a responsividade imune in vitro a Escherichia coli, Staphylococcus aureus e Candida albicans em pacientes com NMO recorrente-remitente, e a correlacionar ao nível de incapacidade neurológica. Nesse contexto, a extensão da linfoproliferação e perfil de citocinas em resposta a S. aureus e C. albicans, em culturas de células mononucleares do sangue periférico (CMSP) foram similares entre pacientes com NMO e indivíduos saudáveis. Entretanto, maior proliferação de células T associada à elevada liberação de IL-1β, IL-6 e IL-17 foi observada em culturas de células derivadas de pacientes com NMO quando estimuladas com E. coli. Ademais, nessas culturas, a produção de IL-10 foi significativamente menor quando comparada ao grupo controle. Ensaios conduzidos em culturas de CMSP depletadas de diferentes subtipos de linfócitos demonstraram que, enquanto células T CD4+ e T CD8+ produzem IL-6 em resposta a E. coli, a produção de IL-17 foi praticamente restrita às células T CD4+. Os níveis de IL-6 e IL-17 in vitro induzidos por E. coli foram correlacionados positivamente às incapacidades neurológicas. Essa maior tendência a produzir citocinas relacionadas ao perfil Th17 foi diretamente associada aos níveis de IL-23 produzidos por monócitos ativados com LPS. De modo interessante, níveis elevados de LPS foram quantificados no plasma de pacientes com NMO e estes foram correlacionados aos níveis plasmáticos de IL-6. Em conclusão, nossos resultados sugerem que uma maior responsividade a E. coli poderia estar envolvida na patogênese da NMO. Esse tipo de investigação é muito importante pois inibidores da ligação ou sinalização do TLR poderiam ser considerados terapias com grande potencial como adjuvantes no tratamento de pacientes com NMO.
Resumo:
O presente estudo baseou-se na análise do conteúdo orgânico de 173 amostras da Formação Pojuca, provenientes dos furos de sondagem 9-FBA-65-BA e 9-FBA-79-BA perfurados na Bacia do Recôncavo. Neste trabalho procedeu-se a um estudo integrando, resultados palinológicos, palinofaciológicos e de geoquímica orgânica com base nos dados de teores de Carbono Orgânico Total (COT) e de pirólise Rock-Eval. A associação palinoflorística identificada indica um paleoambiente dominantemente continental, composto por um sistema fluvial deltaico-lacustre, sob um clima quente e árido. Tal associação enquadra-se àquelas observadas nas bacias do Nordeste brasileiro e insere-se nas características das associações pertencentes à Província Microflorística Dicheiropollis (ex WASA). Foram identificadas 55 espécies de palinomorfos, incluindo grãos de pólen e esporos. A identificação das espécies, Dicheiropollis etruscus e Vitreisporites pallidus permitiu posicionar o intervalo analisado na Biozona Vitreisporites pallidus, considerada como de idade Aratu. Por meio de observação em microscopia óptica com luz branca transmitida e luz ultravioleta; e le-BA, caracterizando um conteúdo orgânico na janela de geração de hidrocarbonetos. Com base nos resultados de pirólise Rock-Eval, verificou-se que a Formação Pojuca, na área, é constituída vando-se em conta os tipos e o grau de preservação da matéria orgânica, foi possível individualizar três palinofácies distintas. As análises quantitativas do conteúdo orgânico mostram uma mistura de material orgânico de origem alóctone, representado por grãos de pólen, esporos e fitoclastos e autóctone dominada por material orgânico amorfo. As mais altas fluorescências são observadas nas Palinofácies 1 e 2, indicando um ambiente mais reduto r à época de sedimentação, destes estratos. Os dados de ICE apresentam valores de maturação de 5 para os sedimentos atravessados pelo poço 9-FBA-65-BA e 6,5-7 para o poço 9-FBA-79 na sua quase totalidade por matéria orgânica do tipo II, rica em hidrogênio e pobre em oxigênio, correspondendo ao um tipo de matéria orgânica propícia à geração de hidrocarbonetos líquidos e gasosos. Os níveis 3 e 4, localizados nas Palinofácies 1 e 2 do poço 9-FBA-79-BA apresentam valores de COT superiores a 1,5%, e considerando os dados de pirólise Rock-Eval, nota-se que estes intervalos são os que oferecem um maior potencial gerador, já que os valores de S2 excedem a 5,0 mg HC/g de rocha, além de valores de IH superiores a 200 e atingindo 600.
Resumo:
En el nou marc universitari que dibuixa l’adaptació de les titulacions a l’Espai Europeu d’Educació Superior, es proposa que el titulat de grau en Psicologia acabi la carrera amb les competències bàsiques mínimes d’ajut psicològic que li permetin fer front a situacions d’emergència inesperades i reaccionar de manera professional sense empitjorar la situació o perjudicar l’estat de les víctimes, i amb un mínim de seguretat en allò què ha de fer o, al menys, en allò que no ha de fer. Es considera que hauria de tenir, com a mínim, el mateix nivell de formació que tenen altres col·lectius que habitualment es troben implicats en una emergència (personal sanitari, bombers, voluntaris, etc.) per tal que no es trobi en inferioritat de condicions pel que es refereix a la manera de proporcionar primers auxilis psicològics a víctimes. Es proposa un programa formatiu en el títol de grau en Psicologia
Resumo:
Objetivos: Determinar a dose eritematosa mínima (DEM) medida por exposição controlada à radiação ultravioleta-B (RUV-B), como limiar para dano solar agudo nos diversos fototipos, e medir a cor da pele constitucional pelo sistema colorimétrico CIELAB. Pacientes e Métodos: Um total de 194 voluntários, sadios, com idades acima de 18 anos, distribuídos em um mínimo de 30 participantes por fototipo. Todos foram classificados por fototipos segundo os critérios de Fitzpatrick. As regiões infra-axilar torácica e nádega foram irradiadas em 4 áreas de 1 cm2, assim como foi registrada a cor da pele desses locais pelo sistema CIELAB. Delineamento: Estudo transversal. Resultados: A média de idade dos participantes foi de 38 anos, sendo 68% do sexo feminino. A avaliação da associação entre as medidas das DEMs e dos valores colorimétricos da coordenada L*, mostrou uma correlação de Pearson negativa com r = -0,91 para um valor p<0,05. Para os valores das DEMs e os escores da classificação dos voluntários por fototipos, obteve-se correlação de Spearman (rs) de +0,95 para p<0,05 e, correlacionando os valores colorimétricos com os escores dos fototipos, encontrou-se em tórax um rs de -0,93 e em nádega -0,92 para um p < 0,05. Conclusões – Concluiu-se que: 1)- a mensuração dos valores colorimétricos da coordenada L* nas regiões infra-axilar torácica e nádega mostraram uma forte correlação com os valores das DEMs, sendo de menor poder invasivo e de maior praticidade para mensuração de sensibilidade à radiação ultravioleta; 2)- apesar de os escores de Fitzpatrick terem alta correlação com os valores das DEMs, mostraram superposição de valores nos fototipos adjacentes; 3)- o grau de associação das classes dos fototipos com a cor da pele permite dizer que a categoria numérica do fototipo aumenta à medida que a pele fica mais escura.
Resumo:
O sistema bancário consiste em um setor da economia muito regulado, e uma das medidas impostas pelas autoridades supervisoras como forma de controle é exigência mínima de capital. Uma das formas encontradas para oferecer maior proteção aos clientes e ao mercado financeiro como um todo é a imposição aos bancos em manterem níveis mínimos de capital vinculados aos riscos a que estão expostos, medida que serve como recurso para desestimular a exposição a riscos não usuais. O capital bancário, portanto, constitui-se em instrumento de proteção contra o risco de quebra de uma instituição, e, desde a adesão ao Acordo Internacional da Basiléia, com vigência a partir de 1995, os bancos brasileiros têm de manter patrimônio líquido compatível com o grau de risco da estrutura de seus ativos. O presente trabalho explora a existência e o grau de relação entre exigência mínima de capital ponderado pela exposição de risco dos ativos e a rentabilidade dos bancos brasileiros, a fim de contribuir para uma análise da situação atual das instituições em relação às normas vigentes sobre requerimento de capital. Trata-se de pesquisa empírica, a qual procura levantar indicações exploratórias, evidenciadas por graus de correlações, mensurados através de estimação com dados em painel. A literatura internacional que versa sobre os impactos da existência de regulação de capital nos bancos demonstra-se divergente e, em alguns casos, não–conclusiva. Os resultados encontrados neste trabalho, com base em amostra composta por bancos brasileiros, não evidenciam relações significativas entre indicador de rentabilidade e indicador de capital ponderado pelos riscos, conhecido no Brasil como Índice de Basiléia. Algumas considerações são sugeridas para justificarem os resultados alcançados, tais como a preferência das instituições por aplicações em ativos de menor risco, como títulos públicos, a arbitragem de capital, proporcionada, principalmente, pelo grau de risco imposto às operações ativas, e a facilidade de enquadrarem-se aos limites mínimos de capital adotados no Brasil, evidenciada pelas altas margens de folga observadas.
Resumo:
Esta pesquisa teve por objetivo caracterizar o aluno matriculado no nível 4 do Curso Supletivo, em 1981, na Escola Estadual de 1o Grau Araújo Porto Alegre, do município de Porto Alegre, RS, bem como levantar possíveis fatores que estejam relacionados com a sua evasão escolar e perspectivas de estudo. A amostra constituiu-se de 88 alunos, que foram caracterizados quanto ao sexo, idade, estado civil, situação profissional, renda mensal, número, motivos e período de interrupções de escolaridade anterior, idade de ingresso no mercado de trabalho, dificuldades para freqüentar o Curso Supletivo e perspectivas de continuidade dos estudos. O instrumento de coleta de dados foi um questionário, aplicado pela própria pesquisadora. Para análise dessas variáveis, utilizou-se o tratamento estatístico descritivo, com cálculo de médias, variância e desvio-padrão. A associação entre algumas variáveis foi estudada pela aplicação do teste do qui-quadrado (X2), a nível de significância de 0,05, e pelo coeficiente de correlação de Pearson. Os resultados permitiram concluir que o nível 4 do Curso Supletivo funciona como uma nova oportunidade de estudo oferecida a alunos jovens, na faixa etária de "15 a 19 anos", solteiros, que abandonaram a escola por razoes socio- econômicas, alguns exercendo atividades de trabalho desde os 10 anos. Ao freqüentá-lo, os alunos, de modo geral, nao esperam que o certificado de 1o grau venha conseguir-lhes emprego ou promoção no emprego atual. As perspectivas de continuidade dos estudos prende-se, de imediato,ao ingresso em diversas modalidades do ensino de 2o grau e, posteriormente,a um Curso Universitário. Verificou-se, ainda, que o abandono do sistema formal é um antecedente que depois se repete na trajetória escolar dos alunos no Curso Supletivo. A incidência mínima de evasão no nível 4, do Curso Supletivo, da escola em estudo, é um fato que constatamos também nas outras escolas das quatro áreas educacionais.
Resumo:
A partir do estudo do sistema de administração do ensino de 1º grau de Minas Gerais, o trabalho constata hipóteses anteriormente formuladas: 1) a administração pública da Educação é comandada por interesses dos setores dirigentes da classe dominante; 2) a dominação que se realiza através dos órgãos administrativos da Educação é sobretudo ideológica. Para melhor fundamentar as questões levantadas, a introdução explicita o pensamento do Guillermo O’Donnell sobre o Estado como o “terceiro neutro” que se apresenta com uma certa exterioridade junto às duas classes antagônicas, mascarando, assim, a dominação; e o de Gramsci, que, a partir da concepção ampliada de Estado, vislumbra a possibilidade de uma contra-ideologia, destacando-se aí o papel dos intelectuais. O capítulo 1, elaborado com apoio em pesquisa bibliográfica, legislação pertinente e entrevistas, aborda a história da administração do ensino de 1º grau no estado de Minas Gerais no período 1930-74, com breve referência à fase antecedente, situando cada etapa em seu contexto político, econômico e social. Procurou-se com isso demonstrar como a administração educacional é comandada basicamente por critérios políticos que refletem os interesses da classe dirigente. Discutem-se principalmente as questões da modernização e da descentralização administrativas no setor educacional, motivadoras das grandes reformas que, apesar de aparentemente transformadoras, mantiveram seu caráter conservador. Constituindo as Delegacias Regionais de Ensino expressão fiel dessa “modernização” e “descentralização”, foi dada ênfase à criação desses órgãos. No capítulo 2, após delimitar o universo da pesquisa de campo realizada em Caratinga MG – foram entrevistados 27 técnicos e 34 usuários – e situar histórica, política e economicamente este município, deixa-se espaço para depoimentos de técnicos e de usuários para depois analisa-los de modo a detectar a submissão de ambos à ideologia dominante, bem como os indícios de recusa/superação dessa ideologia, resultantes da participação desses agentes sociais em outras instâncias organizativas da sociedade civil. Tal reflexão é abordada a partir de quatro temas recorrentes: eficiência, participação da comunidade, descentralização administrativa e interferência político-partidária na administração do ensino de 1º grau. Em conclusão, primeiramente ressaltam-se algumas questões básicas, a saber: a irrelevância da Educação como geradora de uma consciência crítica e via de acesso universal ao saber; o fato de o sistema de administração educacional garantir um espaço para a participação dos setores políticos tradicionais, e ainda como a quase-totalidade dos entrevistados acredita na neutralidade e racionalidade do sistema de administração. A seguir salienta-se a importância do I Congresso Mineiro de Educação (1983) como elemento questionador, com uma breve apresentação e análise desse evento – restrita aos temas centrais desta dissertação – enfocando os colegiados, que parecem indicar uma mudança real de postura na nova política educacional, embora sua dinâmica ainda apresente sérias limitações. Objetivando a superação dessas limitações, o presente trabalho faz algumas recomendações voltadas para os técnicos e os mecanismos do sistema de administração, tendo em vista o fortalecimento de organizações da sociedade civil e maior articulação destas com o sistema.
Resumo:
This paper presents an evaluative study about the effects of using a machine learning technique on the main features of a self-organizing and multiobjective genetic algorithm (GA). A typical GA can be seen as a search technique which is usually applied in problems involving no polynomial complexity. Originally, these algorithms were designed to create methods that seek acceptable solutions to problems where the global optimum is inaccessible or difficult to obtain. At first, the GAs considered only one evaluation function and a single objective optimization. Today, however, implementations that consider several optimization objectives simultaneously (multiobjective algorithms) are common, besides allowing the change of many components of the algorithm dynamically (self-organizing algorithms). At the same time, they are also common combinations of GAs with machine learning techniques to improve some of its characteristics of performance and use. In this work, a GA with a machine learning technique was analyzed and applied in a antenna design. We used a variant of bicubic interpolation technique, called 2D Spline, as machine learning technique to estimate the behavior of a dynamic fitness function, based on the knowledge obtained from a set of laboratory experiments. This fitness function is also called evaluation function and, it is responsible for determining the fitness degree of a candidate solution (individual), in relation to others in the same population. The algorithm can be applied in many areas, including in the field of telecommunications, as projects of antennas and frequency selective surfaces. In this particular work, the presented algorithm was developed to optimize the design of a microstrip antenna, usually used in wireless communication systems for application in Ultra-Wideband (UWB). The algorithm allowed the optimization of two variables of geometry antenna - the length (Ls) and width (Ws) a slit in the ground plane with respect to three objectives: radiated signal bandwidth, return loss and central frequency deviation. These two dimensions (Ws and Ls) are used as variables in three different interpolation functions, one Spline for each optimization objective, to compose a multiobjective and aggregate fitness function. The final result proposed by the algorithm was compared with the simulation program result and the measured result of a physical prototype of the antenna built in the laboratory. In the present study, the algorithm was analyzed with respect to their success degree in relation to four important characteristics of a self-organizing multiobjective GA: performance, flexibility, scalability and accuracy. At the end of the study, it was observed a time increase in algorithm execution in comparison to a common GA, due to the time required for the machine learning process. On the plus side, we notice a sensitive gain with respect to flexibility and accuracy of results, and a prosperous path that indicates directions to the algorithm to allow the optimization problems with "η" variables
Resumo:
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)